大都市圏における過密スケジュールのバス運行は、バス停留所での乗客の過剰な待ち時間を減らし、信頼できるサービスを提供することが望まれています。しかし、バスの数珠つなぎ現象を回避し、運行を常に最適化することは難しく、バス運行業者が日々のバス走行を最適な方法で計画することは困難です。NEC Laboratories Europeでは、バス定期運行をモデル化し、バス制御行動を実現する人工知能（AI）エージェント「REFLEX」を開発しました。REFLEXは、日々200を超えるバス便をわずか1～2分の計算時間で最適化することができ、乗り継ぎ間隔や配車頻度間隔の順守といった厳密な運行上の条件に従った定期サービスを理論上17～35％改善できました。

1. はじめに

大都市圏での過密なバス運行は、定常的なものとなっています。そのため、バスの数珠つなぎ現象を回避することで、乗客の停留所での過剰な待ち時間（Excess Waiting Times：EWT）を減らし、バスの運行間隔を均一に保つ努力がなされています。しかし、バス運行サービスというものは本来不安定なシステムであり、運行間隔の変動は経路を通じて増大し、バスの数珠つなぎ現象を引き起こす結果となっています^1）。運転間隔が長くなったバスが停留所に着くと、多数の乗客が乗る（そして降りる）ことになり、遅延は更に増大してしまいます。

世界の運輸当局は、より信頼できるサービスを提供するため、月単位のペナルティ＆ボーナス方式に基づいた品質インセンティブ契約制度を確立しています。例えば、ロンドン^2）やシンガポール^3）などの都市は、乗客のEWTに基づいた運行業者の罰金制度を採用しています。

バスの数珠つなぎ現象を軽減するために、停留所停車義務免除を認めることや、バスをコントロールポイントに待機させる時間をスケジュールに埋め込むなど、多数のアプローチがシミュレーションされ、提案されています^4）5）6）。

これを更に進めたものとして、マルチエージェントネゴシエーションに基づいた分散制御アーキテクチャが提案されています^7）。ここでは、停留所とバスはリアルタイムで通信するエージェントの役割を果たし、動的なコーディネート（調整）を行います。我々の研究^8）もまた定期的運行の問題に対する最初の研究の1つです。これは、効果にばらつきはあり得ますが、走行中のすべてのバスに対して制御の実行をネゴシエートするエージェントだといえます。

バスの1日の運行は相互に接続し、また高頻度であるため、定期的なバス運行サービスの最適化は多変数な問題です。その結果、この問題の解決は計算上では困難となっており、バス運行業者は、市販の手動計画ソフトウェアと社内に蓄積した経験を利用して、サービスの信頼性という課題を適切に改善することは期待できない、その場しのぎのスケジュールを作成しています。そのため、毎日のスケジュールを更新したりサービスの信頼性を確実に改善できる制御方策を導入するといった、数珠つなぎ現象やその他の不都合な運行状況へ対応するための手段を取れていません。

2. 規則的なバス運行

都市の戦術的計画段階においては、どのバスサービスにも多数のバス運行が割り当てられています。オンデマンド運行を導入せずに定期的サービスの性能を改善するためには、現行の配車時間を変更するか停留所でバス待機を行う以外には達成できません。

バスサービスは、運輸当局とサービス運行業者が課する多数の要件を満たさなければなりません。最初の要件はバスの運行頻度の割り当て段階で発生します。連続した2台のバスの運行間の配車時間は、乗客の需要水準に合わせて事前に定義された時間以内でなければなりません。

もう1つの代表的な制限事項は最大負荷点制限です。これは、乗客の需要がバスサービス供給を越えないことを保証するため、ある期間内において最低限の回数のバス便サービスを、指定のバス停留所に提供しなければならないというものです。

そして最後の制限要件は、バス運転手は次の便を発車する前には短い休憩を取らなければならないとする、乗り継ぎ間隔に関する制限です。

定期性ベースでの最適化という問題の制御変数には、バス便の配車時間変更と、バス停留所でのバス待機時間があります。

前述の運行制限事項のすべてに従いながら、バス運行業者は特定数のバス停留所でのEWTを最小に抑える必要があります。乗客のEWTは凸関数ではなく非線形関数によってモデル化できます。凸関数では指数計算の複雑さによって計算上解決が困難になり、コンピュータの演算回数が毎秒1,012回と仮定すると、1日180回運行するバスの配車とバス待機の最適な制御方策を発見するためには最長10,175年も必要とします。

3. REFLEXによる定期バスサービスの最適化

REFLEXはローリングホライズン式アプローチに従って最適な制御方策を判別します。REFLEXはバスサービス運行に関する自動車両位置（Automated Vehicle Location：AVL）情報を収集し、図1に示すように配車とバス待機スケジュールを変更します。

したがって、EWTを減少し、運行制限事項を満たすという目標のため、REFLEXは、AVLセンサーを通じてバス運行を観察し、アクチュエータ（配車時間の変更とバス待機）を使って動作する、AIエージェントとして働きます。

REFLEXは確率的アニーリングを利用した乗客のEWT関数を、確率的大域的最小点に収束します。運行制限事項の場合、問題となる制限対象の最適化は、「逐次外点欲張り法」（sequential exterior point greedy method）を利用した非制限問題によって近似が可能であり、前述の運行制限事項のすべてを満たしながら、確率的かつ大域的にEWTの最小化へと収束します。

