Skip to Main content Skip to Navigation

Efficient routing on multi-modal transportation networks

Abstract : Mobility is an important aspect of modern society. Consequently, there is a growing demand for services offering efficient route planning. In this thesis, we study multi-modal routing and the Dial-a-Ride system. Both respond to the need of a more efficient utilization of the available transportation infrastructure, which is an important component of sustainable development. Multi-modal route planning is complex because of the various modes of transportation which have to be combined. A generalization of Dijkstra's algorithm may be used to find shortest paths on multi-modal networks. However, its performance is not sufficient for real world applications. For this reason, this thesis introduces a new algorithm called SDALT. It is an adaption of the speed-up technique ALT. To evaluate the performance of SDALT, we produced a graph of a real-world multi-modal network based on transportation data of the French region Ile-de-France. It includes walking, public transportation, car, and bicycle, as well as timetable information and traffic data. Experiments show that SDALT performs well, with speed-ups of a factor 1.5 to 60 with respect to the basic algorithm. Other than finding shortest multi-modal paths that optimally combine the use of several modes of transportation, yet another problem arises: finding an optimal multi-modal return path or 2-way path. When using a private vehicle for parts of the outgoing path, it has to be picked up during the incoming path so that it can be taken to the starting location. For this reason, the parking must be chosen in such a way as to optimize the combined travel times of the outgoing and incoming path. We propose an efficient algorithm that solves this problem faster than previous techniques. The Dial-a-Ride system offers passengers the comfort and flexibility of private cars and taxis at a lower cost and higher eco-efficiency by combining similar transportation demands. It works as follows: passengers request the service by calling a central unit. They specify their pick-up point, their delivery point, the number of passengers, and some limitations on their service time (e.g., the earliest departure time). An algorithm then calculates the routes and schedules of the vehicles. We propose a new efficient and fast heuristic, a Granular Tabu Search, to produce good solutions in a short amount of time (up to 3 minutes). Our algorithm produces better results for more than half of the test instances after 60s of optimization time in comparison with other methods.
Complete list of metadata

Cited literature [125 references]  Display  Hide  Download
Contributor : Dominik Kirchler Connect in order to contact the contributor
Submitted on : Monday, October 28, 2013 - 3:19:16 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:27 PM
Long-term archiving on: : Wednesday, January 29, 2014 - 4:47:54 AM


  • HAL Id : pastel-00877450, version 1



Dominik Kirchler. Efficient routing on multi-modal transportation networks. Data Structures and Algorithms [cs.DS]. Ecole Polytechnique X, 2013. English. ⟨pastel-00877450⟩



Record views


Files downloads