File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

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

TitleLagrangian relaxation for the reliable shortest path problem with correlated link travel times
Authors
KeywordsLagrangian relaxation
Subgradient projection
Reliable shortest path
Constraint generation
Duality gap
Issue Date2017
Citation
Transportation Research Part B: Methodological, 2017, v. 104, p. 501-521 How to Cite?
Abstract© 2017 Elsevier Ltd. 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.
Persistent Identifierhttp://hdl.handle.net/10722/296147
ISSN
2023 Impact Factor: 5.8
2023 SCImago Journal Rankings: 2.660
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorZhang, Yuli-
dc.contributor.authorShen, Zuo Jun Max-
dc.contributor.authorSong, Shiji-
dc.date.accessioned2021-02-11T04:52:56Z-
dc.date.available2021-02-11T04:52:56Z-
dc.date.issued2017-
dc.identifier.citationTransportation Research Part B: Methodological, 2017, v. 104, p. 501-521-
dc.identifier.issn0191-2615-
dc.identifier.urihttp://hdl.handle.net/10722/296147-
dc.description.abstract© 2017 Elsevier Ltd. 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.-
dc.languageeng-
dc.relation.ispartofTransportation Research Part B: Methodological-
dc.subjectLagrangian relaxation-
dc.subjectSubgradient projection-
dc.subjectReliable shortest path-
dc.subjectConstraint generation-
dc.subjectDuality gap-
dc.titleLagrangian relaxation for the reliable shortest path problem with correlated link travel times-
dc.typeArticle-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.trb.2017.04.006-
dc.identifier.scopuseid_2-s2.0-85019443873-
dc.identifier.volume104-
dc.identifier.spage501-
dc.identifier.epage521-
dc.identifier.isiWOS:000412036300025-
dc.identifier.issnl0191-2615-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats