An algorithm for reliable shortest path problem with travel time correlations
Author
Abstract
Suggested Citation
DOI: 10.1016/j.trb.2018.12.011
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- Wu, Xing & (Marco) Nie, Yu, 2011. "Modeling heterogeneous risk-taking behavior in route choice: A stochastic dominance approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(9), pages 896-915, November.
- Carrion, Carlos & Levinson, David, 2012.
"Value of travel time reliability: A review of current evidence,"
Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(4), pages 720-741.
- Carlos Carrion & David Levinson, 2010. "Value of Travel Time Reliability: A review of current evidence," Working Papers 000085, University of Minnesota: Nexus Research Group.
- Monique Guignard, 2003. "Lagrangean relaxation," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 11(2), pages 151-200, December.
- Y. Y. Fan & R. E. Kalaba & J. E. Moore, 2005. "Arriving on Time," Journal of Optimization Theory and Applications, Springer, vol. 127(3), pages 497-513, December.
- Marshall L. Fisher, 1981. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 27(1), pages 1-18, January.
- Robert G. Bland & Donald Goldfarb & Michael J. Todd, 1981. "Feature Article—The Ellipsoid Method: A Survey," Operations Research, INFORMS, vol. 29(6), pages 1039-1091, December.
- Khani, Alireza & Boyles, Stephen D., 2015. "An exact algorithm for the mean–standard deviation shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 252-266.
- Hao Hu & Renata Sotirov, 2018. "Special cases of the quadratic shortest path problem," Journal of Combinatorial Optimization, Springer, vol. 35(3), pages 754-777, April.
- Bi Chen & William Lam & Agachai Sumalee & Qingquan Li & Hu Shao & Zhixiang Fang, 2013. "Finding Reliable Shortest Paths in Road Networks Under Uncertainty," Networks and Spatial Economics, Springer, vol. 13(2), pages 123-148, June.
- Wu, Xing, 2015. "Study on mean-standard deviation shortest path problem in stochastic and time-dependent networks: A stochastic dominance based approach," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 275-290.
- Noland, Robert B. & Small, Kenneth A. & Koskenoja, Pia Maria & Chu, Xuehao, 1998.
"Simulating travel reliability,"
Regional Science and Urban Economics, Elsevier, vol. 28(5), pages 535-564, September.
- Noland, R.B. & Small, K.A. & Koskenoja, P.M. & Chu, X., 1996. "Simulating Travel Reliability," Papers 95-96-7, California Irvine - School of Social Sciences.
- Noland, Robert B. & Small, Kenneth A. & Koskenoja, Pia Maria & Chu, Xuehao, 1997. "Simulating Travel Reliability," University of California Transportation Center, Working Papers qt30w220k0, University of California Transportation Center.
- Xing, Tao & Zhou, Xuesong, 2011. "Finding the most reliable path with and without link travel time correlation: A Lagrangian substitution based approach," Transportation Research Part B: Methodological, Elsevier, vol. 45(10), pages 1660-1679.
- Rostami, Borzou & Chassein, André & Hopf, Michael & Frey, Davide & Buchheim, Christoph & Malucelli, Federico & Goerigk, Marc, 2018. "The quadratic shortest path problem: complexity, approximability, and solution methods," European Journal of Operational Research, Elsevier, vol. 268(2), pages 473-485.
- Watling, David, 2006. "User equilibrium traffic network assignment with stochastic travel times and late arrival penalty," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1539-1556, December.
- Lo, Hong K. & Luo, X.W. & Siu, Barbara W.Y., 2006. "Degradable transport network: Travel time budget of travelers with heterogeneous risk aversion," Transportation Research Part B: Methodological, Elsevier, vol. 40(9), pages 792-806, November.
- Yang, Lixing & Zhou, Xuesong, 2014. "Constraint reformulation and a Lagrangian relaxation-based solution algorithm for a least expected time path problem," Transportation Research Part B: Methodological, Elsevier, vol. 59(C), pages 22-44.
- Zhang, Yuli & Max Shen, Zuo-Jun & Song, Shiji, 2017. "Lagrangian relaxation for the reliable shortest path problem with correlated link travel times," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 501-521.
- Shahabi, Mehrdad & Unnikrishnan, Avinash & Boyles, Stephen D., 2013. "An outer approximation algorithm for the robust shortest path problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 58(C), pages 52-66.
- Yang, Lixing & Zhou, Xuesong, 2017. "Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 68-91.
- Chen, Bi Yu & Li, Qingquan & Lam, William H.K., 2016. "Finding the k reliable shortest paths under travel time uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 189-203.
- Wang, Judith Y.T. & Ehrgott, Matthias & Chen, Anthony, 2014. "A bi-objective user equilibrium model of travel time reliability in a road network," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 4-15.
- Nie, Yu (Marco) & Wu, Xing, 2009. "Shortest path problem considering on-time arrival probability," Transportation Research Part B: Methodological, Elsevier, vol. 43(6), pages 597-613, July.
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- Ihnat Ruksha & Andrzej Karbowski, 2022. "Decomposition Methods for the Network Optimization Problem of Simultaneous Routing and Bandwidth Allocation Based on Lagrangian Relaxation," Energies, MDPI, vol. 15(20), pages 1-28, October.
- Jorge A. Sefair & Oscar Guaje & Andrés L. Medaglia, 2021. "A column-oriented optimization approach for the generation of correlated random vectors," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 777-808, September.
- Zhaoqi Zang & Xiangdong Xu & Kai Qu & Ruiya Chen & Anthony Chen, 2022. "Travel time reliability in transportation networks: A review of methodological developments," Papers 2206.12696, arXiv.org, revised Jul 2022.
- David Corredor-Montenegro & Nicolás Cabrera & Raha Akhavan-Tabatabaei & Andrés L. Medaglia, 2021. "On the shortest $$\alpha$$ α -reliable path problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 287-318, April.
- Liu, Yong & Xiao, Feng & Shen, Minyu & Zhao, Lin & Li, Lu, 2024. "The k-th order mean-deviation model for route choice under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 189(C).
- Jie, Ke-Wei & Liu, San-Yang & Sun, Xiao-Jun & Xu, Yun-Cheng, 2023. "A dynamic ripple-spreading algorithm for solving mean–variance of shortest path model in uncertain random networks," Chaos, Solitons & Fractals, Elsevier, vol. 167(C).
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- Zhang, Yuli & Max Shen, Zuo-Jun & Song, Shiji, 2017. "Lagrangian relaxation for the reliable shortest path problem with correlated link travel times," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 501-521.
- Liu, Yong & Xiao, Feng & Shen, Minyu & Zhao, Lin & Li, Lu, 2024. "The k-th order mean-deviation model for route choice under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 189(C).
- Shen, Liang & Shao, Hu & Wu, Ting & Fainman, Emily Zhu & Lam, William H.K., 2020. "Finding the reliable shortest path with correlated link travel times in signalized traffic networks under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 144(C).
- Zhaoqi Zang & Xiangdong Xu & Kai Qu & Ruiya Chen & Anthony Chen, 2022. "Travel time reliability in transportation networks: A review of methodological developments," Papers 2206.12696, arXiv.org, revised Jul 2022.
- Teng, Wenxin & Chen, Bi Yu, 2024. "Reliable lifelong planning A*: Technique for re-optimizing reliable shortest paths when travel time distribution updating," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 188(C).
- Wu, Xing, 2015. "Study on mean-standard deviation shortest path problem in stochastic and time-dependent networks: A stochastic dominance based approach," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 275-290.
- Chen, Bi Yu & Li, Qingquan & Lam, William H.K., 2016. "Finding the k reliable shortest paths under travel time uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 189-203.
- A. Arun Prakash & Karthik K. Srinivasan, 2017. "Finding the Most Reliable Strategy on Stochastic and Time-Dependent Transportation Networks: A Hypergraph Based Formulation," Networks and Spatial Economics, Springer, vol. 17(3), pages 809-840, September.
- Tan, Zhijia & Yang, Hai & Guo, Renyong, 2014. "Pareto efficiency of reliability-based traffic equilibria and risk-taking behavior of travelers," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 16-31.
- Yang, Lixing & Zhou, Xuesong, 2017. "Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 68-91.
- Prakash, A. Arun & Seshadri, Ravi & Srinivasan, Karthik K., 2018. "A consistent reliability-based user-equilibrium problem with risk-averse users and endogenous travel time correlations: Formulation and solution algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 171-198.
- Khani, Alireza & Boyles, Stephen D., 2015. "An exact algorithm for the mean–standard deviation shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 252-266.
- Amirgholy, Mahyar & Gonzales, Eric J., 2017. "Efficient frontier of route choice for modeling the equilibrium under travel time variability with heterogeneous traveler preferences," Economics of Transportation, Elsevier, vol. 11, pages 1-14.
- Zhang, Yuli & Shen, Zuo-Jun Max & Song, Shiji, 2016. "Parametric search for the bi-attribute concave shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 150-168.
- Xu, Xiangdong & Chen, Anthony & Cheng, Lin & Yang, Chao, 2017. "A link-based mean-excess traffic equilibrium model under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 53-75.
- Teppei Kato & Kenetsu Uchida & William H. K. Lam & Agachai Sumalee, 2021. "Estimation of the value of travel time and of travel time reliability for heterogeneous drivers in a road network," Transportation, Springer, vol. 48(4), pages 1639-1670, August.
- Maocan Song & Lin Cheng & Huimin Ge & Chao Sun & Ruochen Wang, 2024. "Finding the $$\mathrm{K}$$ K Mean-Standard Deviation Shortest Paths Under Travel Time Uncertainty," Networks and Spatial Economics, Springer, vol. 24(2), pages 395-423, June.
- Xiangfeng Ji & Xuegang (Jeff) Ban & Mengtian Li & Jian Zhang & Bin Ran, 2017. "Non-expected Route Choice Model under Risk on Stochastic Traffic Networks," Networks and Spatial Economics, Springer, vol. 17(3), pages 777-807, September.
- Ehrgott, Matthias & Wang, Judith Y.T. & Watling, David P., 2015. "On multi-objective stochastic user equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 81(P3), pages 704-717.
- Zhang, Yu & Tang, Jiafu, 2018. "Itinerary planning with time budget for risk-averse travelers," European Journal of Operational Research, Elsevier, vol. 267(1), pages 288-303.
More about this item
Keywords
Reliable shortest path; Travel time correlations; Lagrangian substitution(relaxation); Deep-cut ellipsoid; Sub-gradient; Eigen-decomposition;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:121:y:2019:i:c:p:92-113. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.