# Optimal Route Planning for Truck-Drone Delivery Using Variable Neighborhood Tabu Search Algorithm
## 2 Literature Review  
The existing studies of TSP-D includes: FSTSP, PDSTSP, HDP, and VRPDR. FSTSP means that a truck carries one or multiple drones, each drone and the truck deliver goods or parcels together, and when each drone completes a delivery task, it returns to the truck to load goods and perform the next delivery task [15]. PDSTSP indicates that both drones and trucks start from a warehouse and deliver goods independently; when each drone completes a delivery task, it goes back to the warehouse to load goods and deliver them to the next customer [8]. HDP represents a scenario in which drones carry out all delivery tasks, while trucks mainly carry drones to specific locations and serve as moving landing points and take-off points for drones [16]. The definition of VRPDR is that all goods are delivered to customers by trucks, and drones are used to resupply goods to trucks from the warehouse [14]. The optimal route planning problem for truck-drone delivery in this paper occurs with the FSTSP, which is an extension of the traveling salesman problem first proposed by [PERSON] and [PERSON] in 2015 [15]. Due to complexity, [PERSON] and [PERSON] assume that there is only one truck and one drone in the FSTSP. Based on the common assumptions of the FSTSP, [PERSON] et al. put forward a derived FSTSP, which defines that each drone's launch point and return point are in the same position, and the delivery route is affected by the flying distance instead of flying time [17]. Optimization methods are commonly used to study the FSTSP in the literature. [PERSON] et al. develop the FSTSP with multiple trucks and multiple drones, which is formulated as a mixed-integer programming model with the objective of minimum delivery costs [18]. [PERSON] establishes an optimal route planning model considering a delivery time window, and utilizes the constrained programming method to solve the problem [8]. Based on the Bellman-Held-Karp dynamic programming approach, [PERSON] et al. employed a three-step exact solution method to solve the FSTSP [19]. The three-step exact solution method can help significantly reduce the solution times, while having impact on the overall solution quality. Since it has been proven that the FSTSP is non-deterministic polynomial-time hard (NP-hard), heuristic algorithms are increasingly used to solve this problem. [PERSON] et al. use a variable neighborhood search hybrid heuristic algorithm [20] and [PERSON] et al. apply a simulated annealing algorithm to solve the FSTSP [21]. [PERSON] et al. develop two heuristic algorithms, i.e., greedy random adaptive search algorithm (GRASA) and traveling salesman problem local search algorithm (TSP-LSA) [22]. GRASA is a metaheuristic algorithm, which first generates a traveling salesman problem for trucks, then uses a decomposition algorithm to remove some customers from the trucks' delivery route and assigns these customers to the drones. TSP-LSA is modified from the reassign heuristic proposed by [PERSON] and [PERSON] [15]. Compared with the reassign heuristic, the TSP-LSA has differences in calculating delivery cost savings and assigning customers between trucks' delivery routes and drones' delivery routes. GRASA has higher solution quality than TSP-LSA, while it needs more computing time. [PERSON] and [PERSON] design a two-stage decomposition heuristic algorithm [23]. In the first stage, a constructive greedy heuristic is utilized to assign the customers to the drones' delivery routes and the trucks' delivery routes. In the second stage, a nonlinear programming problem is solved to obtain the drones' delivery routes, which can minimize the drones' waiting time at rendezvous points. [PERSON] et al. extend the FSTSP by enabling drones to deliver goods to more than one customer between two rendezvous points, and solve the extended FSTSP using a simulated annealing algorithm so as to get the globally optimal solution [7]. Despite the wide range of studies in FSTSP, there are still some gaps in previous studies to be filled.