{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:59:27Z","timestamp":1740182367374,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T00:00:00Z","timestamp":1684108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T00:00:00Z","timestamp":1684108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper. Res. Forum"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We provide a preprocessing method to reduce the vehicle capacity for instances of the capacitated vehicle routing problem. This improves the LP bound of many formulations of the capacitated vehicle routing problem. It also speeds up common algorithms for which the computation time depends on the vehicle capacity. Our simulation experiments suggest that, perhaps surprisingly, often the vehicle capacity is very tight in the sense that it cannot be reduced by much.<\/jats:p>","DOI":"10.1007\/s43069-023-00220-9","type":"journal-article","created":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T14:30:26Z","timestamp":1684161026000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Preprocessing to Reduce Vehicle Capacity for Routing Problems"],"prefix":"10.1007","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3193-823X","authenticated-orcid":false,"given":"Twan","family":"Dollevoet","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4821-2945","authenticated-orcid":false,"given":"Remy","family":"Spliet","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,15]]},"reference":[{"key":"220_CR1","doi-asserted-by":"crossref","unstructured":"Toth P, Vigo D (2014) Vehicle Routing, Problems, Methods, and Applications. (Society for Industrial and Applied mathematics), 2nd","DOI":"10.1137\/1.9781611973594"},{"issue":"3","key":"220_CR2","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/s10107-005-0644-x","volume":"106","author":"R Fukasawa","year":"2006","unstructured":"Fukasawa R, Longo H, Lysgaard J, Poggi de Arag\u00e3o M, Reis M, Uchoa E, Werneck R (2006) Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem. Math Program 106(3):491\u2013511","journal-title":"Math Program"},{"issue":"1","key":"220_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s12532-016-0108-8","volume":"9","author":"D Pecin","year":"2017","unstructured":"Pecin D, Pessoa A, Poggi M, Uchoa E (2017) Improved branch-cut-and-price for capacitated vehicle routing. Math Program Comput 9(1):61\u2013101","journal-title":"Math Program Comput"},{"key":"220_CR4","doi-asserted-by":"crossref","unstructured":"Karp R (1972) Reducibility among combinatorial problems. Complexity of Computer Computations (Springer, Boston) 85\u2013103","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"220_CR5","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1287\/opre.21.1.332","volume":"2","author":"B Faaland","year":"1973","unstructured":"Faaland B (1973) Solution of the Value-Independent Knapsack Problem by Partitioning. Oper Res 2(1):332\u2013337","journal-title":"Oper Res"},{"key":"220_CR6","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0304-0208(08)73235-3","volume":"132","author":"G Laporte","year":"1987","unstructured":"Laporte G, Nobert Y (1987) Exact algorithms for the vehicle routing problem. North-Holland Mathematics Studies 132:147\u2013184","journal-title":"North-Holland Mathematics Studies"},{"key":"220_CR7","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.disopt.2017.02.003","volume":"25","author":"I Diarrassouba","year":"2017","unstructured":"Diarrassouba I (2017) On the complexity of the separation problem of rounded capacity inequalities. Discret Optim 25:86\u2013104","journal-title":"Discret Optim"},{"issue":"2","key":"220_CR8","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/s10107-003-0481-8","volume":"100","author":"J Lysgaard","year":"2004","unstructured":"Lysgaard J, Letchford A, Eglese R (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math Program 100(2):423\u2013445","journal-title":"Math Program"},{"issue":"3","key":"220_CR9","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1016\/j.ejor.2015.02.028","volume":"244","author":"A Letchford","year":"2015","unstructured":"Letchford A, Salazar-Gonz\u00e1lez J (2015) Stronger multi-commodity flow formulations of the Capacitated Vehicle Routing Problem. Eur J Oper Res 244(3):730\u2013738","journal-title":"Eur J Oper Res"},{"key":"220_CR10","unstructured":"Dollevoet T, Munari P, Spliet, R (2020) A p-step formulation of the capacitated vehicle routing problem. Econometric Institute Report Series EI-2020-01, Erasmus University Rotterdam"},{"issue":"5","key":"220_CR11","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1287\/opre.1110.0975","volume":"59","author":"R Baldacci","year":"2011","unstructured":"Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper Res 59(5):1269\u20131283","journal-title":"Oper Res"},{"key":"220_CR12","unstructured":"Augerat P (1995) Approche poly\u00e8drale du probl\u00e8me de tourn\u00e9es de v\u00e9hicules. PhD thesis Institut Nationale Polytechnique de Grenoble"},{"issue":"3","key":"220_CR13","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1057\/jors.1969.75","volume":"20","author":"N Christofides","year":"1969","unstructured":"Christofides N, Eilon S (1969) An Algorithm for the Vehicle Dispatching Problem. Journal of the Operational Research Society 20(3):309\u2013318","journal-title":"Journal of the Operational Research Society"},{"key":"220_CR14","unstructured":"Christofides N, Mingozzi A, Toth, P (1979) The vehicle routing problem. Combinatorial Optimization, Wiley, Chichester:315\u2013338"},{"issue":"4","key":"220_CR15","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1287\/opre.42.4.626","volume":"42","author":"M Fischer","year":"1994","unstructured":"Fischer M (1994) Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees. Oper Res 42(4):626\u2013642","journal-title":"Oper Res"},{"issue":"1","key":"220_CR16","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF02430370","volume":"1","author":"Y Rochat","year":"1995","unstructured":"Rochat Y, Taillard E (1995) Probabilistic diversification and intensification in local search for vehicle routing. J Heuristics 1(1):147\u2013167","journal-title":"J Heuristics"},{"issue":"3","key":"220_CR17","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1016\/j.ejor.2016.08.012","volume":"257","author":"E Uchoa","year":"2017","unstructured":"Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A (2017) New benchmark instances for the Capacitated Vehicle Routing Problem. Eur J Oper Res 257(3):845\u2013858","journal-title":"Eur J Oper Res"},{"key":"220_CR18","unstructured":"CVRPLIB vrp.atd-lab.inf.puc-rio.br. Accessed April 2022"},{"key":"220_CR19","volume-title":"Knapsacak Problems","author":"H Kellerer","year":"2003","unstructured":"Kellerer H, Pferschy U, Pisinger D (2003) Knapsacak Problems. Springer-Verlag, Berlin Heidelberg"}],"container-title":["Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-023-00220-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-023-00220-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-023-00220-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,3]],"date-time":"2023-07-03T12:06:03Z","timestamp":1688385963000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-023-00220-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,15]]},"references-count":19,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,6]]}},"alternative-id":["220"],"URL":"https:\/\/doi.org\/10.1007\/s43069-023-00220-9","relation":{},"ISSN":["2662-2556"],"issn-type":[{"type":"electronic","value":"2662-2556"}],"subject":[],"published":{"date-parts":[[2023,5,15]]},"assertion":[{"value":"20 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2023","order":3,"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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"42"}}