Dsae

1

Métodos Aproximados para la Solución del
Problema de Enrutamiento de Vehículos (Dic
2008)
R. Andrés Jaque Pirabán*

Abstract— This work carries out a review about state of the
art of the vehicle routing problem, summarizing the different
variant of the problem and compiling the different methods that
have been proposed for their solution, emphasizing heuristic
methods.
IndexTerms—Vehicle Routing Problem, heuristics, genetic
algorithms, swarm intelligence, ant colony optimization,
simulated annealing, tabu search, branch and bound
CONTENIDO

I. INTRODUCCIÓN .............................................................1
II. PROBLEMA DE ENRUTAMIENTO DE VEHÍCULOS.1
III. ENTORNOS REALES DE APLICACIÓN DEL VRP .....3
IV. MÉTODOS DESOLUCIÓN.............................................3
A. Métodos Exactos ..........................................................3
B. Métodos Aproximados .................................................4
1)
Algoritmos de Enjambre.......................................4
2)
Algoritmos Evolutivos..........................................4
3)
Sistemas Inmunes Artificiales ..............................4
4)
Algoritmos de BúsquedaLocal ............................5
5)
Algoritmos Constructivos.....................................5
6)
Algoritmos de Dos Fases......................................5
7)
Algoritmos Híbridos.............................................5
V. CONCLUSIONES .............................................................6
VI. TRABAJOS FUTUROS ....................................................6APÉNDICE .............................................................................6
REFERENCIAS ......................................................................6

I. INTRODUCCIÓN

E

L problema de enrutamiento de vehículos (VRP) es un
problema de optimización combinatoria de
gran
importancia en diferentes entornos logísticos, consiste en
servir una serie de clientes ubicadosgeográficamente de
manera dispersa, para atenderlos se cuenta con una flota de
vehículos que parten desde un deposito central, el problema
consiste en asignar a cada vehículo una ruta de clientes, de
manera que se minimice el costo de transporte.

*rajaquep@unal.edu.co, estudiante de Maestría en Ingeniería de Sistemas y
Computación, Universidad Nacional de Colombia

Diferentes variantesdel problema, que incluyen restricciones
adicionales y la incorporación de múltiples variables, son
propuestas como una aproximación generalizada a problemas
reales de enrutamiento de vehículos, así como también se han
propuesto diferentes métodos para encontrar soluciones a
estos problemas. Este documento realiza un estudio del estado
del arte del problema, realizando una revisión detalladade los
métodos de solución que han sido propuestos, haciendo
especial énfasis en los métodos heurísticos y el problema de
enrutamiento de vehículos con ventanas de tiempo,
organizándose de la siguiente manera: (1) Se presenta una
descripción del problema; (2) Se ilustran diferentes entornos
reales de aplicación del VRP; (3) Se describe una recopilación
estructurada de las diferentes técnicaspropuestas para
solucionar el VRP y sus variantes; (4) Por último, se presentan
las conclusiones derivadas de este estudio.

II. PROBLEMA DE ENRUTAMIENTO DE VEHÍCULOS
Uno de los primeros estudios que trataron el problema de
enrutamiento de vehículos se remonta al año 59, en este
trabajo Dantzig y Ramser [1] tratan un problema de despacho
con camiones, este problema surge como unageneralización
del problema clásico del agente viajero (TSP) en el que un
vendedor tiene que visitar una serie de clientes una sola vez,
para luego volver al lugar de partida, construyendo una
camino hamiltoneano 1 sobre el grafo constituido por los
clientes (vértices) y los caminos posibles entre un cliente y
otro (aristas) .
El VRP se representa como un conjunto de nodos a ser
visitados...