# A Branch-and-Price Algorithm for the Online Scheduling of Valet Drivers
## 6 Computational Experiments
### Impact of the Pooling Time  
In this subsection, the impact of pooling time on OVDP is investigated. As the pooling time is a crucial parameter for the valet driving platform, fine tuning it could help reduce \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & \multicolumn{3}{c}{**Cplex**} & \multicolumn{3}{c}{**B\&P**} & \\ \cline{2-9}
**Instance** & **Obj** & **Time** & **CR** & **Obj** & **Time** & **CR** & **Time-I** & **Obj-I** \\ \hline \multirow{5}{*}{75–75} & 396.6 & 22.61 & 6/6 & 396.6 & 5.41 & 6/6 & 76.09\% & 0\% \\  & 423.7 & 19.89 & 6/6 & 423.7 & 5.24 & 6/6 & 73.66\% & 0\% \\  & 418.3 & 21.53 & 6/6 & 418.3 & 4.52 & 6/6 & 79.01\% & 0\% \\  & 410.1 & 20.08 & 6/6 & 410.1 & 5.66 & 6/6 & 71.81\% & 0\% \\  & 427.4 & 18.58 & 6/6 & 427.4 & 4.39 & 6/6 & 76.37\% & 0\% \\ \hline \multirow{5}{*}{75–150} & 889.4 & 73.33 & 6/6 & 889.4 & 16.38 & 6/6 & 77.66\% & 0\% \\  & - & - & 4/6 & 899.4 & 14.98 & 6/6 & - & - \\ \cline{1-1}  & - & - & 5/6 & 829.7 & 18.92 & 6/6 & - & - \\ \cline{1-1}  & 798.8 & 76.41 & 6/6 & 798.8 & 11.17 & 6/6 & 85.38\% & 0\% \\  & 913.1 & 99.12 & 6/6 & 913.1 & 10.14 & 6/6 & 89.77\% & 0\% \\ \hline \multirow{5}{*}{75–225} & - & - & 1/6 & 1260.5 & 27.34 & 6/6 & - & - \\  & - & - & 0/6 & 1270.8 & 51.32 & 6/6 & - & - \\ \cline{1-1}  & - & - & 0/6 & 1260.8 & 32.64 & 6/6 & - & - \\ \cline{1-1}  & - & - & 0/6 & 1372.5 & 32.93 & 6/6 & - & - \\ \cline{1-1}  & - & - & 0/6 & 1411.4 & 20.71 & 6/6 & - & - \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Performance comparison for medium-scale instances. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & \multicolumn{3}{c}{**Cplex**} & \multicolumn{3}{c}{**B\&P**} & \\ \cline{2-9}
**Instance** & **Obj** & **Time** & **CR** & **Obj** & **Time** & **CR** & **Time-I** & **Obj-I** \\ \hline \multirow{5}{*}{100–100} & 594.0 & 38.15 & 6/6 & 594.0 & 14.27 & 6/6 & 62.60\% & 0\% \\  & 540.1 & 36.98 & 6/6 & 540.0 & 10.10 & 6/6 & 72.69\% & 0.02\% \\  & 557.9 & 39.70 & 6/6 & 557.9 & 11.89 & 6/6 & 70.05\% & 0\% \\  & 545.0 & 36.35 & 6/6 & 545.0 & 13.39 & 6/6 & 63.16\% & 0\% \\  & 561.6 & 44.93 & 6/6 & 561.6 & 15.40 & 6/6 & 65.72\% & 0\% \\ \hline \multirow{5}{*}{100–200} & 1121.3 & 218.58 & 6/6 & 1114.7 & 57.65 & 6/6 & 73.63\% & 0.59\% \\  & - & - & 5/6 & 1136.9 & 26.46 & 6/6 & - & - \\ \cline{1-1}  & 1092.9 & 174.43 & 6/6 & 1092.9 & 30.21 & 6/6 & 82.68\% & 0\% \\ \cline{1-1}  & - & - & 5/6 & 1102.1 & 44.44 & 6/6 & - & - \\ \cline{1-1}  & - & - & 1/6 & 1113.7 & 32.54 & 6/6 & - & - \\ \hline \multirow{5}{*}{100–300} & - & - & 0/6 & - & - & 5/6 & - & - \\ \cline{1-1}  & - & - & 0/6 & 1687.4 & 75.15 & 6/6 & - & - \\ \cline{1-1}  & - & - & 0/6 & 1698.4 & 62.47 & 6/6 & - & - \\ \cline{1-1}  & - & - & 0/6 & - & - & 3/6 & - & - \\ \cline{1-1}  & - & - & 0/6 & - & - & 1/6 & - & - \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Performance comparison for large-scale instances. the overall cost for the valet driving platform while ensuring the service quality. The instances are randomly generated according to the method in Section 6.1, the number of valets is set as 100, the number of orders is set to 200, and the scheduling time is limited to 1 min. We then test how the total objective function value changes with respect to the pooling time. In order to better show the impact of pooling time, in the experiment design, a 60-min online scheduling process is simulated. A total of 20 instances are tested. For each instance, the value of pooling time is the only parameter to be tuned, while keeping the other parameters unchanged. The testing results are shown in Table 6 and Figure 8.  
In Table 6, the bold numbers represent the minimum objective function values with different pooling time for each instance. Based on the row of \"Average\", it is observed that the minimum value is obtained when the pooling time is 6 min. It can be more intuitively seen from Figure 8 that the objective value of each instance demonstrates a trend of first descending and then ascending slowly with respect to the pooling time.