Displaying similar documents to “Upward embeddings and orientations of undirected planar graphs.”

The Capacitated Arc Routing Problem. A heuristic algorithm.

Enrique. Benavent, V. Campos, Angel Corberán, Enrique Mota (1990)



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...