Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 147, Issue 3, Pages 629-643Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/S0377-2217(02)00334-X
Keywords
routing; capacitated arc routing problem; local search
Ask authors/readers for more resources
This paper presents a new local search algorithm for the capacitated arc routing problem (CARP). The procedure uses single vehicle moves and moves that operate on two routes, both derived from a node routing context but properly adapted to work well for arc routing problems. We combine the algorithm with the meta-heuristic guided local search and further use the mechanisms of neighbor lists and edge marking to improve the solution quality and to save computation time. Experiments on standard benchmark problems from the literature show that our algorithm outperforms the existing heuristics for the CARP. On a set of new test problems, the local search approach consistently produces high quality solutions and often detects an optimal solution within limited computation time. (C) 2002 Elsevier Science B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available