Tesis OptimizacióN Vrptw

67 %
33 %
Information about Tesis OptimizacióN Vrptw
Education

Published on January 23, 2009

Author: vyepesp

Source: slideshare.net

Description

YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis Doctoral. Escuela Técnica Superior de Ingenieros de Caminos, Canales y Puertos. Universidad Politécnica de Valencia. 352 pp.

El propósito de la tesis consiste en la presentación de un modelo económico de distribución de mercancías que generalice los problemas de rutas sometidos a restricciones temporales de servicio “vehicle routing problem with time windows” (VRPTW) y de un conjunto de técnicas heurísticas y metaheurísticas capaces de resolverlo eficientemente. El trabajo sistematiza el conjunto de métodos de optimización heurística y establece el estado de la técnica en relación con los procedimientos empleados en la resolución del problema VRPTW y sus extensiones. Tras constatar ciertas discrepancias entre los modelos teóricos y los casos reales, la tesis define una función objetivo que mide la rentabilidad económica de las operaciones, y flexibiliza los horarios de entrega con penalizaciones que reflejen la insatisfacción de los clientes. Asimismo se contempla la posibilidad de contar con flotas heterogéneas de vehículos con costes fijos y variables diferenciados, así como capacidad de carga, velocidad y jornadas laborales distintas, y con la posibilidad del uso múltiple. Se incorpora la asimetría en la duración de los viajes, con tiempos de aproximación y de alejamiento que modulen el nivel de congestión por tráfico y otras dificultades de acceso. También es posible el ajuste de diferentes costes horarios en función de las horas extraordinarias y penalizaciones por ruptura en la llegada al depósito.

