An Exact Algorithm for the Capacitated Arc Routing Problem with Deadheading Demand

References

• Ahr D, Reinelt G. A tabu search algorithm for the minmax k-Chinese postman problem. Comput. Oper. Res. (2006) 33:3403–3422Crossref, Google Scholar
• Baldacci R, Maniezzo V. Exact methods based on node-routing formulations for undirected arc-routing problems. Networks (2006) 47:52–60Crossref, Google Scholar
• Bartolini E, Cordeau J-F, Laporte G. Improved lower bounds and exact algorithm for the capacitated arc routing problem. Math. Programming Ser. A (2011) 137:409–452Crossref, Google Scholar
• Belenguer JM, Benavent E. The capacitated arc routing problem: Valid inequalities and facets. Comput. Optim. Appl. (1998) 10:165–187Crossref, Google Scholar
• Belenguer JM, Benavent E. A cutting plane algorithm for the capacitated arc routing problem. Comput. Oper. Res. (2003) 30:705–728Crossref, Google Scholar
• Benavent E, Campos V, Corberán A, Mota E. The capacitated arc routing problem: Lower bounds. Networks (1992) 22:669–690Crossref, Google Scholar
• Benavent E, Corberán A, Plana I, Sanchis JM. Min-max k-vehicles windy rural postman problem. Networks (2009) 54:216–226Crossref, Google Scholar
• Benavent E, Corberán A, Plana I, Sanchis JM. New facets and an enhanced branch-and-cut for the min-max k-vehicles windy rural postman problem. Networks (2011) 58:255–272Crossref, Google Scholar
• Benavent E, Carrotta A, Corberán A, Sanchis JM, Vigo D. Lower bounds and heuristics for the windy rural postman problem. Eur. J. Oper. Res. (2007) 176:855–869Crossref, Google Scholar
• Beullens P, Muyldermans L, Cattrysse D, Van Oudheusden D. A guided local search heuristic for the capacitated arc routing problem. Eur. J. Oper. Res. (2003) 147:629–643Crossref, Google Scholar
• Bode C, Irnich S. Cut-first branch-and-price-second for the capacitated arc-routing problem. (2011) . Technical Report LM-2011-03 (revised), Chair of Logistics Management, Johannes Gutenberg University, Mainz, Germany. Accessed December 23, 2011, http://logistik.bwl.uni-mainz.de/158.phpGoogle Scholar
• Christofides N, Mingozzi A, Toth P. Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxation. Math. Programming (1981) 20:255–282Crossref, Google Scholar
• Eglese RW. Routeing winter gritting vehicles. Discrete Appl. Math. (1994) 48:231–244Crossref, Google Scholar
• Eglese RW, Li LYO, Osman IH, Kelly JP. A tabu search based heuristic for arc routing with a capacity constraint and time deadline. Meta-Heuristics: Theory and Applications (1996) (Kluwer, Boston) 633–650Crossref, Google Scholar
• Frederickson G, Hecht M, Kim C. Approximation algorithms for some routing problems. SIAM J. Comput. (1978) 7:178–193Crossref, Google Scholar
• Golden BL, Wong RT. Capacitated arc routing problems. Networks (1981) 11:305–315Crossref, Google Scholar
• Golden BL, DeArmon JS, Baker EK. Computational experiments with algorithms for a class of routing problems. Comput. Oper. Res. (1983) 10:47–59Crossref, Google Scholar
• Gómez-Cabrero D, Belenguer JM, Benavent E. Cutting plane and column generation for the capacitated arc routing problem. (2005) Presentation, Operational Research Peripatietic Postgraduate Programme (ORP3) MeetingValencia, SpainGoogle Scholar
• Hirabayashi R, Nishida N, Saruwatari Y. Node duplication lower bounds for the capacitated arc routing problems. J. Oper. Res. Soc. Japan (1992) 35:119–133Google Scholar
• ILOG, IBMIBM ILOG CPLEX V12.1 User's Manual for CPLEX (2009) (IBM Corporation). ftp://public.dhe.ibm.com/software/websphere/ilog/docs/optimization/cplex/ps_usrmancplex.pdfGoogle Scholar
• Keenan PB. Spatial decision support systems for large arc routing problems. (2001) . Ph.D. thesis, Department of Management Information Systems, Faculty of Commerce, University College Dublin, Dublin, IrelandGoogle Scholar
• Keenan PB. Lower bounds for the time capacitated arc routing problem. (2005) . Technical report, UCD Business School, University College Dublin, Dublin, Ireland. Accessed November 16, 2011, http://mis.ucd.ie/Members/pkeenan/Working%20papers/TCARPLB.pdfGoogle Scholar
• Kirlik G, Sipahioglu A. Capacitated arc routing problem with deadheading demands. Comput. Oper. Res. (2011) 39:2380–2394Crossref, Google Scholar
• Kiuchi M, Shinano Y, Hirabayashi R, Saruwatari Y. An exact algorithm for the capacitated arc routing problem using parallel branch and bound method. Abstracts of 1995 Spring National Conf. Oper. Res. Soc. (1995) Japan:28–29Google Scholar
• Letchford AN, Oukil A. Exploiting sparsity in pricing routines for the capacitated arc routing problem. Comput. Oper. Res. (2009) 36:2320–2327Crossref, Google Scholar
• Li LYO, Eglese RW. An interactive algorithm for vehicle routing for winter-gritting. J. Oper. Res. Soc. (1996) 47:217–228Crossref, Google Scholar
• Longo H, Poggi de Aragão M, Uchoa E. Solving capacitated arc routing problems using a transformation to the CVRP. Comput. Oper. Res. (2006) 33:1823–1837Crossref, Google Scholar
• Martinelli R, Pecin D, Poggi de Aragão M, Longo H. Column generation bounds for the capacitated arc routing problem. (2010) Presentation, XLII SBPOBento Gonçalves, BrazilAccessed November 16, 2011, http://www.sobrapo.org.br/sbpo2010/xliisbpo-pdf/72618.pdfGoogle Scholar
• Martinelli R, Poggi de Aragão M, Subramanian A. Improved bounds for large scale capacitated arc routing problem. (2011) . Technical Report Monograas em Ciencia da Computação 14/11, Departamento de Informatica, Pontificia Universidade Catolica do Rio de Janeiro, Rio de JaneiroGoogle Scholar
• Parlaktuna O, Sipahioglu A, Kirlik G, Yazici A. Multi-robot sensor-based coverage path planning using capacitated arc routing approach. 2009 IEEE Internat. Sympos. Intelligent Control (2009) (IEEE Computer Society, Piscataway, NJ) 1146–1151Crossref, Google Scholar
• Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Sci. (2006) 40:455–472Link, Google Scholar
• Sipahioglu A, Kirlik G, Parlaktuna O, Yazici A. Energy constrained multi-robot sensor-based coverage path planning using capacitated arc routing approach. Robotics and Autonomous Systems (2010) 58:529–538Crossref, Google Scholar
• SPECSPEC CPU2006 Results (2011) . Standard Performance Evaluation Corporation. Accessed November 25, 2011, http://www.spec.org/cpu2006/results/index.htmlGoogle Scholar
• Stern H, Dror M. Routing electric meter readers. Comput. Oper. Res. (1979) 6:209–223Crossref, Google Scholar
• Trevai C, Ota J, Arai T. Multiple mobile robot surveillance in unknown environments. Advanced Robotics (2007) 21:729–749Crossref, Google Scholar
• Ulusoy G. The fleet size and mix problem for capacitated arc routing. Eur. J. Oper. Res. (1985) 22:329–337Crossref, Google Scholar