Decomposition Strategies for Vehicle Routing Heuristics

References

• Arnold F, Sörensen K (2018) What makes a VRP solution good? The generation of problem-specific knowledge for heuristics. Comput. Oper. Res. 106:280–288.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
• Arnold F, Santana Í, Sörensen K, Vidal T (2021) PILS: Exploring high-order neighborhoods by pattern mining and injection. Pattern Recognition 116.Google Scholar
• Arthur D, Vassilvitskii S (2007) k-means++: The advantages of careful seeding. Gabow H, ed. Proc. 18th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 1027–1035.Google Scholar
• Battarra M, Erdog¨an G, Vigo D (2014) Exact algorithms for the clustered vehicle routing problem. Oper. Res. 62(1):58–71.Link, Google Scholar
• Bent R, Van Hentenryck P (2010) Spatial, temporal, and hybrid decompositions for large-scale vehicle routing with time windows. Cohen D, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin), 99–113.Google Scholar
• Bulhões T, Ha MH, Martinelli R, Vidal T (2018) The vehicle routing problem with service level constraints. Eur. J. Oper. Res. 265(2):544–558.Crossref, Google Scholar
• Chevalier C, Safro I (2009) Comparison of coarsening schemes for multilevel graph partitioning. Stützle T, ed. Proc. Internat. Conf. on Learn. and Intelligent Optim. (Springer, Berlin), 191–205.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
• Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Link, Google Scholar
• El Hachemi N, Crainic TG, Lahrichi N, Rei W, Vidal T (2015) Solution integration in combinatorial optimization with applications to cooperative search and rich vehicle routing. J. Heuristics 21(5):663–685.Crossref, Google Scholar
• Geoffrion A (1970a) Elements of large-scale mathematical programming. Part I: Concepts. Management Sci. 16(11):652–675.Link, Google Scholar
• Geoffrion A (1970b) Elements of large-scale mathematical programming. Part II: Synthesis of algorithms and bibliography. Management Sci. 16(11):676–691.Link, Google Scholar
• Goeke D, Gschwind T, Schneider M (2019) Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier. Discrete Appl. Math. 264:43–61.Crossref, Google Scholar
• Golden B, Wong R (1981) Capacitated arc routing problems. Networks 11(3):305–315.Crossref, Google Scholar
• Groër C, Golden B, Wasil E (2009) The consistent vehicle routing problem. Manufacturing Service Oper. Management 11(4):630–643.Link, Google Scholar
• Groër C, Golden B, Wasil E (2011) A parallel algorithm for the vehicle routing problem. INFORMS J. Comput. 23(2):315–330.Link, Google Scholar
• Joshi C, Laurent T, Bresson X (2019) An efficient graph convolutional network technique for the travelling salesman problem. Preprint, submitted June 4, https://arxiv.org/abs/1906.01227.Google Scholar
• Kool W, van Hoof H, Gromicho J, Welling M (2021) Deep policy dynamic programming for vehicle routing problems. Preprint, submitted February 23, https://arxiv.org/abs/2102.11756.Google Scholar
• Lahrichi N, Crainic TG, Gendreau M, Rei W, Crişan GC, Vidal T (2015) An integrative cooperative search framework for multi-decision-attribute combinatorial optimization: Application to the MDPVRP. Eur. J. Oper. Res. 246(2):400–412.Crossref, Google Scholar
• MacQueen J (1967) Some methods for classification and analysis of multivariate observations. Lecam L, Neyman J, eds. Proc. 5th Berkeley Sympos. on Math. Statist. and Probability, vol. 1 (University of California Press, Berkeley, CA), 281–297.Google Scholar
• Park HS, Jun CH (2009) A simple and fast algorithm for k-medoids clustering. Expert Systems Appl. 36(2):3336–3341.Crossref, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9:61–100.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2019) A generic exact solver for vehicle routing and related problems. Lodi A, Nagarajan V, eds. Integer Programming and Combinatorial Optimization (Springer, Berlin), 354–369.Crossref, Google Scholar
• Pisinger D, Ropke S (2007) A general heuristic for vehicle routing problems. Comput. Oper. Res. 34(8):2403–2435 URL http://dx.doi.org/j.cor.2005.09.012.Crossref, Google Scholar
• Pisinger D, Ropke S (2019) Large neighborhood search. Gendreau M, Potvin JY, eds. Handbook of Metaheuristics, 3rd ed. (Springer, Berlin), 99–127.Crossref, Google Scholar
• Queiroga E, Sadykov R, Uchoa E (2020) A modern POPMUSIC matheuristic for the capacitated vehicle routing problem. Technical report, Caderno do LOGIS, Universidade Federal Fluminense, Niterói, Brazil.Google Scholar
• Ribeiro MH, Plastino A, Martins S (2006) Hybridization of GRASP metaheuristic with data mining techniques. J. Math. Modelling Algorithms 5(1):23–41.Crossref, Google Scholar
• Rodrigues de Holanda Maia M, Plastino A, Penna PHV (2020) MineReduce: An approach based on data mining for problem size reduction. Comput. Oper. Res. 122:104995.Crossref, Google Scholar
• Ropke S, Pisinger D (2006a) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Sci. 40(4):455–472.Link, Google Scholar
• Ropke S, Pisinger D (2006b) A unified heuristic for a large class of vehicle routing problems with backhauls. Eur. J. Oper. Res. 171(3):750–775.Crossref, Google Scholar
• Rossit DG, Vigo D, Tohmé F, Frutos M (2019) Visual attractiveness in routing problems: A review. Comput. Oper. Res. 103:13–34.Crossref, Google Scholar
• Santini A (2019) An adaptive large neighbourhood search algorithm for the orienteering problem. Expert Systems Appl. 123:154–167.Crossref, Google Scholar
• Santini A, Ropke S, Hvattum LM (2018) A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic. J. Heuristics 24:783–815.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
• Sevaux M, Sörensen K (2008) Hamiltonian paths in large clustered routing problems. Prodhon C, Wolfler-Calvo R, Nacima L, Prins C, eds. Proc. EU/Meeting Workshop on Metaheuristics for Logistics and Vehicle Routing, 411–417.Google Scholar
• Shaw P (1997) A new local search algorithm providing high quality solutions to vehicle routing problems. Technical report, Department of Computer Science, University of Strathclyde, Glasgow, Scotland.Google Scholar
• Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. Maher M, Puget JF, eds. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin), 417–431.Google Scholar
• Taillard E (1993) Parallel iterative search methods for vehicle routing problems. Networks 23(8):661–673.Crossref, Google Scholar
• Taillard E, Helsgaun K (2019) POPMUSIC for the travelling salesman problem. Eur. J. Oper. Res. 272(2):420–429.Crossref, Google Scholar
• Toth P, Vigo D, eds. (2014) Vehicle Routing: Problems, Methods, and Applications. MOS-SIAM Series on Optimization. (SIAM, Philadelphia).Crossref, Google Scholar
• Tukey J (1949) Comparing individual means in the analysis of variance. Biometrics 5(2):99–114.Crossref, 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 (2017) Node, edge, arc routing and turn penalties: multiple problems: One neighborhood extension. Oper. Res. 65(4):992–1010.Link, Google Scholar
• Vidal T (2022) Hybrid genetic search for the CVRP: Open-source implementation and swap* neighborhood. Comput. Oper. Res. 140.Google Scholar
• Vidal T, Laporte G, Matl P (2020) A concise guide to existing and emerging vehicle routing problem variants. Eur. J. Oper. Res. 286:401–416.Crossref, Google Scholar
• Vidal T, Crainic TG, Gendreau M, Prins C (2013a) Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. Eur. J. Oper. Res. 231(1):1–21.Crossref, Google Scholar
• Vidal T, Crainic TG, Gendreau M, Prins C (2013b) A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Comput. Oper. Res. 40(1):475–489.Crossref, Google Scholar
• Vidal T, Crainic TG, Gendreau M, Prins C (2014) A unified solution framework for multi-attribute vehicle routing problems. Eur. J. Oper. Res. 234(3):658–673.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
• Walshaw C (2002) A multilevel approach to the travelling salesman problem. Oper. Res. 50(5):862–877.Link, Google Scholar
• Xavier I, Oliveira D, Queiroga E (2021) CVRPLIB–All instances. Accessed December 12, 2021, http://vrp.atd-lab.inf.puc-rio.br/index.php/en/.Google Scholar
• Young G, Householder AS (1938) Discussion of a set of points in terms of their mutual distances. Psychometrika 3:19–22.Crossref, Google Scholar