# A Branch-and-Price Algorithm for the Online Scheduling of Valet Drivers
## 6 Computational Experiments
### Impact of the Pooling Time
From the \"8 min\" column, it can be seen that when the pooling time is large, there may be a situation where no feasible solution can be found. Therefore, we did not include the data from the \"8 min\" column in Figure 8. In addition, when the pooling time is 5 min or 6 min, the objective values are very close. Most of the minimum values are obtained when the pooling time is set as 5 min or 6 min. Therefore, it is believed that the best pooling time should be between 5 min and 6 min. In particular, instances 4, 13, 14, and 16 are almost in line with this trend, showing few irregularities. In addition, instance 8 is also basically in line with the trend of falling first and then rising, but the minimum value is obtained when pooling time is 4 min. To interpret the observed trend, it is assumed that the oracle exists, and the order details are known within 60 min in advance. Then, the global optimal solution can be obtained for the 60 min online scheduling. However, in reality, only the information of a single round can be realized every time, hence only the optimal scheduling for this round can be made. For example, if the pooling time is 5 min, then 60 min will be divided into 12 rounds. We can derive the optimal solution for each round, but for the 60 min as a whole, only 12 local optimal solutions are achieved. If the pooling time is shorter, then each round \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & & & & & & **Pooling Time** & & \\ \cline{2-9}
**Instance** & **1 min** & **2 min** & **3 min** & **4 min** & **5 min** & **6 min** & **7 min** & **8 min** \\ \hline ins-1 & 1755.3 & 1737.9 & 1739.0 & 1735.9 & 1733.1 & **1729.3** & 1737.0 & 1730.5 \\ ins-2 & 1798.1 & 1778.3 & 1771.0 & 1756.0 & **1751.9** & 1754.4 & 1764.1 & 1756.0 \\ ins-3 & 1771.9 & 1745.7 & 1745.5 & 1732.3 & 1740.1 & **1723.0** & 1723.7 & 1723.7 \\ ins-4 & 1762.1 & 1752.3 & 1734.4 & 1746.8 & **1728.8** & 1733.1 & 1743.0 & 1729.7 \\ ins-5 & 1741.7 & 1722.1 & 1714.4 & 1707.5 & **1697.4** & 1698.3 & 1702.0 & — \\ ins-6 & 1782.2 & 1768.3 & 1743.0 & 1745.8 & 1747.2 & 1731.4 & **1727.9** & 1740.6 \\ ins-7 & 1790.6 & 1775.6 & 1766.3 & 1754.6 & **1748.3** & 1759.3 & 1765.6 & 1774.1 \\ ins-8 & 1726.8 & 1707.5 & 1704.8 & **1699.6** & 1701.6 & 1704.9 & 1704.5 & 1699.1 \\ ins-9 & 1777.3 & 1765.8 & 1758.3 & 1757.3 & 1748.5 & **1735.9** & 1736.3 & 1738.2 \\ ins-10 & 1736.6 & 1737.3 & 1704.7 & 1708.6 & 1686.9 & 1690.3 & **1685.2** & 1686.6 \\ ins-11 & 1735.1 & 1722.7 & 1711.3 & 1704.6 & 1696.7 & **1694.9** & 1696.0 & — \\ ins-12 & 1782.5 & 1735.3 & 1728.6 & 1722.5 & 1725.3 & 1719.1 & **1718.7** & — \\ ins-13 & 1716.4 & 1712.9 & 1705.1 & 1705.5 & **1689.7** & 1697.5 & 1701.5 & — \\ ins-14 & 1793.7 & 1780.5 & 1779.9 & 1744.9 & **1735.6** & 1744.0 & 1742.9 & — \\ ins-15 & 1614.5 & 1605.7 & 1598.5 & 1589.9 & 1586.5 & **1572.8** & 1590.4 & 1579.3 \\ ins-16 & 1774.3 & 1770.9 & 1766.3 & 1764.4 & **1750.8** & 1752.2 & 1751.0 & 1762.1 \\ ins-17 & 1839.8 & 1824.1 & 1828.4 & 1809.9 & **1796.5** & 1810.8 & 1798.2 & 1797.9 \\ ins-18 & 1697.5 & 1685.4 & 1683.6 & 1672.8 & 1672.3 & **1670.6** & 1676.4 & 1656.1 \\ ins-19 & 1786.3 & 1772.6 & 1741.6 & 1739.7 & 1738.2 & **1729.9** & 1741.4 & — \\ ins-20 & 1773.1 & 1749.8 & 1740.9 & 1715.9 & **1705.4** & 1722.3 & 1728.0 & 1709.4 \\ Average & 1757.8 & 1742.5 & 1733.3 & 1725.7 & 1719.0 & **1718.7** & 1721.7 & — \\ \hline \hline \end{tabular}
\end{table} 
Table 6: The impact of pooling time on OVDP. is a smaller segment relative to the whole, that is, the less information we know in each round, the worse the decision of each round is made for the whole. This explains why the value of the total objective function decreases with the increase of the pooling time at the beginning. Based on the experimental results, we know that the descending trend is not kept. When the pooling time increases to a certain value, the total objective function value will rise again. It is conjectured that the ascending trend is due to the time window of each order.