La tesis presenta una novedosa heurística de construcción secuencial de rutas basada en criterios económicos (HESECOR) capaz de resolver el modelo propuesto y que, en el caso del problema VRPTW básico, ha llegado en algunos casos a alcanzar la mejor solución publicada. También se han presentado un conjunto de metaheurísticas basadas en la búsqueda secuencial por entornos. Del análisis del comportamiento de dichas técnicas a los problemas básicos y generalizados presentados, se aportan conclusiones de interés práctico, tanto para la optimización heurística de los problemas combinatorios, como para la toma de decisiones en las empresas dedicadas al transporte.

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW E.T.S. de Ingenieros de Caminos, Canales y Puertos http://personales.upv.es/vyepesp/ Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW TESIS DOCTORAL Autor: Víctor Yepes Piqueras Dirigida por: Dr. Josep R. Medina Folgado >ValenciaSeptiembre2002 E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística aplicada a las redes de transporte del tiporedes Optimización heurística económica económica aplicada a las VRPTW de transporte del tipo VRPTW Objetivos Índice Introducción 1 Los problemas de optimización combinatoria 2 Modelos de distribución física y transporte 3 El problema de las rutas de vehículos con restricciones en el horario de servicio: VRPTW 4 Definición del modelo de problema de rutas 5 Propuestas de estrategias de búsqueda secuencial por entornos para la resolución del modelo VRPTW 6 Resumen y conclusiones 5 7 E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Motivación INDICE Introducción Globalización Incremento de las Los problemas de optimización de los mercados expectativas de los clientes combinatoria El transporte Modelos de distribución como física y transporte ventaja El problema de las Exigencia de productos Desarrollo de los rutas de competitiva vehículos con y servicios de calidad intercambios comerciales restricciones en el horario de servicio: VRPTW Definición del Decisiones empresariales modelo de problema de Reducción de Disminución de rutas costes inversión Mejora de servicio Propuestas de estrategias de búsqueda secuencial por entornos Resolución de problemas de transporte para la resolución del modelo VRPTW Sistemas inteligentes Resumen y E.T.S. de Ingenieros de Caminos, Canales y Puertos conclusiones >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW La logística y los problemas de distribución física INDICE A su Introducción Distribución física tiempo Los problemas de optimización Materias primas combinatoria Modelos de Origen Destino Recursos de producción distribución física y transporte Productos finales El problema de las rutas de Logística empresarial vehículos con Al coste restricciones en el horario más bajo de servicio: VRPTW Procesamiento Control de Definición del de pedidos Servicio al modelo de inventarios cliente problema de Previsión de Ubicación fábricas rutas la demanda Servicios de y almacenes Propuestas de Distribución y estrategias de reparación transporte búsqueda Tratamiento Recuperación y secuencial por entornos mercancías tratamiento de para la devueltas desperdicios resolución del Almacenamiento modelo VRPTW Resumen y E.T.S. de Ingenieros de Caminos, Canales y Puertos conclusiones >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW La logística y los problemas de distribución física INDICE Introducción Los problemas de Gran variación de costes en las empresas optimización TRANSPORTE: combinatoria Modelos de distribución física y transporte Costes logísticos: 4-32%. Ballou (1991) El problema de las rutas de vehículos con Costes de transporte: 1/3-2/3 de los costes restricciones en el horario logísticos. Ballou (1991) de servicio: VRPTW Definición del 76,5% del transporte de mercancías en modelo de problema de vehículos. Halse (1992) rutas Propuestas de estrategias de búsqueda secuencial por entornos para la resolución del modelo VRPTW Resumen y E.T.S. de Ingenieros de Caminos, Canales y Puertos conclusiones >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Objetivos, contribución y estructura de la tesis INDICE Introducción Los operadores del transporte Los problemas de optimización deben tomar decisiones combinatoria Modelos de distribución física y transporte El problema de las rutas de vehículos con Procedimientos robustos, flexibles restricciones en el horario de servicio: y rápidos que proporcionen soluciones VRPTW Definición del competitivas modelo de problema de rutas Propuestas de estrategias de búsqueda secuencial Trascendencia económica Complejidad problemas por entornos para la resolución del del transporte de distribución modelo VRPTW Resumen y E.T.S. de Ingenieros de Caminos, Canales y Puertos conclusiones >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Objetivos, contribución y estructura de la tesis INDICE Introducción Contribuciones: Los problemas de optimización combinatoria Modelos de Modelo de distribución con restricciones distribución física y horarias y objetivo económico. transporte El problema de las rutas de Ventanas temporales de flexibilidad vehículos con restricciones adaptable. en el horario de servicio: VRPTW Incorporación de congestión, asimetrías, Definición del modelo de jornadas laborables variables y problema de rutas penalizaciones Propuestas de estrategias de búsqueda Taxonomía de estrategias para la secuencial por entornos optimización combinatoria. para la resolución del modelo VRPTW Resumen y E.T.S. de Ingenieros de Caminos, Canales y Puertos conclusiones >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Objetivos, contribución y estructura de la tesis INDICE Introducción Contribuciones: Los problemas de optimización combinatoria Modelos de Heurística económica de construcción de distribución física y soluciones factibles (HESECOR). transporte El problema de las rutas de Operadores específicos para resolver el vehículos con restricciones VRPTW y generalizaciones. en el horario de servicio: VRPTW Conceptos de márgenes de viaje, esperas Definición del modelo de ineludibles y ventanas temporales efectivas. problema de rutas Nuevas metaheurísticas: perturbación de Propuestas de estrategias de búsqueda la velocidad, exploración convergente, secuencial por entornos búsqueda local adaptativa y otras. para la resolución del modelo VRPTW Resumen y E.T.S. de Ingenieros de Caminos, Canales y Puertos conclusiones >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW La toma de decisiones en las empresas INDICE Introducción ¿Existe Recursos Requisitos Los problemas de optimización escasos solución? Producción combinatoria Personal Modelos de Horas de distribución Presupuesto descanso física y ¿Cuál es transporte Tiempo Otros la mejor? El problema de las rutas de vehículos con restricciones en el horario Método científico de servicio: VRPTW Definición del modelo de problema de rutas Investigación Operativa Propuestas de estrategias de búsqueda secuencial Optimización Incertidumbre por entornos para la resolución del modelo Realidad Modelo Validación Predicción Decisión Cambios VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Algoritmia y complejidad computacional INDICE Introducción Complejidad problema de decisión Los problemas de optimización combinatoria Modelos de distribución física y Rendimiento algorítmico transporte El problema de las rutas de vehículos con Polinómica Exponencial restricciones Cualquiera se en el horario de servicio: VRPTW puede transformar Definición del en tiempo polinomial P NP modelo de problema de rutas Propuestas de Sin estrategias de NP-completo demostrar búsqueda secuencial P⊆NP por entornos Basta uno para la ¿P=NP? resolución del modelo NP-hard VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Técnicas de resolución de problemas de O.C. INDICE Introducción Optimización combinatoria: Los problemas de optimización “contiene los dos elementos que hacen atractivo un combinatoria problema a los matemáticos: planteamiento sencillo y Modelos de distribución dificultad de resolución” (Garfinkel, 1985) física y transporte El problema de las rutas de Explosión combinatoria vehículos con restricciones en el horario de servicio: VRPTW Mota de polvo Ruta más corta Definición del 1041 modelo de 1.86 x problema de en la atmósfera entre 37 rutas Propuestas de estrategias de Mota de polvo Ruta más corta búsqueda 10155 4.66 x secuencial en el Universo entre 100 por entornos para la resolución del modelo 25 nodos en 5 siglos VRPTW 20 nodos en 50 m 20 billones en 1 seg Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Técnicas heurísticas INDICE Introducción Procedimientos sencillos Heurísticas Los problemas de optimización Algoritmos específicos combinatoria Modelos de “tailored algorithms” (Telfar, 1994) distribución física y transporte Flexibilidad en el manejo de las El problema de las rutas de características propias del problema vehículos con restricciones en el horario Éxito regla 80/20 (Ho, 1994) de servicio: VRPTW Metaheurísticas Definición del Métodos generales (Osman et al., 1996) modelo de problema de Emulan estrategias eficientes rutas Propuestas de en la Naturaleza e inteligencia artificial estrategias de búsqueda secuencial Guían procedimientos específicos por entornos para la resolución del Sistemas inteligentes modelo VRPTW (Goonatilake et al., 1995) Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Técnicas metaheurísticas INDICE Algoritmos Introducción Inteligencia genéticos Los problemas de Evolución optimización artificial combinatoria Lógica borrosa biológica Modelos de distribución Algoritmos física y Redes transporte meméticos neuronales El problema de las rutas de METAHEURÍSTICAS vehículos con Estrategias Búsqueda restricciones evolutivas en el horario tabú de servicio: VRPTW Comportamiento GRASP Definición del modelo de de los insectos problema de Mecánica Búsqueda rutas local guiada estadística Propuestas de Colonias de estrategias de búsqueda hormigas Búsqueda secuencial Aceptación ... por entornos local iterada Cristalización para la por umbrales resolución del ... simulada modelo VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Aplicaciones de sistemas inteligentes INDICE Introducción Aprenden, Los problemas de optimización descubren, se combinatoria adaptan, son Modelos de distribución flexibles, explican física y Algoritmos Genéticos (“GA”) transporte situaciones ... - transportes, redes de gas y electricidad El problema de las - procesos industriales, circuitos rutas de vehículos con - evaluación de créditos e inversiones restricciones en el horario Redes Neuronales (“NN”) de servicio: - análisis de datos: diques, lluvias, transportes VRPTW - navegación, robótica, tráfico Definición del modelo de - riesgo de inversiones, robo tarjetas problema de Cristalización Simulada (“SA”) rutas - análisis de ondas, optimización de NN Propuestas de estrategias de - transportes, diseño de circuitos integrados búsqueda - procesado de imagen, plantas de fabricación secuencial por entornos Sistemas Borrosos (“FS”) para la resolución del - enfoque automático de cámaras modelo VRPTW - control de electrodomésticos, tráfico Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Técnicas de resolución de problemas de O.C. INDICE Introducción Los problemas de optimización combinatoria Modelos de distribución física y transporte El problema de las rutas de vehículos con restricciones en el horario de servicio: VRPTW Definición del modelo de problema de rutas Propuestas de estrategias de búsqueda secuencial por entornos para la resolución del modelo VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Evaluación de las heurísticas y las metaheurísticas INDICE Introducción Los problemas de optimización combinatoria Robustez Modelos de distribución física y transporte El problema de las rutas de vehículos con Comparación restricciones Calidad de Tiempo de en el horario de servicio: entre VRPTW la solución cálculo estrategias Definición del modelo de problema de rutas Propuestas de estrategias de búsqueda Barr et al. (1995) secuencial Flexibilidad por entornos para la resolución del modelo VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Evaluación de las heurísticas y las metaheurísticas INDICE Introducción Óptimos de Pareto Los problemas de optimización combinatoria Modelos de distribución física y transporte El problema de las rutas de vehículos con restricciones en el horario de servicio: VRPTW Definición del modelo de problema de rutas Propuestas de estrategias de búsqueda secuencial por entornos para la resolución del modelo VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW > Modelos de distribución física y transporte Características de los problemas de asignación y programación de rutas Problemas básicos de distribución E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Características de los problemas de rutas INDICE Introducción Almacén (5) Tipo de Tamaño de Los problemas de optimización Número flota (4) la flota (3) combinatoria rutas (3) Modelos de Mercancías (2) distribución física y transporte Grafo (4) Restricciones El problema de las Naturaleza de horarias (7) rutas de vehículos con la demanda (6) restricciones en el horario 8,8·109 Costes (3) de servicio: VRPTW 280 años Localización de Ciclos de Definición del modelo de la demanda (3) problema de servicio (2) rutas Operaciones (5) Propuestas de Duración estrategias de búsqueda Precedencias (3) ruta (5) secuencial Capacidad por entornos para la vehículos (3) Velocidad resolución del Función modelo vehículos (4) VRPTW objetivo (9) Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Problemas básicos de distribución INDICE Introducción Los problemas de Traveling Salesman optimización Problem combinatoria Modelos de Cobertura de puntos TSP distribución física y transporte El problema de las rutas de vehículos con Multiple Traveling restricciones en el horario Salesman Problem de servicio: VRPTW m-TSP Definición del modelo de problema de rutas Propuestas de estrategias de Vehicle Routing búsqueda secuencial Problem por entornos para la VRP resolución del modelo VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Vehicle Routing Problem VRP INDICE Introducción Asymmetric VRP AVRP VRP with Satellite Facilities VRPSF Los problemas de Capacited VRP CVRP Open VRP OVRP optimización combinatoria VRP with Length Constraint VRPLC Location VRP LVR Modelos de Period VRP PVRP Dynamic VRP distribución DVRP física y Fixed Routes Problem FRP VRP with Variable Travel Times transporte VRPVRT Fleet Size and Mix VRP FSMVRP El problema de las VRP with Variable Access Time VRPVADT rutas de Vehicle Fleet Mix with VFMVRC vehículos con Stochastic VRP SVRP restricciones Variable Unit Running Cost en el horario VRP with Stochastic Travel VRPST VRP with Heterogeneous Fleet VRPHE de servicio: Times VRPTW VRP with Backhauls VRPB VRP with Stochastic Demands VRPSD Definición del VRP with Deliveries and VRPDB modelo de VRP with Stochastic Demands VRPSDC problema de Backhauls and Customers rutas Pickup and Delivery Problem PDP VRP with Multiple Use of VRPM Propuestas de Vehicles Multi Compartment VRP MCVRP estrategias de búsqueda VRP with Split Delivery VRPSDV Min-max VRP min-maxVRP secuencial por entornos VRP with Time Windows VRPTW VRP with Precedence VRPPC para la resolución del VRP with Soft Time Windows Constraints VRPSTW modelo Multiple Depot VRP MDVRP VRPTW VRP with Time Deadlines VRPTD Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW El problema VRPTW INDICE Introducción Una visita por cliente Los problemas de optimización Ruta empieza y acaba en base combinatoria Flota homogénea Modelos de distribución física y Capacidad en vehículos transporte Horarios de entrega El problema de las rutas de vehículos con restricciones en el horario Pullen y Webb (1967) de servicio: Literatura temprana: VRPTW Knight y Hofer (1968) casos particulares Definición del modelo de problema de Madsen (1976) rutas Propuestas de estrategias de búsqueda Solomon (1987) Hoy: secuencial por entornos para la Proyecto GreenTrip: problema clásico resolución del modelo 40 años/investigador 1996-98 VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW El problema VRPTW: aplicaciones reales INDICE Área económica Aplicación Introducción Los problemas de Distribución de piezas de repuesto Industria del automóvil optimización combinatoria Combustible, gas natural, hormigón Materias primas Modelos de Grandes superficies y pequeños comercios Transporte de alimentos distribución física y transporte Reparto de medicamentos a farmacias Salud El problema de las Distribución de periódicos y revistas Prensa rutas de vehículos con Reparto y recogida de dinero en efectivo Banca restricciones en el horario Recogida de basuras, limpieza de calles, reparto de correo Sector público de servicio: VRPTW Recogida de ganado, leche, cereales, etc. Agricultura Definición del modelo de Suministro de piezas o mercancías entre almacenes Industria problema de rutas Reparación de electrodomésticos a domicilio. Servicios Propuestas de Rutas de autobuses escolares Educación estrategias de búsqueda secuencial Programación de actividades Planificación por entornos para la Rutas de aviones espías, logística militar Defensa resolución del modelo Planificación de flotas de aviones, camiones, trenes, etc. Transporte VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Modelo matemático del problema VRPTW INDICE Introducción ∑∑ ∑ c x Minimizar Los problemas de ij ijk optimización k∈V i∈N j∈N combinatoria Modelos de ∑∑x distribución =1 ∀i ∈ C Sujeto a física y ijk transporte k∈V j∈N ∑q ∑ x ≤ Q El problema de las ∀k ∈ V rutas de i ijk vehículos con i∈C j∈N restricciones ∑ x = 1 ∀k ∈V en el horario de servicio: 0 jk VRPTW j∈N ∑x −∑x =0 ∀h ∈ C , ∀k ∈ V Definición del modelo de ihk hjk problema de i∈N j∈N rutas ∑x =1 ∀k ∈ V i , n +1, k Propuestas de i∈N estrategias de x (b + tij − b jk ) ≤ 0 búsqueda ∀i, j ∈ N , ∀k ∈ V secuencial ijk ik por entornos para la ei ≤ bik ≤ ui ∀i ∈ N , ∀k ∈ V resolución del modelo xijk ∈ {0,1} ∀i , j ∈ N , ∀k ∈ V VRPTW Larsen (1999) Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Complejidad computacional del VRPTW INDICE VRP → NP-hard Introducción Los problemas de (Lenstra y Rinnooy Kan, 1981) optimización combinatoria Modelos de distribución física y VRPTW → NP-hard transporte El problema de las Poco probable rutas de vehículos con llegar a solución restricciones en el horario de servicio: óptima en VRPTW tiempo polinomial Definición del modelo de problema de rutas Solución viable Propuestas de Con rutas fijas estrategias de TSPTW → búsqueda secuencial VRPTW → por entornos para la NP-completo resolución del NP-completo modelo (Savelsberg, 1985) VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Algoritmos de aproximación y heurísticas INDICE Algoritmos secuenciales Introducción Backer y Schaffer (1986) Los problemas de optimización Solomon (1987) combinatoria van Ladeghem (1988) Modelos de Construcción distribución Ioannou et al. (2001) física y transporte Algoritmos paralelos de rutas El problema de las Povtin y Rousseau (1993) rutas de vehículos con Antes y Derigs(1995) restricciones Heurísticas en el horario Russell (1995) de servicio: VRPTW VRPTW Kontoravdis y Bard (1995) Definición del Mejora de rutas modelo de problema de Russell (1977); Savelsbergh (1986,1990,1992); Solomon et al. rutas (1988); Baker y Schaffer (1986); van Landeghem (1988); Thompson Propuestas de y Psaraftis (1993); Potvin y Rousseau (1995) estrategias de búsqueda secuencial Mixtas por entornos para la Kontoravdis y Bard (1995); Antes y Derigs (1995); Russell (1995); resolución del modelo Prosser y Shaw (1996); Cordone y Wolfler-Calvo (1997); Shaw VRPTW (1997, 1998); Caseau y Laburthe (1999); Bräysy (2001) Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Heurística secuencial de Solomon (1987) INDICE Introducción Cliente más alejado al depósito Criterio de inicio de ruta Los problemas de Cierre del inicio de servicio más temprano optimización combinatoria Modelos de Criterio de inserción de cliente distribución física y c 1 [i (u ), u , j (u )] = min c 1 (i p −1 , u , i p ) transporte (Paso 1 4 .2 ) El problema de las p =1 ,..., m rutas de c1 (i, u, j ) = α1c11 (i, u, j ) + α 2 c12 (i, u, j ) vehículos con restricciones α1 + α 2 = 1, α1 ≥ 0, α 2 ≥ 0 en el horario de servicio: c11 (i, u , j ) = d iu + d uj − Gd ij VRPTW G≥0 Definición del ( ) modelo de c12 b ju − b j problema de c 2 [i (u *), u*, j (u *)] = max c 2 [i (u ), u , j (u )] rutas (Paso 2 4 .6 ) Propuestas de u estrategias de c2 (i, j , u ) = λ ⋅ d 0u − c1 (i, j , u ) búsqueda λ≥0 secuencial por entornos para la resolución del modelo VRPTW λ=2; G=1; α1=1; α2=0 Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Búsqueda local INDICE Introducción Solución Los problemas de inicial T optimización combinatoria Modelos de distribución Transformación física y transporte de T en T’ El problema de las rutas de vehículos con restricciones en el horario miopía de servicio: ¿Criterio VRPTW Definición del de parada ? SI modelo de problema de rutas NO Propuestas de estrategias de búsqueda secuencial NO SI Óptimo por entornos ¿Es T’ mejor Reemplazar para la resolución del local que T ? T por T’ modelo VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Taxonomía de los operadores de cambio INDICE Introducción Movimientos dentro de una ruta Los problemas de optimización combinatoria Modelos de distribución física y transporte El problema de las rutas de vehículos con 1-swap restricciones 2-opt en el horario 1-swap* de servicio: VRPTW Definición del modelo de problema de rutas Propuestas de estrategias de búsqueda secuencial por entornos para la resolución del 1-relocate IOPT modelo VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Taxonomía de los operadores de cambio INDICE Introducción Movimientos entre dos rutas Los problemas de optimización combinatoria Modelos de distribución 2-opt* física y 2-relocate 2-swap CROSS transporte 2-opt** El problema de las rutas de Otros vehículos con restricciones en el horario Reconstrucción de servicio: ICROSS Or-opt GENIUS VRPTW Reductor rutas Definición del Intercambio vehículos modelo de Movimientos entre tres rutas problema de Sustitución vehículos rutas Propuestas de estrategias de búsqueda secuencial por entornos para la 3-swap 3-relocate 3-opt* Cíclicas resolución del modelo VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Metaheurísticas VRPTW INDICE Algoritmos genéticos Introducción Los problemas de Garcia et al. (1994) optimización combinatoria Blanton et al. (1993) Thangiah et al. (1994) Modelos de Thangiah (1995) Carlton (1995) distribución física y Potvin et al. (1996) De Backer et al. (1997) transporte Thangiah et al. (1994) Badeau et al. (1997) El problema de las Berger et al. (1998) Chiang et al. (1996) rutas de Potvin et al. (1996) vehículos con Bräysy (1999) Tan et al. (2000) restricciones Chiang et al. (1997) en el horario Berger et al. (2001) Li et al. (2001) de servicio: Schulze et al. (1999) VRPTW Bent et al. (2001) Taillard et al. (1997) Definición del modelo de Brandao (1999) Estrategias problema de rutas Cordeau et al. (2000) evolutivas Propuestas de estrategias de búsqueda Homberger et al. (1999) secuencial por entornos GRASP Bräysy et al. (2000) para la resolución del modelo Kontoravdis et al. (1995) VRPTW Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Metaheurísticas VRPTW INDICE Introducción Colonias de hormigas Redes Los problemas de optimización combinatoria BÚSQUEDA DISPERSA neuronales Modelos de distribución Rochat et al. (1995) física y transporte Reconstrucción Potvin et al. (1999) El problema de las rutas de vehículos con restricciones Gambardella et al. (1999) en el horario Schrimpf et al. (2000) de servicio: VRPTW Definición del Búsqueda local guiada modelo de Búsqueda en entornos amplios problema de rutas Kilby et al. (1999) Shaw (1997, 1998) Propuestas de De Backer et al (2000) estrategias de Bent et al. (2001) búsqueda Búsqueda local iterada secuencial Búsqueda en entornos variables por entornos para la Ibaraki et al. (2001) resolución del Rousseau et al. (2000) modelo ILS VRPTW Bräysy (2001a, 2001b) Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Problemas de Solomon (1987) INDICE Introducción TW ↓ TW ↑ Los problemas de optimización combinatoria Aleatorio R1 R2 Modelos de distribución Agrupado C1 C2 física y transporte Mixto RC 1 RC 2 El problema de las rutas de vehículos con Capacidad Capacidad restricciones pequeña grande en el horario R1-R2 C1 de servicio: VRPTW Definición del 56 problemas modelo de problema de 100 clientes rutas 1 almacén Propuestas de estrategias de Vehículos iguales búsqueda secuencial por entornos Tiempo máximo para la resolución del TW 25%,50%,75%,100% modelo VRPTW C2 RC 1 - RC 2 Resumen y conclusiones E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW Comportamiento de las estrategias de optimización INDICE Introducción 460 Los problemas de 455 optimización Solomon (1987) and combinatoria Potvin et al. (1993) 450 Modelos de distribución 445 física y Thompson et transporte 440 al.(1993) El problema de las 435 NTR rutas de Antes et al. (1995) vehículos con 430 Ioannou et al. (2001) restricciones Cordone et al. (1998) en el horario 425 Russell (1995) de servicio: Caseau et al. (1999) VRPTW 420 Definición del 415 modelo de Bräysy (2001a) problema de 410 rutas 405 Propuestas de

Add a comment

Related presentations

Related pages

Tesis Optimización VRPTW - es.scribd.com

Tesis Optimización VRPTW - Free download as PDF File (.pdf) or read online for free.
Read more

Tesis Optimización VRPTW - Documents

YEPES, V. (2002). Economic heuristic optimization applied to VRPTW type transportation networks. Doctoral Dissertation. Higher Technical School of Civil ...
Read more

Tesis OptimizacióN Vrptw - Education - MySlide.ES

YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis Doctoral. Escuela Técnica Superior de ...
Read more

Optimización heurística económica aplicada a las redes de ...

Optimización heurística económica aplicada a ... Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW [Tesis doctoral ...
Read more

Ü|RpÀ 7ºË Ù²M»§Í K Û

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW iv Prefacio La presente Tesis Doctoral, que tiene por título ...
Read more

Optimización heurística económica aplicada a las redes de ...

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW E.T.S. de Ingenieros de Caminos, Canales y Puertos ...
Read more

Optimización heurística económica aplicada a las redes de ...

Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. on ResearchGate, the professional network for scientists.
Read more