Comparative Analysis of Capacitated Arc Routing Formulations for Designing a New Branch-Cut-and-Price Algorithm

References

• Achterberg T (2007) Constraint integer programming. PhD thesis, Technische Universitat Berlin, Berlin.Google Scholar
• Augerat P, Belenguer J, Benavent E, Corberán A, Naddef D, Rinaldi G (1995) Computational results with a branch and cut code for the capacitated vehicle routing problem. IASI Research Report n. 495, Istituto di Analisi dei Sistemi ed Informatica, Rome.Google Scholar
• Baldacci R, Maniezzo V (2006) Exact methods based on node-routing formulations for undirected arc-routing problems. Networks 47(1):52–60.Crossref, Google Scholar
• Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2):351–385.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Bartolini E, Cordeau JF, Laporte G (2013) Improved lower bounds and exact algorithm for the capacitated arc routing problem. Math. Programming 137(1–2):409–452.Crossref, Google Scholar
• Belenguer J, Benavent E (1998) The capacitated arc routing problem: Valid inequalities and facets. Comput. Optim. Appl. 10(2):165–187.Crossref, Google Scholar
• Belenguer J, Benavent E (2003) A cutting plane algorithm for the capacitated arc routing problem. Comput. Oper. Res. 30(5):705–728.Crossref, Google Scholar
• Ben Amor H, Desrosiers J, Valério de Carvalho J (2006) Dual-optimal inequalities for stabilized column generation. Oper. Res. 54(3):454–463.Link, Google Scholar
• Benavent E, Campos V, Corberán A, Mota E (1992) The capacitated arc routing problem: Lower bounds. Networks 22(7):669–690.Crossref, Google Scholar
• Beullens P, Muyldermans L, Cattrysse D, Van Oudheusden D (2003) A guided local search heuristic for the capacitated arc routing problem. Eur. J. Oper. Res. 147(3):629–643.Crossref, Google Scholar
• Bode C, Irnich S (2012) Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5):1167–1182.Link, Google Scholar
• Bode C, Irnich S (2014) The shortest-path problem with resource constraints with (k, 2)-loop elimination and its application to the capacitated arc-routing problem. Eur. J. Oper. Res. 238(2):415–426.Crossref, Google Scholar
• Bode C, Irnich S (2015) In-depth analysis of pricing problem relaxations for the capacitated arc-routing problem. Transportation Sci. 49(2):369–383.Link, Google Scholar
• Brandão J, Eglese R (2008) A deterministic tabu search algorithm for the capacitated arc routing problem. Comput. Oper. Res. 35(4):1112–1126.Crossref, Google Scholar
• Chen Y, Hao JK, Glover F (2016) A hybrid metaheuristic approach for the capacitated arc routing problem. Eur. J. Oper. Res. 253(1):25–39.Crossref, 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
• Corberán Á, Laporte G (2014) Arc Routing: Problems, Methods, and Applications (Society for Industrial and Applied Mathematics, Philadelphia).Google Scholar
• Dror M (2000) Arc routing: Complexity and approximability. Dror M, ed. Arc Routing: Theory, Solutions, and Applications (Springer Science & Business Media, Dordrecht, Netherlands), 133–170.Crossref, Google Scholar
• Eglese R, Li L (1992) Efficient routeing for winter gritting. J. Oper. Res. Soc. 43(11):1031–1034.Crossref, Google Scholar
• Foulds L, Longo H, Martins J (2015) A compact transformation of arc routing problems into node routing problems. Ann. Oper. Res. 226(1):177–200.Crossref, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, Poggi de Aragão M, Reis M, Uchoa E, Werneck R (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511.Crossref, Google Scholar
• Golden B, Wong R (1981) Capacitated arc routing problems. Networks 11:305–315.Crossref, Google Scholar
• Gómez-Cabrero D, Belenguer J, Benavent E (2005) Cutting plane and column generation for the capacitated arc routing problem. Proc. ORP3 Meeting, Valencia, Spain.Google Scholar
• Irnich S, Villeneuve D (2006) The shortest-path problem with resource constraints and k-cycle elimination for k ≥ 3. INFORMS J. Comput. 18(3):391–406.Link, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Kullmann O (2009) Fundaments of branching heuristics. Biere A, Heule M, van Maaren H, Walsh T, eds. Handbook of Satisfiability (IOS Press, Amsterdam), 205–244.Google Scholar
• Laporte G, Nobert Y (1983) A branch and bound algorithm for the capacitated vehicle routing problem. OR Spectrum 5(2):77–85.Crossref, Google Scholar
• Le Bodic P, Nemhauser G (2017) An abstract model for branching and its application to mixed integer programming. Math. Programming 166(1–2):369–405.Crossref, Google Scholar
• Letchford A (1997) Polyhedral results for some constrained arc-routing problems. PhD thesis, University of Lancaster, Lancaster, UK.Google Scholar
• Letchford A, Oukil A (2009) Exploiting sparsity in pricing routines for the capacitated arc routing problem. Comput. Oper. Res. 36(7):2320–2327.Crossref, Google Scholar
• Longo H, Poggi de Aragão M, Uchoa E (2006) Solving capacitated arc routing problems using a transformation to the CVRP. Comput. Oper. Res. 33(6):1823–1837.Crossref, Google Scholar
• Lysgaard J, Letchford A, Eglese R (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100:423–445.Crossref, Google Scholar
• Martinelli R, Malta M, Poggi M (2016) Improved lower bounds using lm-SRCs for the capacitated arc routing problems. Presentation, International Workshop on Column Generation, May 22–25, Búzios, Brazil.Google Scholar
• Martinelli R, Poggi M, Subramanian A (2013) Improved bounds for large scale capacitated arc routing problem. Comput. Oper. Res. 40(8):2145–2160.Crossref, Google Scholar
• Martinelli R, Pecin D, Poggi M, Longo H (2011) A branch-cut-and-price algorithm for the capacitated arc routing problem. Pardalos PM, Rebennack S, eds. Experimental Algorithms—SEA 2011, Lecture Notes in Computer Science, vol. 6630 (Springer, Berlin, Heidelberg), 315–326.Google Scholar
• Pearn WL, Assad A, Golden BL (1987) Transforming arc routing into node routing problems. Comput. Oper. Res. 14(4):285–288.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 (2014) Improved branch-cut-and-price for capacitated vehicle routing. Lee J, Vygen J, eds. Integer Programming and Combinatorial Optimization—IPCO 2014, Lecture Notes in Computer Science, vol. 8494 (Springer, Cham, Switzerland), 393–403.Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017b) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9:61–100.Crossref, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E, Santos H (2017c) Limited memory rank-1 cuts for vehicle routing problems. Oper. Res. Lett. 45(3):206–209.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, Uchoa E, Poggi de Aragão M (2009) A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem. Networks 54(4):167–177.Crossref, Google Scholar
• Poggi M, Uchoa E (2014) New exact algorithms for the capacitated vehicle routing problem. Vehicle Routing: Problems, Methods, and Applications, MOS-SIAM Series on Optimization, vol. 18 (Society for Industrial and Applied Mathematics, Philadelphia), 59–86.Crossref, Google Scholar
• Poggi de Aragão M, Uchoa E (2003) Integer program reformulation for robust branch-and-cut-and-price. Wolsey L, ed. Ann. Math. Programming Rio (Búzios, Brazil), 56–61.Google Scholar
• Righini G, Salani M (2006) Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3(3):255–273.Crossref, Google Scholar
• Røpke S (2012) Branching decisions in branch-and-cut-and-price algorithms for vehicle routing problems. Presentation, International Workshop on Column Generation, June 13, Bromont, QC, Canada.Google Scholar
• Tilk C, Rothenbächer AK, Gschwind T, Irnich S (2017) Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster. Eur. J. Oper. Res. 261(2):530–539.Crossref, Google Scholar
• Uchoa E, Fukasawa R, Lysgaard J, Pessoa A, De Aragao MP, Andrade D (2008) Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation. Math. Programming 112(2):443–472.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