The constrained shortest path problem with stochastic correlated link travel times

• We first propose the constrained shortest path problem with stochastic correlated link travel times.
• A 0–1 integer programming model for the proposed constrained shortest path problem is formulated.
• A specific Lagrangian relaxation-based approach is presented to relax the hard constraints.
• An algorithmic framework is designed to minimize the gap between the upper and lower bounds.
• The effectiveness of proposed approaches is verified by different scales of transportation networks.

This paper investigates the constrained shortest path problem in a transportation network where the link travel times are assumed to be random variables defined on the basis of joint probability mass functions. A 0–1 integer programming model is formulated to find the least expected travel time paths. Besides the flow balance and side constraints, the unique link selection constraint is particularly introduced to guarantee that only an optimal path can be finally generated. Then, a Lagrangian relaxation solution approach is provided to relax the hard constraints and decompose the relaxed model into two parts. An algorithmic framework, integrating the sub-gradient algorithm, label-correcting algorithm and K-shortest path algorithm, is designed to minimize the gap between the upper and lower bounds to find near-optimal solutions. An extension that considers the joint probability mass functions of link travel times varying with time is discussed. We decompose the time-dependent problem into three subproblems and solve it by the modified algorithmic framework. Computational tests are conducted on different scales of transportation networks. Experimental results in a large-scale network indicate that the proposed algorithm can quickly find the high-quality solutions with small relative gaps, demonstrating the effectiveness of the proposed approaches.