The capacitated arc routing problema heuristic algorithm

1. Benavent López, Enric
2. Campos Aucejo, Vicente
3. Corberán Salvador, Ángel
4. Mota Vidal, Enrique

Exportar

Exportar

×

MLA

modern-language-association

APA

apa

Chicago

chicago-fullnote-bibliography

Harvard

harvard-cite-them-right

Vancouver

vancouver-author-date

---

RIS BibTex

Exportar

×

El documento no se puede exportar porque pertenece a otro portal.

Texto completo

lock_openTexto completo externo

DIALNET GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Questiió: Quaderns d'Estadística, Sistemes, Informatica i Investigació Operativa

Resumen

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

Fuente de los datos: Dialnet