P. Segura Martínez, I. Plana Andani, J. M. Sanchis Llopis
Recientes avances en la tecnología de drones han hecho posible que estos vehículos tengan la capacidad de obtener imágenes y realizar entregas en el mismo vuelo. La capacidad de carga útil de los drones todavía es bastante limitada y el peso de la carga transportada afecta significativamente el consumo de energía y los tiempos de vuelo. En este trabajo presentamos una extensión del clásico problema general de rutas en el que un dron debe atravesar algunas aristas requeridas y visitar un conjunto de nodos de un grafo. El objetivo es minimizar la duración total de la ruta teniendo en cuenta el efecto de la carga transportada por el dron en el tiempo de recorrido de cada arista. Proponemos una formulación matemática y realizamos un análisis del poliedro de soluciones asociado, introduciendo familias de desigualdades válidas. Presentamos un algoritmo de ramificación y corte para resolver el problema, y algunos resultados computacionales obtenidos en instancias generadas para este trabajo.
Keywords: problema general de rutas, drones, cargas
Scheduled
Ramiro Melendreras Award I
November 7, 2023 11:40 AM
CC4: Room 2