Un Método de Solución Híbrido Metaheurístico para el Problema del Viajante de Comercio con Dron
Autores: Gunay-Sezer, Noyan Sebla; Cakmak, Emre; Bulkan, Serol
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
Un Método de Solución Híbrido Metaheurístico para el Problema del Viajante de Comercio con Dron
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Sistemas
Palabras clave
Drones
Entrega de última milla
Logística
Metaheurísticas
TSP-D
Algoritmo híbrido
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 32
Citaciones: Sin citaciones
La idea desafiante de utilizar drones en los sistemas de entrega de última milla de logística aborda un nuevo problema de enrutamiento conocido como el problema del vendedor viajero con drones (TSP-D). El TSP-D tiene como objetivo construir una ruta para entregar paquetes a un conjunto de clientes ya sea por camión o por dron, minimizando así los costos operativos. Dado que el TSP-D se considera NP-difícil, el uso de metaheurísticas es una de las soluciones más prometedoras. Este documento presenta un método de solución metaheurística híbrido para el TSP-D basado en dos algoritmos de vanguardia: el algoritmo genético y el algoritmo de optimización por colonias de hormigas. Las heurísticas en la literatura del TSP-D se basan en dos decisiones consecutivas: el enrutamiento del camión y la asignación del dron. A diferencia de las que se encuentran en la literatura existente, la metaheurística propuesta construye simultáneamente las rutas del camión y del dron. Además, hasta donde sabemos, introducimos por primera vez un método de solución basado en un enfoque de optimización por colonias de hormigas para el TSP-D. Adicionalmente, proponemos un marco de feromonas binarias tanto para el dron como para el camión, desviándonos de la estructura de feromonas tradicional. Los experimentos computacionales indican que el algoritmo metaheurístico híbrido propuesto es capaz de generar rutas óptimas para instancias proporcionadas de referencia del TSP-D. Además, el algoritmo mejora las mejores soluciones conocidas de algunas instancias encontradas por heurísticas rivales.
Descripción
La idea desafiante de utilizar drones en los sistemas de entrega de última milla de logística aborda un nuevo problema de enrutamiento conocido como el problema del vendedor viajero con drones (TSP-D). El TSP-D tiene como objetivo construir una ruta para entregar paquetes a un conjunto de clientes ya sea por camión o por dron, minimizando así los costos operativos. Dado que el TSP-D se considera NP-difícil, el uso de metaheurísticas es una de las soluciones más prometedoras. Este documento presenta un método de solución metaheurística híbrido para el TSP-D basado en dos algoritmos de vanguardia: el algoritmo genético y el algoritmo de optimización por colonias de hormigas. Las heurísticas en la literatura del TSP-D se basan en dos decisiones consecutivas: el enrutamiento del camión y la asignación del dron. A diferencia de las que se encuentran en la literatura existente, la metaheurística propuesta construye simultáneamente las rutas del camión y del dron. Además, hasta donde sabemos, introducimos por primera vez un método de solución basado en un enfoque de optimización por colonias de hormigas para el TSP-D. Adicionalmente, proponemos un marco de feromonas binarias tanto para el dron como para el camión, desviándonos de la estructura de feromonas tradicional. Los experimentos computacionales indican que el algoritmo metaheurístico híbrido propuesto es capaz de generar rutas óptimas para instancias proporcionadas de referencia del TSP-D. Además, el algoritmo mejora las mejores soluciones conocidas de algunas instancias encontradas por heurísticas rivales.