Un modelo y algoritmo para el problema flexible del vendedor viajero con múltiples drones.

Abstract

En el último tiempo han existido desarrollos y aplicaciones importantes en la logística. Diferentes investigaciones demuestran que el uso de drones como herramienta para la entrega de paquetes trae beneficios significativos. Esta memoria de título aborda el problema flexible del vendedor viajero con múltiples drones (Flexible Drones Traveling Salesman Problem, FDTSP por sus siglas en inglés). Este problema busca la combinación óptima que minimice el tiempo para realizar entregas entre un camión y múltiples drones. Este tipo de problema se caracteriza por su complejidad computacional al ser abordado, es por ello que los algoritmos de la literatura obtienen soluciones que a veces se alejan de los óptimos. En el presente estudio se propone un modelo de programación lineal entera mixta y un algoritmo variable neighborhood search (VNS). El VNS propuesto opera en dos fases, una fase enfocada en optimizar la ruta del camión y la segunda fase está centrada en optimizar las rutas de los drones. La primera fase optimiza mediante operadores basados en el problema del vendedor viajero. Posteriormente, en la segunda fase se utiliza un algoritmo simulated annealing para mejorar las rutas de los drones. El modelo y algoritmo son validados en dos conjuntos de instancias que representan condiciones de operación en entornos urbanos, suburbanos y rurales. Los resultados computacionales muestran que el algoritmo propuesto es mejor que los algoritmos de la literatura en la mayoría de las instancias evaluadas, respaldado por un análisis estadístico. Sin embargo, el rendimiento empeora a medida que el número de drones aumenta. En tanto, el modelo logra garantizar la optimalidad en instancias de hasta ocho vértices, evidenciando que para instancias de 20 o más vértices se debe usar una metaheurísitica como el VNS propuesto.

In recent times, there have been significant developments and applications in logistics. Various studies demonstrate that the use of drones as a tool for package delivery brings significant benefits. This thesis addresses the Flexible Drones Traveling Salesman Problem (FDTSP), which seeks to find the optimal combination of a truck and multiple drones to carry out a route delivering packages to customers in minimum time. This type of problem is characterized by its computational complexity to be addressed. That is why algorithms from the literature sometimes obtain solutions that deviate from the optima. In the present study, we propose an integer mixed linear programming model and a variable neighborhood search algorithm (VNS). The proposed VNS optimizes a solution in two phases, with the first phase focused on optimizing the truck’s route and the second phase centered on optimizing the drone routes. The initial phase optimizes using operators based on the Traveling Salesman Problem. Subsequently, in the second phase, a simulated annealing algorithm is employed to enhance the drone routes. The model and VNS are tested on two sets of instances representing operational conditions in urban, suburban, and rural environments. Computational results show that the proposed algorithm outperforms the algorithms from the literature in the majority of the evaluated instances, supported by statistical analysis. However, performance deteriorates as the number of drones increases. Meanwhile, the model succeeds in ensuring optimality in instances with up to eight vertices, demonstrating that for instances with 20 or more vertices, a metaheuristic should be employed as the proposed VNS.