The algorithm was able to increase the efficiency of routes by 20% in 30 minutes compared to thousands of hours of work for specialists.
Route Fifty described how Boston faced high costs for school transportation due to complicated and winding routes, looked for data processing specialists and was able to fix the situation in one summer.
Researchers at the Massachusetts Institute of Technology helped to solve the problem. They won the contest for the best algorithms, developing a system that takes into account not only the basic parameters but also, for example, the desire of children to ride with the same driver and sit on different buses.
Thanks to the developed algorithm, children began to come to school faster, and travel time was reduced, which reduced the cost of the city.
What was the problem
The Boston Public Schools District (BPS) allows parents to choose their child’s school from a list of ten positions in an attempt to reduce inequalities that can arise when students are confined to their own area.
All primary school students who choose a school more than a mile (1.6 km) from home are provided with a bus to 220 schools, but many facilities are much further away – some schools have children from the “20 Different Postal Codes”.
Classes may start at 7:15 am to 9:30 am, so buses pass through several schools on time to drop off and pick up children.
In 2017, the county faced problems: BPS has the highest annual transportation costs per student in the United States, at about $2,000, which together accounted for about 10% of the county’s total budget. Costs have been rising steadily, and the quality of the bus fleet has been significantly lower than in other large areas.
The problem was compounded by the fact that the BPS provides more transportation for students than most other counties, as the city provides school buses for students in private schools and special education institutions outside the city.
Finding a Solution
To solve the problem of poor and expensive maintenance of bus routes, BPS held a competition in which researchers experimented with anonymous data sets of the district to create effective bus routes and determine the optimal time to start classes at each school.
According to BPS Senior Strategic Project Manager Will Eger, the county wanted a working solution that worked quickly and simultaneously, and that would solve most of the logistics problems.
This required taking into account the millions of variables that affect the choice of route, such as road width, infrastructure, bus capacity (wheelchair lifts or child seats), children’s desire to be served each year by the same bus driver, fighters who needed to sit on different buses.
Boston also had about five thousand students with special needs – students needed to be escorted door-to-door, including if the school did not belong to BPS.
The winner of the competition was the team from the MIT Operations Research Center. According to one of the MIT members, Ph.D. Arthur Delaru, the team spent “hundreds of hours developing the solution”, and in order to take into account all the input data, it was necessary to create “so many options (solutions) that they cannot be listed”.
Their solution replaced a very time-consuming process – before ten route planners spent thousands of hours creating special routes for each child and school.
The route planners still work with BPS to track routes with delays and help drivers navigate. “Google Maps isn’t enough, because the service is optimized for cars and doesn’t take into account the size of buses, for example, when turning around.
The MIT algorithm manages the entire route system, providing the basis for more fine-tuning by designers and changes.
Efficiency
Boston tested a new route system in the 2017-2018 academic year: in 30 minutes, the algorithm was able to create a route map 20% more efficient than the manually developed one, and the longer it works, the better the result.
For example, walking time was reduced for junior high school students and those in disadvantaged areas, and travel time, duration and number of stops were reduced.
The launch of the algorithm in the summer of 2017 reduced the fleet by 50 buses (8% of the total fleet) – the largest reduction in one year. Buses traveled 1.6 million kilometers less than in 2016, and carbon dioxide emissions decreased by 20,000 pounds per day. The district saved $5 million and reinvested them in other school initiatives.
What is the peculiarity of the algorithm
The algorithm does not build a route for each school separately and unites them, but uses a system approach. First, the algorithm assigns stops, arranging them in such a way that the child is not on the way for more than an hour, and then determines the best route through several schools.
Thus, the best solution is not to use a minimum number of buses for each school, but the one that most effectively routes the bus through several schools and can adapt to changes in school rules.
Also, the developers use the second algorithm in the system, which understands the economic and logistical consequences of changes in school rules, such as changes in the schedule of classes, and offers solutions.
In its third year of operation, the BPS launched an algorithm in the summer to create a basic timetable for traffic, and during the school year, it will make manual changes in accordance with changes in school rules.
After optimizing the routes, the experts also proposed to optimize the start time, but have not yet been able to prove to parents the need for changes.