HighlightsThis study explores the general multi-criteria constrained shortest path (MCCSP) problem.An exact method for finding all the Pareto optimal paths for MCCSP is proposed.A theoretical bound for MCCSP is shown for understanding the relationship between the complexity and the number of criteria.Performance analysis demonstrates that our algorithm is highly efficient and robust.
AbstractIn this study, we propose an exact method for finding all the Pareto-optimal paths for a multi-criteria constrained shortest path problem. We show that solving the special bi-criteria problem is equivalent to generating at most constrained shortest paths with successive tightened constraints, where is the total number of all Pareto-optimal paths. For the general multi-criteria case, we propose a decomposition procedure and theoretically prove that this method can identify all the Pareto-optimal paths from at most candidate paths, where u is the number of criteria. Numerical studies demonstrate that our algorithm is highly efficient and robust.
The multi-criteria constrained shortest path problem
2017-02-13
17 pages
Article (Journal)
Electronic Resource
English
The Variance-Constrained Shortest Path Problem
Online Contents | 1994
|An improved solution algorithm for the constrained shortest path problem
Elsevier | 2006
|An improved solution algorithm for the constrained shortest path problem
Online Contents | 2007
|Multi-Constrained Shortest Path Model and Solution with Improved Ant Colony Algorithm
British Library Conference Proceedings | 2010
|