Ruteo

INTRODUCCIÓN AL PROBLEMA DE RUTEO DE VEHÍCULOS CON CAPACIDAD
28 de enero de 2010

Índice general
1. Problema de Ruteo de Vehículos
1.1. Problema de Optimización . . . . . . . . . . . . . . . . . . . . . . 1.1.1. 1.1.2. 1.2. 1.3. 1.2.1. 1.3.1. 1.3.2. 1.3.3. 1.3.4. Problemas

4
5 6 7 9 11 11 12 14 15 22 . . . . . . . . . . . . . . . . . . .

P

y

NP

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

Problemas combinatorios

Variaciones del VRP . . . . . . . . . . . . . . . . . . . . . . . . . Características de los principales componentes del VRP Problema del Agente Viajero (TSP). Formulación matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problema del Agente Viajero (TSP) múltiple

Problema de Ruteo de Vehículos conCapacidad (CVRP) Extensiones para los modelos de ujo de vehículos

2. Métodos de solución exactos para el CVRP
2.1. Método de Branch and Bound (B&B) 2.1.1. 2.1.2. 2.1.3. 2.1.4. 2.1.5. 2.1.6. 2.1.7. 2.2. 64 2.2.1. Esquema de ramicación de Bellmore y Malone . . . . . . . . . . . . . . . . . . . . . Bounding (Acotamiento) . . . . . . . . . . . . . . . . . . . Branching (ramicación) . . . . . . .. . . . . . . . . . . . Método B&B para el CVRP . . . . . . . . . . . . . . . . . Relajaciones básicas para el CVRP Cotas avanzadas . . . . . . . . . . . .

25
25 28 29 33 33 43 53 56

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

Teoría de la dualidad . . . . . . . . . . . . . . . . . . . . . Subgradiente de una función convexa . . . . . . . . . . . .

Solución de un programa linealentero por Relajación de Lagrange 56 65

3. Métodos de solución metaheurísticos para el CVRP
3.1. Algoritmos Genéticos . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1. 3.1.2. 3.1.3. 3.1.4. 3.1.5. 3.2. Orígenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . Aplicaciones de los Algoritmos Genéticos Ventajas de los algoritmos genéticos . . . . . . . . . . . . . . . . . . . . .

7071 72 74 75 75 75 76

Características de los algoritmos genéticos . . . . . . . . . Denición . . . . . . . . . . . . . . . . . . . . . . . . . . .

Operadores genéticos . . . . . . . . . . . . . . . . . . . . . . . . .

1

ÍNDICE GENERAL

2

3.2.1. 3.2.2. 3.2.3. 3.3. 3.4.

Operador de Selección . . . . . . . . . . . . . . . . . . . . Operador de Cruce . . . . . . . . . . . . . . .. . . . . . . Operador de Mutación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76 77 78 78 81 81 81 82 82 83 85 92 92 93 94 97

Descripción del algoritmo genético simple 3.4.1. 3.4.2. 3.4.3. Denición del problema Población inicial

Aplicación de los algoritmos genéticos al CVRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . .

Función Fitness . . . . . . . . . . . . . . . . . . . . . . . . Operador de Selección . . . . . . . . . . . . . . . . . . . . Operadores de Cruce . . . . . . . . . . . . . . . . . . . . . Operador de Mutación . . . . . . . . . . . . . . . . . . . . Evolución . . . . . . . . . . . . . . . . . . . . . . . . . . . Generalidades del algoritmo . . . . . . . . . . . . . . . . .Característica del ACO . . . . . . . . . . . . . . . . . . . Aplicación de la optimización por colonia de hormigas al CVRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82 3.4.4. 3.4.5. 3.4.6. 3.5. 3.5.1. 3.5.2. 3.5.3. 3.5.4. 3.5.5.

Optimización por Colonia de Hormigas . . . . . . . . . . . . . . .

Algoritmo Colonia de Hormigas . . . . . . . . . . . . . . . 100

A. Códigos en GAMSpara resolver el CVRP
A.3. Relajación b-matching ejemplo 6

105

A.1. Relajación TP ejemplo 5 . . . . . . . . . . . . . . . . . . . . . . . 105 A.2. Relajación AP ejemplo 5 . . . . . . . . . . . . . . . . . . . . . . . 106 . . . . . . . . . . . . . . . . . . 107 . . . . . . . . . . . . . 108 A.4. Cotas basadas en arborescencia ejemplo 7

B. Solución del CVRP mediante metaheurísticas en...