# A Branch-and-Price Algorithm for the Online Scheduling of Valet Drivers
## 7 Conclusions  
This study focuses on the online valet driving problem with pooling time. The problem is to schedule a cohort of valets to serve the driving orders, which are dynamically released on the platform, with an objective to minimize the total operational cost. To reach the customer site, the valet usually rides on a foldable e-bike, the power level of which is considered as a constraint to fully address the OVDP. Directly handling the OVDP would be difficult and time consuming, thus we decompose the online model into a series of static subproblems. The planning horizon is divided into several segments, each of which is composed of pooling and scheduling stages. To analyze the static valet driving problem, an arc-flow programming model is established, which is then reformulated into a set partitioning form. An exact algorithm based on branch-and-price is designed to obtain the optimal solution to the static subproblem. In order to accelerate the computation process, a label setting algorithm as well as an artificial column technique are employed. In the numerical analysis, the effectiveness of the proposed algorithm is verified. The proposed algorithm outperforms Cplex in terms of computational efficiency and quality of solutions. As a byproduct, the impacts of pooling time and scheduling time on the online valet driving problem are investigated. It is discovered that the best pooling time is around 5 min, and the most suitable scheduling time is approximately 40 s for most of the instances.  
The findings of the present paper reveal that the proposed new scheduling strategy ensures efficient crew scheduling while taking into account the real-time requirement of orders. This algorithm can be applied to current valet driving platforms, and it brings social welfare to valet driving platforms, valet drivers, and ordinary consumers. The most direct benefit is that it can help such platforms better dispatch their valet drivers, thereby reducing the cost of providing valet driving service and allowing valet drivers to complete more orders in a single shift. In addition, the reduction in the cost of valet driving services will also lead to more customers choosing valet driving instead of risky drunk driving, thereby reducing the occurrence of DUI related accidents. With the development of valet driving services, more gig job opportunities will be created and provide additional benefits to society.  
In the future, more complex situations of the OVDP should be considered, such as order cancellation. In particular, the valet driving platform selectively abandons a portion of orders when there are insufficient valet drivers. In terms of solving speed acceleration, more advanced algorithm designs in the B&P could be explored, such as bidirectional labeling algorithms and incorporating various valid inequalities.  
Writing-original draft, L.Z.; Supervision, Z.P. All authors have read and agreed to the published version of the manuscript.  
Natural Science Foundation of China (Grant numbers 72271222, 71871203, L1924063).  
**Data Availability Statement:** Not applicable.  
**Conflicts of Interest:** The authors declare no conflict of interest.