A Fast and Scalable Heuristic for the Solution of Large-Scale Capacitated Vehicle Routing Problems

References

• Accorsi L, Vigo D (2020) A hybrid metaheuristic for single truck and trailer routing problems. Transportation Sci. 54(5):1351–1371.Link, Google Scholar
• Arnold F, Sörensen K (2019) Knowledge-guided local search for the vehicle routing problem. Comput. Oper. Res. 105:32–46.Crossref, Google Scholar
• Arnold F, Gendreau M, Sörensen K (2019) Efficiently solving very large-scale routing problems. Comput. Oper. Res. 107:32–42.Crossref, Google Scholar
• Beek O, Raa B, Dullaert W, Vigo D (2018) An efficient implementation of a static move descriptor-based local search heuristic. Comput. Oper. Res. 94:1–10.Crossref, Google Scholar
• Bergstra J, Bengio Y (2012) Random search for hyper-parameter optimization. J. Machine Learn. Res. 13(10):281–305.Google Scholar
• Cavaliere F, Bendotti E, Fischetti M (2020) Personal communication via email and in person, May.Google Scholar
• Christiaens J, Vanden Berghe G (2020) Slack induction by string removals for vehicle routing problems. Transportation Sci. 54(2):417–433.Link, Google Scholar
• Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12(4):568–581.Link, Google Scholar
• CVRPLIB (2020) Capacitated vehicle routing problem library. Accessed July 19, 2020, http://vrp.galgos.inf.puc-rio.br/index.php/en/.Google Scholar
• Duarte A, Sánchez-Oro J, Mladenović N, Todosijević R (2018) Variable Neighborhood Descent (Springer International Publishing, Cham, Switzerland), 341–367.Crossref, Google Scholar
• Etiemble D (2018) 45-year CPU evolution: one law and two equations. Preprint, submitted March 1, https://arxiv.org/abs/1803.00254.Google Scholar
• Frank E, Hall MA, Witten IH (2016) The WEKA Workbench. Online Appendix for Data Mining: Practical Machine Learning Tools and Techniques, 4th ed. (Morgan Kaufmann Publishers, Burlington, MA).Google Scholar
• Glover F (1989) Tabu search-part I. ORSA J. Comput. 1(3):190–206.Link, Google Scholar
• Glover F (1996) Ejection chains, reference structures and alternating path methods for traveling salesman problems. Discrete Appl. Math. 65(1):223–253.Crossref, Google Scholar
• Helsgaun K (2017) An extension of the Lin-Kernighan-Helsgaun TSP Solver for constrained traveling salesman and vehicle routing problems. Technical report, Roskilde Universitet, Roskilde, Denmark.Google Scholar
• Irnich S, Funke B, Grünert T (2006) Sequential search and its application to vehicle-routing problems. Comput. Oper. Res. 33(8):2405–2429.Crossref, Google Scholar
• Jünger M, Reinelt G, Rinaldi G (1995) Chapter 4: The traveling salesman problem. Ball MO, Magnanti TL, Monma BL, Nemhauser GL, eds. Handbooks in Operations Research and Management Science: Network Models, vol. 7 (Elsevier, Amsterdam), 225–330.Google Scholar
• Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Sci. 220(4598):671–680.Crossref, Google Scholar
• Kytöjoki J, Nuortio T, Bräysy O, Gendreau M (2007) An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Comput. Oper. Res. 34(9):2743–2757.Crossref, Google Scholar
• Lourenço HR, Martin OC, Stützle T (2003) Iterated Local Search (Springer US, Boston), 320–353.Crossref, Google Scholar
• Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, Inc., Hoboken, NJ).Google Scholar
• Matsumoto M, Nishimura T (1998) Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simulation 8(1):3–30.Crossref, Google Scholar
• Mladenović N, Hansen P (1997) Variable neighborhood search. Comput. Oper. Res. 24(11):1097–1100.Crossref, Google Scholar
• PassMark® Software (2020) Professional CPU benchmarks. Accessed July 19, 2020, https://www.passmark.com/index.html.Google Scholar
• R Core Team (2020) R: A Language and Environment for Statistical Computing (R Foundation for Statistical Computing, Vienna).Google Scholar
• Schneider M, Schwahn F, Vigo D (2017) Designing granular solution methods for routing problems with time windows. Eur. J. Oper. Res. 263(2):493–509.Crossref, Google Scholar
• Schrimpf G, Schneider J, Stamm-Wilbrandt H, Dueck G (2000) Record breaking optimization results using the ruin and recreate principle. J. Comput. Phys. 159(2):139–171.Crossref, Google Scholar
• Subramanian A, Uchoa E, Ochi LS (2013) A hybrid algorithm for a class of vehicle routing problems. Comput. Oper. Res. 40(10):2519–2531.Crossref, Google Scholar
• Taillard É, Badeau P, Gendreau M, Guertin F, Potvin JY (1997) A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Sci. 31(2):170–186.Link, Google Scholar
• Toth P, Vigo D (2003) The granular tabu search and its application to the vehicle-routing problem. INFORMS J. Comput. 15(4):333–346.Link, Google Scholar
• Toth P, Vigo D (2014) Vehicle Routing (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Uchoa E (2020) Personal communication via email with the authors, May–June.Google Scholar
• Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A (2017) New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257(3):845–858.Crossref, Google Scholar
• Vidal T, Crainic TG, Gendreau M, Lahrichi N, Rei W (2012) A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Oper. Res. 60(3):611–624.Link, Google Scholar
• Voudouris C, Tsang E (1999) Guided local search and its application to the traveling salesman problem. Eur. J. Oper. Res. 113(2):469–499.Crossref, Google Scholar
• Wilcoxon F (1945) Individual comparisons by ranking methods. Biometrics Bull. 1(6):80–83.Crossref, Google Scholar
• Zachariadis EE, Kiranoudis CT (2010) A strategy for reducing the computational complexity of local search-based methods for the vehicle routing problem. Comput. Oper. Res. 37(12):2089–2105.Crossref, Google Scholar