{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T13:09:33Z","timestamp":1770815373048,"version":"3.50.1"},"reference-count":26,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transportation Science"],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:p>We introduce a p-step formulation for the capacitated vehicle routing problem (CVRP). The parameter p indicates the length of partial paths corresponding to the used variables. This provides a family of formulations including both the traditional arc-based and path-based formulations. Hence, it is a generalization that unifies arc-based and path-based formulations while also providing new formulations. We show that the LP bound of the p-step formulation has an increasing trend but does not increase monotonically. In particular, the LP bound increases when multiplying p by an integer, whereas an increase, decrease, or no change may be observed otherwise. Furthermore, we prove that computing the set partitioning bound is NP-hard, enabling us in combination with the p-step formulation to show that there does not exist a strongest compact formulation for the CVRP, if [Formula: see text]. While ending the search for a strongest compact formulation, we propose the search for the strongest formulation of the CVRP with a number of variables and constraints limited by a polynomial of fixed degree. We provide new strongest such formulations of degree three and higher by using a corresponding p-step formulation. Furthermore, the results of our experiments suggest that there are computational advantages from using the p-step formulation instead of traditional arc-based and path-based formulations.<\/jats:p>\n                  <jats:p>Supplemental Material: The online appendices are available at https:\/\/doi.org\/10.1287\/trsc.2024.0936 .<\/jats:p>","DOI":"10.1287\/trsc.2024.0936","type":"journal-article","created":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T17:22:43Z","timestamp":1765214563000},"page":"87-100","source":"Crossref","is-referenced-by-count":0,"title":["A\n                    <i>p<\/i>\n                    -Step Formulation for the Capacitated Vehicle Routing Problem"],"prefix":"10.1287","volume":"60","author":[{"given":"Twan","family":"Dollevoet","sequence":"first","affiliation":[{"name":"Erasmus School of Economics, Econometric Institute,  Erasmus University Rotterdam, 3000 DR Rotterdam, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5929-593X","authenticated-orcid":false,"given":"Pedro","family":"Munari","sequence":"additional","affiliation":[{"name":"Production Engineering Department, Federal University of S\u00e3o Carlos, S\u00e3o Carlos 13565-905, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4821-2945","authenticated-orcid":false,"given":"Remy","family":"Spliet","sequence":"additional","affiliation":[{"name":"Erasmus School of Economics, Econometric Institute,  Erasmus University Rotterdam, 3000 DR Rotterdam, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2019.0905"},{"key":"B2","unstructured":"Augerat P (1995) Approche poly\u00e8drale du probl\u00e8me de tourn\u00e9es de v\u00e9hicules. PhD thesis, Institut Nationale Polytechnique de Grenoble, Grenoble, France."},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1040.0111"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.0975"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1969.75"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2018.0878"},{"key":"B7","doi-asserted-by":"crossref","unstructured":"Desaulniers G, Desrosiers J, Solomon MM (2006)\n                      Column Generation\n                      , vol. 5 (Springer Science & Business Media, Boston).","DOI":"10.1007\/b135457"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90083-2"},{"key":"B9","unstructured":"Dollevoet TAB, Munari P, Spliet R (2020) A p-step formulation for the capacitated vehicle routing problem. Accessed November 17, 2025, https:\/\/repub.eur.nl\/pub\/123411\/EI-2020-01.pdf."},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1002\/net.20033"},{"key":"B11","unstructured":"Gavish B (1984) The delivery problem: New cutting plane procedures.\n                      Proc. TIMS XXVI Conf\n                      .\n                      (Copenhagen, Denmark)\n                      ."},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2007.05.001"},{"key":"B13","unstructured":"Jepsen M, Petersen B (2009) Partial path column generation for the vehicle routing problem\n                      Internat. Network Optim. Conf. (INOC) (Pisa, Italy)\n                      , 1\u20136."},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73235-3"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2017.05.039"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.02.028"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0481-8"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.05.005"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-016-0108-8"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.05.007"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1002\/net.20212"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2021.1044"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105649"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2023.2481"},{"key":"B26","doi-asserted-by":"crossref","unstructured":"Toth P, Vigo D (2014)\n                      Vehicle Routing, Problems, Methods, and Applications\n                      , 2nd ed. (Society for Industrial and Applied Mathematics, Philadelphia).","DOI":"10.1137\/1.9781611973594"}],"container-title":["Transportation Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/trsc.2024.0936","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T09:58:56Z","timestamp":1770803936000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/trsc.2024.0936"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["10.1287\/trsc.2024.0936"],"URL":"https:\/\/doi.org\/10.1287\/trsc.2024.0936","relation":{},"ISSN":["0041-1655","1526-5447"],"issn-type":[{"value":"0041-1655","type":"print"},{"value":"1526-5447","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1]]}}}