El Problema Periódico de Rutas por Arcos con Servicios Irregulares con drones

T. Corberán Fabra, I. Plana Andani, J. M. Sanchis Llopis

Consideramos un conjunto de aristas que tienen que ser recorridas (aristas requeridas) por un único dron con al menos una cierta frecuencia en cada periodo de tiempo. Estas aristas, además de la frecuencia mínima en cada periodo, tienen asociado un beneficio por recorrerlas y una longitud. El Problema Periódico de Rutas por Arcos con Servicios Irregulares con drones consiste en encontrar una ruta diaria para el dron, cumpliendo los requerimientos de frecuencia y sin superar la distancia máxima que puede recorrer el dron. El objetivo es maximizar el beneficio obtenido al recorrer las aristas requeridas más veces que el mínimo exigido en cada periodo.
Se presenta una formulación del problema y se propone para su resolución un algoritmo exacto del tipo Branch and Cut y uno heurístico basado en Kernel Search. Se presentan algunos resultados computacionales preliminares.

Keywords: rutas, drones, branch and cut, heurístico

Transportation I
June 11, 2025  10:30 AM
Sala 3. Maria Rúbies Garrofé

P. Diaz-Cachinero, J. Contreras, J. I. Muñoz-Hernandez, M. Pourakbari-Kasmaei, M. Lehtonen

A. Mayoral Gómez, D. Gómez González, C. Simón de Blas

L. F. López-Castro, E. L. Solano-Charris, A. Pagès Bernaus

M. Landete Ruíz, M. Leal Palazón, J. F. Monge Ivars, I. Rodríguez Martín