Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 136, Issue -, Pages -Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2021.105445
Keywords
Arc routing problems; Networks; Drones; Conic programming
Categories
Funding
- Spanish Ministry of Education and Science/FEDER Grant [MTM2016-74983-C02-(01-02)]
- Junta de Andalucia project [P18-FR-1422, FEDER-US1256951, CEI-3-FQM331]
- NetmeetData: Ayudas Fundacion BBVA a equipos de investigacion cientoifica 2019
- Ministerio de Ciencia e Innovacion [PID2020-114594GB-C21]
- University of Rome, Sapienza Grant [RM11916B7F962975]
Ask authors/readers for more resources
This paper focuses on the optimization of routing problems with drones, specifically analyzing the coordination between a mothership and a drone to obtain optimal routes for visiting target objects modeled as general graphs. The study presents different approaches based on the assumption of the mothership's route, and develops exact formulations using mixed integer second order cone programs. Computational experiments demonstrate the usefulness of the methods proposed, including a matheuristic algorithm that provides high quality solutions within reasonable time constraints.
This paper addresses the optimization of routing problems with drones. It analyzes the coordination of one mothership with one drone to obtain optimal routes that have to visit some target objects modeled as general graphs. The goal is to minimize the overall weighted distance traveled by both vehicles while satisfying the requirements in terms of percentages of visits to targets. We discuss different approaches depending on the assumption made on the route followed by the mothership: i) the mothership can move on a continuous framework (the Euclidean plane), ii) on a connected piecewise linear polygonal chain or iii) on a general graph. In all cases, we develop exact formulations resorting to mixed integer second order cone programs that are compared on a testbed of instances to assess their performance. The high complexity of the exact methods makes it difficult to find optimal solutions in short computing time. For that reason, besides the exact formulations we also provide a tailored matheuristic algorithm that allows one to obtain high quality solutions in reasonable time. Computational experiments show the usefulness of our methods in different scenarios.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available