Abstract
In this variant of the constrained shortest path problem, the time of traversing an arc is given by a non-negative continuous random variable. The problem is to find a minimum cost path from an origin to a destination, ensuring that the probability of reaching the destination within a time limit meets a certain reliability threshold. To solve this problem, we extend the pulse algorithm, a solution framework for shortest path problems with side constraints. To allow arbitrary non-negative continuous travel-time distributions, we model the random variables of the travel times using Phase-type distributions and Monte Carlo simulation. We conducted a set of experiments over small- and medium-size stochastic transportation networks with and without spatially-correlated travel times. As an alternative to handling correlations, we present a scenario-based approach in which the distributions of the arc travel times are conditioned to a given scenario (e.g., variable weather conditions). Our methodology and experiments highlight the relevance of considering on-time arrival probabilities and correlations when solving shortest path problems over stochastic transportation networks.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, Englewood Cliffs
Asmussen S, Nerman O, Olsson M (1996) Fitting Phase-Type Distributions via the EM Algorithm. Scand J Stat 23(4):419–441
Bobbio A, Horváth A, Telek M (2005) Matching three moments with minimal acyclic phase type distributions. Stoch Models 21(2–3):303–326. https://doi.org/10.1081/stm-200056210
Bolívar MA, Lozano L, Medaglia AL (2014) Acceleration strategies for the weight constrained shortest path problem with replenishment. Optim Lett 8(8):2155–2172. https://doi.org/10.1007/s11590-014-0742-x
Cabrera N, Medaglia AL, Lozano L, Duque D (2020) An exact bidirectional pulse algorithm for the constrained shortest path. Networks 76(2):128–146
Cario MC, Nelson BL (1997) Modeling and generating random vectors with arbitrary marginal distributions and correlation matrix. Technical report
Chen A, Ji Z (2005) Path finding under uncertainty. J Adv Transp 39(1):19–37. https://doi.org/10.1002/atr.5670390104
Chen BY, Lam WHK, Sumalee A, Li Zl YuB, Lam WHK, Sumalee A, ZlL Reliable (2012) Reliable shortest path finding in stochastic networks with spatial correlated link travel times. Int J Geogr Inf Sci 26(2):365–386. https://doi.org/10.1080/13658816.2011.598133
Chen PW, Nie YM (2015) Stochastic optimal path problem with relays. Transp Res Procedia 7:129–148. https://doi.org/10.1016/j.trpro.2015.06.008
Dijkstra E (1959) A note on two problems in connexion with graphs. Numer Math 1:269–271. https://doi.org/10.1007/BF01386390
Dumitrescu I, Boland N (2003) Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem. Networks 42(3):135–153. https://doi.org/10.1002/net.10090
Duque D, Medaglia AL (2019) An exact method for a class of robust shortest path problems with scenarios. Networks 74(4):360–373. https://doi.org/10.1002/net.21909
Duque D, Lozano L, Medaglia AL (2014) Solving the orienteering problem with time windows via the pulse framework. Comput Oper Res 54:168–176. https://doi.org/10.1016/j.cor.2014.08.019
Duque D, Lozano L, Medaglia AL (2015) An exact method for the biobjective shortest path problem for large-scale road networks. Eur J Oper Res 242(3):788–797. https://doi.org/10.1016/j.ejor.2014.11.003
Frank H (1969) Shortest paths in probabilistic graphs. Oper Res 17(4):583–599. https://doi.org/10.1287/opre.17.4.583
Gallo G, Pallottino S (1988) Shortest path algorithms. Ann Oper Res 13(1):1–79. https://doi.org/10.1007/BF02288320
van der Geest P (1998) An algorithm to generate samples of multi-variate distributions with correlated marginals. Comput Stat Data Anal 27(3):271–289. https://doi.org/10.1016/S0167-9473(98)00005-X
Gómez A, Mariño R, Akhavan-Tabatabaei R, Medaglia AL, Mendoza JE (2016) On modeling stochastic travel and service times in vehicle routing. Transp Sci 50(2):627–641. https://doi.org/10.1287/trsc.2015.0601
Haas CN (1999) On modeling correlated random variables in risk assessment. Risk Anal 19(6):1205–1214. https://doi.org/10.1023/A:1007047014741
Hall RW (1986) The fastest path through a network with random time-dependent travel times. Transp Sci 20(3):182–188. https://doi.org/10.1287/trsc.20.3.182
Handler GY, Zang I (1980) A dual algorithm for the constrained shortest path problem. Networks 10(4):293–309. https://doi.org/10.1002/net.3230100403
Huang H, Gao S (2012) Optimal paths in dynamic networks with dependent random link travel times. Transp Res Part B Methodol 46(5):579–598
Ji Z, Kim YS, Chen A (2011) Multi-objective \(\alpha\)-reliable path finding in stochastic networks with correlated link costs: a simulation-based multi-objective genetic algorithm approach (SMOGA). Expert Syst Appl 38(3):1515–1528. https://doi.org/10.1016/j.eswa.2010.07.064
Joksch HC (1966) The shortest route problem with constraints. J Math Anal Appl 14(2):191–197. https://doi.org/10.1016/0022-247x(66)90020-5
Latouche G, Ramaswami V (1999) Introduction to matrix analytic methods in stochastic modeling. Soc Ind Appl Math. doi 10(1137/1):9780898719734
Li J, Han X (2019) Revised pulse algorithm for elementary shortest path problem with resource constraints. In: 2019 seventh international symposium on computing and networking (CANDAR), pp 37–44. https://doi.org/10.1109/CANDAR.2019.00013
Li ST, Hammond JL (1975) Generation of pseudorandom numbers with specified univariate distributions and correlation coefficients. IEEE Trans Syst Man Cybern SMC 5(5):557–561
Li X, Tian P, Leung SCH (2010) Vehicle routing problems with time windows and stochastic travel and service times: models and algorithm. Int J Prod Econ 125(1):137–145. https://doi.org/10.1016/j.ijpe.2010.01.013
Lozano L, Medaglia AL (2013) On an exact method for the constrained shortest path problem. Comput Oper Res 40(1):378–384. https://doi.org/10.1016/j.cor.2012.07.008
Lozano L, Duque D, Medaglia AL (2016) An exact algorithm for the elementary shortest path problem with resource constraints. Transp Sci 50(1):348–357. https://doi.org/10.1287/trsc.2014.0582
Lurie PM, Goldberg MS (1998) An approximate method for sampling correlated random variables from partially-specified distributions. Manag Sci 44(2):203–218
Miller-Hooks E (2001) Adaptive least-expected time paths in stochastic, time-varying transportation and data networks. Networks 37(1):35–52. 10.1002/1097-0037(200101)37:1<35::AID-NET4>3.0.CO;2-G
Miller-Hooks E, Mahmassani H (2003) Path comparisons for a priori and time-adaptive decisions in stochastic, time-varying networks. Eur J Oper Res 146(1):67–82. https://doi.org/10.1016/S0377-2217(02)00231-X
Miller-Hooks ED, Mahmassani HS (1998) Least possible time paths in stochastic, time-varying networks. Comput Oper Res 25(12):1107–1125. https://doi.org/10.1016/S0305-0548(98)00027-6
Miller-Hooks ED, Mahmassani HS (2000) Least expected time paths in stochastic, time-varying transportation networks. Transp Sci 34(2):198–215. https://doi.org/10.1287/trsc.34.2.198.12304
Mirchandani PB (1976) Shortest distance and reliability of probabilistic networks. Comput Oper Res 3(4):347–355. https://doi.org/10.1016/0305-0548(76)90017-4
Nie YM, Wu X (2009) Shortest path problem considering on-time arrival probability. Transp Res Part B Methodol 43(6):597–613. https://doi.org/10.1016/j.trb.2009.01.008
Perez JF, Silva DF, Goez JC, Sarmiento A, Akhavan Tabatabaei R, Riano G (2017) Algorithm 972: jMarkov: an integrated framework for Markov chain modeling. In: ACM Transactions on Mathematical Software. https://github.com/coin-or/jMarkov. Accessed 1 Mar 2021
Prakash AA (2018) Pruning algorithm for the least expected travel time path on stochastic and time-dependent networks. Transp Res Part B Methodol 108:127–147. https://doi.org/10.1016/j.trb.2017.12.015
Santos L, Coutinho-Rodrigues J, Current JR (2007) An improved solution algorithm for the constrained shortest path problem. Transp Res Part B Methodol 41(7):756–771. https://doi.org/10.1016/j.trb.2006.12.001
Sedeño-Noda A, Alonso-Rodríguez S (2015) An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem. Appl Math Comput 265:602–618. https://doi.org/10.1016/j.amc.2015.05.109
Sen S, Pillai R, Joshi S, Rathi AK (2001) A mean-variance model for route guidance in advanced traveler information systems. Transp Sci 35(1):37–49. https://doi.org/10.1287/trsc.35.1.37.10141
Shen L, Shao H, Wu T, Lam WH, Zhu EC (2019) An energy-efficient reliable path finding algorithm for stochastic road networks with electric vehicles. Transp Res Part C Emerg Technol 102(March):450–473. https://doi.org/10.1016/j.trc.2019.03.020
Sigal CE, Pritsker AAB, Solberg JJ (1980) The stochastic shortest route problem. Oper Res 28(5):1122–1129. https://doi.org/10.1287/opre.28.5.1122
Sivakumar RA, Batta R (1994) The variance-constrained shortest path problem. Transp Sci 28(4):309–316. https://doi.org/10.1287/trsc.28.4.309
Stabler B (2016) Transportation networks for research. In: GitHub repository. https://github.com/bstabler/TransportationNetworks. Accessed 1 Mar 2021
Thomas BW, Calogiuri T, Hewitt M (2019) An exact bidirectional A\(^*\) approach for solving resource-constrained shortest path problems. Networks 73(2):187–205. https://doi.org/10.1002/net.21856
Thummler A, Buchholz P, Telek M (2006) A novel approach for phase-type fitting with the EM algorithm. IEEE Trans Depend Secure Comput 3(3):245–258. https://doi.org/10.1109/tdsc.2006.27
Wang L, Yang L, Gao Z (2016) The constrained shortest path problem with stochastic correlated link travel times. Eur J Oper Res 255(1):43–57. https://doi.org/10.1016/j.ejor.2016.05.040
Xing T, Zhou X (2011) Finding the most reliable path with and without link travel time correlation: a Lagrangian substitution based approach. Transp Res Part B Methodol 45(10):1660–1679. https://doi.org/10.1016/j.trb.2011.06.004
Yang L, Yang X, You C (2013) Stochastic scenario-based time-stage optimization model for the least expected time shortest path problem. Int J Uncertainty Fuzziness Knowl Based Syst 21(SUPPL.1):17–33
Zang Z, Xu X, Yang C, Chen A (2018) A distribution-fitting-free approach to calculating travel time reliability ratio. Transp Res Part C Emerg Technol 89:83–95. https://doi.org/10.1016/j.trc.2018.01.027
Zeng W, Miwa T, Wakita Y, Morikawa T (2015) Application of Lagrangian relaxation approach to \(\alpha\)-reliable path finding in stochastic networks with correlated link travel times. Transp Res Part C Emerg Technol 56:309–334. https://doi.org/10.1016/j.trc.2015.04.018
Zhang Y (2019) An algorithm for reliable shortest path problem with travel time correlations. Ph.D. thesis. https://doi.org/10.1037//0033-2909.I26.1.78
Acknowledgements
First and foremost, we would like to thank the editors-in-chief Antonio Alonso-Ayuso and Dolores Romero-Morales and the guest editors Laureano F. Escudero and Nelson Maculan for the invitation to submit to this very special issue dedicated to the Ibero-American operational research community. Special thanks go to Hector Cancela who invited A. Medaglia to teach a course on the pulse framework at Universidad de la República (Uruguay). The active exchange of ideas with students were enlightening and certainly improved parts of this paper. The authors would like to thank the anonymous reviewer who provided insightful ideas to induce correlations via the scenario-based approach. Finally, we would like to thank the partial funding provided by the Office of Research at Universidad de los Andes.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix
Rights and permissions
About this article
Cite this article
Corredor-Montenegro, D., Cabrera, N., Akhavan-Tabatabaei, R. et al. On the shortest \(\alpha\)-reliable path problem. TOP 29, 287–318 (2021). https://doi.org/10.1007/s11750-021-00592-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-021-00592-3
Keywords
- Constrained shortest path problem
- Pulse algorithm
- Stochastic shortest path
- Phase-type distributions
- Spatial correlation
- Chance constraints