# Optimal Route Planning for Truck-Drone Delivery Using Variable Neighborhood Tabu Search Algorithm
## 3 Methodology
### Formulation of the Problem  
Based on the above assumptions, we formulate the proposed problem as a single objective mixed-integer nonlinear programming model.  
Objective function:  
\[\text{min}\ \tau= \max_{n\in N}\left\{u_{m+1}^{n},\ u_{m+1}^{n\prime}\right\}-u_{0} \tag{1}\]  
Constraint conditions:  
\[\sum_{i\in C}x_{0i}^{n}=\sum_{i\in C}x_{i,m+1}^{n}=1,\forall n\in N \tag{2}\]  
Figure 1: Truck–drone delivery routes.  
\(t_{ij}^{\rm T}\) is the travel time required by the truck from \(i\) to \(j\); \(t_{ij}^{\rm D}\) is the travel time required by the drone from \(i\) to \(j\); \(s^{\rm T}\) is the service time of the truck at the customer point; \(\pi_{i}^{n}\) is the waiting time of truck \(n\) at the customer point \(i\); \(L_{ij}\) is the length of route \((i,j)\); \(V^{\rm T}\) is the average driving speed of the trucks; \(V^{\rm D}\) is the average flying speed of the drones.  
Equation (1) is the objective function of the model, which seeks to minimize the total delivery time. The time consumption of the entire delivery process is the arrival time of the last truck or drone returning to the warehouse minus the initial departure time. Equation (2) indicates that each truck starts from the warehouse and finally returns to the warehouse, and only departs once and returns once. Equation (3) indicates that no truck will return to the warehouse immediately after departure. Equation (4) indicates that \(v\) trucks jointly complete the entire delivery process. Equation (5) is the capacity constraint of the truck. Equation (6) indicates that each customer is either visited by a truck or by a drone, and is only visited once. In Equation (7), each drone either does not take off or only takes off once at any possible launch point. Equation (8) ensures that each drone either does not land or only lands once at any possible landing point. Equation (9) is the capacity constraint of the drone. In Equation (10), if the drone launches from customer point \(i\) and is collected by the truck at customer point \(k\), the truck must visit customer point \(k\). Equation (11) states that if the drone launches from the warehouse 0 and is collected by the truck at customer point \(j\), the truck must visit both customer points \(i\) and \(j\). Equation (12) means that both drones and trucks start from the warehouse at initial time \(u_{0}\). Equations (13) and (14) are the subtour elimination constraints for the truck, referring to the position of customers that are visited on the truck's route. Equation (15) means that the time of each delivery by drone cannot exceed the maximum endurance of the drone battery. Equation (16) ensures that the sum of the time the truck arrives at customer point \(i\) plus the time the truck spends at \(i\) and the time it travels to customer point \(j\) is less than or equal to the time the truck arrives at customer point \(j\). Equation (17) means that the time that the truck spends at customer point \(i\) is the sum of the truck's delivery time at \(i\) plus the time required for the drone to launch (or land) at customer point \(i\) and the truck's waiting time at customer point \(i\). Equation (18) calculates the truck's waiting time at a customer point. In Equation (19), the time when the drone reaches customer point \(k\) is greater than or equal to the time when the truck reaches the drone's launch point \(i\) plus the time required for the drone to take off and the drone's travel time from \(i\) to \(k\). Equation (20) means that the time when the drone reaches its landing point (customer point \(j\)) is greater than or equal to the time when the truck reaches customer point \(j\) plus the drone's delivery time at customer point \(k\), the time it takes for the drone to land at customer point \(j\), and the drone's travel time from \(k\) to \(j\). Equation (21) calculates the truck's travel time. Equation (22) calculates the drone's travel time. Equations (23)-(26) define the types of decision variables.