Memetic Algorithm for Computing Shortest Paths in Multimodal Transportation Networks

Omar Dib (1) , Marie-Ange Manier (2) , Alexandre Caminada (2)

1 IRT SystemX
2 UTBM - Université de Technologie de Belfort-Montbeliard

Route planning in multimodal transportation networks is gaining more and more importance. Travelers ask for efficient routing methods allowing them to reach their destinations through the intricate multimodal transportation scheme. In this paper, we propose a new approach for computing multi-modal shortest paths. We only consider railway, bus and pedestrian networks. The travel time is the only metric in our cost function. Our proposed approach is a combination of two meta-heuristics: Genetic Algorithm (GA) and Variable Neighborhood Search (VNS). We compare our approach with the exact shortest path algorithm Dijikstra that has been modified to work in a multimodal environment, as well as, with a pure GA. Results have shown that the success rate of our approach in terms of converging to optimum/near optimum solutions is highly better than a pure GA. Moreover, in contrast to traditional algorithms like Dijkstra, our approach is fast enough for practical routing applications.

Mots clés: Multimodal Shortest Paths; Hybrid Metaheuristics; Memetic Algorithm; Genetic Algorithm; Variable Neighborhood Search; Dijkstra

Domaines: Mathématiques [math]; Informatique [cs]

Omar Dib, Marie-Ange Manier, Alexandre Caminada. Memetic Algorithm for Computing Shortest Paths in Multimodal Transportation Networks. Transportation Research Procedia, 2015, 10, pp.745 - 755. ⟨10.1016/j.trpro.2015.09.028⟩. ⟨hal-01520123⟩