Optimizacion de redes de transporte

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 deValencia

IV Congreso de Ingeniería del Transporte

CIT- 2000

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

repartosde 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 conjuntoposible 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 sise supera 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 delTransporte

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ónactual

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ásicodel 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 variarlos ingresos con la demanda, etcétera.

IV Congreso de Ingeniería del Transporte

CIT- 2000

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...