Simulation-Based Method for Finding Minimum Travel Time Budget Paths in Stochastic Networks with Correlated Link Times
Authors:
- 1 January 2014
- journal article
- Published by SAGE Publications in Transportation Research Record: Journal of the Transportation Research Board
- Vol. 2467 (1) , 140-148
Abstract
The aim of this study was to solve the minimum path travel time budget (MPTTB) problem, in which the travel time budget was the reliability index. This index was defined as the sum of the mean path travel time and the scaled standard deviation, which included the covariance matrix to consider correlation. Two existing solution methods in the literature, the outer approximation algorithm and Monte Carlo simulation method, were applied to solve the MPTTB problem. The former method approximated the hard nonlinear constraint of the MPTTB problem by a series of linear cuts generated iteratively and repeatedly solved a mixed integer program. The latter method, which was a simulation-based method, included two stages. The first stage founded a set of candidate paths, and the second stage generated the distribution of travel times for the existing paths in the candidate set. The numerical results for these two solution methods were conducted on the Chicago sketch network, and results showed that the methods found comparable solutions though they have respective advantages and drawbacks. Although the outer approximation algorithm demonstrated promising performance, it still relied on repeatedly solving a mixed integer program (subproblem) with a commercial solver, which could be a challenging task in its own right. The simulation-based method offers a good Plan B in the case in which other algorithms encounter difficulties.Keywords
This publication has 40 references indexed in Scilit:
- Modeling Heterogeneous Risk-Taking Behavior in Route Choice: A Stochastic Dominance ApproachProcedia - Social and Behavioral Sciences, 2011
- Optimal routing policy problems in stochastic time-dependent networksTransportation Research Part B: Methodological, 2006
- Shortest paths in stochastic networks with correlated link costsComputers & Mathematics with Applications, 2005
- On the online shortest path problem with limited arc cost dependenciesNetworks, 2002
- An adaptive routing algorithm for in-vehicle route guidance systems with real-time informationTransportation Research Part B: Methodological, 2001
- Least Expected Time Paths in Stochastic, Time-Varying Transportation NetworksTransportation Science, 2000
- Adaptive least-expected time paths in stochastic, time-varying transportation and data networksNetworks, 2000
- Expected shortest paths in dynamic and stochastic traffic networksTransportation Research Part B: Methodological, 1998
- The Fastest Path through a Network with Random Time-Dependent Travel TimesTransportation Science, 1986
- Shortest Paths in Probabilistic GraphsOperations Research, 1969