Drone arc routing problems

Abstract

[EN] In this article, we present some drone arc routing problems (Drone ARPs) and study their relation with well-known postman ARPs. Applications for Drone ARPs include traffic monitoring by flying over roadways, infrastructure inspection such as by flying along power transmission lines, pipelines or fences, and surveillance along linear features such as coastlines or territorial borders. Unlike the postmen in traditional ARPs, drones can travel directly between any two points in the plane without following the edges of the network. As a consequence, a drone route may service only part of an edge, with multiple routes being used to cover the entire edge. Thus the Drone ARPs are continuous optimization problems with an infinite number of feasible solutions. In order to solve them as a discrete optimization problem,we approximate each curve in the plane by a polygonal chain, thus allowing the vehicle to enter and leave each curve only at the points of the polygonal chain. If the capacity of the vehicles is unlimited, the resulting problem is a rural postman problem (RPP). We propose an algorithm that iteratively solves RPP instances with an increasing number of points of the polygonal chain and present results on several sets of instances.We also briefly discuss the case in which the drones have limited capacity and several drones are needed.