{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T02:04:50Z","timestamp":1771466690801,"version":"3.50.1"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319388502","type":"print"},{"value":"9783319388519","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-38851-9_16","type":"book-chapter","created":{"date-parts":[[2016,5,31]],"date-time":"2016-05-31T11:33:54Z","timestamp":1464694434000},"page":"231-245","source":"Crossref","is-referenced-by-count":13,"title":["Tractable Pathfinding for the Stochastic On-Time Arrival Problem"],"prefix":"10.1007","author":[{"given":"Mehrdad","family":"Niknami","sequence":"first","affiliation":[]},{"given":"Samitha","family":"Samaranayake","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,1]]},"reference":[{"issue":"3","key":"16_CR1","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1007\/s10957-005-7498-5","volume":"127","author":"Y Fan","year":"2005","unstructured":"Fan, Y., Robert Kalaba, J.E., Moore, I.I.: Arriving on time. J. Optim. Theor. Appl. 127(3), 497\u2013513 (2005)","journal-title":"J. Optim. Theor. Appl."},{"key":"16_CR2","unstructured":"Flajolet, A., Blandin, S., Jaillet, P.: Robust adaptive routing under uncertainty (2014). arXiv:1408.3374"},{"issue":"1","key":"16_CR3","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.trc.2011.05.009","volume":"20","author":"S Samaranayake","year":"2012","unstructured":"Samaranayake, S., Blandin, S., Bayen, A.: A tractable class of algorithms for reliable routing in stochastic networks. Transp. Res. Part C 20(1), 199\u2013217 (2012)","journal-title":"Transp. Res. Part C"},{"issue":"6","key":"16_CR4","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/j.trb.2009.01.008","volume":"43","author":"YM Nie","year":"2009","unstructured":"Nie, Y.M., Wu, X.: Shortest path problem considering on-time arrival probability. Trans. Res. Part B Methodol. 43(6), 597\u2013613 (2009)","journal-title":"Trans. Res. Part B Methodol."},{"issue":"3\u20134","key":"16_CR5","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/s11067-006-9287-6","volume":"6","author":"Y Fan","year":"2006","unstructured":"Fan, Y., Nie, Y.: Optimal routing for maximizing travel time reliability. Netw. Spat. Econ. 6(3\u20134), 333\u2013344 (2006)","journal-title":"Netw. Spat. Econ."},{"issue":"2","key":"16_CR6","first-page":"96","volume":"5","author":"BC Dean","year":"2010","unstructured":"Dean, B.C.: Speeding up stochastic dynamic programming with zero-delay convolution. Algorithmic Oper. Res. 5(2), 96 (2010)","journal-title":"Algorithmic Oper. Res."},{"key":"16_CR7","unstructured":"Samaranayake, S., Blandin, S., Bayen, A.: Speedup techniques for the stochastic on-time arrival problem. In: ATMOS, pp. 83\u201396 (2012)"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Sabran, G., Samaranayake, S., Bayen, A.: Precomputation techniques for the stochastic on-time arrival problem. In: SIAM, ALENEX, pp. 138\u2013146 (2014)","DOI":"10.1137\/1.9781611973198.13"},{"key":"16_CR9","unstructured":"Gutman, R.: Reach-based routing: a new approach to shortest path algorithms optimized for road networks. In: ALENEX\/ANALC, pp. 100\u2013111 (2004)"},{"key":"16_CR10","first-page":"41","volume":"74","author":"M Hilger","year":"2009","unstructured":"Hilger, M., K\u00f6hler, E., M\u00f6hring, R., Schilling, H.: Fast point-to-point shortest path computations with Arc-Flags. Ninth DIMACS Implementation Challenge 74, 41\u201372 (2009)","journal-title":"Ninth DIMACS Implementation Challenge"},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1007\/11841036_50","volume-title":"Algorithms \u2013 ESA 2006","author":"E Nikolova","year":"2006","unstructured":"Nikolova, E., Kelner, J.A., Brand, M., Mitzenmacher, M.: Stochastic shortest paths via quasi-convex maximization. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 552\u2013563. Springer, Heidelberg (2006)"},{"issue":"32","key":"16_CR12","first-page":"249","volume":"8","author":"S Lim","year":"2013","unstructured":"Lim, S., Sommer, C., Nikolova, E., Rus, D.: Practicalroute planning under delay uncertainty: stochastic shortest path queries. Robot. Sci. Syst. 8(32), 249\u2013256 (2013)","journal-title":"Robot. Sci. Syst."},{"key":"16_CR13","unstructured":"Parmentier, A., Meunier, F.: Stochastic shortest paths and risk measures (2014). arXiv:1408.0272"},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/978-3-642-02094-0_7","volume-title":"Algorithmics of Large and Complex Networks","author":"D Delling","year":"2009","unstructured":"Delling, D., Sanders, P., Schultes, D., Wagner, D.: Engineering route planning algorithms. In: Lerner, J., Wagner, D., Zweig, K.A. (eds.) Algorithmics of Large and Complex Networks. LNCS, vol. 5515, pp. 117\u2013139. Springer, Heidelberg (2009)"},{"key":"16_CR15","unstructured":"Gardner, W.G.: Efficient convolution without input\/output delay. In: Audio engineering society convention 97. Audio Engineering Society (1994)"},{"issue":"3","key":"16_CR16","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1145\/3828.3830","volume":"32","author":"R Dechter","year":"1985","unstructured":"Dechter, R., Pearl, J.: Generalized best-first search strategies and the optimality of $$A^*$$ A \u2217 . J. ACM (JACM) 32(3), 505\u2013536 (1985)","journal-title":"J. ACM (JACM)"},{"key":"16_CR17","volume-title":"Artificial Intelligence: A Modern Approach","author":"SJ Russell","year":"1995","unstructured":"Russell, S.J., Norvig, P.: Artificial Intelligence: A Modern Approach. Prentice-Hall Inc., London (1995). ISBN 0-13-103805-2"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A., Werneck, R.: Highway dimension, shortest paths, and provably efficient algorithms. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 782\u2013793. Society for Industrial and Applied Mathematics (2010)","DOI":"10.1137\/1.9781611973075.64"},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"Goldberg, A., Kaplan, H., Werneck, R.: Reach for $$A^*$$ A \u2217 : efficient point-to-point shortest path algorithms. In: ALENEX, vol. 6, pp. 129\u2013143. SIAM (2006)","DOI":"10.1137\/1.9781611972863.13"},{"key":"16_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/978-3-540-68552-4_24","volume-title":"Experimental Algorithms","author":"R Geisberger","year":"2008","unstructured":"Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 319\u2013333. Springer, Heidelberg (2008)"},{"key":"16_CR21","unstructured":"Bast, H., Funke, S., Matijevic, D.: Transit: ultrafast shortest-path queries with linear-time preprocessing. In: 9th DIMACS Implementation Challenge [1] (2006)"},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/978-3-642-20662-7_8","volume-title":"Experimental Algorithms","author":"G D\u2019Angelo","year":"2011","unstructured":"D\u2019Angelo, G., Frigioni, D., Vitale, C.: Dynamic arc-flags in road networks. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 88\u201399. Springer, Heidelberg (2011)"},{"key":"16_CR23","series-title":"Springer Tracts in Advanced Robotics","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/978-3-642-36279-8_36","volume-title":"Algorithmic Foundations of Robotics X","author":"T Hunter","year":"2013","unstructured":"Hunter, T., Abbeel, P., Bayen, A.M.: The path inference filter: model-based low-latency map matching of probe vehicle data. In: Frazzoli, E., Lozano-Perez, T., Roy, N., Rus, D. (eds.) Algorithmic Foundations of Robotics X. STAR, vol. 86, pp. 591\u2013607. Springer, Heidelberg (2013)"},{"key":"16_CR24","unstructured":"Lim, S., Balakrishnan, H., Gifford, D., Madden, S., Rus, D.: Stochastic motion planning and applications to traffic. Int. J. Robot. Res. 3\u201313 (2010)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-38851-9_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,8]],"date-time":"2019-09-08T22:30:48Z","timestamp":1567981848000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-38851-9_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319388502","9783319388519"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-38851-9_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}