Abstract
In 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 |P| constrained shortest paths with successive tightened constraints, where |P| 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 ( u -1)!|P| candidate paths, where u is the number of criteria. Numerical studies demonstrate that our algorithm is highly efficient and robust.
| Original language | English |
|---|---|
| Pages (from-to) | 13-29 |
| Number of pages | 17 |
| Journal | Transportation Research. Part E: Logistics and Transportation Review |
| Volume | 101 |
| DOIs | |
| Publication status | Published - 1 May 2017 |
Bibliographical note
This research was supported by the National Natural Science Foundation of China (Nos. 71431007, 71225004, and 71601054). We also sincerely thank the editor and three anonymous referees for their valuable comments in the revision of this research.Keywords
- Constrained shortest path
- Multi-criteria
- Pareto-optimal paths
- Routing