Título: Mejoras a un algoritmo de Branch and Price para el problema del viajante de comercio con un dron
Directores: Gonzalo Lera Romero y Francisco Soulignac
Jurados: Brian Curcio y Javier Marenco (UTDT)

RESUMEN
En este trabajo estudiamos el problema del viajante de comercio con un dron. En este problema, un camión y un dron se mueven en simultáneo para visitar a todos los clientes de un conjunto una única vez, ya sea únicamente por el camión, únicamente por el dron, o por ambos vehículos al mismo tiempo. El dron tiene una capacidad limitada; solo puede llevar de a un paquete a la vez, después de lo cual debe regresar al camión para buscar otro paquete. Por otro lado, el dron tiene la ventaja de poder evitar la red de tráfico, lo que le permite moverse de un cliente a otro en línea recta.

Analizamos un algoritmo de Branch and Price para este problema propuesto por Roberti and Ruthmair en el trabajo “Exact Methods for the Traveling Salesman Problem with Drone” (Roberti and Ruthmair, 2021), el cual reimplementamos en su totalidad dado que el código fuente no está disponible. Además, proponemos e implementamos mejoras al mismo, entre las cuales se encuentran una nueva relajación para el TSPD, nuevas reglas de dominación parcial, y una versión bidireccional del algoritmo. Estos aportes prueban ser eficaces en los experimentos computacionales realizados, en donde observamos que nuestro algoritmo obtiene resultados mejores que los encontrados en la literatura.

El algoritmo fue testeado sobre las mismas instancias que utilizan en el trabajo Roberti and Ruthmair (2021), introducidas anteriormente por Poikonen et al. (2019). Las mismas llegan a un tamaño máximo de 39 clientes, y mientras que el algoritmo de Roberti y Ruthmair llega a resolver únicamente 11/75 instancias de dicho tamaño, nuestro algoritmo resuelve 71/75.