Optimized route to school bus with algorithm and succeeded in reducing costs by more than 500 million yen
Some people have seen yellow school buses in movies and dramas set in the United States. This school bus first appeared in 1939, but then it became more and more complex due to changes in students, schools and road systems, and it was too expensive and performance was reduced. It has become a hot topic as this problem has been solved by an algorithm.
How One City Saved $ 5 Million by Routing School Buses with an Algorithm-Route Fifty
Parents of children who are going to Boston public schools can choose from several choices as to which school their children will attend. This is aimed at eliminating inequalities, but Boston has more schools than other regions, so parents have more choices and inevitably complicating the bus route.
Boston also offers a wider range of school bus services than any other region, making the problem difficult. Some schools have 20 postal codes for students. In addition, each school has a different start time, some start at 7:15 in the morning and some start at 9:30, which is another factor that increases the difficulty of determining the bus route. The
In 2017, Boston public schools cost $ 2000 per student per year, accounting for 10% of the school district's budget.
For a researcher who was unable to find a company to solve this problem, Boston Public Schools could “determined an anonymized data to derive an optimized route and optimal class start time in the Boston school district?” Decided to hold a contest.
According to Will Eger, a project manager at Boston Public Schools, “There are a lot of habits surrounding transportation within the school district.” This habit refers to problems with the infrastructure of the bus itself, such as the width of the road, the presence or absence of wheelchair lifts and safety seats, the presence of accompanying children, and the presence of children who require the same driver each year. The There were about 5,000 children who needed door-to-door transfers, and it was necessary to fulfill this demand.
Arthur Delarue from the MIT Operations Research Center , the winner of the contest, tells us that there are a myriad of solutions to the above problem and that it took hundreds of hours to solve. Until then, 10 route creators used thousands of hours to work on bus routes, but using the MIT algorithm, the entire route was created in a single operation, and human workers He said he provides the basis for making adjustments. Delarue said, “The route manager's job with the driver, principal, parents, and students is important and cannot be changed. However, the order of visits and route design cannot be solved efficiently by humans. This is the added value we provide. '
When Boston introduced the algorithm for the first time from 2017 to 2018, there was a dramatic change. The algorithm created a route map that was 20% more efficient than a manually created map in 30 minutes. The longer the algorithm was run, the more efficient the map was. Using the algorithm in the summer of 2017, it was possible to reduce 50 buses, reducing the mileage by 1 million miles (about 1.6 million kilometers) annually, and 20,000 pounds of carbon dioxide emissions per day (about 9000) Kilogram) has also decreased. As a result, the school district was able to use the saved $ 5 million (about 525 million yen) for classroom capital investment.
Eger explains that the creation of a new route has not helped students get on another bus or walk more. “We were able to reduce the total number of stops while shortening the walking time of students living in dangerous areas,” which is surprising to the algorithmic solution.
And in December 2017, based on algorithmic recommendations, the Boston School Board approved a change in school start time for the first time in 30 years. This approval involved 85% of schools across Boston.
Studies have shown that setting class start times before 8 o'clock has a negative impact on teenage students. The MIT survey also reveals the inequality that many parents in Boston prefer a late class start time, but those who actually attend a school with a slow class start time are students with wealthy parents. It was. Approving the start time change was in response to such a report.
However, the change in school start time was not realized. The content of the change was 'slower start time for upper grade students and earlier start time for lower grade students', but if the school start time is changed significantly, it will affect the home schedule and increase the burden of childcare This is because we received opposition from our parents.
While no drastic changes have been made to class start times, Eger emphasized that the project has had a positive impact on the whole city, “This is the great research potential that Boston offers. One of the examples we used, many school districts should have similar problems, but these challenges are not within the scope of our expertise. You should concentrate on doing your best in your own work. '