# A Branch-and-Price Algorithm for the Online Scheduling of Valet Drivers
## 3 Problem Description
### Arc-Flow Formulation  
In this section, the arc-flow model for the SVDP is introduced. There are three kinds of decision variables in the model: (i) a binary variable \(x_{ij}^{k}\), \(x_{ij}^{k}=1\) if valet \(k\) traverses arc \((i,j)\), and 0 otherwise; (ii) a continuous variable \(a_{i}\) that represents the arrival time of node \(i\), \(i\in O\cup P\cup D\); (iii) a continuous variable \(B_{i}\) that represents the remaining battery power at node \(i\), \(i\in P\cup D\). Note that \(B_{o(k)}\), \(k\in K\) is a known parameter, which indicates the initial battery power level at the valet' initial location. For ease of understanding, we list all the symbols used here in Table 2. \begin{table}
\begin{tabular}{c c} \hline \hline
**Symbol** & **Definition** \\ \hline \(n\) & The number of customers (orders) \\ \(K\) & Set of valets \(K=\{1,2,\ldots,k\}\) \\ \(P\) & Set of pickup nodes \(P=\{1,2,\ldots,n\}\) \\ \(D\) & Set of delivery nodes \\ \(D=\{n+1,n+2,\ldots,2n\}\) \\ \(o(k)\) & The initial node of valet \(k\) \\ \(O\) & The set of initial nodes of valets, \\ \(O=\{o(1),o(2),\ldots,o(k)\}\) \\ \(0\) & Source node \\ \(s\) & Sink node \\ \(A_{1}\) & Set of arcs, \(A_{1}=\{(0,j)|i\in O\}\) \\ \(A_{2}\) & Set of arcs, \(A_{2}=\{(i,j)|i\in O,j\in P\cup\{s\}\}\) \\ \(A_{3}\) & Set of arcs, \(A_{3}=\{(i,j)|i\in P,j=i+n\}\) \\ \(A_{4}\) & \(A_{4}=\{(i,j)|i\in D,j\in P\cup\{s\},j\
eq i-n\}\) \\ \(A\) & Set of all arcs, \(A=A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\) \\ \(T_{i}\) & Available time of each valet \(i\) \\ \(a_{i}\) & Arrival time of node \(i\) \\ \(t_{ij}\) & Travel time of arc \((i,j)\) \\ \(h_{ij}\) & Power consumption on arc \((i,j)\) \\ \(c_{ij}\) & The cost of arc \((i,j)\) \\ \(B_{i}\) & Battery power level at node \(i\) \\ \([e_{i},l_{i}]\) & Time window of order \(i\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The definition of symbols. Figure 6: The valet scheduling result of the SVDP example. \[Min\quad\sum_{k\in K}\sum_{(i,j)\in A}c_{ij}x_{ij}^{k} \tag{1}\]  
s.t. \[x_{0,o(k)}^{k} =1,\forall k\in K \tag{2}\] \[\sum_{k\in K}\sum_{i\in o(k)\cup D,i\
eq j+n}x_{ij}^{k} =1,\forall j\in P\] (3) \[\sum_{j\in P\cup\{s\}}x_{o(k),j}^{k} =1,\forall k\in K\] (4) \[x_{i,j+n}^{k}-\sum_{j\in D\cup\{o(k)\},i\
eq j+n}x_{ji}^{k} =0,\forall k\in K,i\in P\] (5) \[x_{i-n,i}^{k}-\sum_{j\in P\cup\{s\},i\
eq j-n}x_{ij}^{k} =0,\forall k\in K,i\in D\] (6) \[\sum_{i\in D}x_{is}^{k}+x_{o(k),s}^{k} =1,\forall k\in K\] (7) \[a_{o(k)} \geq T_{o(k)},\forall k\in K\] (8) Figure 6:0 (9) Figure 6:1 (10) Figure 6:2 (11) Figure 6:3 (12) Figure 6:4 (13) Figure 6:5 (14) Figure 6:6 (15) Figure 6:7  
The objective Function (1) is to minimize the total cost, which is the sum of costs on all the traversed arcs. A smaller total cost means a higher utilization rate of valets and better scheduling results. Constraint (2) ensures that each valet must reach its initial node from the source node through a virtual path, in order to maintain consistency with the path set model generated in Section 4.1. The order nodes visited after that initial node represent the orders completed by the valet corresponding to that initial node. Constraint (3) states that the indegree of each pickup node is 1, and the previous node must be either the valet's initial node or another order's delivery node. This ensures that each pickup node is visited only once, meaning each order must be completed. Constraint (4) implies that after departing from an initial node, the valet can only travel to a pickup node or return to the sink node. If the valet travels to a pickup node, it means that the valet has been assigned an order; if the valet directly returns to the sink node, it means that the valet has not been assigned any orders. Constraints (5) and (6) are flow balance constraints for pickup nodes and delivery nodes, respectively, which means that the indegree of each node equals its outdegree.