Optimization Online


Improved Bounds for Large Scale Capacitated Arc Routing Problem

Rafael Martinelli (rmartinelli***at***inf.puc-rio.br)
Marcus Poggi (poggi***at***inf.puc-rio.br)
Anand Subramanian (anand***at***ct.ufpb.br)

Abstract: The Capacitated Arc Routing Problem (CARP) stands among the hardest combinatorial problems to solve or to find high quality solutions. This becomes even more true when dealing with large instances. This paper investigates methods to improve on lower and upper bounds of instances on graphs with over two hundred vertices and three hundred edges, dimensions that, today, can be considered of large scale. On the lower bound side, we propose to explore the speed of a dual ascent heuristic to generate capacity cuts. These cuts are next improved with a new exact separation enchained to the linear program resolution that follows the dual heuristic. On the upper bound, we implement a modified Iterated Local Search procedure to Capacitated Vehicle Routing Problem (CVRP) instances obtained by applying a transformation from the CARP original instances. Computational experiments were carried out on the set of large instances generated by Brandão and Eglese and also on the regular size sets. The experiments on the latter allow for evaluating the quality of the proposed solution approaches, while those on the former present improved lower and upper bounds for all instances of the corresponding set.

Keywords: Arc Routing, Integer Programming, Dual Ascent, Capacity Cuts, Metaheuristics

Category 1: Combinatorial Optimization (Other )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Combinatorial Optimization (Meta Heuristics )

Citation: Computers & Operations Research, Volume 40, Issue 8, August 2013, Pages 2145-2160, ISSN 0305-0548, http://dx.doi.org/10.1016/j.cor.2013.02.013


Entry Submitted: 10/14/2011
Entry Accepted: 10/15/2011
Entry Last Modified: 04/16/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society