Polyhedral analysis and a new algorithm for the length constrained K-drones rural postman problem

Abstract

[EN] The Length Constrained K¿Drones Rural Postman Problem (LC K¿DRPP) is a continuous optimization problem where a set of curved or straight lines of a network have to be traversed, in order to be serviced, by a fleet of homogeneous drones, with total minimum cost. Since the range and endurance of drones is limited, we consider here that the length of each route is constrained to a given limit L. Drones are not restricted to travel on the network, and they can enter and exit a line through any of its points, servicing only a portion of that line. Therefore, shorter solutions are obtained with ¿aerial¿ drones than with ¿ground¿ vehicles that are restricted to the network. If a LC K¿DRPP instance is digitized by approximating each line with a polygonal chain, and it is assumed that drones can only enter and exit a line through the points of the chain, an instance of the Length Constrained K¿vehicles Rural Postman Problem (LC K¿RPP) is obtained. This is a discrete arc routing problem, and therefore can be solved with combinatorial optimization techniques. However, when the number of points in each polygonal chain is very large, the LC K¿RPP instance can be so large that it is very difficult to solve, even for heuristic algorithms. Therefore, it is necessary to implement a procedure that generates smaller LC K¿ RPP instances by approximating each line by a few but ¿significant¿ points and segments. In this paper, we present a new formulation for the LC K¿RPP with two binary variables for each edge and each drone representing the first and second traversals of the edge, respectively. We make a polyhedral study of the set of solutions of a relaxed formulation and prove that several families of inequalities induce facets of the polyhedron. We design and implement a branch¿and¿cut algorithm for the LC K¿RPP that incorporates the separation of these inequalities. This B &C is the main routine of an iterative algorithm that, by solving a LC K¿RPP instance at each step, finds good solutions for the original LC K¿DRPP. The computational results show that the proposed method is effective in finding good solutions for LC K¿DRPP, and that the branch¿and¿cut algorithm for the LC K¿RPP outperforms the only published exact method for this problem.