Ask For Icepicks

Revista EIA, ISSN 1794-1237 Número 12, p. 23-38. Diciembre 2009
Escuela de Ingeniería de Antioquia, Medellín (Colombia)

RESOLUCIÓN DEL PROBLEMA DE ENRUTAMIENTO
DE VEHÍCULOS CON LIMITACIONES DE CAPACIDAD
UTILIZANDO UN PROCEDIMIENTO METAHEURÍSTICO
DE DOS FASES
Julio Mario Daza*
Jairo r . Montoya**
Francesco narDucci***
RESUMEN
Este artículo presenta un procedimiento alternativo pararesolver 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. Estaalternativa se aplicó sobre una instancia generada aleatoriamente y una instancia real
arrojando resultados significativos al compararse con las heurísticas evaluadas.
PALABRAS CLAVE: problema de ruteo de vehículos; problema del agente viajero; optimización combinatoria; heurístico.

*

Ingeniero Industrial, Magíster en Ingeniería Industrial. Profesor, Corporación Universitaria de la Costa,Barranquilla,
Colombia. juliomariodaza@hotmail.com.

** Ingeniero Industrial. Master of Science in Industrial Engineering and Managment; Doctor en Ingenieria Industrial.
Profesor Asociado, Escuela Internacional de Ciencias Económicas y Administrativas, Universidad de La Sabana,
Chía (Cundinamarca), Colombia. jairo.montoya@unisabana.edu.co.
*** Ingeniero Industrial, Magíster en IngenieríaIndustrial. Ingeniero consultor y docente catedrático, Departamento de
Ingeniería Industrial, Universidad del Norte, Barranquilla, Colombia. fnarducci78@hotmail.com.
Artículo recibido 27-VI-2009. Aprobado 18-XI-2009
Discusión abierta hasta junio de 2010

Resolución del pRoblema de enRutamiento de vehículos...

SOLVING THE CAPACITATED VEHICLE ROUTING PROBLEM USING A TWOPHASE METAHEURISTICPROCEDURE
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 obtainnon-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 andreal
data, giving competitive results in comparison with other heuristics tested.
KEY WORDS: vehicle routing problem; traveling salesman problem; combinatorial optimization; heuristic.

RESOLUÇÃO DO PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM
LIMITAÇÕES DE CAPACIDADE UTILIZANDO UM PROCEDIMENTO
METAHEURÍSTICO DE DUAS FASES
RESUMO
Este artigo apresenta um procedimento alternativo para resolver oproblema de roteamento de veículos
com limitações de capacidade e frota homogênea (CVRP). Propõe-se um algoritmo metaheurístico que consta
da combinação de duas fases: desenho de rotas e planejamento da frota. A primeira fase está composta de procedimentos heurísticos e metaheurísticos onde se constrói uma solução inicial que é melhorada mediante busca
tabu obtendo soluções não dominadas em...