# A Branch-and-Price Algorithm for the Online Scheduling of Valet Drivers
## 6 Computational Experiments
### Comparison with Commercial Solver  
In the field of operations research, Cplex is a widely used commercial mathematical programming solver. Due to its excellent solving efficiency and accuracy, the Cplex solver is considered one of the most advanced solvers currently available. Many researchers use Cplex to test algorithms and models they have developed and compare their performance with Cplex's performance as a benchmark. Therefore, in our research, we also use Cplex's solving performance as a benchmark to test the performance of our proposed algorithm. We input the objective function and constraints of the problem defined in Models (1)-(16) into the Cplex solver by programming. The Cplex solver uses its internal optimization algorithms to find the optimal solution and returns the obtained solution and the time taken to solve it as a benchmark for comparison. Moreover, we can set the maximum solving time. If the global optimal solution is not found within the specified time, the solver will output the current optimal solution and the current gap. Therefore, in this subsection, we evaluate the performance of the B&P algorithm in comparison with Cplex in small, medium, and large scales. In the experiment, a 30-min online scheduling process of OVDP is simulated. The pooling time is set to be 5 min and the scheduling time is 1 min. The pickup and delivery points are generated randomly for all the orders. The release time for each order is randomly generated between 0 and 30 min. The width of the time window is 15 min, and the left time window is the order release time. The initial positions of all the valets are also generated randomly. The battery power level of the valets' electric bicycle is generated randomly between 15 and 30 km, and the initial available time of each valet is assumed to be between 0 and 15 min. For each group of experiments, the ratio of the number of orders and the number of valets is used to reflect the three different order levels. The ratios are 1, 2, and 3, respectively. For small, medium, and large scaled instances, the number of valets is 50, 75, and 100, respectively. The testing results with respect to different scales are demonstrated in Tables 3-5. For each table, the first column denotes the name of a type of instance. For example, \"50-100\" means that there are 50 valets and 100 orders in this type of instance, and the ratio of order quantity to valet quantity is 2. For each type, that is, order level, the performance of five instances are recorded. The following six columns present the performance comparison between Cplex and the B&P algorithm. In this experiment, we simulated a 30 min online scheduling process of OVDP, and the polling time for each round is 5 min, so there will be 6 rounds in total. The column \"Obj\" denotes the total objective function value, which is the sum of the objective function value of each round. Similarly, the column \"Time\" standsfor the total computing time, which is the sum of the computing time of each round. The column \"CR\" represents how many rounds have been completed. For example, 5/6 means that five out of six rounds of scheduling have been completed, which means no feasible solution is obtained when calculating the sixth round of scheduling. At this point, the \"Obj\" and \"Time\" cannot be recorded for this instance. In addition, there are extra two indicators, \"Time-I\" and \"Obj-I\", to further illustrate the performance of the proposed B&P algorithm.