Presentación | Participantes | Bibliografía (DML-E) | Bibliografía adicional | Enlaces de interés | Otros proyectos DML | Ayuda  
INICIO | 16 de abril de 2024
  

The Capacitated Arc Routing Problem. A heuristic algorithm.

Título inglés The Capacitated Arc Routing Problem. A heuristic algorithm.
Título español El problema de rutas por arcos con capacidades: un algoritmo heurístico.
Autor/es Benavent, Enrique. ; Campos, V. ; Corberán, Angel ; Mota, Enrique
Organización Dep. Estad. Invest. Oper. Fac. Mat. Univ. Valencia, Valencia, España
Revista 0210-8054
Publicación 1990, 14 (1-2-3): 107-122, 23 Ref.
Tipo de documento articulo
Idioma Inglés
Resumen inglés 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.
Clasificación UNESCO 120315 ; 120704
Palabras clave español Heurística ; Optimización de trayectorias ; Problema del viajante ; Problemas de rutas de vehículos
Código MathReviews MR1114053
Icono pdf Acceso al artículo completo
Equipo DML-E
Instituto de Ciencias Matemáticas (ICMAT - CSIC)
rmm()icmat.es