REFLEXは反復ヒューリスティック探索法を採用しています。この方法の特徴は次のとおりです。

この大域的最小化は確率的（ヒューリスティック）であり、図2にこれを示します。一貫性チェックとしては、目的関数の非凸性及び計算の複雑さから正確な最適化方法は適用不能であるため、このアルゴリズムをランダムな開始ポイントから実行して、より優れた確率的大域的最適解が見つかるかを確認することが可能です。

REFLEXは確率的大域的最適解への迅速な収束を行い、収束までに必要なシーケンスに応じて、異なる指数から多項式までの計算の複雑さを減少します。

4. アジアの運行業者データを利用したREFLEXの試験と妥当性確認

この事例の主なる目標は、（1）乗客のEWT低下による定期的バス運行の改善、（2）すべての制限事項の満足、（3）動的制御方策の実施を可能にするソリューションへの迅速な収束です。

特に大都市圏のバス運行業者は、最先端のソフトウェアパッケージを利用してバスサービスの日々の運行を計画し、運行段階では社内のノウハウに頼っています。このような事情のため、我々は、バス運行業者が現存の計画的運行を改善するためにREFLEXを導入することで、どの程度の利益が得られるかをテストしました。我々は2種類のバスサービス（第一は循環、第二は双方向）のテストを行いました。これら2種類のバスは、以下の条件で選択したものです。

循環サービスは毎日n=245便運行し、7.5kmをカバーし、S=22のバス停留所に毎便平均移動時間37分のサービスを提供しています。両サービスのトポロジーを図3に示します。

循環バスサービスは、住宅街、学校、公共施設をカバーする支線サービスであり、大量高速輸送機関（Mass Rapid Transit：MRT）の駅に接続します。

EWTスコアは0.2098分であり、最適化したバス運行を使用する毎日の運行において、5つの運行制限事項違反が存在します。REFLEXの適用後、配車時間の再計画によるEWTの理論上の改善は22％になり、更にバス待機制御方策によって35％に増加しました。これに加え、すべての運行制限事項も満たされています。主要停留所のすべてにおける乗客の過剰待ち時間の改善は図4に、5つの頻度範囲制限事項違反については図5に示します。
2556MHzプロセッサを使用し1024MBのRAMを備えたマシンで計算性能試験を実施した結果、REFLEXは1分41秒で収束し、全日のバス運行の動的最適化に適用可能なことが示されました。

第二の事例は、1日の便数n＝224回（方向1に112便、方向2に112便）の高頻度双方向バスサービスに対するものです。平均移動時間は方向1で1時間33分、方向2では1時間29分でした（方向1の距離は23.5km、方向2の距離は22.6km）。両方向ともバス停留所の数は同じであり（一方向60停留所）、バス停留所のトポロジーは図3に示したとおりです。

サービス運行業者は、市販のソフトウェアと社内のノウハウによって毎日のバス運行を最適化した結果、サービス全体のEWTスコアは0.06932分、30件の乗り継ぎ間隔制限事項違反があり、14％において運転士の休憩時間が不適切でした。

この事例では、REFLEXで最適な配車/バス待機制御方策を探索し、1分57秒後にEWTスコアを17％低下させて収束しました。30件の乗り継ぎ間隔制限事項違反は6件に低下し、図6に示すように休憩時間が不適切なバス運転士の割合は14％からわずか2.7％に低下しました。また、REFLEXによって、すべての乗り継ぎ間隔制限事項を満たすには、バス運行業者はバス便を追加導入する必要があることも特定されました。

双方向バスサービスの実行不能性の問題に対し、REFLEXは、外点ペナルティ関数がバス運行業者の要求に応じた制限事項にいくつか違反しても、指定した制限事項を満たすことに重点を置くことができるかを調査しました。感度分析によれば、いくつかの制限事項に他よりも重点を置くと、サービス全体のEWTスコアを大きく劣化させずに（2％未満の変動で）バス運行業者の優先制限事項を満たせることが示されました。
バス運行業者は、REFLEXの高速収束を使って、さまざまなシナリオを検討できます。例えば、REFLEXはすべての運行制限事項を満足させながら定期的運行を最適化するだけではなく、いくつかの制限事項に違反があった場合には定期性に関する改善を検討することができます。定期性の改善が困難な場合には、運行業者は主要でない制限事項のいくつかは緩和するという決定ができ、これは非常に有益な機能です。図7に、双方向バスサービスを対象とした、この方針による結果を示します。

5. むすび

我々は、過密な大都市圏での定期的バス運行を改善するため、動的配車/バス待機のフレームワークであるREFLEXを導入し、2種類（循環と双方向）の都市バスサービス運行の定期性最適化のための試験を行いました。その結果、実施可能な改善策があれば、すべての運行上の制限事項をREFLEXで満たすことが可能となりました。

REFLEXは運行上の制限事項の優先順位付けが可能な構造を備えており、バス運行業者の社内ノウハウ及び市販ソフトウェアに基づいて計画された運行と比べて、乗客のEWTが17％～35％まで改善しました。

なお、この研究の一部は、NEC Laboratories Singaporeの協力により行われました。

参考文献

執筆者プロフィール

Konstantinos GKIOTSALITIS NEC Laboratories Europe NEC Europe Ltd.
Nitin MASLEKAR NEC Laboratories Europe NEC Europe Ltd.