RESOLUCIÓN DEL PROBLEMA DE ENRUTAMIENTO DE VEHÍCULOS CON LIMITACIONES DE CAPACIDAD UTILIZANDO UN PROCEDIMIENTO METAHEURÍSTICO DE DOS FASES (SOLVING THE CAPACITATED VEHICLE ROUTING PROBLEM USING A TWOPHASE METAHEURISTIC PROCEDURE)
RESOLUCIÓN DEL PROBLEMA DE ENRUTAMIENTO DE VEHÍCULOS CON LIMITACIONES DE CAPACIDAD UTILIZANDO UN PROCEDIMIENTO METAHEURÍSTICO DE DOS FASES (SOLVING THE CAPACITATED VEHICLE ROUTING PROBLEM USING A TWOPHASE METAHEURISTIC PROCEDURE)
Barra lateral del artículo
PDF
FLIP
Términos de la licencia (VER)
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.
Declaración del copyright
Los autores ceden en exclusiva a la Universidad EIA, con facultad de cesión a terceros, todos los derechos de explotación que deriven de los trabajos que sean aceptados para su publicación en la Revista EIA, así como en cualquier producto derivados de la misma y, en particular, los de reproducción, distribución, comunicación pública (incluida la puesta a disposición interactiva) y transformación (incluidas la adaptación, la modificación y, en su caso, la traducción), para todas las modalidades de explotación (a título enunciativo y no limitativo: en formato papel, electrónico, on-line, soporte informático o audiovisual, así como en cualquier otro formato, incluso con finalidad promocional o publicitaria y/o para la realización de productos derivados), para un ámbito territorial mundial y para toda la duración legal de los derechos prevista en el vigente texto difundido de la Ley de Propiedad Intelectual. Esta cesión la realizarán los autores sin derecho a ningún tipo de remuneración o indemnización.
La autorización conferida a la Revista EIA estará vigente a partir de la fecha en que se incluye en el volumen y número respectivo en el Sistema Open Journal Systems de la Revista EIA, así como en las diferentes bases e índices de datos en que se encuentra indexada la publicación.
Todos los contenidos de la Revista EIA, están publicados bajo la Licencia Creative Commons Atribución-NoComercial-NoDerivativa 4.0 Internacional
Licencia
Esta obra está bajo una Licencia Creative Commons Atribución-NoComercial-NoDerivativa 4.0 Internacional
Contenido principal del artículo
Resumen
Este artículo presenta un procedimiento alternativo para resolver el problema de enrutamiento de vehículos con limitaciones de capacidad y flota homogénea (CVRP). Se propone un algoritmo metaheurístico que consta de la combinación de dos fases: diseño de rutas y planificación de la flota. La primera fase está compuesta de procedimientos heurísticos y metaheurísticos donde se construye una solución inicial que es mejorada mediante búsqueda tabú obteniendo soluciones no dominadas en tiempo de cálculo polinomial. Para la segunda fase, correspondiente a la planificación (scheduling) de la flota, se propone abordar el problema partiendo de una analogía con el problema de programación de máquinas paralelas idénticas. Este procedimiento tiene como función objetivo minimizar el costo fijo causado por la utilización de la capacidad instalada. Esta alternativa se aplicó sobre una instancia generada aleatoriamente y una instancia real arrojando resultados significativos al compararse con las heurísticas evaluadas.
Abstract: This paper presents an alternative procedure to solve the Capacitated Vehicle Routing Problem (CVRP) with homogeneous fleet. The paper proposes a two-phase metaheuristic algorithm: routes design and fleet scheduling. The first phase is based on heuristics and metaheuristics procedures in order to build an initial solution that is then improved using tabu search to obtain non-dominated solutions in polynomial computational time. For the second phase, corresponding to fleet scheduling, the problem is approached using an analogy with the identical parallel machine scheduling problem. This procedure looks for the minimization of the fixed cost of using installed capacity as the objective function. The proposed procedure was tested using both a random-generated instance and real data, giving competitive results in comparison with other heuristics tested.