Cluster Branching for Vehicle Routing Problems

References

• Achterberg T (2009) SCIP: Solving constraint integer programs. Math. Programming Comput. 1:1–41.Crossref, Google Scholar
• Achterberg T, Berthold T (2009) Hybrid branching. van Hoeve WJ, Hooker JN, eds. Integration AI OR Techniques Constraint Programming Combin. Optim. Problems. CPAIOR 2009, Lecture Notes in Computer Science, vol. 5547 (Springer, Berlin, Heidelberg), 309–311.Google Scholar
• Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Lett. 33(1):42–54.Crossref, Google Scholar
• Applegate D, Bixby R, Chvátal V, Cook W (1995) Finding cuts in the TSP, DIMACS.Google Scholar
• Bénichou M, Gauthier JM, Girodet P, Hentges G, Ribière G, Vincent O (1971) Experiments in mixed-integer linear programming. Math. Programming 1:76–94.Crossref, Google Scholar
• Christofides N, Mingozzi A, Toth P (1979) The vehicle routing problem. Christofides N, Mingozzi A, Toth P, Sandi C, eds. Combinatorial Optimization (John Wiley & Sons, Chichester, UK), 325–338.Google Scholar
• Clochard JM, Naddef D (1993) Using path inequalities in a branch and cut code for the symmetric traveling salesman problem. Rinaldi G, Wolsey L, eds. Proc. 3rd Integer Programming Combin. Optim. Conf. (IPCO) (CIACO), 291–311.Google Scholar
• Cornuéjols G, Karamanov M, Li Y (2006) Early estimates of the size of branch-and-bound trees. INFORMS J. Comput. 18(1):86–96.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
• Errami N, Queiroga E, Sadykov R, Uchoa E (2023) VRPSolverEasy: A Python library for the exact solution of a rich vehicle routing problem. INFORMS J. Comput. 36(4):956–965.Link, Google Scholar
• Ester M, Kriegel HP, Sander J, Xu X (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. Simoudis E, Han J, Fayyad U, eds. KDD’96: Proc. 2nd Internat. Conf. Knowledge Discovery Data Mining (AAAI Press, Washington, DC), 226–231.Google Scholar
• Fukasawa R, Longo H, Lysgaard J, Aragão M, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106:491–511.Crossref, Google Scholar
• Gehring H, Homberger J (1999) A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. Proc. EUROGEN99, vol. 2 (University of Jyväskylä, Jyväskylän yliopisto, Finland), 57–64.Google Scholar
• Gower JC, Ross GJ (1969) Minimum spanning trees and single linkage cluster analysis. J. Roy. Statist. Soc.: Ser. C (Appl. Statist.) 18(1):54–64.Google Scholar
• Hendel G, Anderson D, Le Bodic P, Pfetsch ME (2021) Estimating the size of branch-and-bound trees. INFORMS J. Comput. 34(2):934–952.Link, Google Scholar
• Kaufmann L, Rousseeuw P (1987) Clustering by means of medoids. Dodge Y, ed. Statistical Data Analysis (Oxford) Based on the L1-Norm and Related Methods (North Holland, Amsterdam), 405–416.Google Scholar
• Land AH, Doig AG (1960) An automatic method for solving discrete programming problems. Econometrica 28(3):497–520.Crossref, Google Scholar
• Linderoth JT, Savelsbergh MW (1999) A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11(2):173–187. Link, Google Scholar
• Lloyd SP (1957) Least squares quantization in PCM. Technical Report RR-5497, Bell Lab, Murray Hill, NJ.Google Scholar
• Lysgaard J (2003) CVRPSEP: A Package of Separation Routines for the Capacitated Vehicle Routing Problem (Department of Management Science and Logistics, Aarhus School of Business, Aarhus, Denmark).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
• Pecin D, Contardo C, Desaulniers G, Uchoa E (2017a) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3):489–502.Link, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017b) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9(1):61–100.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E (2018) Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems. Eur. J. Oper. Res. 270(2):530–543.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Programming B 183:483–523.Crossref, Google Scholar
• Poggi M, Uchoa E (2014) New exact algorithms for the capacitated vehicle routing problem. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (SIAM, Philadelphia), 59–86.Crossref, Google Scholar
• Poggi de Aragão M, Uchoa E (2003) Integer program reformulation for robust branch-and-cut-and-price algorithms. Wolsey LA, ed. Proc. Conf. Math. Programming: Conf. Honour Nelson Maculan, 56–61.Google Scholar
• Queiroga E, Sadykov R, Uchoa E, Vidal T (2021) 10,000 optimal CVRP solutions for testing machine learning based heuristics. AAAI-22 Workshop Machine Learn. Oper. Res. (ML4OR) (AAAI Press, Washington, DC).Google Scholar
• Rousseeuw PJ (1987) Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. J. Comput. Appl. Math. 20:53–65.Crossref, Google Scholar
• Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling (North Holland, Amsterdam), 269–280.Google Scholar
• Sadykov R, Vanderbeck F (2021) BaPCod: A generic branch-and-price code. Technical Report HAL-03340548, Inria Bordeaux Sud-Ouest, Bordeaux, France.Google Scholar
• Sadykov R, Uchoa E, Pessoa A (2021) A bucket graph–based labeling algorithm with application to vehicle routing. Transportation Sci. 55(1):4–28.Link, Google Scholar
• Scavuzzo L, Aardal K, Lodi A, Yorke-Smith N (2024) Machine learning augmented branch and bound for mixed integer linear programming. Math. Programming, ePub ahead of print August 22, https://doi.org/10.1007/s10107-024-02130-y.Crossref, Google Scholar
• Shapiro SS, Wilk MB (1965) An analysis of variance test for normality (complete samples). Biometrika 52(3/4):591–611.Crossref, Google Scholar
• Silva JMP, Uchoa E, Subramanian A (2025) Cluster branching for vehicle routing problems. https://doi.org/10.1287/ijoc.2024.1036.cd, https://github.com/INFORMSJoC/2024.1036.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 (2022) Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Comput. Oper. Res. 140:105643.Crossref, Google Scholar
• Wilcoxon F (1945) Individual comparisons by ranking methods. Biometrics Bull. 1(6):80–83.Crossref, Google Scholar
• Zhang J, Liu C, Li X, Zhen HL, Yuan M, Li Y, Yan J (2023) A survey for solving mixed integer programming via machine learning. Neurocomputing 519:205–217.Crossref, Google Scholar