{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T14:55:48Z","timestamp":1776696948248,"version":"3.51.2"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,8,1]],"date-time":"2007-08-01T00:00:00Z","timestamp":1185926400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1007\/s10107-007-0178-5","type":"journal-article","created":{"date-parts":[[2007,7,31]],"date-time":"2007-07-31T13:53:51Z","timestamp":1185890031000},"page":"351-385","source":"Crossref","is-referenced-by-count":249,"title":["An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts"],"prefix":"10.1007","volume":"115","author":[{"given":"Roberto","family":"Baldacci","sequence":"first","affiliation":[]},{"given":"Nicos","family":"Christofides","sequence":"additional","affiliation":[]},{"given":"Aristide","family":"Mingozzi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,8,1]]},"reference":[{"key":"178_CR1","unstructured":"Augerat, P.: Approche poly\u00e9drale du probl\u00e8me de tourn\u00e9es de v\u00e9hicules. Ph.D. thesis, Institut National Polytechnique de Grenoble (1995)"},{"key":"178_CR2","unstructured":"Augerat, P., Belenguer, J.M., Benavent, E., Corber\u00e1n, A., Naddef, D., Rinaldi, G.: Computational results with a branch and cut code for the capacitated vehicle routing problem. Tech. Rep. 1 RR949-M, ARTEMIS-IMAG, Grenoble France (1995)"},{"key":"178_CR3","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1137\/1018115","volume":"18","author":"E. Balas","year":"1976","unstructured":"Balas E. and Padberg M.W. (1976). Set partitioning: a survey. SIAM Rev. 18: 710\u2013760","journal-title":"SIAM Rev."},{"key":"178_CR4","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.D. and Mingozzi A. (2006). The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem. Comput. Oper. Res. 33: 2667\u20132702","journal-title":"Comput. Oper. Res."},{"key":"178_CR5","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/S0305-0548(00)00072-1","volume":"29","author":"R. Baldacci","year":"2002","unstructured":"Baldacci R., Hadjiconstantinou E.A., Maniezzo V. and Mingozzi A. (2002). A new method for solving capacitated location problems based on a set partitioning approach. Comput. Oper. Res. 29: 365\u2013386","journal-title":"Comput. Oper. Res."},{"key":"178_CR6","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.A. and Mingozzi A. (2004). An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52: 723\u2013738","journal-title":"Oper. Res."},{"key":"178_CR7","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1287\/opre.12.2.300","volume":"12","author":"M. Balinski","year":"1964","unstructured":"Balinski M. and Quandt R. (1964). On an integer program for a delivery problem. Oper. Res. 12: 300\u2013304","journal-title":"Oper. Res."},{"key":"178_CR8","volume-title":"Network Routing, Handbooks in Operations Research and Management, vol. 8","year":"1995","unstructured":"(1995). Network Routing, Handbooks in Operations Research and Management, vol. 8. Elsevier, Amsterdam"},{"key":"178_CR9","volume-title":"Transportation, Handbooks in Operations Research and Management Science, vol. 14","year":"2007","unstructured":"(2007). Transportation, Handbooks in Operations Research and Management Science, vol. 14. North-Holland, Amsterdam"},{"key":"178_CR10","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1080\/10556789408805563","volume":"3","author":"L. Bianco","year":"1994","unstructured":"Bianco L., Mingozzi A. and Ricciardelli S. (1994). A set partitioning approach to the multiple depot vehicle scheduling problem. Optim. Methods Softw. 3: 163\u2013194","journal-title":"Optim. Methods Softw."},{"key":"178_CR11","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/0-306-48058-1_12","volume-title":"Handbook of Transportation Science, vol. 2","author":"L.D. Bodin","year":"2003","unstructured":"Bodin L.D., Mingozzi A. and Maniezzo V. (2003). Street routing and scheduling problems. In: Hall, R. (eds) Handbook of Transportation Science, vol. 2, pp 413\u2013438. Kluwer, Boston"},{"key":"178_CR12","doi-asserted-by":"crossref","unstructured":"Bramel, J., Simchi-Levi, D.: Set-covering-based algorithms for the capacitated VRP. In: Toth, P., Vigo D. (eds.) The Vehicle Routing Problem, vol. 9, pp. 85\u2013108 SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, (2002)","DOI":"10.1137\/1.9780898718515.ch4"},{"key":"178_CR13","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1057\/jors.1969.75","volume":"20","author":"N. Christofides","year":"1969","unstructured":"Christofides N. and Eilon S. (1969). An algorithm for the vehicle dispatching problem. Oper. Res. Q. 20: 309\u2013318","journal-title":"Oper. Res. Q."},{"key":"178_CR14","first-page":"315","volume-title":"Combinatorial Optimization.","author":"N. Christofides","year":"1979","unstructured":"Christofides N., Mingozzi A. and Toth P. (1979). The vehicle routing problem. In: Christofides, N., Mingozzi, A., Toth, P., and Sandi, C. (eds) Combinatorial Optimization., pp 315\u2013338. Wiley, Chichester"},{"key":"178_CR15","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01589353","volume":"10","author":"N. Christofides","year":"1981","unstructured":"Christofides N., Mingozzi A. and Toth P. (1981). Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxation. Math. Program. 10: 255\u2013280","journal-title":"Math. Program."},{"key":"178_CR16","first-page":"367","volume-title":"Transportation, Handbooks in Operations Research and Management Science, vol. 14","author":"J.-F. Cordeau","year":"2007","unstructured":"Cordeau J.-F., Laporte G., Savelsbergh M.W.P. and Vigo D. (2007). Vehicle routing. In: Barnhart, C. and Laporte, G. (eds) Transportation, Handbooks in Operations Research and Management Science, vol. 14, pp 367\u2013428. North-Holland, Amsterdam"},{"key":"178_CR17","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF01580599","volume":"60","author":"G. Cornu\u00e9jols","year":"1993","unstructured":"Cornu\u00e9jols G. and Harche F. (1993). Polyhedral study of the capacitated vehicle routing. Math. Program. 60: 21\u201352","journal-title":"Math. Program."},{"key":"178_CR18","unstructured":"CPLEX: ILOG CPLEX 9.0 callable library. ILOG (2004)"},{"key":"178_CR19","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1287\/opre.37.2.319","volume":"37","author":"M. Fischetti","year":"1989","unstructured":"Fischetti M. and Toth P. (1989). An additive bounding procedure for combinatorial optimization problems. Oper. Res. 37: 319\u2013328","journal-title":"Oper. Res."},{"key":"178_CR20","unstructured":"Fisher, M.L.: Vehicle routing. In: Ball, M.O., Magnanti T.L., Monma, C.L., Nemhauser, G.L. Network Routing, Handbooks in Operations Research and Management Science, vol. 8, pp. 1\u2013133. North-Holland, Amsterdam (1995)"},{"key":"178_CR21","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., Poggi de Arag\u00e3o M., Reis M., Uchoa E. and Werneck R.F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program. Ser. A 106: 491\u2013511","journal-title":"Math. Program. Ser. A"},{"key":"178_CR22","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1990","unstructured":"Garey M.R. and Johnson D.S. (1990). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York"},{"key":"178_CR23","doi-asserted-by":"crossref","unstructured":"Gendreau, M., Laporte, G., Potvin, J.-Y.: Metaheuristics for the capacitated VRP. In: Toth, P., Vigo D. (eds.) The Vehicle Routing Problem, vol. 9, pp. 129\u2013154 SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, (2002)","DOI":"10.1137\/1.9780898718515.ch6"},{"key":"178_CR24","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1287\/mnsc.39.6.657","volume":"39","author":"K. Hoffman","year":"1993","unstructured":"Hoffman K. and Padberg M.W. (1993). Solving airline crew scheduling problems by branch and cut. Manage. Sci. 39: 657\u2013682","journal-title":"Manage. Sci."},{"key":"178_CR25","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF01592242","volume":"71","author":"S. Kim","year":"1995","unstructured":"Kim S., Chang K.N. and Lee J.Y. (1995). A descent method with linear programming subproblems for nondifferentiable convex optimization. Math. Program. 71: 17\u201328","journal-title":"Math. Program."},{"key":"178_CR26","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/0377-2217(92)90192-C","volume":"59","author":"G. Laporte","year":"1992","unstructured":"Laporte G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res. 59: 345\u2013358","journal-title":"Eur. J. Oper. Res."},{"key":"178_CR27","doi-asserted-by":"crossref","first-page":"1058","DOI":"10.1287\/opre.33.5.1050","volume":"33","author":"G. Laporte","year":"1985","unstructured":"Laporte G., Nobert Y. and Desrochers M. (1985). Optimal routing under capacity and distance restrictions. Oper. Res. 33: 1058\u20131073","journal-title":"Oper. Res."},{"key":"178_CR28","doi-asserted-by":"crossref","unstructured":"Laporte, G., Semet F.: Classical heuristics for the capacitated VRP. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, vol. 9, pp. 109\u2013128. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia (2002)","DOI":"10.1137\/1.9780898718515.ch5"},{"key":"178_CR29","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. and Lysgaard J. (2002). Multistars, partial multistars and the capacitated vehicle routing problem. Math. Program. Ser. A 94: 21\u201340","journal-title":"Math. Program. Ser. A"},{"key":"178_CR30","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1287\/opre.1050.0234","volume":"53","author":"M.E. L\u00fcbbecke","year":"2005","unstructured":"L\u00fcbbecke M.E. and Desrosiers J. (2005). Selected topics in column generation. Oper. Res. 53: 1007\u20131023","journal-title":"Oper. Res."},{"key":"178_CR31","unstructured":"Lysgaard, J.: CVRPSEP: A package of separation routines for the capacitated vehicle routing problem. Technical report, Department of Management Science and Logistics, Aarhus School of Business (2003)"},{"key":"178_CR32","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. and Eglese R.W. (2004). A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program. Ser. A 100: 423\u2013445","journal-title":"Math. Program. Ser. A"},{"key":"178_CR33","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1287\/opre.23.3.389","volume":"23","author":"R.E. Marsten","year":"1975","unstructured":"Marsten R.E., Hogan W.W. and Blankenship J.W. (1975). The boxstep method for large-scale optimization. Oper. Res. 23: 389\u2013405","journal-title":"Oper. Res."},{"key":"178_CR34","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0012-365X(98)00213-1","volume":"194","author":"O. du Merle","year":"1999","unstructured":"du Merle O., Villeneuve D., Desrosiers J. and Hansen P. (1999). Stabilized column generation. Discrete Math. 194: 229\u2013237","journal-title":"Discrete Math."},{"key":"178_CR35","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1287\/opre.47.6.873","volume":"47","author":"A. Mingozzi","year":"1999","unstructured":"Mingozzi A., Boschetti M.A., Ricciardelli S. and Bianco L. (1999). A set partitioning approach to the crew scheduling problem. Oper. Res. 47: 873\u2013888","journal-title":"Oper. Res."},{"key":"178_CR36","unstructured":"Mingozzi, A., Christofides, N., Hadjiconstantinou, E.A.: An exact algorithm for the vehicle routing problem based on the set partitioning formulation. Tech. rep., University of Bologna (1994)"},{"key":"178_CR37","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1287\/trsc.33.3.315","volume":"33","author":"A. Mingozzi","year":"1999","unstructured":"Mingozzi A., Giorgi S. and Baldacci R. (1999). An exact method for the vehicle routing problem with backhauls. Transp. Sci. 33: 315\u2013329","journal-title":"Transp. Sci."},{"key":"178_CR38","doi-asserted-by":"crossref","unstructured":"Naddef, D., Rinaldi, G.: Branch-and-cut algorithms for the capacitated VRP. In: Toth, P., Vigo D. (eds.) The Vehicle Routing Problem, vol. 9. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, pp. 53\u201381 (2002)","DOI":"10.1137\/1.9780898718515.ch3"},{"key":"178_CR39","unstructured":"Niskanen, S., \u00d6sterg\u00e5rd, P.R.J.: Cliquer user\u2019s guide. Tech. Rep. 48, Helsinki University of Technology Communications Laboratory (2003)"},{"key":"178_CR40","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 Appl. Math. 120: 197\u2013207","journal-title":"Discrete Appl. Math."},{"key":"178_CR41","doi-asserted-by":"crossref","unstructured":"Rousseau, L.-M., Gendreau, M., Feillet, D.: Interior point stabilization for column generation. Oper. Res. Lett. (2006). doi:10.1016\/j.orl.2006.11.004","DOI":"10.1016\/j.orl.2006.11.004"},{"key":"178_CR42","doi-asserted-by":"crossref","unstructured":"Toth, P., Vigo, D.: Branch-and-bound algorithms for the capacitated VRP. In: Toth, P., Vigo D. (eds.) The Vehicle Routing Problem, vol. 9. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, pp. 29\u201351 (2002)","DOI":"10.1137\/1.9780898718515.ch2"},{"key":"178_CR43","doi-asserted-by":"crossref","unstructured":"Toth, P., Vigo, D.: The Vehicle Routing Problem, vol. 9. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia (2002)","DOI":"10.1137\/1.9780898718515"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-007-0178-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-007-0178-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-007-0178-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:50:04Z","timestamp":1559123404000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-007-0178-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8,1]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["178"],"URL":"https:\/\/doi.org\/10.1007\/s10107-007-0178-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8,1]]}}}