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.