# Optimization of Truck-Drone Parcel Delivery Using Metaheuristics
## 1 Introduction
### Problem Description  
The TSP-D is defined on a graph \(G=(V,A)\), where \(A\) is a set of arcs, each of which links two nodes in \(V\). \(V=\{0,\ldots,n+1\}\), where nodes \(0\) and \(n+1\) represent the start point and the depot, duplicating the start and return points; the nodes \(1,\ldots,n\) are customer locations. The set of customers is represented by \(N=\{1,\ldots,n\}\). The set of customers that are served by a drone is denoted by \(V_{d}\subseteq N\) (Figure 1) [11]. If a customer is served by a truck, it is called a truck delivery, whereas if a customer is served by a drone, it is called a drone delivery. The drone delivery is represented as a tuple \(<i,j,k>\), in which \(i\) is the launch node (i.e., the node where the truck launches the drone, as in nodes 1 and 6 in Figure 1b), \(j\) is the drone node (i.e., the node that the drone delivers the parcel to, as in nodes 2 and 7 in Figure 1b), and \(k\) is the rendezvous node (i.e., where the truck and drone meet again, as in nodes 3 and 9 in Figure 1b); \(k\) can either be a customer location or the depot. A sortie refers to a sequence of nodes between a launch node and a rendezvous node. For example, the sequences \(<1,2,3>\) and \(<6,7,8,9>\) represent two distinct sorties in Figure 1b. The drone has a constant level of endurance, defined as the maximum time that the drone can fly without needing to be charged. \(<i,j,k>\) is a feasible solution for a drone delivery when \(i\
eq j,j\
eq k,k\
eq i\), \(t_{ij}+t_{ik}\leq e\), where \(t_{ij}\) is the time taken by the drone to move from \(i\) to \(j\), \(t_{jk}\) is the time taken by the drone to move from \(j\) to \(k\), and \(e\) is the drone's endurance. The drone path follows the road on the network for safety. The objective of the TSP-D is to find the tour with the shortest delivery time such that all customer locations are served by either the truck or the drone. The pickup, delivery, and recharging times of the drone are neglected. There are additional constraints that need to be considered:  
* Both vehicles must start from and return to the depot;
* Customers can only be served once, either by the drone or the truck;
* The drone does not have a rendezvous node before the delivery drone node;
* The drone cannot serve more than one customer between nodes \(i\) and \(j\). A very similar problem to the TSP-D is the flying sidekick traveling salesman problem (FSTSP) [12]. The FPSPSP is also a collaboration between a single truck and a single drone to deliver parcels to customers. The difference between the TSP-D and FSTSP is that in the FSTSP, two metrics are used for the distance--one for the truck (Manhattan distance) and one for the drone (Euclidean distance)--as the drone can fly directly from the launch point to the destination, thereby ignoring road restrictions. In the TSP-D, however, the drone must follow the road network. The TSP-D is considered an NP-hard problem [13]. Exact methods have been used to solve the TSP-D [13; 14; 15; 16]; however, due to computational limitations, these methods are only feasible on instances of limited sizes. Heuristics and metaheuristics are generally used to minimize the tour costs. Several taxonomies have been proposed for use in metaheuristics [17; 18], among which solution and population-based approaches are the most common classifications. The route-first, partition-second approach has been used in all reviewed studies. In this approach, the TSP route is constructed first, as if there were no drone. Following that, the drone nodes are selected and removed from the truck route. The Concorde TSP solver [19; 20; 21] is an exact algorithm which is able to find the optimal solution for a traditional TSP problem that includes instances with a large number of nodes. Many studies have used Concorde for the routing step [22; 23; 10; 24]. Figure 1: TSP vs. TSP-D for a graph of size \(n=9\): (**a**) displays an optimal TSP route without the aid of a drone; and (**b**) displays a TSP-D route, where the drone is launched from a truck, delivering parcels to two customers.