Algorithm helps transit agencies schedule reserve drivers
More than25 percent of a typical transit agency’s bus drivers do not have regular work assignments. These reserve drivers cover work resulting from both planned and unplanned work assignment changes such as training, vacations, driver illness, weather, equipment breakdowns, and unexpectedly high volumes of riders on some routes.
A dispatcher assigns planned open work to reserve drivers a day in advance, but unplanned work is assigned as it becomes available without knowledge of which pieces of work may become available later that day—giving rise to the challenging problem of online interval scheduling.
“This is a complex problem with a lot of different factors at play,” says Diwakar Gupta, a professor in the Industrial and Systems Engineering Department. “Assignment decisions must be made sequentially without information about all potential future job requests, and a driver’s earlier assignment may not be interrupted to accommodate a new job. Also, the scheduler may need to select a particular driver when multiple drivers can perform a job, but they do not all have the same amount of time remaining in their duty shift.”
Making assignment decisions is a balancing act that requires choosing between reserve operators or regular operators receiving overtime pay. For example, researchers examined sample data from Metro Transit and found that the average utilization of reserve drivers was between 50 and 60 percent; at the same time, the daily overtime usage during weekdays was well over 100 hours in three of the agency’s largest garages, adding tens of thousands of dollars in overtime costs daily. On the other hand, overtime drivers are fully productive during these assignments, while reserve operators may not be.
To help address this trade-off, U of M researchers designed an algorithm that increases the amount of work covered by same-day reserve drivers. “Because reserve drivers’ wages are already committed and overtime drivers are paid for each minute of extra work performed, increasing the amount of work assigned to reserve drivers can result in savings for transit agencies,” says Gupta.
After conducting in-person observations of transit dispatch operations and performing a robust review of existing literature on interval scheduling, researchers created and tested the new, improved algorithm for online interval scheduling in a transit setting.
“We designed our algorithm to strike a balance between accepting all jobs that can be assigned to reserve drivers and a strategic approach that accepts only jobs longer than a certain threshold in order to achieve the best possible performance in both average and worst-case scenarios,” says Gupta. “One way we did this was to strategically assign some of the work to overtime drivers in order to improve the overall utilization of reserve drivers.”
The National Science Foundation sponsored the research. Metro Transit provided data and allowed a student to shadow dispatchers in one of its garages to help the team learn how assignment decisions were made.
“Metro Transit is committed to delivering all scheduled service and to do so as efficiently as possible while working within the constraints of our work rules and labor agreement,” says Brian Funk, deputy chief operating officer for Metro Transit’s bus service. “Professor Gupta’s research in this area can help to inform staff of the trade-offs when making these challenging decisions.”
The result of this research is an easy-to-implement algorithm with fail-safes such as a dispatcher override feature for certain decisions. Not only does this new method of interval scheduling offer significant potential savings for transit agencies, it has many possible uses in other applications that require the on-demand processing of jobs.