{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T16:54:26Z","timestamp":1779296066583,"version":"3.51.4"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,11,1]],"date-time":"2009-11-01T00:00:00Z","timestamp":1257033600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2010,3]]},"DOI":"10.1007\/s10479-009-0650-0","type":"journal-article","created":{"date-parts":[[2009,10,31]],"date-time":"2009-10-31T07:57:20Z","timestamp":1256975840000},"page":"213-245","source":"Crossref","is-referenced-by-count":117,"title":["Exact algorithms for routing problems under vehicle capacity constraints"],"prefix":"10.1007","volume":"175","author":[{"given":"Roberto","family":"Baldacci","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Toth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniele","family":"Vigo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,11,1]]},"reference":[{"key":"650_CR1","volume-title":"The traveling salesman problem: A computational study","author":"D. L. Applegate","year":"2006","unstructured":"Applegate, D. L., Bixby, R. E., Chv\u00e1tal, V., & Cook, W. J. (2006). The traveling salesman problem: A computational study. Princeton: Princeton University Press."},{"key":"650_CR2","unstructured":"Araque, J. R., Hall, L., & Magnanti, T. (1990). Capacitated trees, capacitated routing and associated polyhedra (Technical Report Discussion Paper 9061). CORE, Louvain La Nueve."},{"key":"650_CR3","unstructured":"Augerat, P. (1995). Approche poly\u00e8drale du probl\u00e8me de tourn\u00e9es de v\u00e9hicules. PhD thesis, Institut National Polytechnique de Grenoble."},{"key":"650_CR4","unstructured":"Augerat, P., Belenguer, J. M., Benavent, E., Corber\u00e1n, A., Naddef, D., & Rinaldi, G. (1995). Computational results with a branch and cut code for the capacitated vehicle routing problem (Technical Report 1 RR949-M). ARTEMIS-IMAG, Grenoble, France."},{"key":"650_CR5","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1016\/S0377-2217(97)00290-7","volume":"106","author":"P. Augerat","year":"1998","unstructured":"Augerat, P., Belenguer, J. M., Benavent, E., Corber\u00e1n, A., & Naddef, D. (1998). Separating capacity constraints in the CVRP using tabu search. European Journal of Operational Research, 106, 546\u2013557.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"650_CR6","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s10107-008-0218-9","volume":"120","author":"R. Baldacci","year":"2009","unstructured":"Baldacci, R., & Mingozzi, A. (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, 120(2), 347\u2013380.","journal-title":"Mathematical Programming"},{"issue":"5","key":"650_CR7","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1287\/opre.1040.0111","volume":"52","author":"R. Baldacci","year":"2004","unstructured":"Baldacci, R., Hadjiconstantinou, E., & Mingozzi, A. (2004). An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Operations Research, 52(5), 723\u2013738.","journal-title":"Operations Research"},{"issue":"9","key":"650_CR8","doi-asserted-by":"crossref","first-page":"2667","DOI":"10.1016\/j.cor.2005.02.023","volume":"33","author":"R. Baldacci","year":"2006","unstructured":"Baldacci, R., Bodin, L., & Mingozzi, A. (2006). The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem. Computers and Operations Research, 33(9), 2667\u20132702.","journal-title":"Computers and Operations Research"},{"issue":"4","key":"650_CR9","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s10288-007-0063-3","volume":"5","author":"R. Baldacci","year":"2007","unstructured":"Baldacci, R., Toth, P., & Vigo, D. (2007). Recent advances in vehicle routing exact algorithms. 4OR: A\u00a0Quarterly Journal of Operations Research, 5(4), 269\u2013298.","journal-title":"4OR: A\u00a0Quarterly Journal of Operations Research"},{"key":"650_CR10","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-0-387-77778-8_1","volume-title":"The vehicle routing problem: latest advances and new challenges","author":"R. Baldacci","year":"2008","unstructured":"Baldacci, R., Battarra, M., & Vigo, D. (2008a). Routing a heterogeneous fleet of vehicles. In B. L. Golden, S. Raghavan, & E. Wasil (Eds.), The vehicle routing problem: latest advances and new challenges (Vol.\u00a043, pp.\u00a03\u201327). Berlin: Springer."},{"issue":"2","key":"650_CR11","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/s10107-007-0178-5","volume":"115","author":"R. Baldacci","year":"2008","unstructured":"Baldacci, R., Christofides, N., & Mingozzi, A. (2008b). An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming Ser. A, 115(2), 351\u2013385.","journal-title":"Mathematical Programming Ser. A"},{"key":"650_CR12","doi-asserted-by":"crossref","unstructured":"Baldacci, R., Battarra, M., & Vigo, D. (2009, to appear). Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs. Networks. DOI: 10.1002\/net.20331","DOI":"10.1002\/net.20331"},{"key":"650_CR13","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1287\/opre.12.2.300","volume":"12","author":"M. Balinski","year":"1964","unstructured":"Balinski, M., & Quandt, R. (1964). On an integer program for a delivery problem. Operations Research, 12, 300\u2013304.","journal-title":"Operations Research"},{"key":"650_CR14","series-title":"SIAM monographs on discrete mathematics and applications","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1137\/1.9780898718515.ch4","volume-title":"The vehicle routing problem","author":"J. Bramel","year":"2002","unstructured":"Bramel, J., & Simchi-Levi, D. (2002). Set-covering-based algorithms for the capacitated VRP. In P. Toth & D. Vigo (Eds.), SIAM monographs on discrete mathematics and applications : Vol. 9. The vehicle routing problem (pp. 85\u2013108). Philadelphia: SIAM."},{"key":"650_CR15","doi-asserted-by":"crossref","first-page":"2080","DOI":"10.1016\/j.cor.2005.08.002","volume":"34","author":"E. Choi","year":"2007","unstructured":"Choi, E., & Tcha, D. W. (2007). A column generation approach to the heterogeneous fleet vehicle routing problem. Computers and Operations Research, 34, 2080\u20132095.","journal-title":"Computers and Operations Research"},{"key":"650_CR16","doi-asserted-by":"crossref","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. Operational Research Quarterly, 20, 309\u2013318.","journal-title":"Operational Research Quarterly"},{"key":"650_CR17","first-page":"315","volume-title":"Combinatorial optimization","author":"N. Christofides","year":"1979","unstructured":"Christofides, N., Mingozzi, A., & Toth, P. (1979). The vehicle routing problem. In N.\u00a0Christofides, A.\u00a0Mingozzi, P.\u00a0Toth, & C. Sandi (Eds.), Combinatorial optimization (pp.\u00a0315\u2013338). New York: Wiley. Chap.\u00a011."},{"key":"650_CR18","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01589353","volume":"10","author":"N. Christofides","year":"1981","unstructured":"Christofides, N., Mingozzi, A., & Toth, P. (1981). Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxation. Mathematical Programming, 10, 255\u2013280.","journal-title":"Mathematical Programming"},{"key":"650_CR19","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01580109","volume":"5","author":"V. Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V. (1973). Edmonds polytopes and weakly Hamiltonian graphs. Mathematical Programming, 5, 29\u201340.","journal-title":"Mathematical Programming"},{"key":"650_CR20","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1002\/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G","volume":"30","author":"J. F. Cordeau","year":"1997","unstructured":"Cordeau, J. F., Gendreau, M., & Laporte, G. (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30, 105\u2013119.","journal-title":"Networks"},{"key":"650_CR21","first-page":"367","volume-title":"Transportation, handbooks in operations research and management science","author":"J. F. Cordeau","year":"2007","unstructured":"Cordeau, J. F., Laporte, G., Savelsbergh, M. W. P., & Vigo, D. (2007). Vehicle routing. In C. Barnhart & G. Laporte (Eds.), Transportation, handbooks in operations research and management science (Vol.\u00a014, pp.\u00a0367\u2013428). Amsterdam: North-Holland."},{"key":"650_CR22","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF01580599","volume":"60","author":"G. Cornu\u00e9jols","year":"1993","unstructured":"Cornu\u00e9jols, G., & Harche, F. (1993). Polyhedral study of the capacitated vehicle routing. Mathematical Programming, 60, 21\u201352.","journal-title":"Mathematical Programming"},{"key":"650_CR23","unstructured":"CPLEX. (2006). ILOG CPLEX 9.0 callable library. ILOG."},{"issue":"1","key":"650_CR24","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"G. B. Dantzig","year":"1959","unstructured":"Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80\u201391.","journal-title":"Management Science"},{"key":"650_CR25","first-page":"167","volume":"41","author":"G. Finke","year":"1984","unstructured":"Finke, G., Claus, A., & Gunn, E. (1984). A two-commodity network flow approach to the traveling salesman problem. Congressus Numerantium, 41, 167\u2013178.","journal-title":"Congressus Numerantium"},{"issue":"2","key":"650_CR26","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1287\/opre.37.2.319","volume":"37","author":"M. Fischetti","year":"1989","unstructured":"Fischetti, M., & Toth, P. (1989). An additive bounding procedure for combinatorial optimization problems. Operational Research, 37(2), 319\u2013328.","journal-title":"Operational Research"},{"key":"650_CR27","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1287\/opre.42.5.846","volume":"42","author":"M. Fischetti","year":"1994","unstructured":"Fischetti, M., Toth, P., & Vigo, D. (1994). A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs. Operational Research, 42, 846\u2013859.","journal-title":"Operational Research"},{"key":"650_CR28","unstructured":"Fischetti, M., Salazar Gonz\u00e1lez, J. J., & Toth, P. (1995). Experiments with a multi-commodity formulation for the symmetric capacitated vehicle routing problem. In 3rd meeting of the EURO working group on transportation Barcelona (pp.\u00a0169\u2013173)."},{"key":"650_CR29","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1287\/opre.42.4.626","volume":"42","author":"M. L. Fisher","year":"1994","unstructured":"Fisher, M. L. (1994). Optimal solution of vehicle routing problems using minimum K-trees. Operational Research, 42, 626\u2013642.","journal-title":"Operational Research"},{"key":"650_CR30","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/s10107-005-0644-x","volume":"106","author":"R. Fukasawa","year":"2006","unstructured":"Fukasawa, R., Longo, H., Lysgaard, J., de\u00a0Arag\u00e3o, M.P., Reis, M., Uchoa, E., & Werneck, R.F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming (A), 106, 491\u2013511.","journal-title":"Mathematical Programming (A)"},{"key":"650_CR31","volume-title":"Computers and intractability; A guide to the theory of NP-completeness","author":"M. R. Garey","year":"1990","unstructured":"Garey, M. R., & Johnson, D. S. (1990). Computers and intractability; A guide to the theory of NP-completeness. New York: Freeman."},{"key":"650_CR32","series-title":"SIAM monographs on discrete mathematics and applications","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1137\/1.9780898718515.ch6","volume-title":"The vehicle routing problem","author":"M. Gendreau","year":"2002","unstructured":"Gendreau, M., Laporte, G., & Potvin, J.-Y. (2002). Metaheuristics for the capacitated VRP. In P. Toth & D.\u00a0Vigo (Eds.), SIAM monographs on discrete mathematics and applications : Vol. 9. The vehicle routing problem (pp.\u00a0129\u2013154). Philadelphia: SIAM."},{"key":"650_CR33","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1002\/net.3230070203","volume":"7","author":"B. L. Golden","year":"1977","unstructured":"Golden, B. L., Magnanti, T. L., & Nguyen, H. Q. (1977). Implementing vehicle routing algorithms. Networks, 7, 113\u2013148.","journal-title":"Networks"},{"key":"650_CR34","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1016\/0377-2217(94)00025-8","volume":"85","author":"L. Gouveia","year":"1995","unstructured":"Gouveia, L. (1995). A result on projection for the vehicle routing problem. European Journal of Operational Research, 85, 610\u2013624.","journal-title":"European Journal of Operational Research"},{"key":"650_CR35","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01582116","volume":"16","author":"M. Gr\u00f6tschel","year":"1979","unstructured":"Gr\u00f6tschel, M., & Padberg, M.\u00a0W. (1979). On the symmetric traveling salesman problem: I and II. Mathematical Programming, 16, 265\u2013280.","journal-title":"Mathematical Programming"},{"key":"650_CR36","first-page":"231","volume-title":"The traveling salesman problem: A guided tour of combinatorial optimization","author":"M. Gr\u00f6tschel","year":"1985","unstructured":"Gr\u00f6tschel, M., & Padberg, M.\u00a0W. (1985). Polyhedral theory. In E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, & D. B. Shmoys (Eds.), The traveling salesman problem: A guided tour of combinatorial optimization (pp.\u00a0231\u2013305). Chichester: Wiley."},{"key":"650_CR37","first-page":"271","volume":"51","author":"G. Laporte","year":"1984","unstructured":"Laporte, G., & Nobert, Y. (1984). Comb inequalities for the vehicle routing problem. Methods of Operations Research, 51, 271\u2013276.","journal-title":"Methods of Operations Research"},{"key":"650_CR38","first-page":"147","volume":"31","author":"G. Laporte","year":"1987","unstructured":"Laporte, G., & Nobert, Y. (1987). Exact algorithms for the vehicle routing problem. Annals of Discrete Mathematics, 31, 147\u2013184.","journal-title":"Annals of Discrete Mathematics"},{"key":"650_CR39","series-title":"SIAM monographs on discrete mathematics and applications","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1137\/1.9780898718515.ch5","volume-title":"The vehicle routing problem","author":"G. Laporte","year":"2002","unstructured":"Laporte, G., & Semet, F. (2002). Classical heuristics for the capacitated VRP. In P. Toth & D. Vigo (Eds.), SIAM monographs on discrete mathematics and applications : Vol. 9. The vehicle routing problem (pp.\u00a0109\u2013128). Philadelphia: SIAM."},{"key":"650_CR40","first-page":"1058","volume":"33","author":"G. Laporte","year":"1985","unstructured":"Laporte, G., Nobert, Y., & Desrochers, M. (1985). Optimal routing under capacity and distance restrictions. Operational Research, 33, 1058\u20131073.","journal-title":"Operational Research"},{"issue":"2\u20133","key":"650_CR41","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s10107-005-0652-x","volume":"105","author":"A. N. Letchford","year":"2006","unstructured":"Letchford, A. N., & Salazar Gonz\u00e1lez J. J. (2006). Projection results for vehicle routing. Mathematical Programming, 105(2\u20133), 251\u2013274.","journal-title":"Mathematical Programming"},{"key":"650_CR42","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10107-002-0336-8","volume":"94","author":"A. N. Letchford","year":"2002","unstructured":"Letchford, A. N., Eglese, R. W., & Lysgaard, J. (2002). Multistars, partial multistars and the capacitated vehicle routing problem. Mathematical Programming, 94, 21\u201340.","journal-title":"Mathematical Programming"},{"key":"650_CR43","unstructured":"Lysgaard, J. (2003). CVRPSEP: A package of separation routines for the capacitated vehicle routing problem (Technical Report). Dept. of Mgt. Science and Logistics, Aarhus School of Business."},{"issue":"2","key":"650_CR44","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/s10107-003-0481-8","volume":"100","author":"J. Lysgaard","year":"2004","unstructured":"Lysgaard, J., Letchford, A. N., & Eglese, R. W. (2004). A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 100(2), 423\u2013445.","journal-title":"Mathematical Programming"},{"key":"650_CR45","series-title":"SIAM monographs on discrete mathematics and applications","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1137\/1.9780898718515.ch3","volume-title":"The vehicle routing problem","author":"D. Naddef","year":"2002","unstructured":"Naddef, D., & Rinaldi, G. (2002). Branch-and-cut algorithms for the capacitated VRP. In P. Toth & D.\u00a0Vigo (Eds.), SIAM monographs on discrete mathematics and applications : Vol. 9. The vehicle routing problem (pp.\u00a053\u201381). Philadelphia: SIAM."},{"key":"650_CR46","unstructured":"Niskanen, S., & \u00d6sterg\u00e5rd, P. R. J. (2003). Cliquer user\u2019s guide (Technical Report 48). Helsinki University of Technology Communications Laboratory."},{"issue":"1\u20133","key":"650_CR47","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/S0166-218X(01)00290-6","volume":"120","author":"P. R. J. \u00d6sterg\u00e5rd","year":"2002","unstructured":"\u00d6sterg\u00e5rd, P. R. J. (2002). A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120(1\u20133), 197\u2013207.","journal-title":"Discrete Applied Mathematics"},{"key":"650_CR48","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/978-0-387-77778-8_14","volume-title":"The vehicle routing problem: Latest advances and new challenges","author":"A. Pessoa","year":"2008","unstructured":"Pessoa, A., de Arag\u00e3o, M. P., & Uchoa, E. (2008). Robust branch-cut-and-price algorithms for vehicle routing problems. In B. L. Golden, S. Raghavan, & E. Wasil (Eds.), The vehicle routing problem: Latest advances and new challenges (Vol.\u00a043, pp. 297\u2013325). Berlin: Springer."},{"key":"650_CR49","doi-asserted-by":"crossref","unstructured":"Pessoa, A., & Uchoa, E. de\u00a0Arag\u00e3o, M.P. (2009, to appear). A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem. Networks. DOI: 10.1002\/net.20330","DOI":"10.1002\/net.20330"},{"key":"650_CR50","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s10107-002-0323-0","volume":"94","author":"T. K. Ralphs","year":"2003","unstructured":"Ralphs, T. K., Kopman, L., Pulleyblank, W. R., & Trotter, L. E. (2003). On the capacitated vehicle routing problem. Mathematical Programming (B), 94, 343\u2013359.","journal-title":"Mathematical Programming (B)"},{"key":"650_CR51","series-title":"The vehicle routing problem","volume-title":"SIAM monographs on discrete mathematics and applications","author":"P. Toth","year":"2002","unstructured":"Toth, P., & Vigo, D. (2002). SIAM monographs on discrete mathematics and applications: Vol.\u00a09. The vehicle routing problem. Philadelphia: SIAM."},{"key":"650_CR52","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s10107-005-0611-6","volume":"106","author":"H. D. Yaman","year":"2006","unstructured":"Yaman, H. D. (2006). Formulations and valid inequalities for the heterogeneous vehicle routing problem. Mathematical Programming Ser. A, 106, 365\u2013390.","journal-title":"Mathematical Programming Ser. A"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-009-0650-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-009-0650-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-009-0650-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T18:07:57Z","timestamp":1559153277000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-009-0650-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11,1]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["650"],"URL":"https:\/\/doi.org\/10.1007\/s10479-009-0650-0","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,11,1]]}}}