# The Capacitated Arc Routing Problem. A heuristic algorithm.

Qüestiió (1990)

• Volume: 14, Issue: 1-2-3, page 107-122
• ISSN: 0210-8054

top

## Abstract

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

## How to cite

top

Benavent, Enrique., et al. "The Capacitated Arc Routing Problem. A heuristic algorithm.." Qüestiió 14.1-2-3 (1990): 107-122. <http://eudml.org/doc/40301>.

@article{Benavent1990,
abstract = {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.},
author = {Benavent, Enrique., Campos, V., Corberán, Angel, Mota, Enrique},
journal = {Qüestiió},
keywords = {Heurística; Optimización de trayectorias; Problema del viajante; Problemas de rutas de vehículos; distribution; heuristics; routing},
language = {eng},
number = {1-2-3},
pages = {107-122},
title = {The Capacitated Arc Routing Problem. A heuristic algorithm.},
url = {http://eudml.org/doc/40301},
volume = {14},
year = {1990},
}

TY - JOUR
AU - Benavent, Enrique.
AU - Campos, V.
AU - Corberán, Angel
AU - Mota, Enrique
TI - The Capacitated Arc Routing Problem. A heuristic algorithm.
JO - Qüestiió
PY - 1990
VL - 14
IS - 1-2-3
SP - 107
EP - 122
AB - 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.
LA - eng
KW - Heurística; Optimización de trayectorias; Problema del viajante; Problemas de rutas de vehículos; distribution; heuristics; routing
UR - http://eudml.org/doc/40301
ER -

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.