Relajaciones decrementales del espacio de estados para el problema de viajante de comercio con un dron

Resumen

La investigación en problemas de ruteo de vehículos que combinan camiones y drones creció fuertemente en la última década debido a sus aplicaciones para la logística de última milla. A pesar de la vasta literatura en el tema, los algoritmos exactos más eficientes diseñados al día de la fecha apenas pueden resolver algunas instancias con hasta 39 clientes. Este hecho es cierto incluso para las variantes más simples del problema que involucran solo un camión y un dron cuyas rutas se sincronizan en las locaciones de los clientes: el problema de viajante de comercio con un dron (TSP-D). En este trabajo diseñamos un nuevo algoritmo exacto para el TSP-D que resuelve todas las instancias de benchmark con hasta 59 clientes, siendo capaz de resolver instancias con hasta 99 clientes en los casos en que el dron es más veloz que el camión. Nuestro método se basa en un algoritmo de programación dinámica que se ejecuta para generar columnas y fijar variables dentro de un algoritmo novedoso que aplica distintas estrategias decrementales para relajar el espacio de estados.