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

Yannick Kergosien (), Antoine Giret (), Emmanuel Néron () and Gaël Sauvanet ()
Additional contact information
Yannick Kergosien: Université de Tours, LIFAT EA 6300, CNRS, ROOT ERL CNRS 7002, 37200 Tours, France
Antoine Giret: Université de Tours, LIFAT EA 6300, CNRS, ROOT ERL CNRS 7002, 37200 Tours, France
Emmanuel Néron: Université de Tours, LIFAT EA 6300, CNRS, ROOT ERL CNRS 7002, 37200 Tours, France
Gaël Sauvanet: La Compagnie des Mobilités, 37000 Tours, France

INFORMS Journal on Computing, 2022, vol. 34, issue 1, 76-92

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.

Keywords: shortest path; label-correcting; multiobjective; cycling itineraries (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1081 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:1:p:76-92

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().