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

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.