In this paper we consider the Capacitated Arc Routing Problem, in which a fleet of K vehicles, all of them based on a specific vertex (the depot) and with a known capacity Q, must service a subset of the edges of the graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity.
A heuristic algorithm for this problem is proposed consisting of: the selection of K centers, the construction of K connected graphs with associated loads not exceeding the vehicle capacities, the resolution of a General Assignment Problem, if necessary, to get a complete assignment of edges to vehicles and finally the construction of the routes by solving heuristically a Rural Postman Problem for each vehicle. Computational results on graphs up to 50 vertices and 97 edges are included. On average, the feasible solution is within 6,4% of the best known lower bound.
@article{urn:eudml:doc:40301,
title = {The Capacitated Arc Routing Problem. A heuristic algorithm.},
journal = {Q\"uestii\'o},
volume = {14},
year = {1990},
pages = {107-122},
mrnumber = {MR1114053},
language = {en},
url = {http://dml.mathdoc.fr/item/urn:eudml:doc:40301}
}
Benavent, Enrique.; Campos, V.; Corberán, Angel; Mota, Enrique. The Capacitated Arc Routing Problem. A heuristic algorithm.. Qüestiió, Tome 14 (1990) pp. 107-122. http://gdmltest.u-ga.fr/item/urn:eudml:doc:40301/