DISE OS

Heur´ısticas para Problemas de
Ruteo de Veh´ıculos
Alfredo Olivera
Instituto de Computaci´on, Facultad de Ingenier´ıa,
Universidad de la Rep´
ublica, Montevideo, Uruguay.
aolivera@fing.edu.uy
Agosto 2004

Resumen
Desde la primera formulaci´on de los Problemas de Ruteo de Veh´ıculos, una gran
cantidad de m´etodos han sido propuestos para su resoluci´
on. Estos m´etodos
incluyen tanto algoritmosexactos como heur´ısticas. En este trabajo se presenta
un relevamiento de algunas de las heur´ısticas que han sido m´
as significativas.
Palabras clave: Ruteo de Veh´ıculos, Heur´ısticas, Optimizaci´
on Combinatoria.

Indice
1 Problemas de Ruteo de Veh´ıculos
1.1 Introducci´
on . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Caracter´ısticas de los Problemas . . . . . . . . . . . . .
1.2.1Los Clientes . . . . . . . . . . . . . . . . . . . . .
1.2.2 Los Dep´ositos . . . . . . . . . . . . . . . . . . . .
1.2.3 Los Veh´ıculos . . . . . . . . . . . . . . . . . . . .
1.3 Formulaci´on Matem´
atica . . . . . . . . . . . . . . . . . .
1.3.1 El Problema del Agente Viajero (TSP) . . . . . .
1.3.2 El Problema de los m Agentes Viajeros (m-TSP)
1.3.3 El Problema con Capacidades (VRP o CVRP) .1.3.4 El Problema con Flota Heterog´enea (FSMVRP)
1.3.5 El Problema con Ventanas de Tiempo (VRPTW)
1.4 M´etodos Exactos . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

2 Heur´ısticas Cl´
asicas para el VRP
2.1 El Algoritmo de Ahorros . . . . . . . . . . . . . . . . . . . . . . .2.1.1 Algoritmo de Ahorros basado en Matching . . . . . . . .
2.2 Heur´ısticas de Inserci´
on . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Inserci´
on Secuencial de Mole & Jameson . . . . . . . . . .
2.2.2 Inserci´
on en Paralelo de Christofides, Mingozzi y Toth . .
2.3 M´etodos Asignar Primero - Rutear Despu´es . . . . . . . . . . . .
2.3.1 Heur´ıstica de Barrido o Sweep . . . . . . . . .. . . . . .
2.3.2 Heur´ıstica de Asignaci´on Generalizada de Fisher y Jaikumar
2.3.3 Heur´ıstica de Localizaci´on de Bramel y Simchi-Levi . . .
2.4 M´etodo Rutear Primero - Asignar Despu´es . . . . . . . . . . . .
2.5 Algoritmos de P´etalos . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Procedimientos de B´
usqueda Local . . . . . . . . . . . . . . . . .
2.6.1 El operador λ-intercambio . . .. . . . . . . . . . . . . . .
2.6.2 El algoritmo de Lin-Kernigham . . . . . . . . . . . . . . .
2.6.3 El operador Or-opt . . . . . . . . . . . . . . . . . . . . . .
2.6.4 Operadores de Van Breedam . . . . . . . . . . . . . . . .
2.6.5 GENI y GENIUS . . . . . . . . . . . . . . . . . . . . . . .
2.6.6 Transferencias c´ıclicas . . . . . . . . . . . . . . . . . . . .

1
1
2
2
2
3
3
4
5
6
7
8
9
10
1012
13
14
15
16
16
17
18
20
21
21
22
24
24
25
25
27

3 Extensiones de las heur´ısticas cl´
asicas
28
3.1 Algoritmo de Ahorros . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Heur´ısticas de Inserci´
on Secuencial . . . . . . . . . . . . . . . . . 30
3.3 Heur´ısticas de Inserci´
on en Paralelo . . . . . . . . . . . . . . . . . 32

i

3.4
3.5

Algoritmo de Barrido . . . . . . . . . . . . . . .. . . . . . . . . .
Rutear Primero - Asignar Despu´es . . . . . . . . . . . . . . . . .

4 Metaheur´ısticas
4.1 Algoritmos de Hormigas . . . . . . . . . . . .
4.1.1 Ant System H´ıbrido para VRP . . . .
4.1.2 MACS para VRPTW . . . . . . . . .
4.2 Tabu Search . . . . . . . . . . . . . . . . . . .
4.2.1 Tabu Search para el VRP . . . . . . .
4.2.2 Tabu Search para el VRPTW . . . . .
4.3 AlgoritmosGen´eticos . . . . . . . . . . . . . .
4.3.1 Algoritmos Gen´eticos para el TSP . .
4.3.2 Algoritmos Gen´eticos para el VRP . .
4.3.3 Algoritmos Gen´eticos para el VRPTW

ii

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
....