{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T05:02:44Z","timestamp":1781931764813,"version":"3.54.5"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2005,10,12]],"date-time":"2005-10-12T00:00:00Z","timestamp":1129075200000},"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":[[2006,5]]},"DOI":"10.1007\/s10107-005-0644-x","type":"journal-article","created":{"date-parts":[[2005,10,12]],"date-time":"2005-10-12T15:10:17Z","timestamp":1129129817000},"page":"491-511","source":"Crossref","is-referenced-by-count":374,"title":["Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem"],"prefix":"10.1007","volume":"106","author":[{"given":"Ricardo","family":"Fukasawa","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Humberto","family":"Longo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Lysgaard","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcus Poggi de","family":"Arag\u00e3o","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcelo","family":"Reis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eduardo","family":"Uchoa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,10,12]]},"reference":[{"key":"644_CR1","first-page":"109","volume":"15","author":"Achuthan","year":"1998","unstructured":"Achuthan, N., Caccetta, L., Hill, S.: Capacited vehicle routing problem: Some new cutting planes. Asia-Pacific J. Oper. Res. 15, 109\u2013123 (1998)","journal-title":"Asia-Pacific J. Oper. Res."},{"key":"644_CR2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1287\/trsc.37.2.153.15243","volume":"37","author":"Achuthan","year":"2003","unstructured":"Achuthan, N., Caccetta, L., Hill, S.: An improved branch-and-cut algorithm for the capacitated vehicle routing problem. Transportation Sci. 37, 153\u2013169 (2003)","journal-title":"Transportation Sci."},{"key":"644_CR3","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1002\/net.3230190702","volume":"19","author":"Agarwal","year":"1989","unstructured":"Agarwal, Y., Mathur, K., Salkin, H.: A set-partitioning based exact algorithm for the vehicle routing problem. Networks 19, 731\u2013739 (1989)","journal-title":"Networks"},{"key":"644_CR4","unstructured":"Araque, J., Hall, L., Magnanti, T.: Capacitated trees, capacitated routing and polyhedra. Technical Report SOR-90-12. Princeton University, 1990"},{"key":"644_CR5","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/BF02085634","volume":"50","author":"Araque","year":"1994","unstructured":"Araque, J., Kudva, G., Morin, T., Pekny, J.: A branch-and-cut algorithm for the vehicle routing problem. Ann. Oper. Res. 50, 37\u201359 (1994)","journal-title":"Ann. Oper. Res."},{"key":"644_CR6","unstructured":"Augerat, P.: Approche poly\u00e8drale du probl\u00e8me de tourn\u00e9es de v\u00e9hicles. PhD thesis, Institut National Polytechnique de Grenoble, 1995"},{"key":"644_CR7","unstructured":"Augerat, P., Belenguer, J., Benavent, E., Corber\u00e1n, A., Naddef, D., Rinaldi, G.: Computational results with a branch and cut code for the capacitated vehicle routing problem. Technical Report 949-M, Universit\u00e9 Joseph Fourier, Grenoble, France, 1995"},{"key":"644_CR8","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1287\/opre.12.2.300","volume":"12","author":"Balinski","year":"1964","unstructured":"Balinski, M., Quandt, R.: On an integer program for a delivery problem. Oper. Res. 12, 300\u2013304 (1964)","journal-title":"Oper. Res."},{"key":"644_CR9","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1287\/opre.48.2.318.12378","volume":"40","author":"Barnhart","year":"2000","unstructured":"Barnhart, C., Hane, C., Vance, P.: Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Oper. Res. 40, 318\u2013326 (2000)","journal-title":"Oper. Res."},{"key":"644_CR10","unstructured":"Blasum, U., Hochst\u00e4ttler, W.: Application of the branch and cut method to the vehicle routing problem. Technical Report ZPR2000-386, Zentrum fur Angewandte Informatik K\u00f6ln, 2000"},{"key":"644_CR11","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1057\/jors.1969.75","volume":"20","author":"Christofides","year":"1969","unstructured":"Christofides, N., Eilon, S.: An algorithm for the vehicle-dispatching problem. Oper. Res. Q. 20, 309\u2013318 (1969)","journal-title":"Oper. Res. Q."},{"key":"644_CR12","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01589353","volume":"20","author":"Christofides","year":"1981","unstructured":"Christofides, N., Mingozzi, A., Toth, P.: Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Math. Prog. 20, 255\u2013282 (1981)","journal-title":"Math. Prog."},{"key":"644_CR13","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF01580599","volume":"60","author":"Cornu\u00e9jols","year":"1993","unstructured":"Cornu\u00e9jols, G., Harche, F.: Polyhedral study of the capacitated vehicle routing problem. Math. Prog. 60, 21\u201352 (1993)","journal-title":"Math. Prog."},{"key":"644_CR14","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"Dantzig","year":"1959","unstructured":"Dantzig, G., Ramser, R.: The truck dispatching problem. Management Science 6, 80\u201391 (1959)","journal-title":"Management Science"},{"key":"644_CR15","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1287\/opre.40.2.342","volume":"40","author":"Desrochers","year":"1992","unstructured":"Desrochers, M., Desrosiers, J., Solomon, M.: A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40, 342\u2013354 (1992)","journal-title":"Oper. Res."},{"key":"644_CR16","unstructured":"Felici, G., Gentile, C., Rinaldi, G.: Solving large MIP models in supply chain management by branch & cut. Technical report, Istituto di Analisi dei Sistemi ed Informatica del CNR, Italy, 2000"},{"key":"644_CR17","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1287\/opre.42.4.626","volume":"42","author":"Fisher","year":"1994","unstructured":"Fisher, M.: Optimal solution of vehicle routing problem using minimum k-trees. Oper. Res. 42, 626\u2013642 (1994)","journal-title":"Oper. Res."},{"key":"644_CR18","unstructured":"Fukasawa, R., Poggi de Arag\u00e3o, M., Porto, O., Uchoa, E.: Robust branch-and-cut-and-price for the capacitated minimum spanning tree problem. In: Proc. of the International Network Optimization Conference. Evry, France, 2003, pp. 231\u2013236"},{"key":"644_CR19","doi-asserted-by":"crossref","unstructured":"Fukasawa, R., Reis, M., Poggi de Arag\u00e3o, M., Uchoa, E.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Technical Report RPEP Vol.3 no.8, Universidade Federal Fluminense, Engenharia de Produ\u00e7\u00e3o, Niter\u00f3i, Brazil, 2003","DOI":"10.1007\/978-3-540-25960-2_1"},{"key":"644_CR20","unstructured":"Hadjiconstantinou, E., Christofides, N., Mingozzi, A.: A new exact algorithm from the vehicle routing problem based on q-paths and k-shortest paths relaxations. In: Laporte, G., Michel Gendreau (eds.), Freight Transportation, 61 in Annals of Operations Research. Baltzer Science Publishers, 1995, pp. 21\u201344"},{"key":"644_CR21","unstructured":"Irnich, S., Villeneuve, D.: The shortest path problem with resource constraints and k-cycle elimination for k \u2265 3, 2003. To appear in JNFORMS Journal on computing. Available at http:\/\/www.dpor.rwth-aachen.de\/de\/publikationen\/pdf\/or_2003-01.pdf ."},{"key":"644_CR22","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1287\/trsc.33.4.391","volume":"33","author":"Kim","year":"1999","unstructured":"Kim, D., Barnhart, C., Ware, K., Reinhardt, G.: Multimodal express package delivery: A service network design application. Transportation Science 33, 391\u2013407 (1999)","journal-title":"Transportation Science"},{"key":"644_CR23","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1287\/trsc.33.1.101","volume":"33","author":"Kohl","year":"1999","unstructured":"Kohl, N., Desrosiers, J., Madsen, O., Solomon, M., Soumis, F.: 2-Path cuts for the vehicle routing problem with time windows. Transportation Science 33, 101\u2013116 (1999)","journal-title":"Transportation Science"},{"key":"644_CR24","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF01720015","volume":"5","author":"Laporte","year":"1983","unstructured":"Laporte, G., Norbert, Y.: A branch and bound algorithm for the capacitated vehicle routing problem. Oper. Res. Spektrum 5, 77\u201385 (1983)","journal-title":"Oper. Res. Spektrum"},{"key":"644_CR25","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10107-002-0336-8","volume":"94","author":"Letchford","year":"2002","unstructured":"Letchford, A., Eglese, R., Lysgaard, J.: Multistars, partial multistars and the capacitated vehicle routing problem. Math. Prog. 94, 21\u201340 (2002)","journal-title":"Math. Prog."},{"key":"644_CR26","doi-asserted-by":"crossref","unstructured":"Letchford, A., Reinelt, G., Theis, D.: A faster exact separation algorithm for blossom inequalities. In: Proceedings of the X IPCO, volume 3064 of Lecture Notes in Computer Science. New York, 2004, pp. 196\u2013205","DOI":"10.1007\/978-3-540-25960-2_15"},{"key":"644_CR27","unstructured":"Letchford, A.N., Salazar, J.J.: Projection results for vehicle routing. Math. Prog. 2004, To appear"},{"key":"644_CR28","unstructured":"Longo, H., Poggi de Arag\u00e3o, M., Uchoa, E.: Solving capacitated arc routing problems using a transformation to the CVRP. Computers & Operations Research, 2004, To appear"},{"key":"644_CR29","unstructured":"Lysgaard, J.: CVRPSEP: A package of separation routines for the capacitated vehicle routing problem, 2003. Available at http:\/\/www.asb.dk\/~lys"},{"key":"644_CR30","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/s10107-003-0481-8","volume":"100","author":"Lysgaard","year":"2","unstructured":"Lysgaard, J., Letchford, A., Eglese, R.: A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Prog. 100 (2), 423\u2013445 (2004)","journal-title":"Math. Prog."},{"key":"644_CR31","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/S0377-2217(03)00353-9","volume":"158","author":"Martinhon","year":"1","unstructured":"Martinhon, C., Lucena, A., Maculan, N.: Stronger k-tree relaxations for the vehicle routing problem. European J. Oper. Res. 158 (1), 56\u201371 (2004)","journal-title":"European J. Oper. Res."},{"key":"644_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/ijoc.7.1.1","volume":"7","author":"Miller","year":"1995","unstructured":"Miller, D.: A matching based exact algorithm for capacitated vehicle routing problems. ORSA J. Comput. 7, 1\u20139 (1995)","journal-title":"ORSA J. Comput."},{"key":"644_CR33","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, chapter 3. SIAM, 2002, pp. 53\u201384","DOI":"10.1137\/1.9780898718515.ch3"},{"key":"644_CR34","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"Padberg","year":"1","unstructured":"Padberg, M., Rao, M.: Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7 (1), 67\u201380 (1982)","journal-title":"Math. Oper. Res."},{"key":"644_CR35","unstructured":"Pigatti, A.: Modelos e algoritmos para o problema de aloca\u00e7\u00e3o generalizada e aplica\u00e7\u00f5es. Master's thesis, Pontif\u00ed cia Universidade Cat\u00f3lica do Rio de Janeiro, Brazil, July 2003"},{"key":"644_CR36","unstructured":"Poggi de Arag\u00e3o, M., Uchoa, E.: Integer program reformulation for robust branch-and-cut-and-price. In: Annals of Mathematical Programming in Rio. B\u00fazios, Brazil, 2003, pp. 56\u201361"},{"key":"644_CR37","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/S0167-8191(03)00045-0","volume":"29","author":"Ralphs","year":"2003","unstructured":"Ralphs, T.: Parallel branch and cut for capacitated vehicle routing. Parallel Computing 29, 607\u2013629 (2003)","journal-title":"Parallel Computing"},{"key":"644_CR38","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s10107-002-0323-0","volume":"94","author":"Ralphs","year":"2003","unstructured":"Ralphs, T., Kopman, L., Pulleyblank, W., Trotter, L. Jr.: On the capacitated vehicle routing problem. Math. Prog. 94, 343\u2013359 (2003)","journal-title":"Math. Prog."},{"key":"644_CR39","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1016\/S0166-218X(01)00351-1","volume":"123","author":"Toth","year":"2002","unstructured":"Toth, P., Vigo, D.: Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics 123, 487\u2013512 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"644_CR40","doi-asserted-by":"crossref","unstructured":"Toth, P., Vigo, D.:The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. SIAM, 2002","DOI":"10.1137\/1.9780898718515"},{"key":"644_CR41","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1287\/ijoc.12.2.111.11896","volume":"12","author":"Akker","year":"2000","unstructured":"Van den Akker, J., Hurkens, C., Savelsbergh, M.: Time-indexed formulation for machine scheduling problems: column generation. INFORMS J. on Computing 12, 111\u2013124 (2000)","journal-title":"INFORMS J. on Computing"},{"key":"644_CR42","doi-asserted-by":"crossref","first-page":"1409","DOI":"10.1287\/mnsc.44.10.1409","volume":"44","author":"Vanderbeck","year":"1998","unstructured":"Vanderbeck, F.: Lot-sizing with start-up times. Management Science 44, 1409\u20131425 (1998)","journal-title":"Management Science"},{"key":"644_CR43","unstructured":"Wenger, K.M.: Generic Cut Generation Methods for Routing Problems. PhD thesis, Institute of Computer Science, University of Heidelberg, 2003"},{"key":"644_CR44","doi-asserted-by":"crossref","unstructured":"Werneck, R.F., Setubal, J.C.: Finding minimum congestion spanning trees. ACM J. of Experimental Algorithmics, 5, 2000","DOI":"10.1145\/351827.384253"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0644-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-005-0644-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0644-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T02:15:58Z","timestamp":1683252958000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-005-0644-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10,12]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,5]]}},"alternative-id":["644"],"URL":"https:\/\/doi.org\/10.1007\/s10107-005-0644-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10,12]]}}}