Publicación:

Un algoritmo alns para el problema de ruteo de vehículos con drones en la distribución de última milla

Resumen

Los vehículos aéreos no tripulados o más conocidos como drones han despertado gran interés en los últimos años, teniendo aplicaciones en operaciones militares y civiles, recientemente se ha investigado acerca de las ventajas de su uso en la distribución de paquetes. En el presente trabajo de investigación se formula un problema similar a el Flying Sidekick Traveling Salesman Problem (FSTSP), en referencia a que los drones y camiones pueden trabajar en conjunto; mientras el dron hace una entrega, el camión puede visitar varios clientes. La diferencia del FSTSP es que este modelo considera que los camiones tienen un límite de capacidad y además se tienen restricciones que limitan el tiempo de la ruta, dicha formulación se conoce como el Problema de Ruteo de Vehículos con Drones (VRPD); esta investigación se centra en la distribución de última milla. Para resolver esta formulación se presenta el algoritmo Adaptive Large Neighborhood Search (ALNS), el cual es validado usando instancias propuestas en la literatura. Se verifica cómo varía la función objetivo de la solución inicial mediante el uso de heurísticas destrucción y reparación, finalmente se realiza un análisis de sensibilidad para algunos parámetros del algoritmo y características de los drones; realizando conclusiones de los resultados arrojados y efectuando recomendaciones para futuras investigaciones.