Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure

References

• Aggarwal A, Coppersmith D, Khanna S, Motwani R, Schieber B (2000) The angular-metric traveling salesman problem. SIAM J. Comput. 29:697–711.Crossref, Google Scholar
• Amaldi E, Galbiati G, Maffioli F (2011) On minimum reload cost paths, tours, and flows. Networks 57:254–260.Crossref, Google Scholar
• Applegate DL, Bixby RE, Chvátal V, Cook WJ (2007) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• Augerat P (1995) Approche polyhédrale du problème de tournées de véhicules. PhD thesis, Institut National Polytechnique de Grenoble, Grenoble, France.Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59:1269–1283.Link, Google Scholar
• Bard JF, Huang L, Jaillet P, Dror M (1998) A decomposition approach to the inventory routing problem with satellite facilities. Transportation Sci. 32:189–203.Link, Google Scholar
• Bautista J, Fernandez E, Pereira J (2008) Solving an urban waste collection problem using ants heuristics. Comput. Oper. Res. 35:302–309.Crossref, Google Scholar
• Beasley J (1983) Route first—cluster second methods for vehicle routing. Omega 11:403–408.Crossref, Google Scholar
• Belenguer JM, Benavent E, Prins C, Prodhon C, Wolfler-Calvo R (2011) A branch-and-cut algorithm for the capacitated location routing problem. Comput. Oper. Res. 38:931–941.Crossref, Google Scholar
• Blasum U, Hochstättler W (2002) Application of the branch and cut method to the vehicle routing problem. Technical report, Zentrum für Angewandte Informatik Köln, Köln, Germany.Google Scholar
• Bräysy O, Martínez E, Nagata Y, Soler D (2011) The mixed capacitated general routing problem with turn penalties. Expert Systems Appl. 38:12954–12966.Crossref, Google Scholar
• Caprara A, Pisinger D, Toth P (1999) Exact solution of the quadratic knapsack problem. INFORMS J. Comput. 11:125–137.Link, Google Scholar
• Chvátal V (1975) On certain polytopes associated with graphs. J. Combinatorial Theory B 18:138–154.Crossref, Google Scholar
• Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12:568–581.Link, Google Scholar
• Contardo C, Martinelli R (2014) A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12:129–146.Crossref, Google Scholar
• Contardo C, Cordeau JF, Gendron B (2013) A computational comparison of flow formulations for the capacitated location-routing problem. Discrete Optim. 10:263–295.Crossref, Google Scholar
• Contardo C, Cordeau JF, Gendron B (2014a) An exact algorithm based on cut-and-column generation for the capacitated location-routing problem. INFORMS J. Comput. 26:88–102.Link, Google Scholar
• Contardo C, Cordeau JF, Gendron B (2014b) A GRASP + ILP-based metaheuristic for the capacitated location-routing problem. J. Heuristics 20:1–38.Crossref, Google Scholar
• Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6:80–91.Link, Google Scholar
• Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. Oper. Res. 2:393–410.Link, Google Scholar
• Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1:269–271.Crossref, Google Scholar
• Edmonds J (1965) Paths, trees and flowers. Canadian J. Math. 17:449–467.Crossref, Google Scholar
• Fischer A, Helmberg C (2013) The symmetric quadratic traveling salesman problem. Math. Programming 142:205–254.Crossref, Google Scholar
• Fisher ML (1994) Optimal solution of vehicle routing problems using minimum k-trees. Oper. Res. 42:626–642.Link, Google Scholar
• Fomeni FD, Letchford AN (2014) A dynamic programming heuristic for the quadratic knapsack problem. INFORMS J. Comput. 26:173–182.Link, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, Poggi de Aragão M, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming Ser. A 106:491–511.Crossref, Google Scholar
• Galbiati G, Gualandi S, Maffioli F (2014) On minimum reload cost cycle cover. Discrete Appl. Math. 164:112–120.Crossref, Google Scholar
• Gallo G, Hammer PL, Simeone B (1980) Quadratic knapsack problems. Math. Programming Stud. 12:132–149.Crossref, Google Scholar
• Gomory RE, Hu TC (1961) Multi-terminal network flows. J. SIAM 9:551–570.Google Scholar
• Gourvès L, Lyra A, Martinhon C, Monnot J (2010) The minimum reload s-t path, trail and walk problems. Discrete Appl. Math. 158:1404–1417.Crossref, Google Scholar
• Gouveia L (1995) A result on projection for the vehicle routing problem. Eur. J. Oper. Res. 85:610–624.Crossref, Google Scholar
• Grötschel M, Padberg MW (1979) On the symmetric travelling salesman problem I: Inequalities. Math. Programming 16: 265–280.Crossref, Google Scholar
• Jünger M, Thienel S, Reinelt G (1994) Provably good solutions for the traveling salesman problem. Zeitschrift Oper. Res. 40: 183–217.Google Scholar
• Kerivin H, Lacroix M, Mahjoub A, Quilliot A (2006) The capacitated vehicle routing problem with reloads. 2006 Internat. Conf. Service Systems Service Management, Troyes, France, 1513–1518.Crossref, Google Scholar
• Laporte G, Nobert Y (1984) Comb inequalities for the vehicle routing problem. Methods Oper. Res. 51:271–276.Google Scholar
• Laporte G, Nobert Y, Desrochers M (1985) Optimal routing under capacity and distance restrictions. Oper. Res. 33:1050–1073.Link, Google Scholar
• Letchford AN, Reinelt G, Theis D (2004) A faster exact separation algorithm for blossom inequalities. Bienstock D, Nemhauser G, eds. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 3064 (Springer, Berlin), 196–205.Crossref, Google Scholar
• Lysgaard J (2003) CVRPSEP: A package of separation routines for the capacitated vehicle routing problem. Accessed November 3, 2015, http://www.hha.dk/lys/CVRPSEP.htm.Google Scholar
• Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100:423–445.Crossref, Google Scholar
• Padberg M (1989) The Boolean quadric polytope: Some characteristics, facets and relatives. Math. Programming 45:139–172.Crossref, Google Scholar
• Padberg MW, Hong S (1980) On the symmetric travelling salesman problem: A computational study. Math. Programming Study 12:78–107.Crossref, Google Scholar
• Padberg MW, Rinaldi G (1990) Facet identification for the symmetric traveling salesman polytope. Math. Programming 47:219–257.Crossref, Google Scholar
• Perrier N, Langevin A, Amaya C-A (2008) Vehicle routing for urban snow plowing operations. Transportation Sci. 42:44–56.Link, Google Scholar
• Pirkwieser S, Raidl GR (2010) Variable neighborhood search coupled with ILP-based very large-neighborhood searches for the (periodic) location-routing problem. Blesa MJ, Blum C, Raidl G, Roli A, Sampels M, eds. Hybrid Metaheuristics, Lecture Notes in Computer Science, Vol. 6373 (Springer-Verlag, Berlin), 174–189.Crossref, Google Scholar
• Rochat Y, Taillard ÉD (1995) Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1: 147–167.Crossref, Google Scholar
• Subramanian A, Uchoa E, Ochi LS (2013) A hybrid algorithm for a class of vehicle routing problems. Comput. Oper. Res. 40: 2519–2531.Crossref, Google Scholar
• Subramanian A, Penna PHV, Uchoa E, Ochi LS (2012) A hybrid algorithm for the heterogeneous fleet vehicle routing problem. Eur. J. Oper. Res. 221:285–295.Crossref, Google Scholar
• Suurballe JW (1974) Disjoint paths in a network. Networks 4: 125–145.Crossref, Google Scholar
• Vidal T, Crainic TG, Gendreau M, Prins C (2014) Implicit depot assignments and rotations in vehicle routing heuristics. Eur. J. Oper. Res. 237:15–28.Crossref, Google Scholar