Routing for unmanned aerial vehicles: Touring dimensional sets

Justo Puerto and Carlos Valverde

European Journal of Operational Research, 2022, vol. 298, issue 1, 118-136

Abstract: In this paper we deal with an extension of the crossing postman problem to design routes that have to visit different shapes of dimensional elements rather than edges. This problem models the design of routes of drones or other vehicles that must visit a number of geographical elements to deliver some good or service and then move directly to the next using straight line displacements. We present two families of mathematical programming formulations. The first one is time-dependent and captures a number of characteristics of real applications at the price of using three indexes variables. The second family of formulations is not time-dependent, instead it uses connectivity properties to ensure the proper definition of routes. We compare them on a testbed of instances with different shapes of elements: second order cone (SOC) representable and polyhedral neighborhoods and polygonal chains. The computational results reported in this paper show that our models are useful and our formulations can solve to optimality medium size instances of sizes similar to other combinatorial problems including neighborhoods that have already been studied in the literature. To address larger instances we also present a heuristic algorithm that runs in two phases: clustering and Variable Neighborhood Search. This algorithm performs very well since it provides promising feasible solutions and, in addition, it can be used to initialize the solvers with feasible solutions.

Keywords: Routing; Networks; Logistics; Conic programming and interior point methods (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721005920
Full text for ScienceDirect subscribers only

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:eee:ejores:v:298:y:2022:i:1:p:118-136

DOI: 10.1016/j.ejor.2021.06.061

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().