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.