| Date post: | 02-Dec-2014 |
| Category: |
Technology |
| Upload: | -victor-yepes |
| View: | 4,974 times |
| Download: | 1 times |
Optimización del
problema generalizado de las
rutas con restricciones
IV Congreso de Ingeniería del Transporte CIT-2000
Valencia, 7-9 Junio 2000
rutas con restricciones
temporales y de capacidad
(CVRPSTW)
Víctor YepesDirector del Área de Producto de la Agència
Valenciana del Turisme. Generalitat Valenciana.
Josep R. MedinaDirector del Laboratorio de Puertos y Costas de la
Universidad Politécnica de Valencia
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
IV Congreso de Ingeniería del
Transporte CIT- 2000
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
Transporte CIT- 2000
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 parauna flota de vehículos que empiecen y terminen en undepósito de modo que se visiten todos los destinos unasola vez al mínimo coste, satisfaciendo a su vez lasrestricciones horarias de inicio de servicio en cadacliente.
Las ventanas temporales definidas para cada cliente i
originan una espera si el vehículo llega antes dellímite inferior ei e impiden el inicio del servicio si sesupera el límite superior ui.
Problema combinatorio difícil NP-completo.
IV Congreso de Ingeniería del
Transporte CIT- 2000
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
Transporte CIT- 2000
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
Transporte CIT- 2000
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.
Heurística de construcción de rutas
con ventanas temporales:
IV Congreso de Ingeniería del
Transporte CIT- 2000
Optimización del problema generalizado de las rutas con
restricciones temporales y de capacidad (CVRPSTW)
algoritmo que elige un criterio para comenzar un itinerario y a continuación reglas para
insertar clientescuando 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
Transporte CIT- 2000
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
Optimización del problema generalizado de las rutas con
restricciones temporales y de capacidad (CVRPSTW)
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
Transporte CIT- 2000
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
Transporte CIT- 2000
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 lugaradecuado del recorrido. Se modifican tiempos de
llegada de inicio de servicio “aguas abajo”
Figura 3.- Ejemplo de rutas alternativas empleando diferentes métricas de inserción
Solomon (I1): Minimiza de forma ponderada elincremento de distancia y tiempo.
No siempre es adecuado. ¿Podemos mejorarlo?
IV Congreso de Ingeniería del
Transporte CIT- 2000
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ásalta
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
Transporte CIT- 2000
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
Transporte CIT- 2000
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
Optimización del problema generalizado de las rutas con
restricciones temporales y de capacidad (CVRPSTW)
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
Transporte CIT- 2000
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ísticasdistancia 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
Transporte CIT- 2000
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.
