Coordinating drones with mothership vehicles: The mothership and drone routing problem with graphs

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.

Automated summary

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.