advertisement

Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW)

50 %
50 %
advertisement
Information about Optimización del problema generalizado de las rutas con restricciones...
Technology

Published on January 27, 2009

Author: vyepesp

Source: slideshare.net

Description

La ponencia presenta un algoritmo heurístico secuencial de construcción de rutas que permite la resolución del problema generalizado de las rutas con restricciones temporales relajadas y de capacidad “capacitance vehicle routing problem with soft time windows” (CVRPSTW). Se adopta una función objetivo basada en la rentabilidad que supera las deficiencias observadas en los modelos clásicos, y que evalúa mediante penalizaciones económicas el quebranto de las restricciones, lo cual mejorará la exploración del espacio de soluciones. Se introducen criterios mejorados de inicio de rutas así como una nueva métrica de proximidad basada en la rentabilidad marginal que perfecciona los principios de ahorro espacio-temporales habituales. La heurística aborda generalizaciones en las suposiciones clásicas del problema tales como la uniformidad en las características de la flota y los clientes, autorizando el paso de distintos recorridos por un nodo o el inicio de varias rutas por un vehículo. Asimismo se describen los criterios que han parametrizado la resolución del problema, lo cual facilita la consecución de conjuntos de soluciones factibles susceptibles de mejora con sistemas inteligentes de optimización.
advertisement

IV Congreso de Ingeniería del Transporte CIT-2000 Valencia, 7-9 Junio 2000 Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Víctor Yepes Director del Área de Producto de la Agència Valenciana del Turisme. Generalitat Valenciana. Josep R. Medina Director del Laboratorio de Puertos y Costas de la Universidad Politécnica de Valencia

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Planificación y Gestión de Redes de distribución de baja demanda: OPTIMIZACIÓN DE RUTAS nº de soluciones crece factorialmente con NC y flota búsqueda determinista del óptimo: INVIABLE técnicas heurísticas: VIABLE repartos de correspondencia, recogida de desechos industriales, atención médica domiciliaria, rutas de autobuses escolares, otros...

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Vehicle Routing Problem with Time Windows (VRPTW) PROBLEMA CLÁSICO Trata de diseñar un conjunto posible de rutas para una flota de vehículos que empiecen y terminen en un depósito de modo que se visiten todos los destinos una sola vez al mínimo coste, satisfaciendo a su vez las restricciones horarias de inicio de servicio en cada cliente. Las ventanas temporales definidas para cada cliente i originan una espera si el vehículo llega antes del límite inferior ei e impiden el inicio del servicio si se supera el límite superior ui. Problema combinatorio difícil NP-completo.

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Figura 1.- Forma de una solución al problema clásico de las rutas de los vehículos con restricciones temporales (VRPTW)

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Métodos de obtención de soluciones factibles al VRPTW Heurísticas de construcción de rutas - secuenciales - paralelas Heurísticas de mejora de rutas -empezando por una solución factible, se inicia una búsqueda local mediante modificaciones de la solución actual Heurísticas mixtas - incluyen simultáneamente procedimientos de construcción y mejora de rutas Metaheurísticas - cristalización simulada - búsqueda tabú - algoritmos genéticos

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Inadecuación del planteamiento clásico del VRPTW Jerarquización en criterios de valoración de las soluciones - primero menor número de rutas posible, luego mínima distancia total recorrida, por último menor tiempo empleado - la realidad impone cuantificar no sólo todos los costes reales de explotación, sino además los ingresos - se debe maximizar la rentabilidad del conjunto de operaciones Las ventanas temporales no son rígidas - puede iniciarse el servicio antes de la hora límite siempre que adoptemos cierta penalización La realidad no es tan simple en sus hipótesis - vehículos distintos con capacidad limitada y jornadas laborables para tripulaciones con costes extraordinarios cuando se trabajan más horas, los vehículos pueden realizar más de una ruta, a los clientes se les puede servir más de una vez, pueden variar los ingresos con la demanda, etcétera.

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Heurística de construcción de rutas con ventanas temporales: algoritmo que elige un criterio para comenzar un itinerario y a continuación reglas para insertar clientes cuando no es posible insertar más clientes, se inicia un nuevo itinerario Solomon (1987) desarrolló I1 para VRPTW que se ha utilizado eficazmente como punto de inicio de metaheurísticas

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Criterios de inicio de una ruta Solomon (I1) determina como criterio de elección del primer cliente aquel que se encuentre más alejado del depósito o el que presente un límite horario de aceptación del servicio más temprano MEJORAS PROPUESTAS Criterio 1: Hora más tardía de llegada del vehículo al depósito. Criterio 2: Menor lapso de tiempo entre el inicio del servicio y el cierre de la ventana temporal del cliente Criterio 3: Cliente más rentable. Criterio 4: Selección del mejor atendiendo de forma ponderada a las reglas anteriores.

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Figura 2.- Proximidad económica de dos nodos al depósito como criterio de inicio de ruta

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Métricas de inserción Criterio para intercalar el mejor nodo en el lugar adecuado del recorrido. Se modifican tiempos de llegada de inicio de servicio “aguas abajo” Solomon (I1): Minimiza de forma ponderada el incremento de distancia y tiempo. No siempre es adecuado. ¿Podemos mejorarlo? Figura 3.- Ejemplo de rutas alternativas empleando diferentes métricas de inserción

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Métricas de inserción propuestas (delante o detrás de un nodo dado) (a) Proporciona un menor incremento de coste (b) Tiene un inicio en el servicio temprano (c ) Presenta una rentabilidad marginal más alta El cliente podrá incluirse en un itinerario si la rentabilidad marginal de la operación supera el beneficio por unidad de coste logrado por el viaje de ida y vuelta al depósito con sólo dicho nodo.

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Figura 4.- Inserción sucesiva de clientes considerando ventanas temporales blandas y tiempos de aproximación

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Ejemplo: problema R103 de Solomon (1987) 100 clientes con coordenadas aleatorias, con bajas demandas (entre 10 y 50). Tiempos de servicio de 90, con horarios de servicio estrictos y de banda estrecha. Vehículos con capacidad 200. La distancia unitaria se recorre en la unidad de tiempo. variables: (1)coordenadas del depósito y de cada uno de los clientes. (2)velocidad media y capacidad máxima de los vehículos. (3)tiempos de aproximación y alejamiento en cada destino en función del instante considerado. (4)costes fijos y variables asociados a los vehículos y sus tripulaciones y a las penalizaciones al superar las jornadas normales y los horarios de servicio. (5)demanda de cada cliente, con sus restricciones temporales y penalizaciones por aceptación de varios servicios. (6)ingresos unitarios por prestación del servicio a cada cliente.

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) SOLUCIONES PUBLICADAS AL R103 Algoritmo I1 de Solomon (1987): distancia recorrida 1484, 14 rutas Mejor resultado: Técnicas metaheurísticas distancia recorrida 1207, 13 rutas Algoritmo de inserción propuesto: distancia recorrida 1931, 13 rutas distancia recorrida 1871, 14 rutas

