Una matheurística para el problema del vendedor viajero con múltiples drones.
Loading...
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
Diferentes investigaciones demuestran que el uso de drones como herramienta de apoyo en la logística trae beneficios significativos. Esta tesis 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 entre un camión y uno o múltiples drones que minimice el tiempo para realizar entregas. Este tipo de problema se caracteriza por su complejidad computacional, es por ello que los algoritmos presentes en la literatura sobre el FDTSP obtienen soluciones alejadas del óptimo. En el presente estudio se propone una matheurística para abordar el FDTSP. Este enfoque utiliza de manera alternada un modelo de programación lineal entera mixta (mixed integer linear programming, MILP por sus siglas en inglés) y una metaheurística basada en el variable neighborhood search. La metaheurística opera mediante dos procedimientos de optimización. El primer procedimiento enfocado en optimizar la asignación de clientes a los vehículos y la ruta del camión, utilizando tres operadores basados en el problema del vendedor viajero. El segundo procedimiento está centrado en optimizar las rutas de los drones, utilizando una metaheurística de simulated annealing. La matheurística es validada en dos conjuntos de instancias que representan condiciones de operación en entornos urbanos, suburbanos y rurales. En la mayoría de las instancias, los resultados computacionales muestran que la matheurística propuesta supera, en promedio, a los algoritmos de la literatura. Adicionalmente, la matheurística obtiene los mejores rendimientos cuando se utiliza una cantidad pequeña de drones y se evalúan instancias con un mayor número de clientes. Estos resultados son validados mediante un test estadístico, indicando que nuestro enfoque es estadísticamente diferente de los algoritmos de la literatura. Adicionalmente, para instancias pequeñas de hasta diez nodos, es posible comprobar que se alcanza el resultado óptimo con la matheurística y el modelo de MILP.
Different studies demonstrate that using drones as a support tool in logistics brings significant benefits. This thesis addresses the flexible drones traveling salesman problem (FDTSP). This problem seeks the optimal combination between a truck and one or multiple drones that minimizes delivery time. This type of problem is characterized by its computational complexity, which is why the state-of-the-art algorithms in the FDTSP literature yield far from optimal solutions. In the present study, a matheuristic is proposed to address the FDTSP. This approach alternates between a mixed integer linear programming (MILP) model and a metaheuristic based on variable neighborhood search. The metaheuristic operates through two optimization procedures. The first procedure focuses on optimizing the assignment of customers to vehicles and the truck’s route, using three operators based on the proposed traveling salesman problem. The second procedure focuses on optimizing the drones’ routes using a simulated annealing metaheuristic. The matheuristic is validated on two sets of instances representing operating conditions in urban, suburban, and rural environments. In most instances, the computational results show that the proposed matheuristic outperforms, on average, the algorithms in the literature. These results are validated through a statistical test indicating that our approach is statistically different from the algorithms in the literature. Additionally, for small instances with up to ten nodes, it is possible to verify that the optimal result is achieved in both the matheuristic and MILP model.
Different studies demonstrate that using drones as a support tool in logistics brings significant benefits. This thesis addresses the flexible drones traveling salesman problem (FDTSP). This problem seeks the optimal combination between a truck and one or multiple drones that minimizes delivery time. This type of problem is characterized by its computational complexity, which is why the state-of-the-art algorithms in the FDTSP literature yield far from optimal solutions. In the present study, a matheuristic is proposed to address the FDTSP. This approach alternates between a mixed integer linear programming (MILP) model and a metaheuristic based on variable neighborhood search. The metaheuristic operates through two optimization procedures. The first procedure focuses on optimizing the assignment of customers to vehicles and the truck’s route, using three operators based on the proposed traveling salesman problem. The second procedure focuses on optimizing the drones’ routes using a simulated annealing metaheuristic. The matheuristic is validated on two sets of instances representing operating conditions in urban, suburban, and rural environments. In most instances, the computational results show that the proposed matheuristic outperforms, on average, the algorithms in the literature. These results are validated through a statistical test indicating that our approach is statistically different from the algorithms in the literature. Additionally, for small instances with up to ten nodes, it is possible to verify that the optimal result is achieved in both the matheuristic and MILP model.
Description
Tesis presentada para optar al grado de Magíster en Ingeniería Industrial
Keywords
Drones, Logística, Traveling salesman problem