# Vehicle Routing Problem with Drones Considering Time Windows and Dynamic Demand
## 3 Model
### Problem Description
* The truck and drone both maintain a constant speed during the delivery process, and the drone needs to replace the battery immediately after merging to ensure the next flight. * To simplify the study, the impact of traffic congestion is not considered. * In this paper, VRPDTWDD is assumed to be explored in two-dimensional (2D) space. Figure 1 is a simple schematic diagram of VRPDTWDD. The entire delivery process can be divided into two time periods: \([T_{a},T_{b}],[T_{b},T_{c}]\). First, perform path planning for some static customers in time period \([T_{a},T_{b}]\). That is, one or more trucks carrying configured drones and packages depart from the distribution center, deliver the packages according to the planned route, and return to the distribution center. Assume that dynamic customers appear at time \(T_{b}\), then perform path planning for the remaining customers in time period \([T_{b},T_{c}]\). The mathematical symbols and meanings used in this paper are given in Table 2. \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Description** \\ \hline \multicolumn{3}{c}{Sets} \\ \hline \multirow{2}{*}{\(V\)} & Collection of all nodes, where 0 and \(n+1\) are distribution centers \\  & \(V=\{0,1,2,\cdots,n,n+1\}\) \\ \hline \multirow{2}{*}{\(C\)} & Collection of all customers \(C=V\backslash\{0,n+1\}\) \\ \hline \multirow{2}{*}{\(A\)} & Set of all arcs \(A=\{(i,j)|i\in V,j\in V,i\
eq j\}\) \\ \hline \multirow{2}{*}{\(K\)} & Collection of all trucks \(K=\{1,2,\ \cdots,k\}\) \\ \hline \multirow{2}{*}{\(P\)} & Collection of all drone trips \(P=\{1,2,\ \cdots,p\}\) \\ \hline \multicolumn{3}{c}{Parameters} \\ \hline \multirow{2}{*}{\(C_{k}/C_{p}\)} & The unit delivery cost for the truck/drone \\ \hline \multirow{4}{*}{\(d^{\prime}_{ij}/d_{ij}\)} & The distance between the truck/drone and customer \(i\) and customer \(j\). Due to the limitation of obstacles on the ground, the distance covered by the drone is calculated using the European formula and that covered by the truck is calculated as \(d^{\prime}_{ij}=\eta\cdot d_{ij}\) \\ \hline \multirow{2}{*}{\(Q_{k}/Q_{p}\)} & Rated load capacity of truck/drone \\ \hline \multirow{2}{*}{\(v_{k}/v_{p}\)} & Traveling/flying speed of truck/drone \\ \hline \multirow{2}{*}{\(a_{i}/b_{i}\)} & The earliest/latest service start time for customer \(i\) \\ \hline \multirow{2}{*}{\(q_{i}\)} & Demand of customer \(i\) \\ \hline \multirow{2}{*}{\(s_{i}\)} & Service time for customer \(i\) \\ \hline \multirow{2}{*}{\(D_{\max}\)} & The maximum flight distance of the drone \\ \hline \multicolumn{3}{c}{Variables} \\ \hline \multirow{2}{*}{\(x^{k}_{ij}(=1)\)} & Truck \(k\) drives from customer \(i\) to customer \(j\) \\ \hline \multirow{2}{*}{\(y^{kp}_{ij}(=1)\)} & The \(p\)-th trip of the drone carried by truck \(k\) runs along the arc \((i,j)\) \\ \hline \multirow{2}{*}{\(h^{kS}_{ip}/h^{kE}_{ip}(=1)\)} & Customer \(i\) is the launch/retrieve node for the drone trip \(p\) carried by truck \(k\), \\  & where S and E are used to distinguish launch and retrieve nodes \\ \hline \multirow{2}{*}{\(Z^{kp}_{i}(=1)\)} & The \(p\)-th trip service of the drone carried to customer \(i\) by truck \(k\) \\ \hline \multirow{2}{*}{\(Z^{k}_{i}(=1)\)} & Customer \(i\) is served by truck \(k\) \\ \hline \multirow{2}{*}{\(t_{i}\)} & Time when the vehicle (truck–drone) arrives at customer \(i\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Model symbols and explanations.