An algorithm to optimize school bus routes will save Boston Public Schools as much as $5 million after computer science and logistics experts competed in a 3 month hackathon won by a team from MIT's Operations Research Center. The challenge was similar to the NP-hard Travelling Salesman Problem.

Boston Public Schools (BPS) invited academics and computer scientists from, among others, Google, Microsoft, Uber, Harvard, and MIT to take part in its Transportation Challenge: Solving Routing and Bell Times, the goal of which was reduce its transportation costs and be able to reinvest the savings made to improve the student experience.

Outlining the the problem on the challenge site:

In FY16, transportation costs accounted for $110 million or 11% of the district’s budget. On a per pupil basis, BPS’s transportation cost is the second highest and more than five times the average of the largest 200 public school districts. Meanwhile, transportation costs have continued to increase, up $33M from FY11, a 7.5% annual increase.

The contest had two parts. Round 1 was to come up with an algorithm to reduce the number of bus routes, reconfigure bus stops, maximize the number of students riding each bus, and cut the amount of time that empty buses are on the road. It also had to take into account that some students require wheelchair-friendly buses and others need home pickup. 

This challenge is an elaboration on the Travelling Salesman Problem, which was formulated in 1930 as finding the best possible route between several places. It is known to be NP-hard - that is, an exact solution cannot be found in polynomial time. Instead the best route can be found by optimization techniques.

Currently BPS transportation staff use a software package to build school bus routes and the process takes several weeks to complete.

The winning algorithm for Round 1 produces the routes in around 30 minutes. It was devised by MIT's Quantum Team which consisted of Professor Dimitris Bertsimas, co-director of the Operations Research Center, and two PhD students Arthur Delarue and Sebastien Martin. They used data from Google Maps to analyze traffic patterns during morning and afternoon rush hours, data provided by BPS on students and their assigned schools together with mapping software and optimization techniques.

The new routing model is expected to improve the on-time performance rate for BPS buses, getting students to and from school on schedule much more consistently. The distance that students walk to and from their bus stops is not anticipated to change, on average. In some cases, bus stop locations might change slightly for some students, while remaining the same for others. The MIT team took steps to ensure that no bus stops are sited in unsafe traffic locations.

Bertimas commented:

“Our solution generates thousands of possible routes, and then picks from trillions of permutations the optimal bus route to connect schools throughout the day. Creating this many permutations by hand simply is not possible. Our algorithm creatively combines optimization theory, human intuition and the power of computing,”

Having been awarded the $15K prize for Round 1, the MIT Quantum Team won a further $15K for Round 2  of the contest which was to find optimal bell times (i.e. the start of the school day) for 125 schools that would take into account preferences among the three choices of 07:30, 08:30 and 09:30.

According to the BPS implementing the Quantum Team’s solutions, could save as much as $5 million through the reduction of 50 or more bus routes and having buses run trips to three different schools each morning and afternoon.

It isn't just schools that benefit, the Quantum Team solution could lead to a 20,000-pound reduction in carbon emissions produced by BPS buses each day, and could remove nearly 1 million miles of traffic-clogging bus trips off the road each year.

SOURCE: http://www.i-programmer.info/news/181-algorithms/11083-school-bus-optimization.html