The constrained shortest path problem with stochastic correlated link travel times

Li Wang, Lixing Yang and Ziyou Gao

European Journal of Operational Research, 2016, vol. 255, issue 1, 43-57

Abstract: 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.

Keywords: Constrained programming; Constrained shortest path problem; Stochastic correlated link travel times; Lagrangian relaxation; Label-correcting algorithm (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716303770
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:ejores:v:255:y:2016:i:1:p:43-57

DOI: 10.1016/j.ejor.2016.05.040

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().