A memetic algorithm for computing multicriteria shortest paths in stochastic multimodal networks

Omar Dib (1) , A. Caminada (2) , M-A Manier (2) , L. Moalic (3)

1 IRT SystemX
2 UTBM - Université de Technologie de Belfort-Montbeliard
3 IRTES - SET - Laboratoire Systèmes et Transports

Modern transport systems are nowadays very complex. Building Advanced Travelers Information Systems (ATIS) has therefore become a certain need. Since passengers do not only seek a short-time travel, but they tend to optimize several criteria, an efficient routing system should incorporate a multi-objective analysis into its search process. Besides, the transport system may behave in an uncertain manner. Therefore, integrating uncertainty into routing algorithms may provide better itineraries. The main objective of this work is to propose a Memetic Approach (MA) in which a Genetic Algorithm (GA) is combined with a Hill Climbing (HC) local search procedure in order to solve the multicriteria shortest path problem in stochastic multimodal transport networks. Experimental results have been assessed by solving real life itinerary problems defined on the transport network of the city of Paris and its suburbs. Results indicate that unlike classical deterministic algorithms and pure GA and hill climbing, the proposed MA provide better itineraries within a reasonable amount of time.

Mots clés: hill climbing; genetic algorithms; stochastic multimodal networks; Multicriteria optimization; memetic algorithms

Domaines: Recherche opérationnelle [math.OC]; Optimisation et contrôle [math.OC]

Omar Dib, A. Caminada, M-A Manier, L. Moalic. A memetic algorithm for computing multicriteria shortest paths in stochastic multimodal networks. Genetic and Evolutionary Computation Conference Companion (GECCO 2017), Jul 2017, Berlin, Germany. pp.103-104, ⟨10.1145/3067695.3076064⟩. ⟨hal-01586883⟩