Reserve Driver Online Scheduling for Transit Operations

该奖项的目标是开发随机算法，以提高备用司机的利用率，当公交机构(如公共汽车、轻轨、地铁、渡轮)需要使用备用司机来应对计划内和计划外缺席、公交车故障、天气和特殊事件时。开发的算法将最大化奖励(分配给待命司机的工作量)，方法是在正在考虑的工作分配给后备司机时实现的奖励与未来工作可能带来的更高奖励之间进行权衡，后者可能会因为之前的决定而被拒绝。算法将通过有策略地将部分工作分配给加班司机来实现这一目标，以提高备用司机的整体利用率。这些决定将基于从算法指定的概率分布中随机抽取的结果。由于作业到达间隔时间和持续时间从一天到第二天有很大差异，基于平均性能的算法在许多情况下可能表现不佳。因此，开发的算法将致力于在最坏的情况下实现最佳性能。如果成功，研究将产生备用司机工作分配问题的实时解决方案，该问题保证性能不低于最佳可能性能的某个阈值，其中，如果在进行工作分配之前知道所有工作，并且此类分配是最优的，则实现后者。它将为一类算法提供概念上的证明，该算法包括一个可由用户选择的可自由选择的参数，其值将用于传达用户对以下两种方法之一的偏好程度：接受所有可以调度的作业，或部署一种随机化算法，其建议取决于作业长度。如果成功，这项研究的结果将有助于实现候补司机调度过程的自动化，并使工作分配更有效率，潜在地为公交机构每天节省数千美元。数据显示，后备司机的利用率相对较低(50%至60%)，同时加班费支出较高(大型交通机构每天的加班费约为数万美元)。更广泛地说，这项工作也将有助于在高度随机的应用领域中开发新的调度方法。

The objective of this award is to develop randomized algorithms to improve utilization of reserve drivers when transit agencies (e.g., bus, light rail, subway, ferry) need to use them to cover work that arises from planned and unplanned absences, bus breakdowns, weather, and special events. The developed algorithms will maximize reward (amount of work assigned to on-call drivers) by trading off the reward that would be realized if a job being considered were assigned to a reserve driver against a potentially higher reward from a future job, which could be rejected on account of the earlier decision. The algorithms will achieve this goal by strategically assigning some work to overtime drivers to improve the overall utilization of reserve drivers. Such decisions will be based on the outcomes of random draws from probability distributions specified by the algorithm. Because the job inter-arrival times and durations vary significantly from one day to the next, average performance based algorithms can perform poorly in many instances. Therefore, developed algorithms will aim to achieve the best performance in the worst-case. If successful, the research will produce a real-time solution to the reserve driver work assignment problem that guarantees performance no worse than a certain threshold of the best possible performance, where the latter is realized if all pieces of work are known before making work assignments and such assignments are made optimally. It will provide a proof-in-concept for a class of algorithms that include a discretionary parameter, to be selected by the user, whose value will serve to convey the degree of a user's preference for one of two approaches: accept all jobs that can be scheduled, or deploy a randomized algorithm whose recommendation depends on the job length. If successful, the results of this research will serve to automate the reserve-driver dispatch process and make work assignment more efficient, potentially saving transit agencies thousands of dollars daily. Data show relatively poor utilization of reserve drivers (50 to 60 percent range) and simultaneously high expenditures on overtime (of the order of tens of thousand of dollars daily for large transit agencies). More broadly, this work will also contribute to the development of new scheduling approaches in highly random application domains.