通学バスのルートをアルゴリズムで最適化し5億円以上のコスト削減に成功

by Denisse Leon

アメリカを舞台とした映画やドラマの中で黄色いスクールバスを見たことがある人もいるはず。このスクールバスは1939年に初めて登場しましたが、その後、学生や学校、道路システムの変化によりどんどん複雑になり、あまりにもコストが高くつき、パフォーマンスも低下するという問題を抱えました。この問題がアルゴリズムによって解決したとして、話題になっています。

How One City Saved $5 Million by Routing School Buses with an Algorithm - Route Fifty
https://www.routefifty.com/tech-data/2019/08/boston-school-bus-routes/159113/

ボストンの公立学校に通うことになる子どもの親は、子どもがどの学校に通うかをいくつかの選択肢から選ぶことができます。これは不平等をなくすことを目的としていますが、ボストンは他の地域に比べて学校の数が多いため、親の選択肢が多くなり、必然的にバスのルートは複雑になってしまいます。

また、ボストンでは他の地域よりも広範囲にわたってスクールバスサービスを提供していることも問題を難しくしています。学校によっては生徒の郵便番号が20種類に及ぶところもあるとのこと。さらに、それぞれの学校は開始時間が異なっていて、朝7時15分に開始するところがあれば9時30分スタートのところもあり、これもバスルート決定の難易度を上げる1つの要素となっています。

2017年、ボストンの公立学校では生徒一人あたりの送迎コストが年間2000ドル(約21万円)になり、学区の予算の10％を占めるまでになりました。

by Austin Pacheco

この問題を解決する業者が見つからなかったため、ボストン公立学校は「匿名化されたデータにより、ボストンの学区における最適化されたルートと最適な授業開始時間を導き出すことができるか？」という研究者向けのコンテストを開催することにしました。

ボストン公立学校のプロジェクトマネージャーであるWill Eger氏によると、「学区内の交通手段をめぐる状況には多くのクセがある」とのこと。このクセとは、道路幅や、車いす用リフトの有無や安全シートの有無といったバス自体のインフラの問題、付き添いがいる子どもの存在、毎年同じ運転手を必要とする子どもの存在、といったものを指します。ドアツードアの送迎を必要とする子どもも約5000人おり、この要望を叶える必要もありました。

コンテストの勝者であるMIT Operations Research CenterのArthur Delarue氏は、上記の問題の解法が無数にあり、解決には何百時間も要したことを語っています。それまでバスのルート決めは、10人のルート作成者が何千時間も使って作業にあたっていましたが、MITのアルゴリズムを使えば、一度の作業でルートの全体像を作り出し、人間の作業員が調整するための基礎を提供してくれるとのこと。Delarue氏は「運転手や校長、親、生徒とやりとりするルート・マネージャーの仕事は重要であり、換えがききません。しかし、訪れる順序やルートのデザインは人間が効率的に解決できるものではありません。これが私たちが提供する付加価値です」とコメントしました。

ボストンが2017年から2018年にかけてで初めてアルゴリズムを導入すると、劇的な変化がみられたとのこと。アルゴリズムは手動で作った地図よりも20％効率的なルートマップを30分で作成し、アルゴリズムを走らせる時間が長いほど、マップの効率性は上がっていきました。2017年の夏にアルゴリズムを利用したところバス50台を削減でき、年間でみると100万マイル(約160万キロメートル)の走行距離削減、1日あたりの二酸化炭素排出量は2万ポンド(約9000キログラム)も減ったそうです。この結果、学区は節約された500万ドル(約5億2500万円)を教室の設備投資に回すことができました。

by Element5 Digital

Eger氏は、新しいルートの作成によって生徒が別のバスに乗ったり、歩く距離が増えたりしていないことを説明。「危険な地域に住む生徒たちの歩く時間を短くしながら、トータルの停留所数を減らすことができたのです」とアルゴリズムによる解法に対し驚きを示しています。

そして、2017年12月、アルゴリズムの推奨に基づいて、ボストン市の学校委員会は30年ぶりに学校の開始時間の変更を承認しました。この承認はボストン全体の85％の学校が関与することとなりました。

8時より前に授業の開始時間を設定することは、10代の学生たちに悪影響があることが研究で示されています。またMITの調査で、ボストンでは多くの両親が遅い授業開始時間を好みつつも、実際に授業開始時間が遅い学校に通っているのは裕福な両親を持つ生徒であるという不平等も明らかになりました。開始時間の変更を承認は、このような報告を受けてのものでした。

しかし、学校開始時間の変更は、実現には至りませんでした。変更内容は「高学年の生徒の開始時間を遅く、低学年の生徒の開始時間を早くする」というものでしたが、学校の開始時間を大きく変更すると家庭のスケジュールに影響を及ぼし、育児負担が増加するという両親からの反対を受けたためです。

by stem.T4L

授業の開始時間の抜本的な変更は行われていませんが、Eger氏はプロジェクトが都市全体にいい影響を与えてきたことを強調し、「これは、ボストンが提供している素晴らしい研究のポテンシャルを私たちが利用した例の1つです。多くの学区は同様の問題を抱えているはずですが、このような課題は私たちの専門知識の範囲ではありません。専門家に頼り、私たちは自分自身の仕事で最善を尽くすことに集中すべきです」と述べました。