More than Metro Transit buses 25 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.
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. 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.
“This is a complex problem with a lot of different factors at play,” says Diwakar Gupta, University of Minnesota professor in the Industrial and Systems Engineering Department. “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.”
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.
For more information, read the full article in the April 2016 issue of CTS Catalyst.