Routing in a Stochastic Network with Nonrecurrent Incidents: Behavioral Interpretation of Dynamic Traffic Assignment
Publication: ASCE-ASME Journal of Risk and Uncertainty in Engineering Systems, Part A: Civil Engineering
Volume 6, Issue 1
Abstract
In an advanced traveler information system (ATIS), this study examines how to map a driver’s time constraints and risk-taking behavior to real-time routing in a probabilistic time-dependent network (or stochastic network). Accounting for en route delays and alternate routings, ATIS networks are shown to exhibit other than the first-in first-out property (FIFO) behavior: drivers who depart earlier may not arrive ahead of those who depart later. In this paper, the term FIFO is used well beyond the traditional connotation of a single queue or a single path; it applies toward multiple routes. It is used to describe a well-recognized phenomenon in dynamic traffic assignment, wherein a commuter who delays their departure time may arrive at work earlier than one who takes off earlier. Given a network with full spatiotemporal information, a wait-time search algorithm is employed to account for the best-planned delays at the origin or en route. The algorithm elicits the bottlenecks in the network and obtains the optimal wait times a driver needs to avoid these bottlenecks, given their tolerance for risk. The herein defined routing policy makes decision at every network node—based on the current states—to determine the optimal wait time (if any) and the next-hop node. The model also valuates a driver’s risk tolerance by imputing the worth of safety as a cost metric. Empirical results were obtained from a central Arkansas highway network based on incident reports obtained from the state police between the years 2000 to 2003. Solidly founded on Bellman’s optimality condition, the fundamental diagram of traffic flow, and multiattribute utility theory, the algorithm is shown to be operationally feasible for real-time applications.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The authors are grateful to J. Hu for his work, from which the current research built. During the conduct of this research, the authors were grateful for the support from G. DelPorto and J. Heflin of the Federal Highway Administration, plus M. Bradley and D. Pearce of the Arkansas Department of Transportation. They are also appreciative of inputs from W. Xiao, G. Hill, D.-J. Joo, T. Maroo, N. Davis, C. Covington, M. Le, J. McKenzie, and R. McGee, who participated as members of the research team. In particular, the authors wish to thank G. Hill and D.-J. Joo for validating the accuracy of sample computations (Hill, G., and Joo, D.-J. “Optimizing Travel Times in Policy-based Routing: A Deviation on Shortest-path Algorithm using Arc Extension.” Working Paper, Dept. of Systems Engineering, University of Arkansas at Little Rock, Little Rock, Arkansas). The statements and opinions expressed here in the paper belong to the authors and do not necessarily reflect those of the sponsors or the organizations mentioned in this paper. The research is supported by Federal-aid Project No. ITSR (001) to the University of Arkansans at Little Rock.
References
Abdel-Aty, M., and M. F. Abdalla. 2004. “Modeling repeated multinomial route choices under advanced traveler information system—Generalized estimating equations with polytomous logit function.” Transp. Res. Rec. 1882 (1): 61–69. https://doi.org/10.3141/1882-08.
Bellman, R. 1958. “On a routing problem.” Quart. Appl. Math. 16 (1): 87–90. https://doi.org/10.1090/qam/102435.
Chabini, I. 1998. “Discrete dynamic shortest path problems in transportation application: Complexity and algorithms with optimal run time.” Transp. Res. Rec. 1645 (1): 170–175. https://doi.org/10.3141/1645-21.
Chang, T. S., L. K. Nozick, and M. A. Turnquist. 2005. “Multiobjective path finding in stochastic dynamic networks, with application to routing hazardous materials shipments.” Transp. Sci. 39 (3): 383–399. https://doi.org/10.1287/trsc.1040.0094.
de Alfaro, L. 1999. “Computing maximum or minimum reachability times in probabilistic systems.” In Vol. 1664 of Proc., CONCUR ’99: Concurrency Theory, edited by J. C. M. Baeten, and S. Mauw, 66–81. Berlin: Springer.
Dean, B. C. 2004. “Shortest paths in FIFO time-dependent networks: Theory and algorithms.” Networks 44 (1): 41–46. https://doi.org/10.1002/net.20013.
Dijkstra, E. W. 1959. “A note on two problems in connection with graphs.” Numerische Math. 1 (1): 269–271. https://doi.org/10.1007/BF01386390.
Dong, J., and H. S. Mahmassani. 2009. “Flow breakdown, travel reliability and real-time information in route choice behavior.” In Transportation and traffic theory 2009: Golden jubilee, 675–695. Berlin: Springer.
Dong, J., and H. S. Mahmassani. 2013. “Improving network traffic flow reliability through dynamic anticipatory tolls.” Transportmetrica B 1 (3): 226–236.
Fajardo, D., and S. T. Waller. 2012. “Finding minimum-cost dynamic routing policies in stochastic-state networks with link failures.” Transp. Res. Rec. 2283 (1): 113–121. https://doi.org/10.3141/2283-12.
Fan, Y. Y., R. E. Kalaba, and J. E. Moore. 2005. “Shortest paths in stochastic networks with correlated link costs.” J. Comput. Appl. Math. 49 (9–10): 1549–1564. https://doi.org/10.1016/j.camwa.2004.07.028.
Fonzone, A., J. D. Schmocker, J. Ma, and D. Fukuda. 2012. “Link-based route choice considering risk aversion, disappointment, and regret.” Transp. Res. Rec. 2322 (1): 119–128. https://doi.org/10.3141/2322-13.
Fu, L. 2001. “An adaptive routing algorithm for in-vehicle route guidance systems with real-time information.” Transp. Res. B 35 (8): 749–765. https://doi.org/10.1016/S0191-2615(00)00019-9.
Fu, L., D. Sun, and L. R. Rilett. 2006. “Heuristic shortest path algorithms for transportation applications: State of the art.” Comput. Oper. Res. 33 (11): 3324–3343. https://doi.org/10.1016/j.cor.2005.03.027.
Gao, S., and I. Chabini. 2006. “Optimal routing policy problems in stochastic time-dependent networks.” Transp. Res. 40 (2): 93–122. https://doi.org/10.1016/j.trb.2005.02.001.
Gazis, D. C. 2002. Traffic theory, 36–38. Berlin: Springer.
Greenshields, B. D. 1935. “A study of traffic capacity.” Highway Res. Board Proceedings 14: 448–477.
Hu, J., and Y. Chan. 2008a. “A dynamic shortest-path algorithm for continuous arc travel-times: Implication for traffic incident management.” Transp. Res. Rec. 2089 (1): 51–57. https://doi.org/10.3141/2089-07.
Hu, J., and Y. Chan. 2008b. “Dynamic routing to minimize travel time and incident risks.” In Proc., 10th Int. Conf. on Application of Advanced Technologies in Transportation. Reston, VA: ASCE.
ITS metaLAB. 2009. Intelligent transportation systems in central Arkansas, quarterly and final report. Little Rock, AR: Univ. of Arkansas at Little Rock.
Jaillet, P., J. Qi, and M. Sim. 2016. “Routing optimization under uncertainty.” Oper. Res. 64 (1): 186–200. https://doi.org/10.1287/opre.2015.1462.
Ji, X., K. Iwamura, and Z. Shao. 2007. “New models for shortest path problem with fuzzy arc lengths.” Appl. Math. Modell. 31 (2): 259–269. https://doi.org/10.1016/j.apm.2005.09.001.
Keeney, R. L., and H. Raiffa. 1976. Decisions with multiple objectives’ preferences and value tradeoffs. New York: Wiley.
Kerner, B. S. 2004. The physics of traffic: Empirical freeway pattern features, engineering applications, and theory. Berlin: Springer.
Li, Q., Y. Nie, S. Vallamsundar, J. Lin, and T. Homem-de-Mello. 2014. “Finding efficient and environmentally friendly paths for risk-averse freight carriers.” Netw. Spatial Econ. 16 (1): 255–275. https://doi.org/10.1007/s11067-013-9220-8.
Long, J., W. Y. Szeto, Z. Gao, H. J. Huang, and Q. Shi. 2016. “The nonlinear equation system approach to solving dynamic user optimal simultaneous route and departure time choice problems.” Transp. Res. B 83 (Jan): 179–206. https://doi.org/10.1016/j.trb.2015.11.005.
Lu, X., S. Gao, E. Ben-Elia, and R. Pothering. 2014. “Travelers’ day-to-day route choice behavior with real-time information in a congested risky network.” Math. Popul. Stud. 21 (4): 205–219. https://doi.org/10.1080/08898480.2013.836418.
Miller-Hooks, E., and B. Y. Yang. 2005. “Updating paths in time-varying networks given arc weight changes.” Transp. Sci. 39 (4): 451–464. https://doi.org/10.1287/trsc.1040.0112.
Mostafizi, A., S. Dong, and H. Wang. 2017. “Percolation phenomenon in connected vehicle network through a multi-agent approach: Mobility benefits and market penetration.” Transp. Res. 85 (Dec): 312–333. https://doi.org/10.1016/j.trc.2017.09.013.
Nozick, L. K., G. F. List, and M. A. Turnquist. 1997. “Integrated routing and scheduling in hazardous materials transportation.” Transp. Sci. 31 (3): 200–215. https://doi.org/10.1287/trsc.31.3.200.
Opasanon, S., and E. Miller-Hooks. 2005. “Adjustable preference path strategies for use in multicriteria, stochastic, and time-varying transportation networks.” Transp. Res. Rec. 1923 (1): 137–143. https://doi.org/10.1177/0361198105192300115.
Seshadri, R., and K. K. Srinivasan. 2014. “Algorithm for determining path of maximum reliability on a network subject to random arc connectivity failures.” Transp. Res. Rec. 2467 (1): 80–90. https://doi.org/10.3141/2467-09.
Sherali, H. D., and S. Subramanian. 1999. “Opportunity cost-based models for traffic incident response problem.” J. Transp. Eng. 125 (3): 176–185. https://doi.org/10.1061/(ASCE)0733-947X(1999)125:3(176).
Smeed, R. J. 1967. “Some circumstances in which vehicles will reach their destination earlier by starting later.” Transp. Sci. 1 (4): 308–317. https://doi.org/10.1287/trsc.1.4.308.
Srinivasan, K. K., and Z. Guo. 2004. “Day-to-day evolution of network flows under route-choice dynamics in commuter decisions.” Transp. Res. Rec. 1894 (1): 198–208. https://doi.org/10.3141/1894-21.
Sussman, J. M. 2004. “ITS: What we know now that we wish we knew then: A retrospective on the ITS 1992 strategic plan.” In Proc., 2004 Annual Meeting, Washington, DC: Transportation Research Board.
Tringides, C. A., X. Ye, and R. M. Pendyala. 2004. “Departure-time choice and mode choice for nonwork trips—Alternative formulations of joint model systems.” Transp. Res. Rec. 1898 (1): 1–9. https://doi.org/10.3141/1898-01.
Wang, S., H. Shao, L. Tao, and Q. Ni. 2010. “Travel time reliability-based optimal path finding.” In Proc., 3rd Int. Joint Conf. on Computational Science and Optimization, 531–534. New York: IEEE.
Wijeratne, A. B., M. A. Turnquist, and P. B. Mirchandani. 1993. “Multiobjective routing of hazardous materials in stochastic networks.” Eur. J. Oper. Res. 65 (1): 33–43. https://doi.org/10.1016/0377-2217(93)90142-A.
Wu, X., and Y. M. Nie. 2011. “Modeling heterogeneous risk-taking behavior in route choice: A stochastic dominance approach.” Transp. Res. Part A Policy Pract. 45 (Jan): 896–915.
Xing, T., and X. Zhou. 2011. “Finding the most reliable path with and without link travel time correlation: A Lagrangian substitution based approach.” Transp. Res. 45 (10): 1660–1679. https://doi.org/10.1016/j.trb.2011.06.004.
Ziliaskopoulos, A. K., and H. S. Mahmassani. 1993. “Time-dependent, shortest-path algorithm for real-time intelligent vehicle highway system applications.” Transp. Res. Rec. 1408: 94–100.
Zockaie, A., Y. Nie, X. Wu, and H. S. Mahmassan. 2013. “Impacts of correlations on reliable shortest path finding: A simulation-based study.” Transp. Res. Rec. 2334 (1): 1–9. https://doi.org/10.3141/2334-01.
Information & Authors
Information
Published In
ASCE-ASME Journal of Risk and Uncertainty in Engineering Systems, Part A: Civil Engineering
Volume 6 • Issue 1 • March 2020
Copyright
©2020 American Society of Civil Engineers.
History
Received: Sep 14, 2018
Accepted: Jun 5, 2019
Published online: Jan 8, 2020
Published in print: Mar 1, 2020
Discussion open until: Jun 8, 2020
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.