Online taxi dispatching via exact offline optimization

• Autorzy: Maciejewski M.

Warianty tytułu

PL

Przydział taksówek do zleceń w trybie online poprzez optymalizację dokładną offline

• Języki publikacji: EN

Abstrakty

EN

The paper proposes an online taxi dispatching strategy that is based on solving exactly the equivalent offline problem at each decision epoch. 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. Then the MIP strategy that solves the offline problem with a finite planning horizon at each decision epoch is described. The performance of MIP was evaluated on the simulation scenario of taxi services in the city of Mielec and compared with that of two selected strategies (RES and NOS). The obtained results show the advantage of MIP over the reference strategies in terms of the solution quality, but at the cost of response time.

PL

W artykule zaproponowano strategię przydziału online taksówek do zleceń opartą na dokładnym rozwiązaniu odpowiednika problemu w trybie offline dla każdej epoki decyzyjnej. W pierwszej kolejności opisano ogólny szkielet symulacji dynamicznych usług transportowych w MATSim (Multi-Agent Transport Simulation). Następnie zdefiniowano model przydziału taksówek do zleceń w trybie online oraz sformułowano problem offline jako problem programowania mieszanego całkowitoliczbowego MIP. W oparciu o ten problem stworzono strategię MIP polegającą na rozwiązywaniu problemu offline dla skończonego horyzontu planistycznego dla każdej epoki decyzyjnej. Efektywność strategii MIP oceniono na podstawie scenariusza symulacyjnego usług taksówkowych w Mielcu i porównano z efektywnością dwóch wybranych strategii (RES i NOS). Otrzymane rezultaty wskazują na przewagę MIP nad strategiami referencyjnymi pod względem jakości rozwiązań, ale kosztem czasu odpowiedzi.

Słowa kluczowe

EN

online taxi dispatching; dynamic vehicle routing; rolling horizon; multi-agent simulation; MATSim

PL

przydział taksówek do zleceń w trybie online; marszrutyzacja dynamiczna pojazdów; ruchomy horyzont planistyczny; symulacja wieloagentowa; MATSim

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2014
• Tom: nr 4
• Opis fizyczny: Bibliogr. 17 poz., rys., tab., pełen tekst na CD

Twórcy

autor

Maciejewski M.

• TU Berlin, Transport Systems Planning (VSP)
• Poznan University of Technology, Division of Transport Systems

Bibliografia

• [1] 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.
• [2] 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.
• [3] 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.
• [4] Fleischmann B., Gnutzmann S., Sandvoß E.: Dynamic vehicle routing based on online traffic information. Transportation Science, 38(4), pp. 420–433, 2004.
• [5] Gendreau M., Laporte G., Semet F.: A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel computing, 27(12), pp. 1641–1653, 2001.
• [6] Gurobi Optimizer Reference Manual, Version 5.6, 2013.
• [7] Horn M.: Fleet scheduling and dispatching for demand-responsive passenger services. Transportation Research Part C Emerging Technologies, 10(1), pp. 35–63, 2002.
• [8] 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.
• [9] Lees-Miller J.D.: Empty vehicle redistribution for personal rapid transit. PhD thesis, University of Bristol, 2011.
• [10] Ma W., Wang K.: On the on-line weighted k-taxi problem. In: Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Springer, pp. 152–162, 2007.
• [11] 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.
• [12] 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-berlin.de/publications, 2013.
• [13] 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 Transportation Systems, Dresden, p. 1–10, 2013. Logistyka – nauka 2142 Logistyka 4/2014
• [14] 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.
• [15] 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.
• [16] 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.
• [17] Yang J., Jaillet P., Mahmassani H.: Real-time multivehicle truckload pickup and delivery problems. Transportation Science, 38(2), pp. 135–148, 2004.