An improved heuristic for the capacitated arc routing problem

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.11.005 Byline: Luis Santos (a)(c), Joao Coutinho-Rodrigues (a)(c), John R. Current (b)(c) Abstract: The capacitated arc routing problem (CARP) is an important and practical problem in the OR literature. In short, the problem is to identify routes to service (e.g., pickup or deliver) demand located along the edges of a network such that the total cost of the routes is minimized. In general, a single route cannot satisfy the entire demand due to capacity constraints on the vehicles. CARP belongs to the set of NP-hard problems; consequently numerous heuristic and metaheuristic solution approaches have been developed to solve it. In this paper an "ellipse rule" based heuristic is proposed for the CARP. This approach is based on the path-scanning heuristic, one of the mostly used greedy-add heuristics for this problem. The innovation consists basically of selecting edges only inside ellipses when the vehicle is near the end of each route. This new approach was implemented and tested on three standard datasets and the solutions are compared against: (i) the original path-scanning heuristic; (ii) two other path-scanning heuristics and (iii) the three best known metaheuristics. The results indicate that the "ellipse rule" approach lead to improvements over the three path-scanning heuristics, reducing the average distance to the lower bound in the test problems by about 44%. Author Affiliation: (a) Department of Civil Engineering, Faculty of Sciences and Technology, Polo II, University of Coimbra, 3030-788 Coimbra, Portugal (b) Department of Management Sciences, The Fisher College of Business, The Ohio State University, 632 Fisher Hall, 2100 Neil Avenue, Columbus. OH 43210-1144, USA (c) INESC-Coimbra, R. Antero Quental, 199, 3000-033 Coimbra, Portugal