IV Congreso de Ingeniería del CIT- 2000 Transporte Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) CONCLUSIONES El algoritmo propuesto resuelve el problema generalizado CVRPSTW. Se propone una función objetivo más cercana a la realidad (rentabilidad). Se mejoran los criterios de inicio de rutas y las métricas de inserción habituales. No es evaluable la bondad de la solución respecto a criterios anteriores. Es un buen generador de soluciones factibles para alimentar metaheurísticas inteligentes.

Add a comment

Related presentations

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

In this presentation we will describe our experience developing with a highly dyna...

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

Un recorrido por los cambios que nos generará el wearabletech en el futuro

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Related pages

Optimización del problema generalizado de las rutas con ...

Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW) Víctor Yepes Director del Área de Producto, ...
Read more

Optimización del problema generalizado de las rutas con ...

×Close Share Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW)
Read more

Optimización económica de redes de transporte

Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (Cvrpstw), en Colomer, J.V. y García, A. ...
Read more

» Optimización económica de redes de transporte El blog ...

Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (Cvrpstw), en Colomer, J.V. y García, A. ...
Read more

El ruteo inteligente - La comunidad logística de México ...

Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW), en Colomer, J.V. y García, A. ...
Read more

Secuenciación heurística de un proyecto con ...

Optimización del problema generalizado de las rutas con restricciones temporales y de capacidad (CVRPSTW)
Read more

Unidad 5 Optimizacion De Redes Terminologia ensayos y ...

... del problema generalizado de las rutas con restricciones temporales y de... capacidad ... 2000 Optimización del problema generalizado de ...
Read more

Problema optimización - Documents

Optimización del problema generalizado de las rutas con restricciones temporales y ... la resolución del problema generalizado de las rutas con ...
Read more

250ST2131 - Modelos de Optimización de Redes de Transporte

Comprensión y capacidad de cuantificación de las variables ... de transporte y optimización del ... y su relación con los problemas de ...
Read more