In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem

References

• Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Lett. 33(1):42–54.Crossref, Google Scholar
• Ahr D (2004) Contributions to multiple postmen problems. Unpublished doctoral dissertation, Department of Computer Science, Heidelberg University, Heidelberg, Germany.Google Scholar
• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice Hall, Englewood Cliffs, NJ).Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011a) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011b) Dynamic NG-path relaxation. Presentation at the ROUTE 2011 Conference, June 3, Technical University of Barcelona, Barcelona, Spain. http://www.uv.es/route2011/Roberti.pdf.Google Scholar
• Bartolini E, Cordeau J-F, Laporte G (2013a) Improved lower bounds and exact algorithm for the capacitated arc routing problem. Math. Programming 137(1–2):409–452.Crossref, Google Scholar
• Bartolini E, Cordeau J-F, Laporte G (2013b) An exact algorithm for the capacitated arc routing problem with deadheading demand. Oper. Res. 61(2):315–327.Link, Google Scholar
• Belenguer JM, Benavent E (1998) The capacitated arc routing problem: Valid inequalities and facets. Comput. Optim. Appl. 10(2): 165–187.Crossref, Google Scholar
• Belenguer JM, Benavent E (2003) A cutting plane algorithm for the capacitated arc routing problem. Comput. Oper. Res. 30(5): 705–728.Crossref, Google Scholar
• Belenguer JM, Benevent E, Irnich S (2014) The capacitated arc routing problem: Exact algorithms. Corberán Á, Laporte G, eds. Arc Routing: Problems, Methods, and Applications (SIAM, Philadelphia), 183–222.Google Scholar
• Ben Amor H, Desrosiers J, Valério de Carvalho JM (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 (2013) The shortest-path problem with resource constraints with (k, 2)-loop elimination and its application to the capacitated arc-routing problem. Technical Report LM-2013-01, Mainz School of Management and Economics, Johannes Gutenberg University, Mainz, Germany.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
• Corberán Á, Prins C (2010) Recent results on arc routing problems: An annotated bibliography. Networks 56(1):50–69.Crossref, Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM (2002) Accelerating strategies in column generation for vehicle routing and crew scheduling problems. Ribeiro CC, Hansen P, eds. Essays and Surveys in Metaheuristics, Operations Research/Computer Science Interfaces Series (Kluwer, Boston), 309–324.Crossref, Google Scholar
• Desaulniers G, Lessard F, Hadjar A (2008) Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows. Transportation Sci. 42(3):387–404.Link, Google Scholar
• Eglese RW, Li LYO (1992) Efficient routing for winter gritting. J. Oper. Res. Soc. 43(11):1031–1034.Crossref, Google Scholar
• Fu H, Mei Y, Tang K, Zhu Y (2010) Memetic algorithm with heuristic candidate list strategy for capacitated arc routing problem. Proc. IEEE Congress Evolutionary Computation (IEEE, Piscataway, NJ).Crossref, Google Scholar
• Golden BL, Wong RT (1981) Capacitated arc routing problems. Networks 11(3):305–315.Crossref, Google Scholar
• Gómez-Cabrero D, Belenguer JM, Benavent E (2005) Cutting planes and column generation for the capacitated arc routing problem. Presented at Oper. Res. Peripatetic Postgraduate Programme (ORP3), Valencia, Spain, 259–266.Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, New York), 33–65.Crossref, 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
• Kohl N (1995) Exact methods for time constrained routing and related scheduling problems. Unpublished dissertation, Department of Mathematical Modelling, Technical University of Denmark, Lyngby.Google Scholar
• Lacomme P, Prins C, Ramdane-Chérif W (2001) A genetic algorithm for the capacitated arc routing problem and its extensions. Boers EJW, Cagnoni S, Gottlieb J, Hart E, Lanzi PL, Raidl G, Smith RE, Tijink H, eds. Appl. Evolutionary Comput.—EvoWorkshops2001: EvoCOP, EvoFlight, EvoIASP, EvoLearn, and EvoSTIM. Proc., Lecture Notes in Computer Science, Vol. 2037 (Springer-Verlag, Berlin), 473–483.Crossref, Google Scholar
• Larsen J (1999) Parallelization of the vehicle routing problem with time windows. Unpublished doctoral thesis, Department of Mathematical Modelling, Technical University of Denmark, Lyngby.Google Scholar
• Letchford AN (1997) Polyhedral results for some arc routing problems. Unpublished doctoral dissertation, Department of Management Science, Lancaster University, Lancaster, UK.Google Scholar
• Letchford AN, 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, de Aragão MP, Uchoa E (2006) Solving capacitated arc routing problems using a transformation to the CVRP. Comput. Oper. Res. 33(6):1823–1837.Crossref, Google Scholar
• Martinelli R, Poggi de Aragão 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 de Aragão M, Longo H (2011) A branch-cut-and-price algorithm for the capacitated arc routing problem. Pardalos PM, Rebennack S, eds. Experimental Algorithms: 10th Internat. Sympos. (SEA 2011), Lecture Notes in Computer Science, Vol. 6630 (Springer-Verlag, Berlin), 315–326.Crossref, Google Scholar
• McGill R, Tukey JW, Larsen WA (1978) Variations of box plots. Amer. Statistician 32(1):12–16.Crossref, Google Scholar
• Muyldermans L (2012) Personal communication. Email. July 18.Google Scholar
• Polacek M, Doerner K, Hartl R, Maniezzo V (2008) A variable neighborhood search for the capacitated arc routing problem with intermediate facilities. J. Heuristics 14(5):405–423.Crossref, Google Scholar
• Prins C (2014) The capacitated arc routing problem: Heuristics. Corberán Á, Laporte G, eds. Arc Routing: Problems, Methods and Applications (SIAM, Philadelphia), 131–158.Google Scholar
• Righini G, Salani M (2006) Bounded bidirectional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3(3):255–273.Crossref, Google Scholar
• Santos L, Coutinho-Rodrigues J, Current JR (2010) An improved ant colony optimization based algorithm for the capacitated arc routing problem. Transportation Res. Part B 44(2):246–266.Crossref, Google Scholar
• Wøhlk S (2008) A decade of capacitated arc routing. Golden BL, Raghavan S, Wasil EA, eds. The Vehicle Routing Problem: Latest Advances and New Challenges, Operations Research/Computer Science Interfaces Series, Vol. 43 (Springer, New York), 29–48.Crossref, Google Scholar