Adaptations of k-Shortest Path Algorithms for Transportation Networks

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

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)

The computation of the k-shortest paths, should they be elementary or not, has been extensively investigated in the literature, yielding to extremely performant algorithms. For elementary paths, the best known algorithm to this day is the algorithm of Yen enhanced by the extension of Lawler, while for the search of non-elementary paths, the algorithm with the best complexity is due to Eppstein but is outperformed in practice by the Recursive Enumeration Algorithm. In the context of transportation networks, graphs are time dependent, meaning that the cost of an edge depends on the time at which it is crossed. If for each edge one cannot arrive later if he departs earlier, the network is said to respect the FIFO property. Under this hypothesis, the usual Dijkstra shortest path algorithm is still polynomial. Additionally, since each edge is associated to a transportation type, one may want to restrict a path to be in a regular language. To find a shortest path under this constraint a polynomial algorithm, called DRegLC, works on the product of the network and the graph representing an automaton accepting the regular language. In this paper, some k-shortest paths algorithms are adapted to be used on such transportation networks with a regular language constraint. Also, the computation of the k-shortest elementary paths is considered using k-shortest non elementary paths algorithms, deleting loops while searching if possible. To address this approach, a new algorithm is presented to speedup the search of elementary paths while scanning as few paths containing loops as possible.

Domaines: Recherche opérationnelle [math.OC]

Grégoire Scano, Marie-José Huguet, Sandra Ulrich Ngueveu. Adaptations of k-Shortest Path Algorithms for Transportation Networks. International Conference on Industrial Engineering and Systems Management, Oct 2015, Seville, Spain. ⟨hal-01207475⟩