Enrutamiento De Vehículos Con Ventanas De Tiempo - Vrptw

Enrutamiento de vehículos con ventanas de tiempo
(Vehicle Routing Problem with time windows - VRPTW)

Integrantes: Carlos Fernández Alfonso Muñoz Javier Salas Profesor: Alfredo Candia, Ayudante: Francisco Pérez Carrera: Ingeniería Civil Industrial

Curicó, Miércoles 28 de junio de 2012

_________________________________Enrutamiento de vehículos con ventanas de tiempo

Contenido
1. 2.3. Contextualización ........................................................................................................................ 3 Motivación .................................................................................................................................. 4 Bases teóricas.............................................................................................................................. 7 3.1. 3.2. 3.3. 4. Modelación matemática del problema ............................................................................... 7 Explicación de las restricciones ........................................................................................... 9 Discusión de la complejidad computacional..................................................................... 10

Métodos heurísticos de resolución ........................................................................................... 10 4.1. 4.2. 4.3. 4.4. 4.5. 4.6. Heurísticas de Ahorro ........................................................................................................ 11 Heurísticas de Inserción.................................................................................................... 11 Heurísticas de Mejora/Intercambio .................................................................................. 11 Heurísticas Clúster First, Route Second ............................................................................ 11 Heurísticas Route First, Cluster Second ............................................................................ 11Metaheurísticas................................................................................................................. 11

5. 6. 7. 8.

Aplicaciones industriales ........................................................................................................... 12 Parámetros del caso.................................................................................................................. 12 Implementación del problema .................................................................................................. 17 Solución del problema............................................................................................................... 18 8.1. 8.2. 8.3. Rutas vehiculares.............................................................................................................. 19 Tiempos de atención ......................................................................................................... 20 Costo total anual ............................................................................................................... 21

9.

Discusión deresultados............................................................................................................. 21

Proyecto de licenciatura. Fernández, Muñoz, Salas

2

_________________________________Enrutamiento de vehículos con ventanas de tiempo

1.

Contextualización

Los problemas de rutas de vehículos (Vehicle Routing Problem - VRP) en realidad son un amplio conjunto de variantes y personalizaciones de problemas, desde los más sencillos hasta algunos quehoy en día siguen siendo materia de investigación. En ellos en general, se trata de averiguar las rutas de una flota de transporte para dar servicio a determinados clientes. Este tipo de problemas pertenece a los problemas de optimización combinatoria. A continuación desarrollaremos nuestro proyecto con una empresa dedicada al rubro de los alimentos, la cual está ubicada en la ciudad de Talca....