# Vehicle Routing Problem with Drones Considering Time Windows and Dynamic Demand
## 5 Computational Experiments
### Actual Case Study  
This study takes the customers of a self-operated store of a certain brand in Shenyang from 8:00 a.m. to 11:00 a.m. as the data for verifying the feasibility of the proposed method. During this period, the company provided services to 30 customers in total. The spatial distribution of customers is shown in Figure 10 and detailed information for the customers is listed in Table 5. The identifiers in the \"Customer Type\" column are explained as follows: a for canceled customers and b for newly added customers. The maximum loading capacity of the truck is 100 kg, the average speed is 30 km/h, and the unit delivery cost is about $0.78/km [52]; the maximum loading capacity of the drone is 12 kg, the maximum flight distance is 20 km, the average speed is 45 km/h, and the unit delivery cost is about $0.078/km [52]. Figure 10: Spatial distribution of customer locations. 0 represents the depot, and 1–30 represents the customer. First, when entering the initial planning stage, we use the SACHOA algorithm to plan the delivery route for the initial static customers; the results are shown in Table 6.  
Before determining the delivery route for the dynamic planning stage, we use the k-means clustering method to cluster all customers. The clustered customer set is shown in Table 7. Based on the dynamic degree, only areas 1, 2, and 3 are considered for delivery route changes in the dynamic planning stage, while delivery routes for other regions remain the same. According to the actual situation, the dynamic service time window also opens when the distribution center starts the same-day delivery service, that is, it will enter the dynamic planning stage. The update interval is set to 60 min, resulting in three dynamic time windows [8:00-9:00], [9:00-10:00], and [10:00-11:00] on the given day. Table 8 displays the relevant dynamic customer information received during these periods. According to the information in Table 8, both [9:00-10:00] and [10:00-11:00] have dynamic demands, so two delivery route adjustments are required. At the beginning of each period, starting from the location of the current vehicle service customer, the routes for both the customers whose deliveries have not yet been made and the dynamic customers in the previous period are re-planned. It is worth noting that the SACHOA algorithm is more suitable for handling cases with 100 or fewer customers. In the end, the company used 4 trucks and 3 drones to provide delivery services to all customers, at a total delivery cost of $232.1869. Figure 11 shows the delivery routes of all vehicles. Of these, the solid lines represent the delivery routes for the trucks and the dotted lines represent the delivery routes for the drones. It can be observed from Figure 11 that when there is a new demand, the vehicle will continue to serve new customers without returning to the distribution center, which improves its utilization rate. At the same time, the new delivery route tries to keep close to the delivery \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Vehicle** & **Route** & **Vehicle** & **Route** \\ \hline Truck 1 & 0\(\rightarrow\)4\(\rightarrow\)3\(\rightarrow\)17\(\rightarrow\)15\(\rightarrow\)20\(\rightarrow\)0 & Drone 1 & 3\(\rightarrow\)6\(\rightarrow\)2\(\rightarrow\)5\(\rightarrow\)17; 17\(\rightarrow\)18\(\rightarrow\)15 \\ Truck 2 & 0\(\rightarrow\)14\(\rightarrow\)16\(\rightarrow\)0 & Drone 2 & 14\(\rightarrow\)7\(\rightarrow\)13\(\rightarrow\)16; 16\(\rightarrow\)10\(\rightarrow\)0 \\ Truck 3 & 0\(\rightarrow\)9\(\rightarrow\)11\(\rightarrow\)1\(\rightarrow\)8\(\rightarrow\)12\(\rightarrow\)19\(\rightarrow\)0 & - & - \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Initial planning stage delivery scheme.