# Vehicle Routing Problem with Drones Considering Time Windows and Dynamic Demand
## 3 Model  
### Problem Description  
VRPDTWDD can be described as follows: there is a distribution center in a city's logistics network. The distribution center has an unlimited number of homogeneous trucks and drones. These trucks and drones provide package delivery services for customers with time window constraints. First, the distribution center formulates a delivery route and delivers the goods to the static customers who booked the previous day. In the process of delivery, it needs to re-plan the route of the vehicles being distributed or dispatch new vehicles to provide services if there is new customer demand. Static customers refer to customers whose demand remains unchanged in the delivery cycle; dynamic customers include new customers added during the delivery process and new customers derived from the new demands of the original customers. The ratio of dynamic customers to all customers is called the dynamic degree. The dynamic degree will increase with time, and the truck must decide on whether to respond to dynamic customers. The goal of this problem is to find the optimal route to minimize the delivery costs. Before establishing the VRPDTWDD model, certain operational configurations need to be given:  
* The logistic network including static and dynamic customers. * Each customer (node) needs to be served once by a truck or drone. * Vehicle access customer needs to satisfy time window constraints. * Each truck and its drone are deployed in pairs and must leave and return to a distribution center once. For each pair, the drone is equipped atop a truck and can only be launched and retrieved from the same truck. * Drones can be launched and retrieved at the customer node or the distribution center. * Each drone has multiple non-overlapping flights in a collaborative route, with a maximum of one launch and retrieve for each customer. * During the delivery process, the drone can pick up one or more packages from the truck (multiple packages need to meet load and battery capacity constraints), take off \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Reference** & **T** & **D** & **SV/MV** & **TW** & **DD** & **Objective** & **Method** \\ \hline [PERSON] and [PERSON] [18] & 1 & 1 & SV & no & no & Min time & MILP, Heuristic \\ \hline [PERSON] et al. [19] & 1 & 1 & SV & no & no & Min cost & MILP, GRASP \\ \hline [PERSON] et al. [20] & 1 & 1 & SV & no & no & Min time & MILP, Approximation algorithm \\ \hline [PERSON] and [PERSON] [23] & 1 & 1 & SV & no & no & min time & MILP, Heuristic \\ \hline [PERSON] et al. [30] & m & m & SV & no & no & Min time & MIP, Heuristic \\ \hline [PERSON] and [PERSON] [31] & 1 & m & SV & no & no & Min time & MILP, Heuristic \\ \hline [PERSON] et al. [37] & 1 & 1 & MV & no & no & Min time & MIP, Heuristic \\ \hline [PERSON] et al. [38] & 1 & m & MV & no & no & Min time & MILP, Heuristic \\ \hline [PERSON] et al. [41] & m & m & SV & no & no & Min time & Worst-case analysis \\ \hline [PERSON] et al. [42] & m & 1 & MV & no & no & Min cost & MILP, ALNS \\ \hline [PERSON] et al. [47] & m & m & SV & no & no & Min time & MILP, Metaheuristic \\ \hline [PERSON] et al. [48] & m & m & SV & yes & no & Min cost & MIP, VNS \\ \hline [PERSON] and [PERSON] [15] & m & m & SV & no & yes & Min time & Function approximation \\ \hline [PERSON] et al. [14] & 1 & 1 & SV & no & yes & \
\begin{tabular}{c} maximize the number of \\ orders delivered \\ \end{tabular} & Heuristic \\ \hline This paper & m & m & MV & yes & yes & Min cost &
\begin{tabular}{c} Two-stage optimization \\ model, SACHOA \\ \end{tabular} \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of related studies. to deliver the packages to the customer when the truck stops, and return to the truck at a subsequent customer node (including the distribution center). * When the truck and its drone regroup at the retrieve node, whoever arrives first will wait for the other.