Perbandingan Metode Tabu Search dengan Metode Hungarian Algorithm untuk Penentuan Driver Assignment pada Simulasi Taksi Online

Eryn Eryn, Andreas Handojo, Tanti Octavia

Abstract


Taxi in one of the public transportation that is widely used by people in all parts of the world. Over time, taxis have continued to grow until now online taxis have emerged. Taxis also develop in the dispatch function in installing drivers with requests from customers. As the function of installing drivers to this request develops, the parameters used to get matching results also   increase and the complexity increases. However, with the conditions that are increasingly developing, the matching process between drivers and customers is still required to use the least amount of time and resources and still produce optimal results.  So from this, in this matching process a lot of progress was made in order to get the results of installing drivers to customers that can minimize time and distance.

The application is made in Python programming language, Bootstrap 3 for the front end menu, and django as a framework. The Google Maps API is used to get time and distances and as a front end in the online map section. MySQL is used as a database to store simulation data.

The final result of this program is an assignment simulation application between driver and passenger using two algorithms and 3 factors, that is time, distance and last trip by the driver. Simulation can display a comparison of the results of the assignment to facilitate the process of comparison of algorithms. 

Keywords


hungarian algorithm; tabu search; google maps api; taxi online; simulation

Full Text:

PDF

References


Andoko, V. P. 2019. Simulasi Online Taxi’s Dispatch System Dengan Metode Combinatorial Optimization.

De Oliveira, A. A. M., Souza, M. P., Pereira, M. de A., Reis, F. A. L., Almeida, P. E. M., Silva, E. J., & Crepalde, D. S. 2015. Optimization of taxi cabs assignment in geographical location-based systems. Proceedings of the Brazilian Symposium on GeoInformatics, 2015-November, 92–104.

Fatmawati, Prihandono, B., & Noviani, E. 2015. Penyelesaian Traveling Salesman Problem dengan Metode Tabu Search - PDF. URI = https://docplayer.info/48172249-Penyelesaian-travelling-salesman-problem-dengan-metode-tabu-search.html

Glover, F. 1990. Tabu Search—Part II. ORSA Journal on Computing, 2(1), 4–32. DOI = https://doi.org/10.1287/ijoc.2.1.4

Konig, D. 1931. Gr´afok ´es m´atrixok. matematikai ´es fizikai lapok, 38.

KUHN, H. W. 1955. The hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, 83–97

Masoud, N., & Jayakrishnan, R. 2017. A real-time algorithm to solve the peer-to-peer ride-matching problem in a flexible ridesharing system. Transportation Research Part B: Methodological, 106(October), 218–236. DOI = https://doi.org/10.1016/j.trb.2017.10.006

Munkres, J. 1957. Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38. DOI = https://doi.org/10.1137/0105003

Schreieck, M., Safetli, H., Siddiqui, S. A., Pflügler, C., Wiesche, M., & Krcmar, H. 2016. A Matching Algorithm for Dynamic Ridesharing. Transportation Research Procedia, 19(June),272–285. DOI= https://doi.org/10.1016/j.trpro.2016.12.087

Shen, Y., & Kwan, R. S. K. 2001. Computer-Aided Scheduling of Public Transport, 505(June), 9–11. DOI = https://doi.org/10.1007/978-3-642-56423-9

Shen, Y., & Kwan, R. S. K. 2011. Tabu Search for Driver Scheduling, (1995), 121–135. DOI = https://doi.org/10.1007/978-3-642-56423-9_7

SINGH, S. 2013. A Comparative Analysis of Assignment Problem. IOSR Journal of Engineering, 02(08), 01–15. DOI =https://doi.org/10.9790/3021-0281011


Refbacks

  • There are currently no refbacks.


Jurnal telah terindeks oleh :