Título: Un algoritmo basado en generación de columnas para Star Routing
Director: Dr Javier Marenco
Jurados: Dr Brian Curcio y Dr Pablo Factorovich

Resumen:

Dados un grafo G = (N, E) y una flota de vehículos capacitados inicialmente ubicada sobre el vértice depósito, el problema de Star Routing pide minimizar el costo de cubrir a un conjunto de clientes S incluido en N realizando únicamente circuitos cerrados sobre G. Para cubrir a un cliente ubicado sobre un nodo v, no se exige que el recorrido del vehículo incluya a v, sino que tiene permitido pasar suficientemente cerca de este nodo. En un escenario que modela una empresa logística que envía paquetes a domicilio utilizando una cuadrilla de vehículos, este requerimiento equivale a pedir que cada chofer tenga la posibilidad de estacionar en una esquina cercana a la dirección del destinatario y acercarse a pie a entregar el envío.

Star Routing es una formulación particularmente difícil de tratar del problema de ruteo de vehículos. En esta tesis presentamos algoritmos eficientes que lo resuelven de manera exacta. En un análisis posterior se proponen heurísticas que permiten procesar instancias más grandes, pagando el costo de prescindir de soluciones óptimas. El análisis de la calidad de la solución aproximada implica la definición de cotas para limitar el error y merece ser profundizado ya que dista de la trivialidad.

El espacio de búsqueda de los algoritmos que resuelven Star Routing es categóricamente más grande que el de las formulaciones tradicionales de VRP y este hecho lo vuelve particularmente interesante a fines teóricos. Dado que en la literatura hasta la fecha está ampliamente aceptado que los algoritmos de generación de columnas representan una técnica eficiente para tratar problemas de ruteo de vehículos, suena razonable utilizar una formulación de estas características para Star Routing. Es usual que la dificultad del problema y por lo tanto la mayor parte de la carga computacional se concentren en el subproblema de pricing. Es por esto que hacemos una comparación entre varias ideas de la literatura que se mostraron eficientes para resolverlo, ahora adaptadas a nuestro caso particular. Muchas de las ideas desarrolladas en esta tesis se pueden adaptar a otras formulaciones complejas de problemas de optimización combinatoria sin dificultad excesiva.