The Capacitated Arc Routing Problem: A heuristic algorithm

The Capacitated Arc Routing Problem: A heuristic algorithm

0.00 Avg rating0 Votes
Article ID: iaor1992648
Country: Spain
Volume: 14
Start Page Number: 107
End Page Number: 122
Publication Date: Aug 1990
Journal: QUESTIIO
Authors: , , ,
Abstract:

In this paper the authors consider the Capacitated Arc Routing Problem, in which a fleet of K vehicles, all of them based on a specified vertex (the depot) and with a known capacity Q, must service a subset of the edges of a 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 Generalized 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.

Reviews

Required fields are marked *. Your email address will not be published.