A k-shortest paths based algorithm for multimodal time-dependent networks to compute alternative routes

Grégoire Scano (1) , Marie-José Huguet (1, 2) , Sandra Ulrich Ngueveu (1, 3)

1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
2 INSA Toulouse - Institut National des Sciences Appliquées - Toulouse
3 Toulouse INP - Institut National Polytechnique (Toulouse)

Usual computations of alternative routes and the measure of their similarities and/or dierences do not embrace the variability of networks specics and user preferences. Indeed, the denition and evaluation of the dierence between paths is often embedded into algorithm internals and thus does not take into account that similar or dissimilar paths may vary depending on the user and/or the network. In this article, a generic method to generate alternative routes on FIFO time-dependent multimodal graphs with regular language constraints is presented. It relies on the computation, in a rst stage, of the k-shortest paths before the enforcement of a distinction criteria based on word metrics and comparison procedures in a second stage. We rst present a variant of a k-shortest paths algorithm taking into account both the multimodality and the time-dependency inherent to transportation networks. Then, we propose several methods for evaluating the dierences between routes. Experiments are conducted in realistic cases of transportation networks and associated results show the relative eciency and interest of the approach.

Mots clés: k-shortest paths; al-ternative routes; multimodal time-dependent networks

Domaines: Recherche opérationnelle [math.OC]

Grégoire Scano, Marie-José Huguet, Sandra Ulrich Ngueveu. A k-shortest paths based algorithm for multimodal time-dependent networks to compute alternative routes. LAAS-CNRS. 2015. ⟨hal-01180453⟩