Publicación:

Algoritmo VNS para la solución de un sistema de nave nodriza en un problema de ruteo de vehículos con drones en la entrega y recogida de paquetes

Resumen

Este documento presenta un modelo matemático y una metodología de solución eficiente para el problema de ruteo de vehículos con drones (VDRP) en el cual el objetivo es cumplir la demanda de servicios de recogidas y entregas en una red minimizando el costo total de la operación. para esto el problema es formulado como programa lineal de enteros mixtos (MILP). El modelo formulado contempla la mayoría de las condiciones e interacciones del sistema de nave nodriza (vehículo-dron) como las restricciones que se generan por la forma de operación de cada uno de ellos, a saberse restricciones de capacidad de carga y rango de vuelo. Así mismo, se tienen en cuenta algunas suposiciones con el fin de simplificar un poco el problema. La metodología de solución se basa en la utilización de una extensión del clásico algoritmo de Clarke and Wright para resolver el VDRP con la cual se genera una solución inicial que sea buena y se busca su optimización mediante un algoritmo de búsqueda de vecindario variable (VNS). Se llevan a cabo algunos experimentos numéricos con el fin de medir el rendimiento de las heurísticas y dar respuesta al problema planteado considerando diferentes instancias. Al ser un tema poco explorado por la literatura se considera que este documento amplía tanto preguntas como respuestas en este sistema de nave nodriza que se considera aun innovador en la planificación de las tareas de entrega y recogida de paquetes.