An Algorithm for the Minimum Robust Cost Path on Networks with Random and Correlated Link Travel Times

Ravi Seshadri () and Karthik K. Srinivasan ()
Additional contact information
Ravi Seshadri: Indian Institute of Technology
Karthik K. Srinivasan: Indian Institute of Technology

Chapter Chapter 11 in Network Reliability in Practice, 2012, pp 171-208 from Springer

Abstract: Abstract Transportation networks are subject to a large degree of uncertainty due to traveler behavior, recurring congestion, capacity variability (construction zones, traffic incidents), variation in demands, etc.. resulting in unstable and unpredictable trip travel times. This has led to an emphasis on travel time reliability as a key determinant of route choice and an important measure of system performance, thus motivating research on optimizing travel time reliability on such stochastic networks. In this context, this work proposes an algorithm to compute the path of minimum robust cost (defined as a weighted combination of mean squared and variance of path travel time) on a network with stochastic and correlated link travel times.The proposed approach involves transforming the robust cost objective to a link separable or sum of squares form. Based on this formulation, a related multiple objective optimization problem is defined, and it is shown that the optimal robust cost path must lie in the non-dominated solution set of the multiple objective problem. Thus, a label correcting procedure for the multicriteria shortest path problem is applied to compute the non-dominated set and hence, the path of minimum robust cost. In addition, a new criterion of dominance is proposed (permutation invariant non-dominance or PIND) to reduce the size of the non-dominated path set while maintaining optimality with respect to the robust path problem. An approximate label correcting type procedure is developed to compute this reduced path set. Empirical experiments on a real-world network indicate that the PIND path set is significantly smaller than the corresponding ND set (between 60% and 95% on tested networks). In addition, computational tests on synthetic networks of size up to 1,500 nodes (7,500 links) demonstrate the efficiency of the proposed heuristic (computational time

Keywords: Risk Aversion; Short Path Problem; Cost Vector; Link Travel Time; Travel Time Variability (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations: View citations in EconPapers (6)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:trachp:978-1-4614-0947-2_11

Ordering information: This item can be ordered from
http://www.springer.com/9781461409472

DOI: 10.1007/978-1-4614-0947-2_11

Access Statistics for this chapter

More chapters in Transportation Research, Economics and Policy from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().