{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T13:08:11Z","timestamp":1776776891938,"version":"3.51.2"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2005,11,14]],"date-time":"2005-11-14T00:00:00Z","timestamp":1131926400000},"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,2]]},"DOI":"10.1007\/s10107-005-0662-8","type":"journal-article","created":{"date-parts":[[2005,11,14]],"date-time":"2005-11-14T15:26:37Z","timestamp":1131981997000},"page":"471-499","source":"Crossref","is-referenced-by-count":96,"title":["A new ILP-based refinement heuristic for Vehicle Routing Problems"],"prefix":"10.1007","volume":"105","author":[{"given":"Roberto De","family":"Franceschi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matteo","family":"Fischetti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Toth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,11,14]]},"reference":[{"key":"662_CR1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0166-218X(01)00338-9","volume":"123","author":"Ahuja","year":"2002","unstructured":"Ahuja, R.K., Ergun, O., Orlin, J.B., Punnen, A.B.: A survey of very large-scale neighborhood search techniques. Discrete Applied Math. 123, 75\u2013102 (2002)","journal-title":"Discrete Applied Math."},{"key":"662_CR2","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1287\/ijoc.13.1.56.9748","volume":"13","author":"Balas","year":"2001","unstructured":"Balas, E., Simonetti, N.: Linear time dynamic programming algorithms for new classes of Restricted TSPs. Informs J. Comput. 13, 56\u201375 (2001)","journal-title":"Informs J. Comput."},{"key":"662_CR3","doi-asserted-by":"crossref","unstructured":"Baldacci, R., Hadjiconstantinou, E.A., Mingozzi, A.: An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 2004 (forthcoming)","DOI":"10.1287\/opre.1040.0111"},{"key":"662_CR4","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF02253612","volume":"54","author":"Burkard","year":"1995","unstructured":"Burkard, R.E., Deineko, V.G.: Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood. Comput. 54, 191\u2013211 (1995)","journal-title":"Comput."},{"key":"662_CR5","doi-asserted-by":"crossref","unstructured":"Cordeau, J.-F., Gendreau, M., Hertz, A., Laporte, G., Sormany, J.-S.: New heuristics for the vehicle routing problem. In: A. Langevin, D. Riopel (eds.). Logistics Systems: Design and Optimization, Kluwer, Boston, 2005 forthcoming","DOI":"10.1007\/0-387-24977-X_9"},{"key":"662_CR6","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1057\/jors.1969.101","volume":"20","author":"Christofides","year":"4","unstructured":"Christofides, N., Eilon, S.: Expected distances in distribution problems. Oper. Res. Quarterly 20 (4), 437\u2013443 (1969)","journal-title":"Oper. Res. Quarterly"},{"key":"662_CR7","unstructured":"Christofides, N., Mingozzi, A., Toth, P.: The vehicle routing problem. Combinatorial Optimization (Wiley, Chichester), 1979"},{"key":"662_CR8","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1007\/s101070050010","volume":"87","author":"Deineko","year":"2000","unstructured":"Deineko, V.G., Woeginger, G.J.: A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem. Math. Programming 87, 519\u2013542 (2000)","journal-title":"Math. Programming"},{"key":"662_CR9","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1287\/mnsc.39.1.115","volume":"39","author":"Dell'Amico","year":"1993","unstructured":"Dell'Amico, M., Fischetti, M., Toth, P.: Heuristic algorithms for the multiple depot vehicle scheduling problem. Management Sci. 39, 115\u2013125 (1993)","journal-title":"Management Sci."},{"key":"662_CR10","unstructured":"Ergun, O.: New neighborhood search algorithms based on exponentially large neighborhoods. Operations Research Center Thesis, MIT, 2001"},{"key":"662_CR11","doi-asserted-by":"crossref","unstructured":"Ergun, O., Orlin, J.B.: Two dynamic programming methodologies in very large scale neighborhood search applied to the Traveling Salesman Problem. Working Paper 4463-03, MIT Sloan School of Management, 2003","DOI":"10.2139\/ssrn.489784"},{"key":"662_CR12","unstructured":"Ergun, O., Orlin, J.B., Steele-Feldman, A.: A computational study on a large-scale neighborhood search algorithm for the vehicle routing problem with capacity and distance constraints. Working paper, School of Ind. and Sys. Engr. Georgia Institute of Technology, Atlanta, 2002"},{"key":"662_CR13","doi-asserted-by":"crossref","unstructured":"Ergun, O., Orlin, J.B., Steele-Feldman, A.: Creating very large scale neighborhoods out of smaller ones by compounding moves: a study on the Vehicle Routing Problem. Working Paper 4393-02, MIT Sloan School of Management, 2002","DOI":"10.2139\/ssrn.349701"},{"key":"662_CR14","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s001860200198","volume":"56","author":"Firla","year":"2002","unstructured":"Firla, R.T., Spille, B., Weismantel, R.: Exponentialirreducible neighborhoods for combinatorial optimization problems. Math. Meth. Oper. Res. 56, 29\u201344 (2002)","journal-title":"Math. Meth. Oper. Res."},{"key":"662_CR15","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1287\/mnsc.47.6.833.9810","volume":"47","author":"Fischetti","year":"6","unstructured":"Fischetti, M., Lodi, A., Martello, S., Toth, P.: A polyhedral approach to simplified crew scheduling and vehicle scheduling problems. Management Sci. 47 (6), 833\u2013850 (2001)","journal-title":"Management Sci."},{"key":"662_CR16","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1287\/opre.42.5.846","volume":"42","author":"Fischetti","year":"1994","unstructured":"Fischetti, M., Toth, P., Vigo, D.: A branch and bound algorithm for the capacitated vehicle routing problem on directed graphs. Oper. Res. 42, 846\u2013859 (1994)","journal-title":"Oper. Res."},{"key":"662_CR17","doi-asserted-by":"crossref","unstructured":"Fisher, M.: Vehicle routing. In: M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser (eds.). Network Routing, Handbooks in OR & MS Vol. 8, Elsevier, Amsterdam, 1995","DOI":"10.1016\/S0927-0507(05)80105-7"},{"key":"662_CR18","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1002\/net.3230110205","volume":"11","author":"Fisher","year":"1981","unstructured":"Fisher, M.L., Jaikumar, R.: A generalized assignment heuristic for vehicle routing. Networks 11, 109\u2013124 (1981)","journal-title":"Networks"},{"key":"662_CR19","doi-asserted-by":"crossref","unstructured":"Fukasawa, R., Poggi de Arag\u00e3o, M., Reis, M., Uchoa, E: Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Relat\u00f3rios de Pesquisa em Engenharia de Produ\u00e7\u00e3o, RPEP 3 (8), Universidade Federal Fluminense, 2003","DOI":"10.1007\/978-3-540-25960-2_1"},{"key":"662_CR20","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1287\/opre.22.2.340","volume":"22","author":"Gillett","year":"1974","unstructured":"Gillett, B.E., Miller, L.R.: A heuristic algorithm for the vehicle dispatch problem. Oper. Res. 22, 340\u2013349 (1974)","journal-title":"Oper. Res."},{"key":"662_CR21","unstructured":"Gendreau, M., Hertz, A., Laporte, G.: A Tabu Search Heuristic for the VRP, Technical Reoprt CRT-777, 1991"},{"key":"662_CR22","doi-asserted-by":"crossref","first-page":"1276","DOI":"10.1287\/mnsc.40.10.1276","volume":"40","author":"Gendreau","year":"1994","unstructured":"Gendreau, M., Hertz, A., Laporte, G.: A tabu search heuristic for the vehicle routing problem. Management Sci. 40, 1276\u20131290 (1994)","journal-title":"Management Sci."},{"key":"662_CR23","doi-asserted-by":"crossref","unstructured":"Gendreau, M., Laporte, G., Potvin, J.-Y.: Metaheuristics for the capacitated VRP. In: P. Toth, D. Vigo (eds.). The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, 2002","DOI":"10.1137\/1.9780898718515.ch6"},{"key":"662_CR24","doi-asserted-by":"crossref","unstructured":"Golden, B.L., Wasil, E.A., Kelly, J.P., Chao, I-M.: Metaheuristics in Vehicle Routing. In: T.G. Crainic, G. Laporte (eds.). Fleet Management and Logictics. Kluwer, Boston, 1998 pp. 33\u201356","DOI":"10.1007\/978-1-4615-5755-5_2"},{"key":"662_CR25","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1057\/palgrave.jors.2600392","volume":"48","author":"Glover","year":"1997","unstructured":"Glover, F., Punnen, A.P.: The traveling salesman problem: New solvable cases and linkages with the development of approximation algorithms. J. Oper. Res. Soc. 48, 502\u2013510 (1997)","journal-title":"J. Oper. Res. Soc."},{"key":"662_CR26","unstructured":"Gutin, G.M.: On an approach to solving the traveling salesman problem, Proc. The USSR Conference on System Research (Moscow, USSR), 1984 pp. 184\u2013185 (in Russian)"},{"key":"662_CR27","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0305-0548(98)00064-1","volume":"26","author":"Gutin","year":"1999","unstructured":"Gutin, G.M.: Exponential neighborhood local search for the traveling salesman problem. Comput. Oper. Res. 26, 313\u2013320 (1999)","journal-title":"Comput. Oper. Res."},{"key":"662_CR28","unstructured":"Gutin, G., Yeo, A., Zverovitch, A.: Exponential neighborhoods and domination analysis for the TSP. In: G. Gutin, A. Punnen (eds.). The Traveling Salesman Problem and its Variations. Kluwer, 2002 pp. 223\u2013256"},{"key":"662_CR29","unstructured":"ILOG Cplex 8.1: user's manual and reference manual, ILOG, S.A., http:\/\/www.ilog.com\/, 2003"},{"key":"662_CR30","unstructured":"ILOG Concert Technology 1.2: User's manual and reference manual, ILOG, S.A., http:\/\/www.ilog.com\/, 2003"},{"key":"662_CR31","unstructured":"Johnson, D.S., McGeoch, L.A.: Experimental analysis of heuristics for the STSP. In: G. Gutin, A.P. Punnen (eds.). The Traveling Salesman Problem and Its Variations Kluwer Academic Publishers, 9, pp. 369\u2013487, 2002"},{"key":"662_CR32","doi-asserted-by":"crossref","unstructured":"Laporte, G., Semet, F.: Classical heuristics for the capacitated VRP. In: P. Toth, D. Vigo (eds.). The Vehicle Routing Problem SIAM Monographs on Discrete Mathematics and Applications, Chap. 5, 2002","DOI":"10.1137\/1.9780898718515.ch5"},{"key":"662_CR33","doi-asserted-by":"crossref","unstructured":"Li, F., Golden, B.L., Wasil, E.A.: Very large-scale vehicle routing: New test problems, algorithms, and results. Comput. Oper. Res. 2004 (forthcoming)","DOI":"10.1016\/j.cor.2003.10.002"},{"key":"662_CR34","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.N., Eglese, R.W.: A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Prog. 100 (2), 423\u2013442 2004","journal-title":"Math. Prog."},{"key":"662_CR35","doi-asserted-by":"crossref","unstructured":"Mester, D., Braysy, O.: Active guided evolution strategies for the large scale vehicle routing problems with time windows. Comput. Oper. Res. 2004 (forthcoming)","DOI":"10.1016\/j.cor.2003.11.017"},{"key":"662_CR36","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1080\/02522667.2001.10699482","volume":"22","author":"Punnen","year":"2001","unstructured":"Punnen, A.P.: The Traveling Salesman Problem: new polynomial approximation and domination analysis. J. Information Optim. Sci. 22, 191\u2013206 (2001)","journal-title":"J. Information Optim. Sci."},{"key":"662_CR37","unstructured":"Ralphs, T.: Branch and Cut and Price Applications: Vehicle Routing, http:\/\/branchandcut.org\/VRP\/"},{"key":"662_CR38","unstructured":"Rego, C., Glover, F.: Local search and metaheuristcs. In: G. Gutin, A. Punnen (eds.). The Traveling Salesman Problem and its Variations, Kluwer, 2002 pp. 309\u2013368"},{"key":"662_CR39","doi-asserted-by":"crossref","unstructured":"Reimann, M., Doerner, K., Hartl, R.F.: D-Ants: Savings based ants divide and conquer the vehicle routing problem. Comput. Oper. Res. 2004 (forthcoming)","DOI":"10.1016\/S0305-0548(03)00014-5"},{"key":"662_CR40","unstructured":"Sarvanov, V.I., Doroshko, N.N.: The approximate solution of the travelling salesman problem by a local algorithm with scanning neighborhoods of factorial cardinality in cubic time, (in Russian), Software: Algorithms and Programs 31, Mathematical Institute of the Belorussian Academy of Sciences, Minsk, 1981, pp. 11\u201313"},{"key":"662_CR41","unstructured":"Taillard, E.: Eric Taillard's Page, Vehicle Routing Instances, http:\/\/ina.eivd.ch\/collaborateurs\/etd\/problemes.dir\/vrp.dir\/vrp.html."},{"key":"662_CR42","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1023\/A:1021157406318","volume":"115","author":"Tarantilis","year":"2002","unstructured":"Tarantilis, C.-D., Kiranoudis, C.T.: Bone Route: An adaptive memory-based method for effective fleet management. Ann. Oper. Res. 115, 227\u2013241 (2002)","journal-title":"Ann. Oper. Res."},{"key":"662_CR43","doi-asserted-by":"crossref","unstructured":"Toth, P., Vigo, D.: An overview of vehicle routing problems. In: P. Toth, D. Vigo (eds.). The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, 2002","DOI":"10.1137\/1.9780898718515.ch1"},{"key":"662_CR44","unstructured":"Vigo, D.: VRPLIB: A Vehicle Routing Problem LIBrary, http:\/\/www.or.deis.unibo.it\/research_pages\/OR instances\/VRPLIB\/VRPLIB. html"},{"key":"662_CR45","unstructured":"Wenger, K.M.: Generic cut generation methods for routing problems. Ph.D Dissertation, Institute of Computer Science, University of Heidelberg, 2003"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0662-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-005-0662-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0662-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T11:16:33Z","timestamp":1683285393000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-005-0662-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,11,14]]},"references-count":45,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2006,2]]}},"alternative-id":["662"],"URL":"https:\/\/doi.org\/10.1007\/s10107-005-0662-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,11,14]]}}}