{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T06:17:27Z","timestamp":1773901047975,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T00:00:00Z","timestamp":1615507200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T00:00:00Z","timestamp":1615507200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100016378","name":"Technische Universit\u00e4t Dortmund","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100016378","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Most state-of-the-art algorithms for the Vehicle Routing Problem, such as Branch-and-Price algorithms or meta heuristics, rely on a fast feasibility test for a given route. We devise the first approach to approximately check feasibility in the Stochastic Vehicle Routing Problem with time windows, where travel times are correlated and depend on the time of the day. Assuming jointly normally distributed travel times, we use a chance constraint approach to model feasibility, where two different application scenarios are considered, depending on whether missing a customer makes the rest of the route infeasible or not. The former case may arise, e.g., in drayage applications or in the pickup-and-delivery VRP. In addition, we present an adaptive sampling algorithm that is tailored for our setting and is much faster than standard sampling techniques. We use a case study for both scenarios, based on instances with realistic travel times, to illustrate that taking correlations and time dependencies into account significantly improves the quality of the solutions, i.e., the precision of the feasibility decision. In particular, the nonconsideration of correlations often leads to solutions containing infeasible routes.<\/jats:p>","DOI":"10.1007\/s10288-021-00476-z","type":"journal-article","created":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T07:02:44Z","timestamp":1615532564000},"page":"217-239","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the stochastic vehicle routing problem with time windows, correlated travel times, and time dependency"],"prefix":"10.1007","volume":"20","author":[{"given":"Federica","family":"Bomboi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9974-404X","authenticated-orcid":false,"given":"Christoph","family":"Buchheim","sequence":"additional","affiliation":[]},{"given":"Jonas","family":"Pruente","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,12]]},"reference":[{"key":"476_CR1","unstructured":"Bakach I, Campbell AM, Ehmke JF, Urban TL (2018) Modeling Correlation in Vehicle Routing Problems with Makespan Objectives and Stochastic Travel Times, Working Paper 7\/2018, Faculty of Economics and Management, University of Magdeburg"},{"issue":"3","key":"476_CR2","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/0377-2217(92)90323-2","volume":"56","author":"C Bastian","year":"1992","unstructured":"Bastian C, Rinnooy Kan AHG (1992) The stochastic vehicle routing problem revisited. Eur J Op Res 56(3):407\u2013412","journal-title":"Eur J Op Res"},{"issue":"3","key":"476_CR3","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/j.spl.2008.09.006","volume":"79","author":"I Bebu","year":"2009","unstructured":"Bebu I, Mathew T (2009) Confidence intervals for limited moments and truncated moments in normal and lognormal models. Stat Probab Lett 79(3):375\u2013380","journal-title":"Stat Probab Lett"},{"key":"476_CR4","unstructured":"Bomboi F, Pruente J (2018) A new drayage problem with different customer services and container requirements, Technical Report"},{"issue":"2","key":"476_CR5","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1287\/opre.9.2.145","volume":"9","author":"CE Clark","year":"1961","unstructured":"Clark CE (1961) The greatest of a finite set of random variables. Op Res 9(2):145\u2013162","journal-title":"Op Res"},{"issue":"4","key":"476_CR6","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1287\/opre.12.4.568","volume":"12","author":"G Clarke","year":"1964","unstructured":"Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Op Res 12(4):568\u2013581","journal-title":"Op Res"},{"issue":"1","key":"476_CR7","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s10107-017-1151-6","volume":"172","author":"T Dinh","year":"2018","unstructured":"Dinh T, Fukasawa R, Luedtke J (2018) Exact algorithms for the chance-constrained vehicle routing problem. Math Progr 172(1):105\u2013138","journal-title":"Math Progr"},{"issue":"2","key":"476_CR8","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/j.ejor.2014.06.045","volume":"240","author":"JF Ehmke","year":"2015","unstructured":"Ehmke JF, Campbell AM, Urban TL (2015) Ensuring service levels in routing problems with time windows and stochastic travel times. Eur J Op Res 240(2):539\u2013550","journal-title":"Eur J Op Res"},{"issue":"1","key":"476_CR9","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.ejor.2015.07.027","volume":"249","author":"F Errico","year":"2016","unstructured":"Errico F, Desaulniers G, Gendreau M, Rei W, Rousseau LM (2016) A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times. Eur J Op Res 249(1):55\u201366","journal-title":"Eur J Op Res"},{"issue":"1","key":"476_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0377-2217(95)00050-X","volume":"88","author":"M Gendreau","year":"1996","unstructured":"Gendreau M, Laporte G, S\u00e9guin R (1996) Stochastic vehicle routing. Eur J Op Res 88(1):3\u201312","journal-title":"Eur J Op Res"},{"key":"476_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jocs.2019.04.003","volume":"34","author":"R Goel","year":"2019","unstructured":"Goel R, Maini R, Bansal S (2019) Vehicle routing problem with time windows having stochastic customers demands and stochastic service times: Modelling and solution. J Comput Sci 34:1\u201310","journal-title":"J Comput Sci"},{"issue":"2","key":"476_CR12","first-page":"109","volume":"11","author":"BL Golden","year":"1979","unstructured":"Golden BL, Yee JR (1979) A framework for probabilistic vehicle routing. A I I E Trans 11(2):109\u2013112","journal-title":"A I I E Trans"},{"key":"476_CR13","unstructured":"Google Maps. www.maps.google.com"},{"key":"476_CR14","unstructured":"Guo ZG, Mak KL (2004) A heuristic algorithm for the stochastic vehicle routing problems with soft time windows, Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753), 2:1449-1456"},{"issue":"12","key":"476_CR15","doi-asserted-by":"publisher","first-page":"1204","DOI":"10.1016\/j.ifacol.2016.07.673","volume":"49","author":"A Gutierrez","year":"2016","unstructured":"Gutierrez A, Dieulle L, Labadie N, Velasco N (2016) A multi population memetic algorithm for the vehicle routing problem with time windows and stochastic travel and service times. IFAC-PapersOnLine 49(12):1204\u20131209","journal-title":"IFAC-PapersOnLine"},{"issue":"301","key":"476_CR16","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding W (1963) Probability Inequalities for Sums of Bounded Random Variables. J Am Stat Assoc 58(301):13\u201330","journal-title":"J Am Stat Assoc"},{"key":"476_CR17","doi-asserted-by":"crossref","unstructured":"Hou L, Zhou H (2010) Stochastic Vehicle Routing Problem with Uncertain Demand and Travel Time and Simultaneous Pickups and Deliveries, 2010 Third International Joint Conference on Computational Science and Optimization(CSO). 01, 32-35","DOI":"10.1109\/CSO.2010.38"},{"issue":"7","key":"476_CR18","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1016\/0305-0548(93)90064-P","volume":"20","author":"V Lambert","year":"1993","unstructured":"Lambert V, Laporte G, Louveaux F (1993) Designing collection routes through bank branches. Comput Op Res 20(7):783\u2013791","journal-title":"Comput Op Res"},{"issue":"1","key":"476_CR19","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.ijpe.2010.01.013","volume":"125","author":"X Li","year":"2010","unstructured":"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\u2013145","journal-title":"Int J Prod Econ"},{"key":"476_CR20","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.eswa.2016.07.022","volume":"64","author":"DM Miranda","year":"2016","unstructured":"Miranda DM, Conceicao SV (2016) The vehicle routing problem with hard time windows and stochastic travel and service time. Expert Syst Appl 64:104\u2013116","journal-title":"Expert Syst Appl"},{"issue":"2","key":"476_CR21","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1109\/TVLSI.2007.912191","volume":"16","author":"S Nadarajah","year":"2008","unstructured":"Nadarajah S, Kotz S (2008) Exact distribution of the Max\/Min of two Gaussian random variables. IEEE Trans Very Large Scale Integr VLSI Syst 16(2):210\u2013212","journal-title":"IEEE Trans Very Large Scale Integr VLSI Syst"},{"key":"476_CR22","first-page":"118","volume":"2009","author":"OE Nahum","year":"2009","unstructured":"Nahum OE, Hadas Y (2009) Developing a model for the stochastic time-dependent vehicle-routing problem. Int Conf Comput Ind Eng 2009:118\u2013123","journal-title":"Int Conf Comput Ind Eng"},{"key":"476_CR23","unstructured":"Novoa C, Berger R, Linderoth J, Storer R (2006) A set-partitioning-based model for the stochastic vehicle routing problem, technical report 06T-008"},{"issue":"4","key":"476_CR24","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s13676-016-0099-7","volume":"6","author":"J Oyola","year":"2017","unstructured":"Oyola J, Arntzen H, Woodruff DL (2017) The stochastic vehicle routing problem, a literature review part II Solution methods. EURO J Transp Logist 6(4):349\u2013388","journal-title":"EURO J Transp Logist"},{"issue":"3","key":"476_CR25","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s13676-016-0100-5","volume":"7","author":"J Oyola","year":"2018","unstructured":"Oyola J, Arntzen H, Woodruff DL (2018) The stochastic vehicle routing problem, a literature review, part I: models. EURO J Transp Logist 7(3):193\u2013221","journal-title":"EURO J Transp Logist"},{"issue":"5","key":"476_CR26","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1111\/0885-9507.00154","volume":"14","author":"D Park","year":"1999","unstructured":"Park D, Laurence RR (1999) Forecasting Freeway Link Travel Times with a Multilayer Feedforward Neural Network. Computer-Aided Civil and Infrastructure Engineering 14(5):357\u2013367","journal-title":"Computer-Aided Civil and Infrastructure Engineering"},{"key":"476_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/s12351-019-00452-w","author":"M Rajabi-Bahaabadi","year":"2019","unstructured":"Rajabi-Bahaabadi M, Shariat-Mohaymany A, Babaei M, Vigo D (2019) Reliable vehicle routing problem in stochastic networks with correlated travel times. Oper Res Int J. https:\/\/doi.org\/10.1007\/s12351-019-00452-w","journal-title":"Oper Res Int J"},{"issue":"8","key":"476_CR28","doi-asserted-by":"publisher","first-page":"1522","DOI":"10.1109\/TCAD.2007.893544","volume":"26","author":"D Sinha","year":"2007","unstructured":"Sinha D, Zhou H, Shenoy NV (2007) Advances in computation of the maximum of a set of gaussian random variables. IEEE Trans Comput Aided Des Integr Circuits Syst 26(8):1522\u20131533","journal-title":"IEEE Trans Comput Aided Des Integr Circuits Syst"},{"issue":"1","key":"476_CR29","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.cor.2012.06.008","volume":"40","author":"D Tas","year":"2013","unstructured":"Tas D, Dellaert N, Van Woensel T, de Kok T (2013) Vehicle routing problem with stochastic travel times including soft time windows and service costs. Comput Oper Res 40(1):214\u2013224","journal-title":"Comput Oper Res"},{"key":"476_CR30","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.trc.2014.08.007","volume":"48","author":"D Tas","year":"2014","unstructured":"Tas D, Dellaert N, Van Woensel T, de Kok T (2014a) The time-dependent vehicle routing problem with soft time windows and stochastic travel times. Transp Res Part C Emerg Technol 48:66\u201383","journal-title":"Transp Res Part C Emerg Technol"},{"issue":"3","key":"476_CR31","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/j.ejor.2013.05.024","volume":"236","author":"D Tas","year":"2014","unstructured":"Tas D, Gendreau M, Dellaert N, Van Woensel T, de Kok AG (2014b) Vehicle routing with soft time windows and stochastic travel times: a column generation and branch-and-price solution approach. Eur J Oper Res 236(3):789\u2013799","journal-title":"Eur J Oper Res"},{"key":"476_CR32","doi-asserted-by":"crossref","unstructured":"Toth P, Vigo D (2002) The Vehicle Routing Problem, Siam","DOI":"10.1137\/1.9780898718515"},{"issue":"1","key":"476_CR33","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1287\/trsc.2017.0748","volume":"53","author":"D Vareias Anastasios","year":"2019","unstructured":"Vareias Anastasios D, Repoussis Panagiotis P, Tarantilis Christos D (2019) Assessing customer service reliability in route planning with self-imposed time windows and stochastic travel times. Transp Sci 53(1):256\u2013281","journal-title":"Transp Sci"},{"key":"476_CR34","unstructured":"Van\u00a0Woensel T, Kerbache L, Peremans H, Vandaele N (2003) A Vehicle Routing Problem with Stochastic travel times. In: Fourth Aegean international conference on analysis of manufacturing systems location, Samos"},{"issue":"4","key":"476_CR35","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s11067-013-9190-x","volume":"13","author":"J Zhang","year":"2013","unstructured":"Zhang J, Lam WHK, Chen BY (2013) A stochastic vehicle routing problem with travel time uncertainty: trade-off between cost and customer service. Netw Spatial Econ 13(4):471\u2013496","journal-title":"Netw Spatial Econ"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-021-00476-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10288-021-00476-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-021-00476-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,27]],"date-time":"2022-05-27T13:05:47Z","timestamp":1653656747000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10288-021-00476-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,12]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["476"],"URL":"https:\/\/doi.org\/10.1007\/s10288-021-00476-z","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"value":"1619-4500","type":"print"},{"value":"1614-2411","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,12]]},"assertion":[{"value":"11 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 March 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}