Heuristic solutions for the K-Drones Arc Routing Problem

P. Segura Martínez, Á. Corberán Salvador, J. M. Sanchis Llopis, I. Plana Andani, J. F. Campbell

In this talk we present the K-Drones Arc Routing Problem (KDARP). This arc routing problem, where a fleet of drones is available, consist of finding a set of tours starting and ending at a point called the depot and with the length of the single routes limited by a maximum distance, such that all the given edges are traversed with minimum total cost. Unlike vehicles in traditional arc routing problems, drones can travel directly between any two points in the plane without following the edges of the network, so that a drone route may traverse only part of an edge, with multiple routes being used to cover the entire edge. Some applications of this problem includes traffic monitoring, infrastructures inspection or surveillance along linear features such as coastlines or territorials borders. For this problem, we propose a matheuristic algorithm and some computational results are presented.

Keywords: Drones arc routing distance constraints matheuristic

A. Martínez-Gavara, T. Pastore, R. Martí, P. Festa

S. Gil, E. García Pardo, A. Duarte, A. Alonso-Ayuso

R. Alvarez-Valdes, C. Parreño Torres, R. Ruiz