Reserve Driver Online Scheduling for Transit Operations

点击翻译按钮获取中文摘要

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.