# A Branch-and-Price Algorithm for the Online Scheduling of Valet Drivers
## 3 Problem Description
### Problem Statement  
In the online valet driving problem, we discretize the time into time rounds with the same time length. Each round consists of a pooling time and a scheduling time, which is used to collect and schedule orders, respectively. At the end of each pooling time, the scheduling for this round starts, as does the pooling time for the next round. Each round is considered as a static valet driving problem, but the two adjacent rounds are not independent. For example, the position where the valet finishes the task in the previous round will be the initial position of the next round. The relationship among the round, pooling time, and scheduling time is shown in Figure 3.  
The SVDP is defined on a directed graph \(G=(V,A)\), where \(V=\{0,s\}\cup O\cup P\cup D\) is the node set and \(A=A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\) is the arc set. Nodes 0 and \(s\) represent the source node and sink node, respectively, which are both dummy nodes. Every valet must start from the source node and end at the sink node. Let set \(K\) be the set of valets, \(K=\{1,2,\ldots,k\}\). The node mapping function is defined as \(o(k),k\in K\), where \(o(k)\) is the node of the initial location of valet \(k\). The node set \(O\) represents the set of the initial locations of the valets, where \(O=\{o(1),o(2),\ldots,o(k)\}\). The node set \(P\) stands for the set of pickup nodes, where \(P=\{1,2,\ldots,n\}\) customers are all waiting for service at the pickup nodes. The node set \(D\) indicates the set of delivery nodes, where \(D=\{n+1,n+2,\ldots,2n\}\) are specified destinations. In addition, the pickup and delivery nodes appear in pairs, such as node \(i\) and node \(n+i\) for the order \(i\). The arc set \(A_{1}\) represents the arcs from source node to the valets' initial nodes, which are virtual arcs, where \(A_{1}=\{(0,j)|j\in O\}\). The arc set \(A_{2}\) stands for the arcs from valets' initial nodes to pickup nodes or sink node, where \(A_{2}=\{(i,j)|i\in O,j\in P\cup\{s\}\}\). For pickup and delivery, the arc set \(A_{3}\) contains the arcs from pickup nodes to the corresponding delivery nodes, where \(A_{3}=\{(i,j)|i\in P,\)\(j=i+n\}\). Similarly, the arc set \(A_{4}\) includes the arcs from delivery nodes to the next pickup nodes or sink node, where \(A_{4}=\{(i,j)|i\in D,j\in P\cup s,j\
eq i-n\}\). Because the valet could be scheduled multiple times, the available time \(T_{i}\) of each valet \(i\) needs to be checked before the scheduling starts in each round. To improve the system service level, it is assumed that the customer needs to be served within a certain time window after placing an order. A time window \([e_{i},l_{i}]\) is imposed on each pickup node, where \(e_{i}\) and \(l_{i}\) denote the earliest and the latest time allowed to serve the order \(i\), respectively. The expression \(t_{ij}\) indicates the travel time on arc \((i,j)\), and \(h_{ij}\) indicates the power consumption on arc \((i,j)\). In addition, it is assumed that the valet's e-bike has a power level limit, which means that the valet can no longer take orders when the battery depletes. For better understanding, we provide an example of SVDP, as shown in Figure 4. In this example, there are three valets and three orders. Nodes 1, 2, and 3 are the initial nodes of each valet. Nodes 4, 5, and 6 are the pickup nodes of each order. Nodes 7, 8, and 9 are the delivery nodes of each order. Because the source node and sink node are virtual nodes, they do not appear in Figure 4. In addition, \"Available Time\" represents the time when the valet will complete the current task and become available for the next task. \"Battery level\" refers to the remaining mileage of the valet's e-bike. The information in parentheses, such as \((1,5)\), represents the coordinates of the node, whereas the information in brackets, such as \([55;75]\), represents the time window of the node. Figure 5 shows the corresponding directed graph for this example, where \"AT\" represents \"Available Time\" and \"TW\" represents time window.