# A Branch-and-Price Algorithm for the Online Scheduling of Valet Drivers
## 6 Computational Experiments
### Comparison with Commercial Solver
\"Time-I\" represents the increase of the computation time when using Cplex instead of the B&P, which is derived as follows:  
\[\text{Time-I}=\frac{\text{Time(Cplex)}-\text{Time(B\&P)}}{\text{Time(Cplex)}} \times 100\% \tag{39}\]  
\"Obj-I\" represents the increase of the objective value when the commercial solver is employed, which is obtained as below:  
\[\text{Obj-I}=\frac{\text{Obj(Cplex)}-\text{Obj(B\&P)}}{\text{Obj(Cplex)}} \times 100\% \tag{40}\]  
From Table 3, for small-scale instances, it is observed that both Cplex and the B&P algorithm can complete six rounds of scheduling with ratio 1 and 2. Particularly, for the fifth instance in \"50-100\", the B&P algorithm not only outperforms Cplex with respect to computation time, but also is better off in the total objective function value. Except for this instance, the obtained total objective values by Cplex and the B&P algorithm in \"50-100\" are the same. As the ratio reaches 3, for all the instances, Cplex cannot complete six rounds of computation, but the proposed B&P algorithm can. According to Time-I, it is discovered that the computational efficiency of the B&P algorithm is much higher than that of Cplex. Moreover, the larger the ratio, the more advantageous is the B&P algorithm over Cplex. For medium-scale instances in Table 4, it is observed that two more instances of six rounds cannot be completed for Cplex compared with the small-scale cases, when the ratio is 2. In addition, in the type of ratio 3, Cplex fails to complete even one round of scheduling in four instances. In comparison, the B&P algorithm is still capable of solving all the rounds of all the instances. Obviously, the computing efficiency of the B&P is still significantly better than Cplex. \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  & 268.4 & 5.63 & 6/6 & 268.4 & 1.69 & 6/6 & 69.98\% & 0\% \\  & 316.7 & 5.26 & 6/6 & 316.7 & 2.20 & 6/6 & 58.17\% & 0\% \\
50–50 & 306.2 & 4.90 & 6/6 & 306.2 & 1.82 & 6/6 & 62.86\% & 0\% \\  & 297.2 & 5.73 & 6/6 & 297.2 & 1.78 & 6/6 & 68.94\% & 0\% \\  & 324.9 & 5.44 & 6/6 & 324.9 & 1.93 & 6/6 & 64.52\% & 0\% \\ \hline  & 618.9 & 23.53 & 6/6 & 618.9 & 4.86 & 6/6 & 79.37\% & 0\% \\  & 553.4 & 20.54 & 6/6 & 553.4 & 4.36 & 6/6 & 78.77\% & 0\% \\
50–100 & 545.6 & 20.72 & 6/6 & 545.6 & 5.19 & 6/6 & 74.95\% & 0\% \\  & 632.5 & 21.90 & 6/6 & 632.5 & 3.05 & 6/6 & 86.07\% & 0\% \\  & 592.3 & 83.67 & 6/6 & 583.2 & 4.68 & 6/6 & 94.41\% & 1.54\% \\ \hline  & - & - & 2/6 & 864.6 & 9.06 & 6/6 & - & - \\  & - & - & 1/6 & 872.0 & 13.87 & 6/6 & - & - \\
50–150 & - & - & 1/6 & 873.6 & 7.31 & 6/6 & - & - \\  & - & - & 1/6 & 977.0 & 8.87 & 6/6 & - & - \\  & - & - & 4/6 & 883.1 & 10.42 & 6/6 & - & - \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Performance comparison for small-scale instances. For large-scale instances in Table 5, it is observed that the B&P algorithm also has three uncompleted instances out of the six rounds. However, based on the instances whose six rounds have been completed, it is demonstrated that the computation efficiency of the B&P algorithm is still much higher than that of Cplex. In particular, for the second instance in \"100-100\" and the first instance in \"100-200\", the B&P algorithm not only outperforms Cplex with respect to the computational efficiency, but also achieves better total objective function value than Cplex. In summary, based on the numerical results of various scales, the B&P algorithm is significantly better than Cplex in terms of computational efficiency. In addition, in terms of total objective function value, the B&P algorithm also holds advantage over Cplex in the instances where Cplex fails to deliver the optimal solution.