ドイツのシーメンス株式会社の研究開発部はドイツ国鉄と協力し、AIを使用して、鉄道駅のスケジューリングシステムのプロトタイプを開発しました。 プロトタイプのために選ばれた駅は、1時間に68列車以上が14の線路のいずれかに出入りします。プラットフォームは6つ、線路は14本という、かなり大きい駅です。
予め計画された時間表の一部分
このコンピュータシステムは、列車が遅延した際に起こるリアルタイムでのスケジューリング問題に取り組みます。このような場合、すでに存在する時刻表との誤差を最小限に抑えて、新しい到着時間を再計画します。プロトタイプシステムは、実際の鉄道ネットワーク及び予め決められた時刻表から得られたデータサンプルに基づいてリアルタイム条件の元で作動します。
この対話的なツールによって、駅の他の活動にもスケジュールを合わせることができます。例えば、線路やプラットフォームは、保守工事の際、数時間閉鎖することがあります。 あるいは、予定されていない列車が到着し、それが優先順位の高い列車であることがあります。
上の図は、予め決められた時刻表の一部です。X軸に示されている番号・アルファベットはプラットフォームの名前です。40と80の線路は、プラットフォームへ着けることなく駅を通り過ぎる列車のための線路です。Y軸には時間が示されています。ここに示されている図は、大きなモニタースクリーンで実際に表示できる時間表と比較して小さな部分となっています。
列車は、駅の両端から入ってきます。どちらから入ってくるかは、到着・出発の左右のタグにて表示されています。遅延が確認された場合には、到着時間の下にそれが示されています。
現実には、この駅で3人の駅制御担当者が、入ってくる列車をリアルタイムでプラットフォームへ割り当てています。この際に彼らが重要視していることは、乗客の移動(元々予定されたプラットフォームから新しく割り当てられたプラットフォームへの移動)を少なくし、ある列車には優先順位を与え、かつ安全基準を守ることです。
このコンピュータシステムはすべての駅の状況をモデリングし、駅制御担当者が上の仕事を行ないやすいようにします。新しいスケジュールの決定に合った制約を特定し、システムは良い解を探索します。
多くのすでに確立された規則や安全性の規則がある場合からは、固定的な制約が定義されます。列車が通り過ぎたことを保証するために切替え交差部分を空きにしておく時間の制約などがこれにあたります。これらの固定された制約は、新しく計算されたスケジュールでも破られることはありません。
一方、より緩やかな制約には、例えばプラットフォームで列車が止まっていなければいけない最短時間に関する制約があります。これは例えば予め計画された時間よりも短くなることがあります。ローカル列車が遅れた際に、その列車が交差を越えて割り当てられたプラットフォームへ入ってくる時間が遅れることがあります。これにより、他の同じように優先度が低い列車が駅の外で待たなければいけない場合が生じます。 ローカル列車が大幅に遅れた場合、それによって、この列車と接続する遠距離列車が玉突き式に影響を受けることがあります。線路時刻表は、列車間の依存性を示します。これにより、乗客が確実に接続列車に乗れるようにしています。
システムは駅制御担当者からの修正及び列車の遅延を基礎に新しいスケジュールを計算します。これらの時間と割当の制約により時刻表は制限されます。新しいスケジュールは、列車のプラットフォームでの待ち時間を短縮する、あるいは、他の列車を遅らせる、あるいは最悪のケースでは列車と乗客をより負荷の少ないプラットフォームに移動させるなどして作られます。乗客の移動が発生する場合には、同じプラットフォームの反対側への移動ですむのならば、問題が少なくてすみますが、地下道などを使っての移動が発生することはなるべく避けねばなりません。
再スケジュールされた時刻表の一部
上記時刻表の全部分
このような問題の場合、ある遅延から生じた問題の解決方法は一つではありません。
ですから、このシステムはより主観的な最適化に応じることができる対話的となっています。このシステムでは、乗客があるプラットフォームで乗降するために列車が停車している時間が図の上で示されています。時刻表を再スケジュールした時に(上を参照して下さい。)再割当が、元のスケジュールの右側に表示され、駅のスケジュールのインパクトの厳しさに応じて色づけがされています。駅制御担当者はそれによって、ある種の列車(学校の遠足、あるいは老婦人の待っている列車)は元のプラットフォームへ残すべきで移動させてはいけないと設定し、再スケジューリングを走らせます。この再スケジューリングは、小さめのUNIXのワークステーションで20秒ほどかかります。この時間は、実際にリアルタイムで大きめの多忙な鉄道駅で使用するのに十分な性能です。
このアプリケーションは、2年人分の開発工数をかけ、1万5千行のプログラムです。 このコード数の3分の1は、Motifベースのグラフィックの為に使われています。グラフィックもPrologで書かれています。IF/Prologの制約処理パッケージにより、この問題を、効果的に、読みやすい便利な形式で書くことができるようになっています。IF/Prologにより、開発者は、問題をルールと制約として表現することができ、十分とは言えないソルバーの設計に集中する必要はなくなります。
IF/Prologは、多くのデータの形式と共に、ルールと制約を、読みやすい修正可能な形式に設定します。この標準制約解決技術は、問題が生じた時に、それを処理できる数の解決の選択肢に狭め、駅制御担当者がより高度なレベルでの問題処理ができるような解決を選べるようにしています。
ある駅スケジュールのサンプル