Label-setting algorithms for a polynomial bi-objective multimodal shortest path problem
Résumé
Taking into account the multimodality of urban transportation networks for computing the itinerary of an individual passenger introduces a number of additional constraints such as restriction and/or preferences in using some modes. In this paper, such constraints are gathered under the concept of viable path modeled by a deterministic nite state automaton. Several polynomial algorithms are proposed to solve a bi-objective problem where the goal is to find all the nondominated viable shortest paths under the two objectives travel time and number of modal transfers. Among these algorithms, we consider an improved variant of the topological label-setting algorithm provided by Lozano and Storchi (2001), a new multilabel multi-queue algorithm and its bidirectional variant. The different algorithms are compared on a real network. The results show that, on the considered network, the proposed algorithms outperform the Lozano and Storchi (2001) algorithm, both for the time-independent and time-dependent case. Finally, A* acceleration techniques are discussed.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...