This paper studies the path finding problem in stochastic networks with known travel time distributions on each link of the network, in the presence of spatial and temporal travel time correlations. As a result of traffic dynamics and the decisions of network users, distributions with different characteristics can be observed for the link travel time at different time intervals. Considering correlations in a dynamic stochastic network and applying simulation-based realistic travel time distributions and correlations in the path finding problem in stochastic networks are the main contributions of this study. Two reliability-based optimal path finding problems were considered: the shortest path problem with on-time arrival probability and the minimum travel time budget path problem. For each problem, user heterogeneity can be considered in the developed approach, as users are allowed to have different preferences for travel time reliability. Solution algorithms for both problems were implemented and tested on a large-scale network in Chicago, Illinois, with networkwide link travel time distributions and correlations obtained from a traffic simulator. Numerical results demonstrate the impacts of correlations in a dynamic stochastic network on the optimal path travel time distribution. The developed approach can be used in the reliability-based user equilibrium problem to solve the main subproblem, the path finding problem, in dynamic stochastic networks.
Get full access to this article
View all access options for this article.
References
1.
MahmassaniH. S., KimJ., ChenY., StogiosY., and VovshaP.. SHRP 2 L04: Incorporating Reliability Performance Measures in Operations and Planning Modeling Tools. Transportation Research Board of the National Academies, Washington, D.C., 2013.
2.
JiZ., KimY. S., and ChenA.. 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.
3.
WhitmoreG. A., and FindlayM. C.. Stochastic Dominance: An Approach to Decision-Making Under Risk. Lexington Books, Lanham, Md., 1978.
4.
LevyH.Stochastic Dominance and Expected Utility: Survey and Analysis. Management Science, Vol. 38, 1992, pp. 555–592.
5.
FanY. Y., KalabaR. E., and MooreJ. E.. Arriving on Time. Journal of Optimization Theory and Applications, Vol. 127, No. 3, 2005, pp. 497–513.
6.
NieY., and WuX.. Shortest Path Problem Considering On-Time Arrival Probability. Transportation Research Part B, Vol. 43, 2009, pp. 597–613.
7.
WuX., and NieY.. Implementation Issues for the Reliable A Priori Shortest Path Problem. In Transportation Research Record: Journal of the Transportation Research Board, No. 2091, Transportation Research Board of the National Academies, Washington, D.C., 2009, pp. 51–60.
8.
NikolovaE.Approximation Algorithms for Reliable Stochastic Combinatorial Optimization. In Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques, Springer, Berlin, 2010, pp. 338–351.
9.
WuX., and NieY.. Modeling Heterogeneous Risk-Taking Behavior in Route Choice: A Stochastic Dominance Approach. Procedia—Social and Behavioral Sciences, Vol. 17, 2011, pp. 382–404.
10.
NieY., WuX., DillenburgJ. F., and NelsonP. C.. Reliable Route Guidance: A Case Study from Chicago. Transportation Research Part A, Vol. 46, No. 2, 2012, pp. 403–419.
11.
ZockaieA., NieY., WuX., and MahmassaniH. 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.
12.
HallR. W.Travel Outcome and Performance: The Effect of Uncertainty on Accessibility. Transportation Research Part B, Vol. 17, No. 4, 1983, pp. 275–290.
13.
SivakumarR., and BattaR.. The Variance-Constrained Shortest Path Problem. Transportation Science, Vol. 28, No. 4, 1994, pp. 309–316.
14.
SenS., PillaiR., JoshiS., and RathiA. K.. A Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems. Transportation Science, Vol. 35, No. 1, 2001, pp. 37–49.
15.
LoH. K., LuoX. W., and SiuB. W. Y.. Degradable Transport Network: Travel Time Budget of Travelers with Heterogeneous Risk Aversion. Transportation Research Part B, Vol. 40, 2006, pp. 792–806.
16.
DongJ., and MahmassaniH. S.. Flow Breakdown and Travel Time Reliability. In Transportation Research Record: Journal of the Transportation Research Board, No. 2124, Transportation Research Board of the National Academies, Washington, D.C., 2009, pp. 203–212.
17.
HutsonK., and ShierD.. Extended Dominance and a Stochastic Shortest Path Problem. Computers and Operations Research, Vol. 36, 2009, pp. 584–596.
18.
BoylesS. D., and WallerS. T.. A Mean-Variance Model for the Minimum Cost Flow Problem with Stochastic Arc Costs. Networks, Vol. 56, No. 3, 2010, pp. 215–227.
19.
XingT., and ZhouX.. 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.
20.
ShahabiM., UnnikrishnanA., and BoylesS. D.. An Outer Approximation Algorithm for Robust Shortest Path Problem. Transportation Research Part E, Vol. 58, 2013, pp. 52–66.
21.
ZockaieA., NieY. M., and MahmassaniH. S.. Simulation-Based Method for Finding Minimum Travel Time Budget Paths in Stochastic Networks with Correlated Link Times. In Transportation Research Record: Journal of the Transportation Research Board, No. 2467, Transportation Research Board of the National Academies, Washington, D.C., 2014, pp. 140–148.
22.
FrankM., and WolfeP.. An Algorithm for Quadratic Programming. Naval Research Logistics Quarterly, Vol. 3, 1969, pp. 95–110.
23.
ChenA., and JiZ. W.. Path Finding Under Uncertainty. Journal of Advanced Transportation, Vol. 39, 2005, pp. 19–37.
24.
Miller-HooksE. D., and MahmassaniH. 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.
25.
FanY. Y., KalabaR. E., and MooreJ. E.. Shortest Paths in Stochastic Networks with Correlated Link Costs. Computers and Mathematics with Applications, Vol. 49, 2005, pp. 1549–1564.
26.
GaoS., and ChabiniI.. Optimal Routing Policy Problems in Stochastic Time-Dependent Networks. Transportation Research Part B, Vol. 40, No. 2, 2006, pp. 93–122.
27.
NieY., and WuX.. Reliable A Priori Shortest Path Problem with Limited Spatial and Temporal Dependencies. In Proceedings of the 18th International Symposium on Transportation and Traffic Theory, 2009, pp. 169–196.
28.
ChenB. Y., LamW. H. K., SumaleeA., and LiZ.. 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.
29.
HuangH., and GaoS.. Optimal Paths in Dynamic Networks with Dependent Random Link Travel Times. Transportation Research Part B, Vol. 46, 2012, pp. 579–598.
30.
ZiliaskopoulosA. K., and MahmassaniH. S.. Time-Dependent, Shortest-Path Algorithm for Real-Time Intelligent Vehicle Highway System Applications. In Transportation Research Record 1408, TRB, National Research Council, Washington, D.C., 1993, pp. 94–100.
31.
MahmassaniH. S., and SbaytiH.. DYNASMART-P Version 1.6 User’s Guide. Northwestern University Transportation Center, Evanston, Ill., 2009.
32.
ZockaieA., ChenY., and MahmassaniH. S.. Adaptive Drivers and Time-Dependent Origin-Destination Demand Estimation: Methodology and Application to Large-Scale Network. Presented at 93rd Annual Meeting of the Transportation Research Board, Washington, D.C., 2014.
