# Vehicle Routing Problem with Drones Considering Time Windows and Dynamic Demand
## 3 Model
### Mathematical Model  
#### 3.2.1 Initial Planning Stage  
A two-stage vehicle route planning strategy is adopted for VRPDTWDD. The first stage is the initial planning stage. The initial planning stage is mainly for route planning for static customers who have made reservations, which can be regarded as a static VRPDTW problem. The optimization model in the initial stage of construction is as follows:  
\[\min f=C_{k}\sum_{k\in K}\sum_{i\in V}\sum_{j\in V}d^{\prime}_{ij}x^{k}_{ij}+C _{p}\sum_{k\in K}\sum_{p\in P}\sum_{i\in V}\sum_{j\in V}d_{ij}y^{kp}_{ij} \tag{1}\]  
s.t.  
\[\sum_{k\in K}\sum_{p\in P}Z^{kp}_{i}+\sum_{k\in K}Z^{k}_{i}=1,\;\forall i\in C, \tag{2}\]  
\[\sum_{j\in V}y^{kp}_{ij}\geq Z^{kp}_{i},\;\forall i\in C,p\in P,k\in K, \tag{3}\]  
\[Z^{k}_{i}=\sum_{j\in V}x^{k}_{ji},\;\forall i\in C,k\in K, \tag{4}\]  
\[h^{kE}_{ip}+\sum_{j\in V}y^{kp}_{ij}=h^{kS}_{ip}+\sum_{j\in V}y^{kp}_{ji},\; \forall i\in C,p\in P,k\in K, \tag{5}\]  
\[\sum_{j\in V}y^{kp}_{ij}=\sum_{j\in V}y^{kp}_{ji}\leq 1,\;\forall i\in V,p\in P,k\in K, \tag{6}\]  
\[\sum_{j\in V}x^{k}_{ij}=\sum_{j\in V}x^{k}_{ji}\leq 1,\;\forall i\in V,k\in K, \tag{7}\]  
\[Z^{kp}_{i}+Z^{kp}_{j}\geq 1-M(1-y^{kp}_{ij}),\;\forall(i,j)\in A,p\in P,k\in K, \tag{8}\]  
\[h^{kS}_{ip}\geq 1-M(2-y^{kp}_{ij}-Z^{kp}_{j}+Z^{kp}_{i}),\forall i\in V,j\in C,i\
eq j,p\in P,k\in K, \tag{9}\]  
\[h^{kE}_{jp}\geq 1-M(2-y^{kp}_{ij}-Z^{kp}_{i}+Z^{kp}_{j}),\forall j\in V,i\in C,i\
eq j,p\in P,k\in K, \tag{10}\]  
Figure 1: A simple diagram of VRPDTWDD.  
whether to respond to dynamic customers. When the dynamic degree is small, choosing to respond to dynamic customers can quickly satisfy their needs, but the delivery cost will also increase. When the dynamic degree is large, responding to dynamic customers can reduce delivery costs, but the demand cannot be met quickly. To better balance cost and service speed, we adopt a regular update strategy that divides time domains. We divide the dynamic time window of the distribution center into time domains with the same duration. At the end of each time domain, the received dynamic demands are processed according to the response strategies of different dynamic demands. Subsequently, based on the location of the current vehicle service customer as the starting point, the route is re-planned for the customers whose deliveries have not been met thus far as well as the dynamic customers in the previous period. In this way, we can transform the dynamic VRPDTWDD problem into multiple static VRPDTW problems.  
Dynamic demand includes various situations, including adding new customer demands, canceling customer demands, adding new demands from existing customers, adjusting the time windows, and changing the delivery address. For different types of dynamic demands, the specific response strategy is as follows: we add new customer demands to the delivery network. If the dynamic level is low at this time, we insert the new demand customer node into the original delivery scheme for repair; if the level of dynamic degree is high, then the dynamic problem is converted into a multi-stage static sub-problem based on time domain division for processing. When the new demand has no impact on the vehicle capacity and time windows, the dynamic degree is defined as a lower level. On the contrary, when the new demand violates the vehicle capacity or time windows, the dynamic degree is defined as a higher level. We delete customers with canceled demand directly from the delivery network. New demands from existing customers and changes in delivery addresses are treated as customer nodes that are canceled first and subsequently added. For customers who adjust the time windows, we make the corresponding adjustments in the delivery network.