{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T02:51:58Z","timestamp":1787021518883,"version":"build-2736575974"},"reference-count":31,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transportation Science"],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:p>This paper considers the vehicle routing problem with stochastic demands under optimal restocking. We develop an exact algorithm that is effective for solving instances with many vehicles and few customers per route. In our experiments, we show that in these instances, solving the stochastic problem is most relevant (i.e., the potential gains over the deterministic equivalent solution are highest). The proposed branch-price-and-cut algorithm relies on an efficient labeling procedure, exact and heuristic dominance rules, and completion bounds to price profitable columns. Instances with up to 76 nodes could be solved in less than five hours, and instances with up to 148 nodes could be solved in long runs of the algorithm. The experiments also allowed new findings on the problem. The solution to the stochastic problem is up to 10% less costly than the deterministic equivalent solution. Opening new routes reduces restocking costs and in many cases results in solutions with less transportation costs. When the number of routes is not fixed, the optimal solutions under detour-to-depot and optimal restocking are nearly equivalent. However, when the number of routes is limited and the expected demand along a route is allowed to exceed the vehicle capacity, optimal restocking may be significantly more cost-effective than the detour-to-depot policy.<\/jats:p>","DOI":"10.1287\/trsc.2020.0976","type":"journal-article","created":{"date-parts":[[2020,6,16]],"date-time":"2020-06-16T12:25:27Z","timestamp":1592310327000},"page":"1073-1090","source":"Crossref","is-referenced-by-count":45,"title":["New Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands"],"prefix":"10.1287","volume":"54","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-7593-919X","authenticated-orcid":false,"given":"Alexandre M.","family":"Florio","sequence":"first","affiliation":[{"name":"Department of Business Decisions and Analytics, University of Vienna, 1010 Vienna, Austria;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-0461-0979","authenticated-orcid":false,"given":"Richard F.","family":"Hartl","sequence":"additional","affiliation":[{"name":"Department of Business Decisions and Analytics, University of Vienna, 1010 Vienna, Austria;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0001-6127-8223","authenticated-orcid":false,"given":"Stefan","family":"Minner","sequence":"additional","affiliation":[{"name":"School of Management, Technical University of Munich, 80333 Munich, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.0975"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.46.3.316"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2006.12.009"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2018.0878"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/b135457"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1002\/net.20471"},{"key":"B7","doi-asserted-by":"crossref","unstructured":"Desaulniers G, Madsen O, Ropke S (2014) The vehicle routing problem with time windows. Toth P, Vigo D, eds.\n                      Vehicle Routing: Problems, Methods, and Applications\n                      , 2nd ed., MOS-SIAM Series on Optimization (Society for Industrial and Applied Mathematics, Philadelphia), 119\u2013159.","DOI":"10.1137\/1.9781611973594.ch5"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01415995"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.23.3.166"},{"key":"B10","doi-asserted-by":"crossref","unstructured":"Florio AM, Hartl RF, Minner S (2018) Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands.\n                      Eur. J. Oper. Res.\n                      ePub ahead of print October 31, https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.ejor.2018.10.045.","DOI":"10.1016\/j.ejor.2018.10.045"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0644-x"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2014.03.028"},{"key":"B13","doi-asserted-by":"crossref","unstructured":"Gendreau M, Jabali O, Rei W (2014) Stochastic vehicle routing problems. Toth P, Vigo D, eds.\n                      Vehicle Routing: Problems, Methods, and Applications\n                      , 2nd ed., MOS-SIAM Series on Optimization (Society for Industrial and Applied Mathematics, Philadelphia), 213\u2013239.","DOI":"10.1137\/1.9781611973594.ch8"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2016.0709"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.29.2.143"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-25486-2_2"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.05.040"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1070.0449"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(93)90002-X"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(89)90354-8"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1287\/opre.50.3.415.7751"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2017.0780"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1050.0234"},{"key":"B24","unstructured":"Lysgaard J (2004) CVRPSEP: A package of separation routines for the capacitated vehicle routing problem. Technical report, University of Aarhus, Aarhus, Denmark."},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973594.ch3"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.07.039"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.3.3.192"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973594"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.08.012"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.34.1.99.12278"},{"issue":"1","key":"B31","first-page":"159","volume":"27","author":"Yee JR","year":"1980","journal-title":"Logist. Quart."}],"container-title":["Transportation Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/pubsonline.informs.org\/doi\/pdf\/10.1287\/trsc.2020.0976","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T08:17:06Z","timestamp":1680423426000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/pubsonline.informs.org\/doi\/10.1287\/trsc.2020.0976"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["10.1287\/trsc.2020.0976"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1287\/trsc.2020.0976","relation":{},"ISSN":["0041-1655","1526-5447"],"issn-type":[{"value":"0041-1655","type":"print"},{"value":"1526-5447","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7]]}}}