Solución al problema de ruteo de vehículos con restricciones de capacidad y reordenamiento de carga en los sitios de demanda
Loading...
Files
Date
2011
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
La industria del transporte de carga ha crecido enormemente la última década. Los líderes de la industria operan redes de miles de vehículos terrestres y bodegas. Por lo tanto, se vuelve particularmente importante optimizar los procesos de reparto. En la actualidad se han investigado diversas variantes del problema de ruteo de vehículos capacitados (CVRP), sin embargo, los aspectos relacionados a la manipulación de carga no han sido estudiados a cabalidad.
En la presente tesis se analiza el problema de ruteo de vehículos con restricciones de capacidad de dos dimensiones y manipulación de carga en los sitios de demanda (2LCVRP-H). Éste consiste en un problema operacional de transporte de carga que integra tanto el ámbito del ruteo como el de carga de objetos al interior de vehículos. Los objetos poseen distintas densidades y dimensiones, mientras la flota se considera fija y homogénea. Se considera conocida la ubicación de los clientes y su respectiva demanda como un conjunto de objetos rectangulares a ser entregados en sólo una visita, respetando las restricciones de capacidad de los vehículos y buscando minimizar los costos asociados al ruteo y a la manipulación de objetos en los sitios de demanda, a diferencia de lo realizado en estudios anteriores.
Para resolver el modelo formulado se propone un proceso metaheurístico de tres etapas: ruteo, empaque y optimización, que amplía la gama de instancias que se puede resolver de manera eficiente. El modelo de programación entera mixta (MIP) presenta un buen desempeño sobre instancias pequeñas, considerando el trade off entre ruteo y packing, logrando resolver de manera exacta instancias de 6 clientes, 10 ítems y 2 vehículos en un tiempo promedio aproximado de 10 minutos. Mientras que el proceso heurístico propuesto logró resolver instancias de hasta 20 clientes, 60 ítems y 5 vehículos en menos de 30 minutos. Finalmente, dada la estructura del MIP, se propone adaptar el modelo presentado para considerar pick-up and deliveries y ventanas de tiempo.
En la presente tesis se analiza el problema de ruteo de vehículos con restricciones de capacidad de dos dimensiones y manipulación de carga en los sitios de demanda (2LCVRP-H). Éste consiste en un problema operacional de transporte de carga que integra tanto el ámbito del ruteo como el de carga de objetos al interior de vehículos. Los objetos poseen distintas densidades y dimensiones, mientras la flota se considera fija y homogénea. Se considera conocida la ubicación de los clientes y su respectiva demanda como un conjunto de objetos rectangulares a ser entregados en sólo una visita, respetando las restricciones de capacidad de los vehículos y buscando minimizar los costos asociados al ruteo y a la manipulación de objetos en los sitios de demanda, a diferencia de lo realizado en estudios anteriores.
Para resolver el modelo formulado se propone un proceso metaheurístico de tres etapas: ruteo, empaque y optimización, que amplía la gama de instancias que se puede resolver de manera eficiente. El modelo de programación entera mixta (MIP) presenta un buen desempeño sobre instancias pequeñas, considerando el trade off entre ruteo y packing, logrando resolver de manera exacta instancias de 6 clientes, 10 ítems y 2 vehículos en un tiempo promedio aproximado de 10 minutos. Mientras que el proceso heurístico propuesto logró resolver instancias de hasta 20 clientes, 60 ítems y 5 vehículos en menos de 30 minutos. Finalmente, dada la estructura del MIP, se propone adaptar el modelo presentado para considerar pick-up and deliveries y ventanas de tiempo.
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2011