Simulation-Based Method for Finding Minimum Travel Time Budget Paths in Stochastic Networks with Correlated Link Times
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.
Get full access to this article
View all access and purchase options for this article.
References
1. Hall R. W. The Fastest Path Through a Network with Random Time-Dependent Travel Times. Transportation Science, Vol. 20, No. 3, 1986, pp. 182–188.
2. Fu L., and Rilett L. R. Expected Shortest Paths in Dynamic and Stochastic Traffic Networks. Transportation Research Part B, Vol. 32, No. 7, 1998, pp. 499–516.
3. Fu L. An Adaptive Routing Algorithm for In-Vehicle Route Guidance Systems with Real-Time Information. Transportation Research Part B, Vol. 35, No. 8, 2001, pp. 749–765.
4. Miller-Hooks E. D., and Mahmassani H. S. Least Expected Time Paths in Stochastic, Time Varying Transportation Networks. Transportation Science, Vol. 34, No. 2, 2000, pp. 198–215.
5. Miller-Hooks E. D. Adaptive Least-Expected Time Paths in Stochastic, Time-Varying Transportation and Data Networks. Networks, Vol. 37, No. 1, 2001, pp. 35–52.
6. Waller S. T., and Ziliaskopoulos A. K. On the Online Shortest Path Problem with Limited Arc Cost Dependencies. Networks, Vol. 40, No. 4, 2002, pp. 216–227.
7. Fan Y. Y., Kalaba R. E., and Moore J. E. Shortest Paths in Stochastic Networks with Correlated Link Costs. Computers and Mathematics with Applications, Vol. 49, No. 9, 2005, pp. 1549–1564.
8. Gao S., and Chabini I. Optimal Routing Policy Problems in Stochastic Time-Dependent Networks. Transportation Research Part B, Vol. 40, No. 2, 2006, pp. 93–122.
9. Wu X., and Nie Y. Modeling Heterogeneous Risk-Taking Behavior in Route Choice: A Stochastic Dominance Approach. Procedia–Social and Behavioral Sciences, Vol. 17, 2011, pp. 382–404.
10. Frank H. Shortest Path in Probabilistic Graphs. Operation Research, Vol. 17, No. 4, 1969, pp. 583–599.
11. Fan Y. Y., Kalaba R. E., and Moore J. E. Arriving on Time. Journal of Optimization Theory and Applications, Vol. 127, No. 3, 2005, pp. 497–513.
12. Nie Y., and Wu X. Shortest Path Problem Considering On-Time Arrival Probability. Transportation Research Part B, Vol. 43, 2009, pp. 597–613.
13. Nie Y., and Wu X. Reliable A Priori Shortest Path Problem with Limited Spatial and Temporal Dependencies. Proc., 18th International Symposium on Transportation and Traffic Theory, 2009, pp. 169–196.
14. Miller-Hooks E., and Mahmassani H. S. Path Comparisons for A Priori and Time-Adaptive Decisions in Stochastic, Time-Varying Networks. European Journal of Operational Research, Vol. 146, No. 1, 2003, pp. 67–82.
15. Nie Y., Wu X., Dillenburg J. F., and Nelson P. C. Reliable Route Guidance: A Case Study from Chicago. Transportation Research Part A, Vol. 46, No. 2, 2012, pp. 403–419.
16. Hall R. W. Travel Outcome and Performance: The Effect of Uncertainty on Accessibility. Transportation Research Part B, Vol. 17, No. 4, 1983, pp. 275–290.
17. Sivakumar R., and Batta R. The Variance-Constrained Shortest Path Problem. Transportation Science, Vol. 28, No. 4, 1994, pp. 309–316.
18. Sen S., Pillai R., Joshi S., and Rathi A. K. A Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems. Transportation Science, Vol. 35, No. 1, 2001, pp. 37–49.
19. Uchida T., and Iida Y. Risk Assignment: A New Traffic Assignment Model Considering Risk of Travel Time Variation. Proc., 12th International Symposium on Transportation and Traffic Theory (Daganzo C., ed.), Elsevier, Amsterdam, Netherlands, 1993, pp. 89–105.
20. Lo H. K., Luo X. W., and Siu B. W. Y. Degradable Transport Network: Travel Time Budget of Travelers with Heterogeneous Risk Aversion. Transportation Research Part B, Vol. 40, 2006, pp. 792–806.
21. Shao H., Lam W. H. K., Meng Q., and Tam M. L. Demand-Driven Traffic Assignment Problem Based on Travel Time Reliability. In Transportation Research Record: Journal of the Transportation Research Board, No. 1985, Transportation Research Board of the National Academies, Washington, D.C., 2006, pp. 220–230.
22. Loui R. P. Optimal Paths in Graphs with Stochastic or Multidimensional Weights. Communications of the ACM, Vol. 26, No. 9, 1983, pp. 670–676.
23. Mirchandani P. B., and Soroush H. Generalized Traffic Equilibrium with Probabilistic Travel Time and Perceptions. Transportation Science, Vol. 21, No. 3, 1987, pp. 133–152.
24. Yin Y., Lam W. H. K., and Ieda H. New Technology and the Modeling of Risk-Taking Behavior in Congested Road Networks. Transportation Research Part C, Vol. 12, No. 3, 2004, pp. 171–192.
25. Markowitz H. Portfolio Selection. The Journal of Finance, Vol. 7, No. 1, 1952, pp. 77–91.
26. Samuelson P. A. The Fundamental Approximation Theorem of Portfolio Analysis in Terms of Means, Variances and Higher Moments. Review of Economic Studies, Vol. 37, No. 4, 1970, pp. 537–542.
27. Li R., Rose G., and Sarvi M. Using Automatic Vehicle Identification Data to Gain Insight into Travel Time Variability and Its Causes. In Transportation Research Record: Journal of the Transportation Research Board, No 1945, Transportation Research Board of the National Academies, Washington, D.C., 2006, pp. 24–32.
28. Yu G., and Yang J. On the Robust Shortest Path Problem. Computers and Operations Research, Vol. 25, No. 6, 1998, pp. 457–468.
29. Bell M. G., and Cassir C. Risk-Averse User Equilibrium Traffic Assignment: An Application of Game Theory. Transportation Research Part B, Vol. 36, 2002, pp. 671–681.
30. Bertsimas D., and Sim M. Robust Discrete Optimization and Network Flows. Mathematical Programming, Vol. 98, 2003, pp. 49–71.
31. Ordóñez F., and Stier-Moses N. E. Wardrop Equilibria with Risk-Averse Users. Transportation Science, Vol. 44, No. 1, 2010, pp. 63–86.
32. Polychronopoulos G. H., and Tsitsiklis J. N. Stochastic Shortest Path Problems with Recourse. Networks, Vol. 27, No. 2, 1996, pp. 133–143.
33. Xing T., and Zhou X. Finding the Most Reliable Path With and Without Link Travel Time Correlation: A Lagrangian Substitution Based Approach. Transportation Research Part B, Vol. 45, 2011, pp. 1660–1679.
34. Huang H., and Gao S. Optimal Paths in Dynamic Networks with Dependent Random Link Travel Times. Transportation Research Part B, Vol. 46, 2012, pp. 579–598.
35. Shahabi M., Unnikrishnan A., and Boyles S. D. An Outer Approximation Algorithm for Robust Shortest Path Problem. Transportation Research Part E, Vol. 58, 2013, pp. 52–66.
36. Hutson K., and Shier D. Extended Dominance and a Stochastic Shortest Path Problem. Computers and Operations Research, Vol. 36, 2009, pp. 584–596.
37. Boyles S. D., and Waller S. T. A Mean-Variance Model for the Minimum Cost Flow Problem with Stochastic Arc Costs. Networks, Vol. 56, No. 3, 2010, pp. 215–227.
38. Sun H., and Gao Z. Stochastic Traffic Equilibrium Based on Travel Time Robust Reliability. Journal of Transportation Systems Engineering and Information Technology, Vol. 12, No. 2, 2012, pp. 76–84.
39. Chen B. Y., Lam W. H. K., Sumalee A., and Li Z. Reliable Shortest Path Finding in Stochastic Networks with Spatial Correlated Link Travel Times. International Journal of Geographical Information Science, Vol. 26, No. 2, 2012, pp. 365–386.
40. Chen A., and Ji Z. W. Path Finding under Uncertainty. Journal of Advanced Transportation, Vol. 39, 2005, pp. 19–37.
41. Ji Z., Kim Y. S., and Chen A. Multi-objective Reliable Path Finding in Stochastic Networks with Correlated Link Costs: A Simulation-based Multi-objective Genetic Algorithm Approach (SMOGA). Expert Systems with Applications, Vol. 38, 2011, pp. 1515–1528.
42. Zockaie A., Nie Y., Wu X., and Mahmassani H. S. Impacts of Correlations on Reliable Shortest Path Finding: A Simulation-Based Study. In Transportation Research Record: Journal of the Transportation Research Board, No. 2334, Transportation Research Board of the National Academies, Washington, D.C., 2013, pp. 1–9.
Cite article
Cite article
Cite article
OR
Download to reference manager
If you have citation software installed, you can download article citation data to the citation manager of your choice
Information, rights and permissions
Information
Published In
Article first published online: January 1, 2014
Issue published: January 2014
Authors
Metrics and citations
Metrics
Journals metrics
This article was published in Transportation Research Record: Journal of the Transportation Research Board.
VIEW ALL JOURNAL METRICSArticle usage*
Total views and downloads: 102
*Article usage tracking started in December 2016
Altmetric
See the impact this article is making through the number of times it’s been read, and the Altmetric Score.
Learn more about the Altmetric Scores
Articles citing this one
Receive email alerts when this article is cited
Web of Science: 0
Crossref: 25
- Estimating Path Travel Costs in Large-Scale Networks Using Machine-Lea...
- Optimal decisions in stochastic graphs with uncorrelated and correlate...
- Travel time reliability in transportation networks: A review of method...
- Reliable trajectory-adaptive routing strategies in stochastic, time-va...
- Estimation of Path Travel Time Distributions in Stochastic Time-Varyin...
- Incorporating Travel Time Reliability in Equitable Congestion Pricing ...
- Passenger’s routes planning in stochastic common-lines’ multi-modal tr...
- Cross Entropy Chance Distribution Model of Uncertain Random Shortest P...
- Shortest path problem on uncertain networks: An efficient two phases a...
- Branch-Price-and-Cut Algorithms for the Vehicle Routing Problem with S...
- Solving vehicle routing problems with stochastic and correlated travel...
- Reliable Least-Time Path Estimation and Computation in Stochastic Time...
- Robust routing, its price, and the tradeoff between routing robustness...
- Uncertain programming models for multi-objective shortest path problem...
- Reliable shortest path finding in stochastic time-dependent road netwo...
- On the modeling of passenger mobility for stochastic bi-modal urban co...
- Pareto Optimal Path Generation Algorithm in Stochastic Transportation ...
- An iterative learning approach for network contraction: Path finding p...
- The Shortest Path Problem and Its Critical Edge in Uncertain Environme...
- Robust Shortest Path Problem With Distributional Uncertainty
- A Strategic User Equilibrium for Independently Distributed Origin-Dest...
- Lagrangian relaxation for the reliable shortest path problem with corr...
- Meeting a deadline: shortest paths on stochastic directed acyclic grap...
- Path Finding in Stochastic Time Varying Networks with Spatial and Temp...
- Genetic Algorithm–Based Routing Problem Considering the Travel Reliabi...
Figures and tables
Figures & Media
Tables
View Options
Get access
Access options
If you have access to journal content via a personal subscription, university, library, employer or society, select from the options below:
loading institutional access options
Alternatively, view purchase options below:
Purchase 24 hour online access to view and download content.
Access journal content via a DeepDyve subscription or find out more about this option.
