The multi-criteria constrained shortest path problem

Ning SHI, Shaorui ZHOU, Fan WANG, Yi TAO, Liming LIU

Research output: Journal PublicationsJournal Article (refereed)

11 Citations (Scopus)

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 languageEnglish
Pages (from-to)13-29
Number of pages17
JournalTransportation Research. Part E: Logistics and Transportation Review
Volume101
DOIs
Publication statusPublished - 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

Fingerprint Dive into the research topics of 'The multi-criteria constrained shortest path problem'. Together they form a unique fingerprint.

  • Cite this