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

James Campbell, Ángel Corberán, Isaac Plana, José M. Sanchis () and Paula Segura
Additional contact information
James Campbell: University of Missouri–St. Louis
Ángel Corberán: Universitat de València
Isaac Plana: Universitat de València
José M. Sanchis: Universitat Politècnica de València
Paula Segura: Universitat Politècnica de València

Computational Optimization and Applications, 2022, vol. 83, issue 1, No 3, 67-109

Abstract: Abstract 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.

Keywords: Drones; Rural postman problem; Length constraints; Facets; Branch and cut (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-022-00383-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:83:y:2022:i:1:d:10.1007_s10589-022-00383-x

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-022-00383-x

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().