# A Branch-and-Price Algorithm for the Online Scheduling of Valet Drivers
## 1 Introduction
Based on the above valet driving related literature, it is observed that the existing research work is mostly taken from a more macro viewpoint. To the best of our knowledge, crew scheduling in the online valet driving problem is largely untouched territory. However, researching crew scheduling in the valet driving problem is crucial, for several reasons. First, as the price of valet driving services remains relatively high, many people are reluctant to use them. This reluctance leads to an increase in drunk driving incidents that often result in serious accidents and injuries. Second, as legal and safety awareness around drunk driving increases, more and more people are beginning to use valet driving services. As the number of drivers and platforms offering these services grows, efficient crew scheduling becomes increasingly important to ensure that customers have access to reliable and timely service. Given the importance of this issue, we conducted research and proposed a targeted B&P algorithm to solve it. This algorithm can obtain the exact optimal solution of SVDP in a short time, which can effectively improve the scheduling efficiency of the platform for  
Figure 1: Snapshots for valet driving in practice. (**a**) Waiting for valet orders [7]. (**b**) Riding to the customer [8]. (**c**) Say no to DUI [9]. valet drivers and bring multiple benefits in many aspects. Efficient scheduling allows the platform to make better use of their available valet drivers, resulting in increased profits for the platform. Additionally, well-scheduled valets are able to complete more orders within a given time period, increasing their earnings. Furthermore, improved scheduling efficiency translates into lower service costs for customers, making the service more accessible and reducing incidents of drunk driving. As the popularity of valet driving services grows, the industry will create new job opportunities, providing additional benefits to society beyond those noted above. In order to better understand the crew scheduling in the online valet driving problem, we first demonstrate the general process of the valet driving service in Figure 2. The customer, a gray figurine, calls for the valet driving service on the cloud platform through a mobile app. After placing the order, the platform will assign a driver, the black figure, to provide the valet driving service at the designated place. After arrival on an e-bike, the valet puts the foldable e-bike in the trunk of the customer's vehicle and then drives the customer to her destination. Upon completing the valet driving service, the valet driver continues to ride to the next customer for service. We summarize the novelty of this paper as follows:  
1. In the present paper, we investigate the crew scheduling in the online valet driving problem (OVDP), which has not been previously studied. The objective of the OVDP is to minimize the total cost while maintaining a certain quality of service. To denote the service quality, a time window is set for each order to ensure that the customer wait time does not exceed the threshold after placing the order. In addition, all the valet driving requests have to be fulfilled. As the valet rides a foldable e-bike while not driving vehicles, the power level of the e-bike should be considered in the OVDP problem. 2. We provide a feasible scheduling strategy for the OVDP problem, which decomposes the OVDP into multiple static valet driving problems (SVDP). 3. We devise a feasible modeling scheme for crew scheduling in the SVDP and formulate a mixed integer linear programming (MILP) model to address the corresponding problem. To solve this problem, we propose an exact branch-and-price (B&P) algorithm. Additionally, we introduce a greedy-based constructive heuristic to efficiently obtain an initial solution and implement an artificial column technique when the initial solution cannot be obtained after branching. Figure 2: Illustration of the valet driving service. 4.