# Optimal Route Planning for Truck-Drone Delivery Using Variable Neighborhood Tabu Search Algorithm
## 3 Methodology
### Notation and Problem Statement  
It is assumed that at the initial time \(u_{0}\), a fleet \(N=\{1,\ 2,\ \cdots,\ v\}\) consisting of \(v\) trucks needs to deliver \(m\) parcels to \(m\) different customers \(C=\{1,\ 2,\ \cdots,\ m\}\). One customer receives one parcel, and each truck is equipped with a drone. Trucks equipped with drones depart from the warehouse and deliver parcels to customers one by one, following a given route. All customers can be served by a truck or a drone. After the delivery is completed, trucks and drones return to the warehouse. For simplicity, the warehouse is represented by \(D=\{0,\ m+1\}\), that is, the truck departs from \(\{0\}\) and returns to \(\{m+1\}\). Therefore, the set of all nodes in the delivery network is \(E=\{0,\ 1,\ 2,\ \cdots,\ m,\ m+1\}\), and the truck can start from the set of nodes \(E^{+}=\{0,\ 1,\ 2,\cdots,\ m\}\) and reach the set of nodes \(E^{-}=\{0,\ 1,\ 2,\cdots,\ m+1\}\). The set of delivery routes in the delivery network is \(A=\{(i,\ j):\ i\in E^{+},\ j\in E^{-},\ i\
eq j\}\). Figure 1 shows the truck-drone delivery routes.  
Drones can only take off on nodes \(E^{+}=\{0,\ 1,\ 2,\cdots,\ m\}\) and can only land on nodes \(E^{-}=\{0,\ 1,\ 2,\cdots,\ m,\ m+1\}\). A truck delivers a parcel at customer point \(i\) and launches the drone at \(i\), then the truck goes to the next customer point \(j\), and the drone goes to customer point \(k\). After completing the delivery task, the drone returns to customer point \(j\) and is collected by the truck. Swap the drone battery with a new or fully recharged battery and load the drone with the parcel for the next delivery task at customer point \(j\). Meanwhile, the truck continues to the next customer point until all parcels are delivered, then returns to the warehouse.  
Each truck route can be represented by two nodes, i.e., \((i,j)\): \(i\in E^{+},j\in E^{-},i\
eq j\). Different from the truck route, each drone route is represented by three nodes, i.e., \((i,k,j)\), which means that a drone takes off at point \(i\), \(i\in E^{+}\), delivers a parcel to point \(k\), \(k\in\{E^{-}\colon\ k\
eq i\}\), and returns to point \(j\), \(j\in\left\{C:\ j\
eq i,\ j\
eq k,\ t_{\text{L}}+t_{\text{R}}+t_{ik}^{\text{D}}+ t_{kj}^{\text{D}}+s^{\text{D}}\leq e\right\}\). \(t_{\text{L}}\) and \(t_{\text{R}}\) are the time required for a drone to take off and land, \(t_{ik}^{\text{D}}\) is the time it takes for a drone to fly from launch point \(i\) to customer point \(k\), and \(t_{kj}^{\text{D}}\) is the travel time of a drone from customer point \(k\) to land point \(j\). \(s^{\text{D}}\) is the service time of a drone at a customer point, and \(e\) is the maximum endurance of a drone. We define the set of all drone routes as \(P=\{(i,k,j)\}\), the set of drone routes starting from point \(i\) as \(P_{i}^{+}\), and the set of drone routes ending at point \(j\) as \(P_{j}^{-}\).  
Therefore, the problem studied in this paper is defined as: when the number of trucks (one truck carries one drone) is given, determine the truck-drone delivery routes as well as the sequence of each delivery task, so as to minimize the total delivery time.  
To this end, we define the following decision variables:  
\(x_{ij}^{n}\): If truck \(n\in N\) goes from point \(i\in E^{+}\) to point \(j\in E^{-},j\
eq i\), \(x_{ij}^{n}=1\); otherwise \(x_{ij}^{n}=0\);  
\(y_{p}^{n}\): If the delivery route of the drone on truck \(n\in N\) is \(p\in P\), \(y_{p}^{n}=1\); otherwise \(y_{p}^{n}=0\);  
\(u_{j}^{n}\): The time when truck \(n\in N\) arrives at customer point \(j\in E^{-}\);  
\(u_{j}^{n\prime}\): The time when the drone on truck \(n\in N\) arrives at customer point \(j\in E^{-}\);  
\(z_{i}^{n}\): The position of node \(i\in E\) on the route of truck \(n\in N\).