Modelos y algoritmos basados en programación lineal entera para problemas de ruteo de vehículos

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2022-03-18

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

spa

Temas:

OPTIMIZACION COMBINATORIA - PROBLEMAS DE RUTEO DE VEHICULOS - PICKUP-AND-DELIVERY - DEPENDENCIA DEL TIEMPO - FECHAS DE DISPONIBILIDAD - PROGRAMACION LINEAL ENTERA - BRANCH-AND-CUT - COMBINATORIAL OPTIMIZATION - VEHICLE ROUTING PROBLEMS - PICKUP-AND-DELIVERY - TIME DEPENDENCY - RELEASE DATES - INTEGER LINEAR PROGRAMMING - BRANCH-AND-CUT

Descripción:

En esta tesis se abordan variantes de uno de los problemas más importantes en el área del transporte, conocido como el Problema de Ruteo de Vehículos (VRP), a través de métodos basados en Programación Lineal Entera (ILP). El VRP consiste en determinar un conjunto de rutas de costo mínimo para una flota de vehículos que deben visitar exactamente una vez a determinados clientes, comenzando y finalizando sus recorridos en un único depósito, y satisfaciendo una restricción de capacidad. La primera variante abordada es el VRP con Pickups and Deliveries (VRPPD), en la cual se consideran precedencias 1-a-1 entre los clientes. La investigación se centra en estudiar la factibilidad de utilizar modelos basados en ILP heurísticamente, como parte de un algoritmo de búsqueda local, para explorar espacios de búsqueda grandes a fin de mejorar soluciones de una calidad media o alta. Se obtienen muy buenos resultados, mostrando que el desarrollo tiene potencial para ser utilizado en la práctica. La segunda variante contempla una generalización de la versión mono-vehículo del VRP sin capacidades, conocida como Problema del Viajante de Comercio (TSP). En esta versión denominada TDTSPTW se incluyen ventanas de tiempo y se incorpora variabilidad en los tiempos de viaje entre dos clientes que permite capturar la congestión y su potencial impacto en la práctica. Se desarrolla un algoritmo exacto siguiendo un esquema Branch-and-Cut, que es evaluado en instancias de prueba. A nuestro saber y entender, esta fue una de las primeras comparaciones exhaustivas de enfoques exactos para el TDTSPTW, donde resultados obtenidos mejoraron los de la literatura. Finalmente, la tercera variante estudiada se denomina TSP-rd e incorpora fechas de disponibilidad para modelar el tiempo en el que cada uno de los productos llegan al depósito. Se dispone de un único vehículo que puede realizar múltiples rutas y que en todo momento debe decidir si conviene esperar a que lleguen más productos al depósito, o si es mejor comenzar el recorrido para entregar aquellos que ya están disponibles. El objetivo es minimizar el tiempo de finalización. Se propone un nuevo algoritmo basado en ILP que demuestra ser mejor que el estado del arte. Adicionalmente, se adapta el modelo a otras variantes de TSP-rd y se explora el comportamiento en nuevas instancias de prueba. Hasta donde sabemos, es el mejor modelo exacto para el problema.

Identificador:

https://hdl.handle.net/20.500.12110/tesis_n7045_Montero