Una formulación para el problema de ruteo de vehículos con tiempos de viaje dependientes del tiempo para la actualización de rutas con información en tiempo real
Loading...
Date
2009
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
En esta investigación se estudia el problema de ruteo dinámico de vehículos con ventanas de tiempo e información en tiempo real respecto de las condiciones de oferta y demanda del sistema. Los objetivos de la presente investigación son: (i) cuantificar los beneficios del uso de tiempos de viaje dependientes del tiempo en la construcción de rutas de despacho vehiculares; (ii) cuantificar los beneficios del uso de información en tiempo real para actualizar planes en la operación de rutas de despacho vehiculares, considerando cambios en los niveles de servicio de la red de transporte, y nuevas demandas; y (iii) desarrollar un algoritmo de solución para el problema. Se construyó una red espacio-tiempo para reflejar la condición de tiempos de viaje dependientes del tiempo.
A partir de ella, se formuló el problema como un modelo de programación lineal entera mixta, distinguiendo dos versiones: una para el inicio del período de planificación, y otra para la actualización de las rutas, lo que ocurrirá si aparece una nueva demanda y/o si existe algún incidente que varíe los tiempos de viaje de la red. Posteriormente, se desarrolló un algoritmo de solución del problema de carácter heurístico a fin de obtener respuestas en tiempo real. El experimento consistió en probar cuatro estrategias de operación que se diferenciaron principalmente por el tipo de congestión (recurrente y no-recurrente) considerada al momento de construir las rutas. Además, se consideraron cuatro escenarios que se distinguen por la proporción de clientes que aparecen en tiempo real, y por el nivel de impacto de los incidentes. Los resultados mostraron que, al planificar las rutas considerando ambos tipos de congestión, los costos totales disminuyen, aun visitando un número mayor de clientes.
A partir de ella, se formuló el problema como un modelo de programación lineal entera mixta, distinguiendo dos versiones: una para el inicio del período de planificación, y otra para la actualización de las rutas, lo que ocurrirá si aparece una nueva demanda y/o si existe algún incidente que varíe los tiempos de viaje de la red. Posteriormente, se desarrolló un algoritmo de solución del problema de carácter heurístico a fin de obtener respuestas en tiempo real. El experimento consistió en probar cuatro estrategias de operación que se diferenciaron principalmente por el tipo de congestión (recurrente y no-recurrente) considerada al momento de construir las rutas. Además, se consideraron cuatro escenarios que se distinguen por la proporción de clientes que aparecen en tiempo real, y por el nivel de impacto de los incidentes. Los resultados mostraron que, al planificar las rutas considerando ambos tipos de congestión, los costos totales disminuyen, aun visitando un número mayor de clientes.
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2009