Lagrangian relaxation for the reliable shortest path problem with correlated link travel times

Yuli Zhang, Zuo-Jun Max Shen and Shiji Song

Transportation Research Part B: Methodological, 2017, vol. 104, issue C, 501-521

Abstract: Finding a reliable shortest path (RSP) in a stochastic network is a fundamental problem in transportation science. Link travel time correlation significantly affects path reliability, but also greatly increases the complexity of the RSP problem due to the quadratic form of the standard deviation term. Lagrangian relaxation (LR) based on problem reformulation, which only needs to solve a series of shortest path problems, has been recognized as an efficient method to obtain near-optimal RSPs with the optimality gap guarantee. This paper proposes a novel LR approach based on a new convex problem reformulation, and new methods to update Lagrangian multipliers and handle negative cycles of the resulting shortest path problems. Different from existing LR approaches, which adopt the classical subgradient method to solve the dual problem, a constraint generation (CG) algorithm and a subgradient projection (SP) algorithm are proposed to update Lagrangian multipliers effectively, and both algorithms are further modified to handle negative cycles. We also reveal the connection between different reformulations of the RSP problem and show that the proposed approach has a smaller duality gap than existing ones. Experiments on real transportation networks validate the effectiveness of the proposed approach in terms of convergence rate, run time, duality gap and optimality by comparison with the existing LR approaches and the outer approximation algorithm.

Keywords: Reliable shortest path; Lagrangian relaxation; Subgradient projection; Constraint generation; Duality gap (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261516307688
Full text for ScienceDirect subscribers only

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:eee:transb:v:104:y:2017:i:c:p:501-521

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2017.04.006

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().