Un algoritmo Kernel Search para el Problema Periódico de Rutas por Arcos con Servicios Irregulares con drones y beneficios máximos

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

Consideramos un conjunto de aristas que tienen que ser recorridas por un único dron con al menos una cierta frecuencia en cada periodo de tiempo. Las aristas deben ser recorridas un número mínimo de veces en cada periodo y tienen asociado un beneficio al recorrerlas. El problema trata de encontrar una ruta diaria para el dron sin superar la distancia máxima permitida, cumpliendo los requerimientos de frecuencia. El objetivo es maximizar el beneficio obtenido.
Presentamos una formulación y proponemos dos métodos de resolución: un algoritmo exacto de Branch-and-Cut y un heurístico Kernel Search. Este último se basa en identificar un conjunto de variables prometedoras que puedan formar parte de una solución óptima del problema global y resolver el subproblema entero resultante. A este subproblema se le añaden otras variables prometedoras y se vuelve a resolver. Esto se repite hasta que se alcanza un tiempo máximo o se han utilizado todas las variables. Presentamos un estudio computacional

Keywords: rutas, drones, kernel search, branch and cut

Location, Routes and Inventories I
September 5, 2026  10:00 AM
Aula 30

M. V. Gutiérrez Padilla, G. Paredes

J. Rodriguez-Pereira, M. Cherkesly, M. Rancourt, G. Laporte

I. Valero Pedrón, F. Parreño Torres, M. Reula, C. Parreño Torres, M. T. Alonso Martínez