ImpactU Versión 3.11.2 Última actualización: Interfaz de Usuario: 16/10/2025 Base de Datos: 29/08/2025 Hecho en Colombia
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)
Este articulo presenta un procedimiento alternativo para resolver el problema de enrutamiento de vehiculos con limitaciones de capacidad y flota homogenea (CVRP). Se propone un algoritmo metaheuristico que consta de la combinacion de dos fases: diseno de rutas y planificacion de la flota. La primera fase esta compuesta de procedimientos heuristicos y metaheuristicos donde se construye una solucion inicial que es mejorada mediante busqueda tabu obteniendo soluciones no dominadas en tiempo de calculo polinomial. Para la segunda fase, correspondiente a la planificacion (scheduling) de la flota, se propone abordar el problema partiendo de una analogia con el problema de programacion de maquinas paralelas identicas. Este procedimiento tiene como funcion objetivo minimizar el costo fijo causado por la utilizacion de la capacidad instalada. Esta alternativa se aplico sobre una instancia generada aleatoriamente y una instancia real arrojando resultados significativos al compararse con las heuristicas 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.