U researchers design scheduling algorithm

Metro Transit could use the new system to assign drivers and save money.

Kristina Busch

University of Minnesota researchers are working to create an algorithm to solve scheduling issues for public transit. 
 
 
A study found that dispatchers manually assign driving jobs to workers on a daily basis, and when bus drivers call in sick or have some sort of emergency, dispatchers must quickly assign jobs to reserve drivers or overtime bus drivers.
 
 
“The need for reserve drivers happens at any time,” said project lead researcher and industrial and systems engineering professor Diwakar Gupta. “We asked, ‘What is the best way to assign a job whenever someone calls in sick or late or is involved in some kind of accident?’”
 
 
Gupta, along with other University researchers, designed and tested an algorithm for online interval scheduling that eliminated bias in scheduling and allowed reserve drivers to be assigned to shifts, which could lower costs because overtime drivers are more expensive. 
 
 
These assignments are difficult to plan for, according to the study. About 25 percent of bus drivers across transit agencies do not have regular job assignments. 
 
 
At Metro Transit, reserve drivers, who have fixed hourly wages, were assigned these substitute jobs about 80 percent of the time last year, said Metro Transit spokesman Drew Kerr. 
 
 
Overtime Metro Transit drivers were assigned in the other cases, but the agency needed to pay those workers per overtime minute, leading to thousands in extra costs. 
 
 
But the cost saving comes with a caveat: Reserve drivers were found to be less efficient than overtime or regular drivers, according to the study.
 
 
The project, sponsored by the National Science Foundation, created a code and a set of instructions to generate a probability that assigns either a reserve or overtime driver to a certain shift, said Gupta. 
 
 
“Reserve drivers are not different from other drivers because their salary is fixed. … If you make them sit idle, you’re still paying their salary,” Gupta said. “They are paid for working eight hours regardless if they drive a bus or not.”
 
 
The algorithm still needs some work, and it is still just a concept, he said. He and other University researchers plan to engage with Metro Transit and work out any problems so they can potentially implement the algorithm in the future, Gupta said. 
 
 
“Metro Transit is committed to operating effectively and efficiently, and that includes continually reviewing the utilization of reserve [drivers],” Kerr said.
 
 
By working with the University’s External Stakeholder Engagement program, he and researchers hope to discuss the algorithm with other experts. 
 
 
If employers can automate the dispatch process, he said, they won’t need as many dispatchers. Still, Gupta said, it’s a double-edged sword because dispatch automation could mean fewer jobs.  
 
 
“Job assignment will be more transparent, and we can override the algorithm to change if we wanted to,” he said. “Sometimes people don’t know why they were assigned to a certain shift or job, so this removes any potential bias.”