SIAM News Blog
SIAM News
Print

A School Bus Trip to the Crossroads of Policy and Optimization

By Dimitris Bertsimas, Arthur Delarue, and Sébastien Martin

When was the last time you saw a school bus? From famous children’s TV shows such as Scholastic’s Magic School Bus to the very real (and often unpleasant) experience of waiting behind one during a morning commute, the yellow school bus has become ingrained in the American psyche. This perception is matched by reality: over 50 percent of U.S. schoolchildren rely on an army of half a million school buses to travel to and from school every day. Every aspect of school district policy—from special education to school choice—hinges on transportation logistics. Getting it right means boosting a district’s finances and significantly improving the quality of the classroom experience.

A Boston school bus on its route. Image courtesy of boston.com.
One can state the problem of routing school buses for a given district fairly simply. All students in the district must be assigned to a bus stop within walking distance of their home. They must be picked up at the same time each day and transported to the school in which they are enrolled. Then, when the afternoon bell rings and classes are done, the students get back on the bus and are dropped off at the same stop. On a given trip, a single bus will usually only carry students for one particular school, but varying start and end times allows buses to serve several schools in succession. The problem then becomes deciding the following: to which stop students are assigned; what time they will be picked up; what buses serve which stops, and in what order; and what time each school in the district will begin classes. The objective is to optimize cost and student wellbeing (e.g., time spent on a bus) while getting everyone to school on time.

In the U.S., very few school districts face a transportation headache as acute as that of Boston Public Schools (BPS). A wealth of special education programs and associated transportation needs, the intricacies of school choice policy and the subsequent effect on student-to-school distance, and the infamous Boston traffic are just a few factors that complicate BPS transportation on a daily basis. The situation’s difficulty justifies why the district spends almost $120 million on transportation every year to deliver more than 25,000 students to over 200 schools.

The BPS routing problem’s inherent complexity manifests itself as a flurry of specific operational constraints. For instance, some students live on narrow streets that cannot be navigated by large buses, some require special vehicle accommodation due to disabilities, while others must be accompanied by adult monitors. Additionally, each individual school can have different requirements for pick-up and drop-off time windows, etc. More constraints must be taken into account in the bell time assignment factor, from parent and staff preferences to pediatric developmental guidelines on student sleep schedules.

In an effort to rein in rising transportation costs and reinvest money into classrooms, BPS chief operating officer John Hanlon and strategic project manager Will Eger organized a month-long “Transportation Challenge” in April 2017. They hoped to drum up interest among both academics and industry leaders in designing innovative solutions for the problem of school bus routing and bell time assignment. We threw our hat in the ring, motivated by BPS’s compelling enthusiasm for creative solutions and the potential impact of millions of dollars of reinvestment into classrooms, in accordance with the MIT Operations Research Center’s core mission of leveraging state-of-the-art analytics to solve important societal problems.

Traffic congestion in Boston in the morning (left) and the afternoon (right). Greener roads are less congested, while redder roads are more congested. Travel time data from the Google Maps API.

As participants, we sought a way to reduce the overall number of buses used daily by BPS, as the high cost of leasing and maintaining a physical bus is the main driver of district transportation spending. The diversity and number of constraints inherent to the problem suggested an optimization-based approach. Over the past 50 years, optimization has proved itself a dependable tool capable of delivering reliable solutions to the most complex real-world problems, from transportation scheduling to personalized health care. Our solution hinges on a judicious decomposition of the problem, allowing us to apply state-of-the-art optimization algorithms to obtain a comprehensive solution. We first assigned students to stops in a way that balances walking distance with the total number of stops per school. After fixing the stops, we provided several school bus routing options for each school. In the final routing step (considering all schools together), we selected a single routing option for each school to maximize re-use of school buses and therefore minimize cost. Lastly, we solved the bell time assignment problem by using our routing engine to compute an approximation of the cost of assigning a particular bell time to a particular school.

High-level view of one bus's itinerary. Map visualization powered by Google Maps.
One can solve each step in the above decomposition using an appropriate optimization formulation. The first step of bus stop assignment can be solved directly as a binary optimization problem. We generated several full-routing solutions for each school by solving a mixed-integer optimization problem using column generation. The last routing step—which aims to produce a routing solution that is optimal for the entire system, rather than individual schools—was formulated as another mixed-integer optimization problem and solved to optimality. Finally, we formulated the bell time selection problem as a quadratic assignment problem and solved it using partially randomized local search methods. Our decomposition and choice of solvers allowed us to compute a solution for the entire problem in under two hours.

During the course of the transportation challenge, we developed the core of our methodology and demonstrated its applicability to Boston’s particular version of the school bus routing and bell time assignment problem. The district compared our approach to other methods, proposed by academic institutions and specialized companies from across the U.S., and awarded us first place in both the school bus routing phase and the bell time assignment phase of the challenge. We projected that our routing solution alone could save up to 120 buses, an 18 percent decrease over the previous year’s 650 buses. Optimizing school bus routing as well as bell time assignment increased projected savings by as much as 100 buses.

A simulation of the Boston Public Schools routing system in action, using fictional students. We overlay schools (in green), bus yards (in black) and bus stops (in red) on the Boston city map, and show the routes followed by school buses (in yellow) throughout the course of the morning. Video built in Julia with the SFML package, travel time data from the Google Maps API.

Because of the sizable potential reinvestment into classrooms, BPS decided at the end of April to implement our routing solution for the upcoming school year (2017-2018). We spent the next four months further tailoring our algorithm to the specific needs of BPS, and our final routing assignment went live in August 2017. However, for the first year BPS decided to limit savings to 50 buses, a measure of caution in light of the accelerated implementation timeline. Ultimately, our routing methods led to an educational reinvestment of $5 million for BPS this year, with possibly larger savings to come over the next few years as our system improves and is implemented more completely.

Our collaboration with BPS represents an innovative approach to public policy, in which administrative leaders join forces with experts at academic and private entities to greatly enhance the efficiency of day-to-day public operations. The enterprise benefited from following an aggressive timeline, going from concept to city-wide implementation in the span of just five months. In the end, this is as much a story about political courage and unflinching work ethic on the part of BPS as it is about analytics positively impacting the educational future of tens of thousands of students.

Dimitris Bertsimas is the Boeing Leaders for Global Operations Professor of Management at the MIT Sloan School of Management. He also serves as co-director of the Operations Research Center and director of the Master of Business Analytics Program at MIT. He has coauthored over 200 scientific papers in optimization, stochastic systems, machine learning, and their application in health care, transportation and finance. Arthur Delarue is a Ph.D. student at the MIT Operations Research Center, working on mixed-integer optimization and its applications to real-world transportation problems under the supervision of Dimitris Bertsimas. Sébastien Martin is a Ph.D. student at the MIT Operations Research Center, with years of experience working on transportation and routing optimization projects at UC Berkeley and MIT, under the supervision of Dimitris Bertsimas and Patrick Jaillet.

blog comments powered by Disqus