# Solving the Parallel Drone Scheduling Traveling Salesman Problem via Constraint Programming
###### Abstract  
Drones are currently seen as a viable way of improving the distribution of parcels in urban and rural environments, while working in coordination with traditional vehicles, such as trucks. In this paper, we consider the parallel drone scheduling traveling salesman problem, where a set of customers requiring a delivery is split between a truck and a fleet of drones, with the aim of minimizing the total time required to serve all the customers. We propose a constraint programming model for the problem, discuss its implementation and present the results of an experimental program on the instances previously cited in the literature to validate exact and heuristic algorithms. We were able to decrease the cost (the time required to serve customers) for some of the instances and, for the first time, to provide a demonstrated optimal solution for all the instances considered. These results show that constraint programming can be a very effective tool for attacking optimization problems with traveling salesman components, such as the one discussed. parallel drone scheduling; traveling salesman problem; constraint programming drones; optimization +
Footnote †: journal: _arxiv: 12.0  
0000-0001-4010-40  
salesman problem (TSP) called flying sidekick TSP (FSTSP) and parallel drone scheduling TSP (PDSTSP). In both cases a truck and drones collaborate to deliver parcels, the difference being that, in the former, model drones can be launched and collected from the truck during its tour, while, in the latter, the drones are operated directly from the central depot, while the truck executes a traditional delivery tour. In the remainder of the paper, we will focus on the second problem, addressing the interested reader to [4] for full details and some solution strategies for the FSTSP. More specifically, in the PDSTSP, there is a truck that can leave the depot, serve a set of customers, and return to the depot, and a set of drones, each of which can leave the depot, serve a customer, and return to the depot before serving other customers. Not all the customers can be served by the drones, either due to their location or the characteristics of their parcel. The objective of the approach is to minimize the time needed to serve all the customers and to get the last vehicle back to the depot. A first mixed-integer linear programming (MILP) model for the PDSTSP and some heuristic methods [5,6] are proposed in [3]. A more refined model, and the first metaheuristic method, based on a two-step strategy embedding a dynamic programming-based component, are discussed in [7] (later extended in [8] for a variation of the problem using several trucks). A similar two-step approach, but based on matheuristics concepts [9] is presented in [10]. A hybrid ant colony optimization metaheuristic is discussed in [11]. An improved variable neighbour search metaheuristic is presented in [12]. Most of the work published to date has focused on heuristic methods, while exact methods have been able to solve systematically only instances with up to 20 customers [10]. Two other recent studies have dealt with variations of the problem where several trucks are employed, and also present results for the basic PDSTSP. In [13], three MILP models are proposed, one of which is arc-based and the other two are set-covering-based, together with a branch-and-price approach using one of the set-covering-based models. A heuristic version of one of the solvers is also discussed, leading to a matheuristic approach developed to target large instances. A more realistic variation of the PDSTSP is introduced in [14], where concepts such as the capacity of the vehicles, load balancing and decoupling of costs and times are taken into account. The authors propose an MILP model and a ruin-and-recreate metaheuristic for the problem. Several other PDSTSP variants and extensions have also been introduced and investigated in the literature. We refer the interested reader to [15,16] for a complete survey.