Benchmarking minimum passenger waiting time in online taxi dispatching with exact offline optimization methods

Michał Maciejewski

doi:10.5604/08669546.1146978

Authors

Michał Maciejewski TU Berlin, Faculty of Mechanical Engineering and Transport Systems, Transport Systems Planning and Transport Telematics (VSP), Berlin, Germany; Poznan University of Technology, Faculty of Machines and Transport, Division of Transport Systems, Poznan, Poland Author

DOI:

https://doi.org/10.5604/08669546.1146978

Keywords:

online taxi dispatching, dynamic vehicle routing, multi-agent simulation, MATSim

Abstract

This paper analyses the use of exact offline optimization methods for benchmarking online taxi dispatching strategies where the objective is to minimize the total passenger waiting time. First, a general framework for simulating dynamic transport services in MATSim (Multi-Agent Transport Simulation) is described. Next, the model of online taxi dispatching is defined, followed by a formulation of the offline problem as a mixed integer programming problem. Three benchmarks based on the offline problem are presented and compared to two simple heuristic strategies and a hypothetical simulation with teleportation of idle taxis. The benchmarks are evaluated and compared using the simulation scenario of taxi services in the city of Mielec. The obtained (approximate) lower and upper bounds for the minimum total passenger waiting time indicate directions for further research.

References

Alshamsi A., Abdallah S., Rahwan I.: Multiagent self-organization for a taxi dispatch system. In: 8th International Conference on Autonomous Agents and Multiagent Systems, pp. 21-28, 2009.

Balmer M., Meister K., Rieser M., Nagel K., Axhausen K.: Agent-based simulation of travel demand: structure and computational performance of MATSim-T. In: Innovations in Travel Modeling (ITM) ’08, Portland, Oregon, June 2008, also VSP WP 08-07, www.vsp.tu- berlin.de/publications, 2008.

Cheng S., Nguyen T.: Taxisim: a multiagent simulation platform for evaluating taxi fleet operations. In: Proceedings of the 2011 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, Vol. 2, IEEE Computer Society, pp. 14—21, 2011.

Groetschel M., Krumke S., Rambau J., Winter T., Zimmermann U.: Combinatorial online optimization in real time. Online, 16, pp. 679- 704, 2001.

Gurobi Optimizer Reference Manual, Version 5.6, 2013.

Lee D., Wang H., Cheu R., Teo S.: Taxi dispatch system based on current demands and real-time traffic conditions. Transportation Research Record, Journal of Transportation Research Board, 1882, pp. 193-200, 2004.

Ma W., Wang K.: On the on-line weighted k- taxi problem. In: Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Springer, pp. 152-162, 2007.

Maciejewski M.: Online taxi dispatching via exact offline optimization. Logistyka, 4/2014, pp. 2133-2142, 2014.

Maciejewski M., Nagel K.: Towards multi- agent simulation of the dynamic vehicle routing problem in MATSim. In: Wyrzykowski R.. Dongarra J., Karczewski K., Wasniewski J. (eds.): Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science, 7204, Springer Berlin Heidelberg, pp. 551-560, 2012.

Maciejewski M., Nagel K.: Simulation and dynamic optimization of taxi services in MATSim. VSP Working Paper 13-05, TU Berlin, Transport Systems Planning and Transport Telematics. www.vsp.tu-bcrlin.de/ publications, 2013.

Maciejewski M., Nagel K.: A microscopic simulation approach for optimization of taxi services. In: Albrecht T., Jaekel B., Lehnert M. (eds.): Proceedings of the 3rd International conference on Models and Technologies for Intelligent Trans portation Systems, Dresden, p. 1-10, 2013.

Maciejewski M., Nagel K.: The influence of multi-agent cooperation on the efficiency of taxi dispatching. In: Wyrzykowski R., Dongarra J., Karczewski K., Wasniewski J. (eds.): Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science, 8385, Springer Berlin Heidelberg, p. 751-760, 2014.

Seow K., Dang N., Lee D.: A collaborative multiagent taxi-dispatch system. IEEE Transactions on Automation Science and Engineering, 7(3), pp. 607-616, 2010.

Wang H., Lee D., Cheu R.: PDPTW based taxi dispatch modeling for booking service. In: Fifth International Conference on Natural Computation, ICNC'09, vol. 1, pp. 242-247, 2009.

Wong K. I., Bell M. G. H.: The optimal dispatching of taxis under congestion: A rolling horizon approach. Journal of Advanced Transportation, 40, pp. 203-220, 2006.

Yang J., Jaillet P., Mahmassani H.: Real-time multivehicle truckload pickup and delivery problems. Transportation Science, 38(2), pp. 135-148, 2004.