The multi-criteria constrained shortest path problem

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

Research output: Journal PublicationsJournal Article (refereed)Researchpeer-review

3 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
Externally publishedYes

Fingerprint

Decomposition
candidacy
Shortest path
Optimal path
Multi-criteria
Bicriteria

Keywords

  • Constrained shortest path
  • Multi-criteria
  • Pareto-optimal paths
  • Routing

Cite this

@article{d748139d366142c2b8cab13142331011,
title = "The multi-criteria constrained shortest path problem",
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.",
keywords = "Constrained shortest path, Multi-criteria, Pareto-optimal paths, Routing",
author = "Ning SHI and Shaorui ZHOU and Fan WANG and Yi TAO and Liming LIU",
year = "2017",
month = "5",
day = "1",
doi = "10.1016/j.tre.2017.02.002",
language = "English",
volume = "101",
pages = "13--29",
journal = "Transportation Research, Part E: Logistics and Transportation Review",
issn = "1366-5545",
publisher = "Elsevier Ltd",

}

The multi-criteria constrained shortest path problem. / SHI, Ning; ZHOU, Shaorui; WANG, Fan; TAO, Yi; LIU, Liming.

In: Transportation Research. Part E: Logistics and Transportation Review, Vol. 101, 01.05.2017, p. 13-29.

Research output: Journal PublicationsJournal Article (refereed)Researchpeer-review

TY - JOUR

T1 - The multi-criteria constrained shortest path problem

AU - SHI, Ning

AU - ZHOU, Shaorui

AU - WANG, Fan

AU - TAO, Yi

AU - LIU, Liming

PY - 2017/5/1

Y1 - 2017/5/1

N2 - 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.

AB - 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.

KW - Constrained shortest path

KW - Multi-criteria

KW - Pareto-optimal paths

KW - Routing

UR - http://commons.ln.edu.hk/sw_master/7267

U2 - 10.1016/j.tre.2017.02.002

DO - 10.1016/j.tre.2017.02.002

M3 - Journal Article (refereed)

VL - 101

SP - 13

EP - 29

JO - Transportation Research, Part E: Logistics and Transportation Review

JF - Transportation Research, Part E: Logistics and Transportation Review

SN - 1366-5545

ER -