# A Branch-and-Price Algorithm for the Online Scheduling of Valet Drivers
## 2 Literature Review  
In the valet related literature, valet parking takes up the largest percentage of research work. Although valet driving is a field receiving more and more attention, another variant of the valet driving, i.e., valet charging, is considered as well. In the field of electric vehicles (EV), [PERSON] and [PERSON] [16] proposed a novel business model where a platform provides valet charging services to EV users. After the user places a charging order, the valet responds and picks up the low-power EV from the customer and then drives to a charging station. When the battery is fully charged, the valet drives the EV back to the customer. A queuing network model is constructed to capture the stochastic matching dynamics, and an economic equilibrium model is introduced to justify the incentives of valets, customers, and the platform. The EV charging station location problem was discussed in [17], where the valet charging service was concerned with demand uncertainty. The problem was formulated as a two-stage stochastic mixed-integer model, and a SAA-based hybrid-cut L-shaped algorithm was designed to solve it. The similarity between the above studies and the present research is that we both focus on the valet, and the platforms both need to schedule a cohort of valets. However, the crew scheduling was not considered in the valet charging related papers. To the best of our knowledge, there are hardly any papers exploring crew scheduling in the online valet driving problem. Thus, other types of crew scheduling literature are included for an inclusive review. Within the literature on the topic of crew scheduling, it is observed that airline crew scheduling is the most covered topic. In [18], the airline crew pairing optimization problem was investigated, and an algorithm based on a combination of column and cut generation was employed. As for the crew and vehicle scheduling, the schedules of vehicle and crew were to be determined simultaneously in order to satisfy a given set of trips over time. [PERSON] and [PERSON] [19] considered a multi-depot vehicle and crew scheduling problem and constructed a novel mathematical programming model, which is then solved via an exact solution procedure based on branch-and-price. The flexible vehicle and crew scheduling problem faced by urban bus transport was noted in [20]. A MILP model was built and a variable neighborhood search method was used to solve it. At present, the development of EVs is in full swing. Therefore, some scholars also consider the involvement of EVs in the above scenarios. [PERSON] et al. [21] introduced the integrated EV and crew scheduling problem (E-VCSP) considering with a set of timetabled trips and charging stations. An adaptive large neighborhood search method was introduced together with the branch-and-price algorithm to address the E-VCSP. In addition, there are also some less explored domains with respect to crew scheduling. For example, [PERSON] et al. [22] studied the network repair crew scheduling and routing problem, and it accounted for the emergency repair scheduling of a rural road network, which had been damaged by a natural disaster. To obtain the optimal strategy, an exact dynamic programming (DP) algorithm was used, and an iterated greedy-randomized constructive procedure was integrated as well. The home care crew scheduling problem was addressed in [23], where a group of home carers need to be assigned for visiting the patients' homes, such that the total service level is maximized. As a matter of fact, the OVDP problem shares some similarities to the dial-a-ride problem (DARP) to a certain extent. And hence, the literature on the topic of dial-a-ride is reviewed, especially the studies most closely related to the OVDP. The dial-a-ride problem consists of designing vehicle routes and schedules for \(n\) users who specify pickup and delivery requests between origins and destinations [24]. [PERSON] and [PERSON] [25] described and classified the primary features of the DARP and discussed the modeling aspects of the problem.