# A Branch-and-Price Algorithm for the Online Scheduling of Valet Drivers
## 6 Computational Experiments
### Impact of the Scheduling Time  
In this section, the impact of scheduling time on the OVDP is investigated. As it is known, scheduling time is also a very important parameter for the valet driving platform. The experiment setting is similar to that in Section 6.2, except the length of the scheduling time is adjusted here. The number of valets is set as 100, the number of orders is set to be 300, and the pooling time is supposed to be 5 min. We then test how the total objective function value changes over various scheduling times. A total of 20 instances are generated and tested. For each instance, we only change the value of the scheduling time, keeping other parameters unchanged. The experimental results are shown in Table 7 and Figure 9.  
Figure 8: The total cost with respect to the pooling time. In Table 7, the numbers in bold face and the numbers marked with a star represent the minimum and maximum total objective function values obtained for each instance, respectively. For the column of \"10 s\", because the scheduling time is set to be small, it is observed that no feasible solution can be found. However, as the scheduling time increases, as is shown in the column of \"20 s\", it is discovered that at least one feasible solution can be obtained for each instance. Based on the bold-face numbers, it is observed that the minimum total objective value of each instance mainly occurs when the scheduling time is 40 s. The maximum total objective value of each instance occurs when the scheduling time is 5 min. From Figure 9, it can be clearly observed that the value of the overall objective initially decreases and then increases. To shed light on the above trend, a possible explanation is provided. On the one hand, when the scheduling time is relatively small, for some instances, it will be difficult to obtain feasible solutions. For longer periods of time, a feasible solution could be obtained, but it is still not optimal. This is why increasing the scheduling time at the beginning will reduce the total objective value. On the other hand, during the scheduling, some valets may experience idleness and wait for the platform to assign new orders. For such a reason, the longer the scheduling time, the longer the waiting will be for the idle valets. In addtion, longer scheduling time also makes the overall efficiency of valets lower, which naturally leads to the increase of the objective value. Additionally, the longer scheduling time further narrows down the remaining time window when assigning the orders. For example, when \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & \multicolumn{6}{c}{**Scheduling Time**} \\ \cline{2-7}
**Instance** & **10 s** & **20 s** & **40 s** & **60 s** & **3 min** & **5 min** \\ \hline ins-1 & **1719.6** & 1720.5 & 1720.3 & 1725.9 & 1730.5 & 1738.3 * \\ ins-2 & — & 1730.0 & **1728.2** & 1728.8 & 1737.6 & 1760.4 * \\ ins-3 & — & 1750.1 & **1746.2** & 1747.2 & 1761.0 & 1769.6 * \\ ins-4 & — & **1743.6** & 1747.4 & 1748.3 & 1758.0 & 1777.7 * \\ ins-5 & 1791.9 & **1790.4** & 1799.0 & 1803.0 & 1811.8 & 1818.4 * \\ ins-6 & — & 1749.6 & 1748.6 & 1753.1 & 1771.7 & 1777.1 * \\ ins-7 & — & 1771.7 & **1771.6** & 1771.6 & 1780.0 & 1794.0 * \\ ins-8 & 1743.3 & 1743.3 & 1741.7 & **1740.1** & 1746.4 & 1762.0 * \\ ins-9 & 1811.4 & 1811.4 & **1800.9** & 1802.7 & 1814.8 & 1849.1 * \\ ins-10 & 1819.3 & 1819.3 & **1815.6** & 1815.6 & 1983.5 & 1991.0 * \\ Average & — & 1771.6 & **1770.5** & 1772.4 & 1832.1 & — \\ \hline \hline \end{tabular}
\end{table} 
Table 7: The impact of scheduling time on OVDP. Figure 9: The total cost with respect to the scheduling time. the scheduling time is longer than the width of the original time window of the order, the completion of the scheduling surely exceeds the time window. Therefore, when the scheduling time increases after reaching the minimum objective value, an ascending trend is expected. Eventually, no feasible solution can be obtained when not enough time is left for the scheduling process.