Here’s a math problem even the brightest school districts struggle to solve: getting hordes of elementary, middle and high school students onto buses and to school on time every day. 
Transporting all of these pupils presents a large and complex problem. Some school districts use existing software systems to develop their bus routes. Others still develop these routes manually.
In such problems, improving operational efficiency even a little could result in great advantages. Each school bus costs school districts somewhere between US$60,000 and $100,000. So, scheduling the buses more efficiently will result in significant monetary savings.
Over the past year, we have been working with the Howard County Public School System (HCPSS) in Maryland to analyze its transportation system and recommend ways to improve it. We have developed a way to optimize school bus routes, thanks to new mathematical models.
Finding the optimal solution to this problem is very valuable, even if that optimal solution is only slightly better than the current plan. A solution that is only one percent worse would require a considerable number of additional buses due to the size of the operation.
By optimizing bus routes, schools can cut down on costs, while still serving all of the children in their district. Our analysis shows that HCPSS can save between five and seven percent on the number of buses needed.
Route planning
A bus trip in the afternoon starts from a given school and visits a sequence of stops, dropping off students until the bus is empty. A route is a sequence of trips from different schools that are linked together to be served by one bus.
Our goal was to reduce both the total time buses run without students on board – also known as aggregate deadhead time – as well as the number of routes. Fewer routes require fewer buses, since each route is assigned to a single bus. Our approach uses data analysis and mathematical modeling to find the optimal solution in a relatively short time.
To solve this problem, a computer algorithm considers all of the bus trips in the district. Without modifying the trips, the algorithm assigns them to routes such that the aggregate deadhead time and the number of routes are minimized. Individual routes become longer, allowing the bus to serve more trips in a single route.
Since the trips are fixed, in this way we can decrease the total time the buses are en route. Minimizing the deadhead travel results in cost savings and reductions in air pollution.
The routes that we generated can be viewed as a lower bound to the number of buses needed by school districts. We can find the optimal solution for HCPSS in less than a minute.
Serving all students
While we were working on routes, we decided to also tackle the problem of the bus trips themselves. To do this, we needed to determine what trips are required to serve the students for each school in the system, given bus capacities, stop locations and the number of students at each stop. This has a direct impact on how routes are chosen.
Most existing models aim to minimize either the total travel time or the total number of trips. The belief in such cases is that, by minimizing the number of trips, you can minimize the number of buses needed overall.
However, our work shows that this is not always the case. We found a way to cut down on the number of buses needed to satisfy transportation demands, without trying to minimize either of the above two objectives. Our approach considers not only minimizing the number of trips, but also how these trips can be linked together.
New start times
Last October, we presented our work at the Maryland Association of Pupil Transportation conference. An audience member at that conference suggested that we analyze school start and dismissal times. By changing the high school, middle school and elementary school start times, bus operations could potentially be even more efficient. Slight changes in school start times can make it possible to link more trips together in a single bus route, hence decreasing the number of buses needed overall.
We developed a model that optimizes the school bell times, given that each of the elementary, middle and high school start times fall within a prespecified time window. For example, the time window for elementary school start times would be from 8:15 to 9:25 a.m.; for middle schools, from 7:40 to 8:30 a.m.; and all high schools would start at 7:25 a.m.
Our model looks at all of the bus trips and searches for the optimal combination of school dismissal time such that the number of school buses, which is the major contributing factor to costs, is minimized. We found that, in most cases, optimizing the bell times results in significant savings regarding the number of buses.
Next steps
Using our model, we ran many different “what if?” scenarios using different school start and dismissal times for the HCPSS. Four of these are currently under consideration by the Howard County School Board for possible implementation.
We are also continuing to enhance our current school bus transportation models, as well developing new ways to further improve efficiency and reduce costs.
For example, we are building models that can help schools select the right vendors for their transportation needs, as well as minimize the number of hours that buses run per day.
In the future, the type of models we are working on could be bundled into a software system that schools can use by themselves. There is really no impediment in using these types of systems as long as the school systems have an electronic database of their stops, trips and routes.
Such software could potentially be implemented in all school districts in the nation. Many of these districts would benefit from using such models to evaluate their current operations and determine if any savings can be realized. With many municipalities struggling with budgets, this sort of innovation could save money without degrading service.
Ali Haghani, Professor of Civil & Environmental Engineering, University of Maryland and Ali Shafahi, Ph.D. Candidate in Computer Science, University of Maryland
Shares