Back to Search Start Over

An Efficient Label-Correcting Algorithm for the Multiobjective Shortest Path Problem.

Authors :
Kergosien, Yannick
Giret, Antoine
Néron, Emmanuel
Sauvanet, Gaël
Source :
INFORMS Journal on Computing. Winter2022, Vol. 34 Issue 1, p76-92. 17p.
Publication Year :
2022

Abstract

This paper proposes an exact algorithm to solve the one-to-one multiobjective shortest path problem. The solution involves determining a set of nondominated paths between two given nodes in a graph that minimizes several objective functions. This study is motivated by the application of this solution method to determine cycling itineraries. The proposed algorithm improves upon a label-correcting algorithm to rapidly solve the problem on large graphs (i.e., up to millions of nodes and edges). To verify the performance of the proposed algorithm, we use computational experiments to compare it with the best-known methods in the literature. The numerical results confirm the efficiency of the proposed algorithm. Summary of Contribution: The paper deals with a classic operations research problem (the one-to-one multiobjective shortest path problem) and is motivated by a real application for cycling itineraries. An efficient method is proposed and is based on a label-correcting algorithm into which several additional improvement techniques are integrated. Computational experiments compare this algorithm with the best-known methods in the literature to validate the performance on large-size graphs (Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) instances from the ninth DIMACS challenge). New instances from the context of cycling itineraries are also proposed. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
10919856
Volume :
34
Issue :
1
Database :
Academic Search Index
Journal :
INFORMS Journal on Computing
Publication Type :
Academic Journal
Accession number :
155827917
Full Text :
https://doi.org/10.1287/ijoc.2021.1081