(57)【要約】交通移動計画を最適化する方法に関する。計画監視部は、領域の交通状態に基づいて、交通について第１の計画境界を決定する。計画作成部は、第１の計画境界を用いて、交通について第１の交通移動計画を反復的に作成する。計画作成部は、第１の最適化された交通移動計画として、第１の交通移動計画の中の１つを選択して、交通移動を制御するために出力する。計画監視部は、計画ウィンドウについて、領域の現在の交通状態を判断して、第１の計画境界をアップデートして、交通について、現在の交通状態に基づいた第２の計画境界を提供する。計画作成部は、第２の計画境界を用いて、交通について第２の交通移動計画を反復的に作成し、第２の最適化された交通移動計画として、第１及び第２の交通移動計画の中の１つを選択して、交通移動を制御するために出力する。
2006511394.tif 000002
【特許請求の範囲】
【請求項１】
複数の交通と複数の交通状態とを有する領域について、最適化された交通移動計画を作成する方法であって、
領域の交通状態に基づいて、交通に関する第１の計画境界を決定する工程と、
第１の計画境界を用いて、領域の交通に関する第１の複数の交通移動計画を反復的に作成する工程と、
実行する第１の最適化された交通移動計画として、第１の複数の交通移動計画の１つを選択する工程と、
領域内の交通移動を制御するために、第１の最適化された交通移動計画を出力する工程と、
領域の現在の交通状態を確認する工程と、
現在の交通状態に基づいて、第１の計画境界をアップデートして、交通に関する第２の計画境界を与える工程と、
第２の計画境界を用いて、領域の交通に関する第２の複数の交通移動計画を反復的に作成する工程と、
実行する第２の最適化された交通移動計画として、第１及び第２の複数の交通移動計画の１つを選択する工程と、
領域内の交通移動を制御するために、第２の最適化された交通移動計画を出力する工程とを含む方法。
【請求項２】
実行する第２の最適化された交通移動計画として、第１の最適化された交通移動計画を選択する工程をさらに含む、請求項１の方法。
【請求項３】
実行する第２の最適化された交通移動計画として、第１の複数の交通移動計画の１つを選択する工程をさらに含む、請求項１の方法。
【請求項４】
実行する第２の最適化された交通移動計画として、第２の複数の交通移動計画の１つを選択する工程をさらに含む、請求項１の方法。
【請求項５】
第１の最適化された交通移動計画について、第１の複数の交通状態を用いる工程と、
第１の最適化された交通移動計画について、第１の複数の交通状態と現在の交通状態を比較し、第１の複数の交通移動計画にほぼ基づいて、第２の計画境界を用いて計画を続けて、領域の交通に関する第２の複数の交通移動計画を反復的に作成する工程とをさらに含む、請求項１の方法。
【請求項６】
第１の最適化された交通移動計画について、第１の複数の交通状態を用いる工程と、
第１の最適化された交通移動計画について、第１の複数の交通状態と現在の交通状態を比較し、第２の計画境界を用いて応答良く再計画を実行し、領域の交通に関する第２の複数の交通移動計画として、(ａ) 領域の交通に関する第１の複数の交通移動計画の幾つかにほぼ基づいた第３の複数の交通移動計画と、(ｂ) 領域の交通に関する第１の複数の交通移動計画に依存しない第４の複数の交通移動計画とを反復的に作成する工程とをさらに含む、請求項１の方法。
【請求項７】
第１及び第２の複数の交通移動計画の各々と目的関数値を関連付ける工程と、
計画を続ける際に、第２の計画境界を用いる工程と、
目的関数値に基づいて、第１の複数の交通移動計画の少なくとも１つを破棄する工程と、
第１の複数の交通移動計画の少なくとも１つを、その目的関数値を改善するために変更する工程と、
第１の複数の交通移動計画の中の複数の計画を用いて、第２の複数の交通移動計画の１つを作成する工程と、
現在の交通状態に関する少なくとも１つの変動に応答するように、第１の複数の交通移動計画の少なくとも１つを変更する工程と、
第１の複数の交通移動計画に依存しないように、第２の複数の交通移動計画の少なくとも１つを作成する工程とをさらに含む、請求項５の方法。
【請求項８】
第１及び第２の複数の交通移動計画について、目的関数値を決定する工程と、
目的関数値に基づいて、第２の最適化された交通移動計画として、第１及び第２の複数の交通移動計画の１つを選択する工程とをさらに含む、請求項１の方法。
【請求項９】
目的関数値の各々について複数のゴールを用いる工程をさらに含む、請求項８の方法。
【請求項１０】
目的関数値に基づいて、第１及び第２の交通移動計画をランク付けする工程と、
ランクに基づいて、実行する第２の最適化された交通移動計画を選択する工程とをさらに含む、請求項８の方法。
【請求項１１】
第１の計画境界を用いることを続けて、実行する第１の最適化された交通移動計画として第１の複数の交通移動計画の１つを選択する前に、所定の時間、領域の交通に関する第１の複数の交通移動計画を反復的に作成する工程をさらに含む、請求項１の方法。
【請求項１２】
第１の計画期間を第１の計画境界と、より遅い第２の計画期間を第２の計画境界と関連付ける工程と、
スケジュール変更を入力する工程と、
第１の複数の交通移動計画の少なくとも１つを、第２計画期間及びスケジュール変更に合わせて調節する工程と、
第１の複数の交通移動計画の調節された少なくとも１つを用いて、第２の複数の交通移動計画の少なくとも１つを作成する工程とをさらに含む、請求項１の方法。
【請求項１３】
第１の計画境界をアップデートする前に、調節する工程と、所定の時間、第２の複数の交通移動計画を作成する工程と続けることをさらに含む、請求項１２の方法。
【請求項１４】
第１及び第２の複数の交通移動計画の各々について、対応する目的関数値と対応する存在時間とを与える工程と、
第１の複数の交通移動計画の各々について、対応する存在時間の関数として、対応する目的関数値をダウングレードする工程とをさらに含む、請求項１２の方法。
【請求項１５】
第１の複数の交通移動計画の少なくとも１つを削除する工程をさらに含む、請求項１の方法。
【請求項１６】
第１及び第２の複数の交通移動計画について目的関数値を決定する工程と、
目的関数値に基づいて、第２の最適化された交通移動計画として、第１及び第２の複数の交通移動計画の中の１つを選択する工程とをさらに含む、請求項６の方法。
【請求項１７】
第１の計画期間を第１の計画境界と、より遅い第２の計画期間を第２の計画境界と関連付ける工程と、
スケジュール変更を入力する工程と、
第１の複数の交通移動計画の少なくとも１つを、第２計画期間及びスケジュール変更に合わせて調節する工程と、
第１の複数の交通移動計画の調節された少なくとも１つを用いて、第２の複数の交通移動計画の少なくとも１つを作成する工程とをさらに含む、請求項６の方法。
【請求項１８】
第１の計画境界をアップデートする前に、調節する工程と、所定の時間、第２の複数の交通移動計画を作成する工程とを続けることをさらに含む、請求項１７の方法。
【請求項１９】
第１の計画境界を伴った第１の最適化された交通移動計画と共に、現在実行している複数の予約を用いており、
第１の計画境界を伴った第１の最適化された交通移動計画と共に、現在実行予定である複数の予約を用いており、
第１の計画境界を伴った第２の最適化された交通移動計画と共に、次の計画サイクルの間に実行予定となると想定される複数の予約を用いている、請求項１の方法。
【請求項２０】
交通移動計画のプールに、第１の複数の交通移動計画と、第２の複数の交通移動計画の中の少なくとも幾つかの計画を含める工程をさらに含む、請求項１の方法。
【請求項２１】
第１の複数の交通移動計画に関する第１の作成と、第２の複数の交通移動計画に関する第２の作成とを含んでいる、プール内にある交通移動計画の複数の作成を用いる工程とさらに含む、請求項２０の方法。
【請求項２２】
プール内にある第１及び第２の複数の交通移動計画の中の約５０個を用いる工程をさらに含む、請求項２０の方法。
【請求項２３】
領域の現在の交通状態を再確認する工程と、
再確認された現在の交通状態に基づいて、第２の計画境界をアップデートして、交通に関する第３の計画境界を与える工程と、
第３の計画境界を用いて、交通移動計画の第３の作成において、第３の複数の交通移動計画を反復的に作成する工程と、
第１、第２及び第３の作成における交通移動計画の各々について、対応する目的関数と、対応する存在時間とを与える工程と、
第１及び第２の作成における交通移動計画の各々について、対応する存在時間の関数として、対応する目的関数値をダウングレードする工程と、
第１及び第２の複数の交通移動計画の各々に関したダウングレードされた対応する目的関数値と、第３の作成における交通移動計画の各々に関した対応する目的関数値とに基づいて、最良の計画を決定する工程と、
第２の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第２の最適化された交通移動計画の対応する目的関数値を、最良の計画の目的関数値と比較する工程とをさらに含む、請求項２１の方法。
【請求項２４】
作成の各々について計画サイクルを用いており、
ダウングレードを行う前に、計画サイクルの所定の数について、目的関数値を維持する工程をさらに含む、請求項２３の方法。
【請求項２５】
第１及び第２の複数の交通移動計画と共に計画ウィンドウを用いており、
計画ウィンドウが終わった後に移動計画を破棄する工程をさらに含む、請求項２４の方法。
【請求項２６】
目的関数値の１つは正の値で、目的関数値の別の１つは負の値であり、
それら正及び負の値の両方をダウングレードする工程をさらに含む、請求項２４の方法。
【請求項２７】
目的関数値の１つは正の値で、目的関数値の別の１つは負の値であり、
それら正及び負の値の何れかをダウングレードする工程とをさらに含む、請求項２４の方法。
【請求項２８】
プール内の交通移動計画の各々について、対応する目的関数値があり、
対応する目的関数値に基づいて、プール内の交通移動計画を順序付けする工程と、
順序に基づいて、実行する第２の最適化された交通移動計画として、プール内の交通移動計画の１つを選択する工程とをさらに含む、請求項２０の方法。
【請求項２９】
交通移動計画の１つについて、それをプールに加える前に対応する目的関数値を決定する工程をさらに含む、請求項２８の方法。
【請求項３０】
交通移動計画の１つをプールに加える際に、それを順序付けする工程をさらに含む、請求項２９の方法。
【請求項３１】
プール内における交通移動計画の各々に、対応する存在時間があり、
対応する存在時間の関数として、プールの交通移動計画の対応する１つの対応する目的関数値をダウングレードする工程と、
ダウングレードに応答して、プールの交通移動計画の対応する１つを再順序付けする工程をさらに含む、請求項３１の方法。
【請求項３２】
プール内の交通移動計画について所定の数を維持するために、第１の複数の交通移動プールの幾つかと、第２の複数の交通移動プールの幾つかとをプールから削除する工程をさらに含む、請求項２０の方法。
【請求項３３】
領域の交通状態には複数の種類があり、
第１の最適化された交通移動計画について、第１の複数の交通状態と現在の交通状態を比較する際に、交通状態の少なくとも１つの種類における変化の確認をする工程をさらに含む、請求項６の方法。
【請求項３４】
交通状態の少なくとも１つの種類における変化には、鉄道網の変化と列車順序の変化の少なくとも１つが含まれる、請求項３３の方法。
【請求項３５】
第１の最適化された交通移動計画について、第１の複数の交通状態と、現在の交通状態を比較して、再計画スコアを決定する工程と、
再計画スコアが所定の値を超える場合、再計画を実行する工程とをさらに含む、請求項６の方法。
【請求項３６】
列車のスケジュール変化を把握して、列車のスケジュール変化を含む再計画スコアを反応良く決定する工程と、
列車のスケジュール変化を含む再計画スコアが所定の値を超える場合、再計画を実行する工程とをさらに含む、請求項３５の方法。
【請求項３７】
変化した列車のスケジュールの数を計画期間内における列車の数で割った値から、変化した列車の相対的な数を決定する工程と、
追加された列車の数を、計画期間内の列車の数と追加された列車の数との和で割った値から、新しい列車の相対的な数を決定する工程と、
変化した列車の相対的な数と、新しい列車の相対的な数とを用いて、再計画スコアを決定する工程とをさらに含む、請求項３６の方法。
【請求項３８】
変化した列車のスケジュールの相対的な全継続期間を決定する工程と、
変化した列車の相対的な数に、変化した列車のスケジュールの相対的な全継続期間を掛ける工程と、
新しい列車のスケジュールの相対的な全継続期間を決定する工程と、
新しい列車の相対的な数に、新しい列車のスケジュールの相対的な全継続期間を掛けて、積を求める工程と、
その積を用いて再計画スコアを決定する工程とをさらに含む、請求項３７の方法。
【請求項３９】
第１の最適化された交通移動計画について、第１の複数の交通状態と、現在の交通状態を比較して、再計画スコアを決定する工程とをさらに含んでおり、
領域の交通状態には複数の種類があり、
再計画スコアが所定の値を超えた場合に、又は、交通状態の種類の少なくとも１つに応答して、再計画が実行される、請求項６の方法。
【請求項４０】
再計画スコアの関数として数を決定する工程と、
第４の複数の交通移動計画をその数だけ作成する工程とさらに含む、請求項３９の方法。
【請求項４１】
上記の数は第１の数であり、
第１の複数の交通移動計画を第２の数だけ決定する工程と、
再計画スコアの関数から割合を決定する工程と、
割合に第２の数を掛けた値として第１の数を決定する工程とをさらに含む、請求項４０の方法。
【請求項４２】
再計画スコアの関数として数を決定する工程と、
第３の複数の交通移動計画をその数だけ再作成する工程とをさらに含む、請求項３９の方法。
【請求項４３】
上記の数は、第１の数であり、
第１の複数の交通移動計画を第２の数だけ決定する工程と、
再計画スコアの上記の関数から割合を決定する工程と、
割合に第２の数を掛けた値として第１の数を決定する工程とをさらに含む、請求項４２の方法。
【請求項４４】
再計画スコアの関数として第１の数と第２の数とを決定する工程と、
第３の複数の交通移動計画を第１の数だけ再作成する工程と、
第４の複数の交通移動計画を第２の数だけ作成する工程とをさらに含む、請求項３９の方法。
【請求項４５】
第１の数は、再計画スコアの第１の関数であり、
第２の数は、再計画スコアの第２の関数であり、
第１及び第２の関数の和は１に等しい、請求項３９の方法。
【請求項４６】
第１の数は、再計画スコアの第１の関数であり、
第２の数は、再計画スコアの第２の関数であり、
スケジュール変化がない場合、第１及び第２の関数の和は０.５未満である、請求項３９の方法。
【請求項４７】
現在の交通状態に基づいて、第１の最適化された交通移動計画について第１の目的関数値を与える工程と、
第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定する工程と、
現在の交通状態に基づいて、最良の計画について第２の目的関数値を与える工程と、
第１の最適化された交通移動計画を最良の計画で置き換えるか否かを決定するために、第１の目的関数値を第２の目的関数値と比較する工程とをさらに含む、請求項１の方法。
【請求項４８】
第２の目的関数値が、第１の目的関数値と比較して所定の量小さいことを判断して、第１の最適化された交通移動計画を、最良の計画で応答良く置き換える工程をさらに含む、請求項４７の方法。
【請求項４９】
第１及び第２の複数の交通移動計画の各々について、対応する目的関数値と、対応する存在時間とを与える工程と、
第１の複数の交通移動計画の各々について、対応する存在時間の関数として、対応する目的関数値をダウングレードする工程と、
第１の複数の交通移動計画の各々に関しており、ダウングレードされた対応する目的関数値と、第２の複数の交通移動計画の各々に関した対応する目的関数値とに基づいて、最良の計画を決定する工程と、
第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の最適化された交通移動計画の対応する目的関数値を、最良の計画の目的関数値と比較する工程とをさらに含む、請求項４７の方法。
【請求項５０】
第１の最適化された交通移動計画について、第１の複数の交通状態と現在の交通状態を比較して、再計画スコアを決定する工程と、
再計画スコアが所定の値を超えたことを判断し、現在の交通状態を反応良く用いて、第２の交通移動計画を作成する工程と
現在の交通状態に基づいて、第１の最適化された交通移動計画について第１の目的関数値を与える工程と、
第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定する工程と、
現在の交通状態に基づいて、最良の計画について第２の目的関数値を与える工程と、
第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する工程とをさらに含む、請求項６の方法。
【請求項５１】
領域の交通状態には、複数の種類があり、
現在の交通状態において、領域の交通状態の少なくとも１つの種類の変化を確信して、現在の交通状態を反応良く用いて、第２の複数の交通移動計画を作成する工程と、
現在の交通状態に基づいて、第１の最適化された交通移動計画について第１の目的関数値を与える工程と、
第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定する工程と、
現在の交通状態に基づいて、最良の計画について第２の目的関数値を与える工程と、
第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する工程とをさらに含む、請求項６の方法。
【請求項５２】
領域内の鉄道網にある複数の列車について、第１の複数の交通移動計画を作成する工程と、
鉄道網における交通状態の変化を受けて、鉄道網に亘る列車の移動を動的に最適化する工程とを含む、請求項１の方法。
【請求項５３】
鉄道網には、複数の線路区間があり、
複数の予約の各々は、線路区間の１区間における計画された使用を、１本の列車の進入日時から離脱日時で示しており、
予約を組み合わせて、第１及び第２の複数の交通移動計画を作成する工程を含む、請求項５２の方法。
【請求項５４】
第１の計画境界は予約の集合であり、
鉄道網の列車の各々について、現在位置及び速度を確認する工程と、
第１の最適化された交通移動計画と、鉄道網の列車の現在位置及び速度とから予約を決定する工程とを含む、請求項５３の方法。
【請求項５５】
予約の幾つかは、現在の複数の予約であり、
１本の列車には、先頭車両と最後の車両とがあり、
先頭車両は、線路区間の１つを用いており、
先頭車両が線路区間の１つに到着する前に負った遅れと、先頭車両がその線路区間で負った遅れの延長とを決定する工程と、
現在の予約の各々について、遅れと遅れの延長とが負わされる、請求項５４の方法。
【請求項５６】
１本の列車は、先頭車両及び最後の車両を含む複数の車両を用いており、
進入日時は、線路区間の１つに先頭車両が入る日時であり、
離脱日時は、線路区間の１つから最後の車両が出る日時である、請求項５４の方法。
【請求項５７】
鉄道網における複数の線路障害、線路速度制限及び列車位置間隔を確認する工程と、
鉄道網における複数の線路障害、線路速度制限及び列車位置間隔に基づいて、再計画スコアを計算する工程と、
再計画スコアが所定の値を超えたことを判断して、鉄道網の現在の交通状態を反応良く用いて、第２の複数の交通移動計画を作成する工程と、
鉄道網の現在の交通状態に基づいて、第１の複数の交通移動計画について第１の目的関数値を与える工程と、
第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定する工程と、
鉄道網の現在の交通状態に基づいて、最良の計画について第２の目的関数値を与える工程と、
第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する工程とをさらに含む、請求項５４の方法。
【請求項５８】
複数の列車に関する複数の列車スケジュールがあり、
複数の列車スケジュールについて、少なくとも１つの列車スケジュールの変更を決定する工程と、
少なくとも１つの列車スケジュールの変更に対応して、鉄道網の現在の交通状態を用いて、第２の複数の交通移動計画を作成する工程と、
鉄道網の現在の交通状態に基づいて、第１の複数の最適化された交通移動計画について第１の目的関数値を与える工程と、
第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定する工程と、
鉄道網の現在の交通状態に基づいて、最良の計画について第２の目的関数値を与える工程と、
第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する工程とをさらに含む、請求項５４の方法。
【請求項５９】
第１の最適化された交通移動計画を複数のコマンドに変換する工程と、
それらコマンドとして、鉄道網について、複数のルートクリアコマンド及び制御コマンドを用いる工程と、
鉄道網の列車に関した交通移動をリアルタイムに制御するために、複数のルートクリアコマンド及び制御コマンドを出力する工程とをさらに含む、請求項５２の方法。
【請求項６０】
コンピュータ支援処理システムを用いて、複数のルートクリアコマンド及び制御コマンドを実行する工程をさらに含む、請求項５９の方法。
【請求項６１】
コンピュータ支援処理システムから、鉄道網の列車に関するデータを受け取る工程と、
データを用いて、鉄道網の列車について第１の複数の交通移動計画を作成する工程とを含む、請求項６０の方法。
【請求項６２】
鉄道網の列車について、第２の複数の交通移動計画を周期的に作成する工程と、
鉄道網の現在の交通状態に基づいて、第１の複数の最適化された交通移動計画について第１の目的関数値を与える工程と、
第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定する工程と、
鉄道網の現在の交通状態に基づいて、最良の計画について第２の目的関数値を与える工程と、
第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する工程とをさらに含む、請求項５２の方法。
【請求項６３】
オンタイム動作、ベストタイム及び全遅延の最小化を含む群から選択された少なくとも１つの目的を採用して、第１及び第２の目的関数値を決定する工程を含む、請求項６２の方法。
【請求項６４】
交通状態には複数の種類があり、
再計画スコアにおいて、複数の種類の各々について重み因子が用いられる、請求項５０の方法。
【請求項６５】
複数の種類における第１の種類は、複数の線路障害に関しており、第２の種類は、複数の線路速度制限に関しており、第３の種類は、複数の列車位置間隔に関しており、
第１、第２及び第３の種類に関する複数の和を用いる、請求項６４の方法。
【請求項６６】
線路の速度制限についてゼロの速度を採用する工程と、
第１の種類に関する和を、第２の種類の和と同じする工程とをさらに含む、請求項６５の方法。
【請求項６７】
第１の最適化された交通移動計画の表示を示す工程をさらに含む、請求項１の方法。
【請求項６８】
鉄道網の列車の複数の計画された移動を表示するために、第１の最適化された交通移動計画に関した時間−距離表示を含む列車グラフを表示する工程をさらに含む、請求項６７の方法。
【請求項６９】
領域には鉄道網があり、
鉄道網に、複数の線路障害と、線路速度制限及び列車位置間隔があり、
鉄道網における複数の線路障害、線路速度制限及び列車位置間隔の関数として再計画スコアを決定する工程をさらに含む、請求項５０の方法。
【請求項７０】
列車のスケジュール変更を確認し、第２の複数の交通移動計画を反応良く作成する、請求項５１の方法。
【請求項７１】
複数の交通とそれら交通の複数の交通状態とを有する領域について動的最適化交通プランニング装置であって、
交通状態を示す情報を入力する入力手段と、
複数のルーチンを実行する実行手段とを具えており、
それらルーチンは、
領域の交通状態に基づいて交通に関する第１の計画境界を決定し、領域の現在の交通状態を確認し、第１の計画境界をアップデートして、現在の交通状態に基づいて交通に関する第２の計画境界を与える計画監視部と、
領域の交通について、第１の計画境界を連続的に使用して、第１の複数の交通移動計画を反復的に作成し、第２の計画境界を連続的に使用して、第２の複数の交通移動計画を反復的に作成し、実行する第１の最適化された交通移動計画として第１の複数の交通移動計画の１つを選択し、実行する第２の最適化された交通移動計画として第１及び第２の複数の交通移動計画の１つを選択し、第１及び第２の最適化された交通移動計画を連続的に出力する計画作成部と、
第１及び第２の最適化された交通移動計画を、領域内の交通移動を制御する複数のコマンドに連続的に変換する計画実行部とを具える装置。
【請求項７２】
計画作成部は、第１の最適化された交通移動計画について、第１の複数の交通状態を採用し、
計画監視部は、第１の最適化された交通移動計画について、第１の複数の交通状態と現在の交通状態を比較し、
計画作成部は、第１の複数の交通移動計画にほぼ基づいて、所定の時間、第２の計画境界を用いて計画することを継続して、領域の交通に関する第２の複数の交通移動計画を反復的に作成する、請求項７１の動的最適化交通プランニング装置。
【請求項７３】
計画作成部は、第１の最適化された交通移動計画について、第１の複数の交通状態を採用し、
計画監視部は、第１の最適化された交通移動計画について、第１の複数の交通状態と現在の交通状態を比較して、計画作成部に信号を反応良く送り、
計画作成部は、その信号に応答して、第２の計画境界を用いて再計画を実行し、領域の交通に関する第２の交通移動計画として、(ａ) 領域の交通に関する第１の複数の交通移動計画の幾つかにほぼ基づいた第３の複数の交通移動計画と、(ｂ) 領域の交通に関する第１の複数の交通移動計画に依存しない第４の複数の交通移動計画とを反復的に作成する、請求項７１の動的最適化交通プランニング装置。
【請求項７４】
計画実行部は、第１及び第２の最適化された交通移動計画を、領域内の交通移動を手動で制御するための対応する短期の移動計画案に連続的に変換する、請求項７１の動的最適化交通プランニング装置。
【請求項７５】
計画実行部は、第１及び第２の最適化された交通移動計画を、領域内の交通移動を自動制御するための複数のコマンドに連続的に変換する、請求項７１の動的最適化交通プランニング装置。
【請求項７６】
領域はコミュータレールシステムを含んでおり、交通状態はコミュータレールの交通状態である、請求項７１の動的最適化交通プランニング装置。
【請求項７７】
領域は鉄道網を含んでおり、交通状態は鉄道網の交通状態である、請求項７１の動的最適化交通プランニング装置。
【請求項７８】
計画監視部は、第１の計画境界と対応する計画期間とを決定し、
計画作成部は、鉄道網について、複数の列車のスケジュールと、列車の特徴と、線路の記述とを入力し、第１の最適化された交通移動計画として、第１の計画境界から対応する計画期間に広がる所定の時間間隔に亘って、複数の列車に関する複数の交会/通過計画を出力する、請求項７７の動的最適化交通プランニング装置。
【請求項７９】
鉄道網は複数の列車を含んでおり、交通状態は、列車の遅れ、鉄道網の変化、及び列車のスケジュール変更とを含んでおり、
計画監視部は、計画作成部による再計画の実行が必要であるか否かを、列車の遅れ、鉄道網の変化、及び列車のスケジュール変更の少なくとも１つから決定する、請求項７７の動的最適化交通プランニング装置。
【請求項８０】
第１の最適化された交通移動計画は、複数の第１の交通境界を含んでおり、
入力手段は、現在の交通状態を用いて、交通状態を示す情報をアップデートし、
計画監視部は、第１の最適化された交通移動計画の複数の第１交通状態と、現在の交通状態を比較し、再計画スコアを決定し、再計画スコアが所定の値を超えたことを判断し、
計画作成部は、再計画スコアの関数として第１の数と第２の数とを決定し、第１の複数の交通移動計画における第１の数の計画を再作成し、第２の複数の交通移動計画における第２の数の計画を再作成する、請求項７１の動的最適化交通プランニング装置。
【請求項８１】
入力手段は、現在の交通状態を用いて、交通状態を示す情報をアップデートし、
計画作成部は、現在の交通状態に基づいて、第１の最適化された交通移動計画関する第１の目的関数値を与え、領域の交通に関する第２の複数の交通移動計画を作成し、第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定し、現在の交通状態に基づいて、最良の計画に関する第２の目的関数値を与え、第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する、請求項７１の動的最適化交通プランニング装置。
【請求項８２】
第１の最適化された交通移動計画は、複数の第１の交通状態を含んでおり、
入力手段は、現在の交通状態を用いて、交通状態を示す情報をアップデートし、
計画監視部は、第１の最適化された交通移動計画の複数の第１交通状態と、現在の交通状態を比較し、再計画スコアを決定し、再計画スコアが所定の値を超えたことを判断し、
計画作成部は、現在の交通状態を反応良く用いて第２の複数の交通移動計画を作成し、現在の交通状態に基づいて、第１の最適化された交通移動計画に関する第１の目的関数値を与え、第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定し、現在の交通状態に基づいて、最良の計画に関する第２の目的関数値を与え、第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する、請求項７１の動的最適化交通プランニング装置。
【請求項８３】
入力手段は、現在の交通状態を用いて、交通状態を示す情報をアップデートし、
計画監視部は、複数の種類の領域の交通状態を採用し、現在の交通状態における複数の種類の領域の交通状態の少なくとも１つの変化を検知し、
計画作成部は、現在の交通状態を反応良く用いて第２の複数の交通移動計画を作成し、現在の交通状態に基づいて、第１の最適化された交通移動計画に関する第１の目的関数値を与え、第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定し、現在の交通状態に基づいて、最良の計画に関する第２の目的関数値を与え、第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する、請求項７１の動的最適化交通プランニング装置。
【請求項８４】
実行手段は、計画監視部、計画作成部及び計画実行部用の１つのプロセッサを含む、請求項７１の動的最適化交通プランニング装置。
【請求項８５】
実行手段は、計画監視部及び計画作成部用の第１のプロセッサと、計画実行部用の第２のプロセッサとを含む、請求項７１の動的最適化交通プランニング装置。
【請求項８６】
実行手段は、計画監視部用の第１のプロセッサと、計画作成部用の第２のプロセッサと、計画実行部用の第３のプロセッサとを含む、請求項７１の動的最適化交通プランニング装置。
【請求項８７】
複数の交通とそれら交通の複数の交通状態とを有する領域の交通管理システムであって、
交通状態を示す情報を入力する入力手段と、
複数のルーチンを実行する実行手段であって、それらルーチンは、
領域の交通状態に基づいて、交通に関する第１の計画境界を決定し、領域の現在の交通状態を確認し、第１の計画境界をアップデートして、現在の交通状態に基づいて、交通に関する第２の計画境界を与える計画監視部と、
領域の交通について、第１の計画境界を連続的に使用して、第１の複数の交通移動計画を反復的に作成し、第２の計画境界を連続的に使用して、第２の複数の交通移動計画を反復的に作成し、実行する第１の最適化された交通移動計画として第１の複数の交通移動計画を選択し、実行する第２の最適化された交通移動計画として第１及び第２の複数の交通移動計画の１つを選択し、第１及び第２の最適化された交通移動計画を連続的に出力する計画作成部と、
第１及び第２の最適化された交通移動計画を、領域内の交通移動を制御する複数のコマンドに連続的に変換する計画実行部とを具える実行手段と、
コマンドを実行して、領域内の交通移動を制御する実行手段とを具えるシステム。
【請求項８８】
コマンドを実行する実行手段は、領域内の列車の移動を制御するコンピュータ支援処理システムである、請求項８７の交通管理システム。
【請求項８９】
コンピュータ支援処理システムは、鉄道のインフラストラクチャと、領域の制御に関する情報のデータベースを含んでいる、請求項８８の交通管理システム。
【請求項９０】
コマンドを実行する実行手段は、交通を制御するコマンドを発する交通制御システムである、請求項８７の交通管理システム。
【請求項９１】
交通制御システムは、運行制御センター、鉄道網管理センター、鉄道網制御センター及び交通制御センターを含む群から選択される、請求項９０の交通管理システム。
【請求項９２】
領域は、複数の列車を有する鉄道網を含んでおり、
交通状態を示す情報は、鉄道網からの動的データを含んでおり、
計画作成部は、鉄道網について、複数の列車スケジュール、列車の特徴、及び線路の記述を入力し、第１及び第２の最適化された交通移動計画として、鉄道網の列車に関する複数の最適化された交会/通過計画を出力し、
コマンドを実行する実行手段は、鉄道網からの動的データを使用し、
交会/通過計画は、鉄道網からの動的データに基づいて、列車スケジュール、列車の特徴及び線路の記述の如何なる制限にも違反しない、請求項８７の交通管理システム。
【請求項９３】
領域は、複数の列車を有する鉄道網を含んでおり、
実行手段は、鉄道網の列車の計画された複数の移動を示すために、第１の最適化された交通移動計画に関した時間−距離表示を含む列車グラフを示す、請求項８７の交通管理システム。
【請求項９４】
計画境界は、第１の最適化された交通移動計画に関する複数の予約と、第１の最適化された交通移動計画に関しており、現在実行予定である複数の予約と、第２の最適化された交通移動計画に関しており、次の計画サイクルの間に実行予定になると予期される複数の予約とを具えている、請求項８７の交通管理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
[関連出願の参照]  本発明は、同一出願人によって２００２年１２月２０日に出願された米国仮特許出願第６０/４３５,１４４号、表題「Dynamic Optimizing Traffic Planner Method and System」に関連している。
【背景技術】
【０００２】
[発明の分野]  本発明は、概して交通プランニング(traffic planning)方法に関しており、より詳細には、最適化された交通移動計画を作成して、動的に変更する方法に関する。また、本発明は、例えば、鉄道又はコミュータレールの動的最適化を行う交通プランニングシステムのような動的最適化交通プランニングシステムに関する。
【０００３】
[背景技術情報]  交通インフラストラクチャは、特定の地理的領域内に存在しており、乗物(例えば、トラック、列車、船舶などがあるが、これらに限定されない)に用いられる複数の物理的経路(例えば、道路、線路、運河などがあるが、これらに限定されない)で構成されている。交通プランニングは、特定の交通インフラストラクチャと有限の期間とについて、付随する複数の乗物が流れる複数のルート(つまり、乗物当たり１つのルート)を決定するプロセスである。それら乗物は、特定の時刻にて各々に対応したルートに沿って配置されるように計画される。同時に、それら複数のルートは、移動計画を構成する。
【０００４】
交通プランニングは、従来より人によって実行されてきたが、交通プランニングプロセスは、自動化された交通プランナ(traffic planner)や単純な交通プランナによっても実行される。これらプランナは、交通インフラストラクチャのデータ、計画される個々の乗物、乗物のスケジュール、物理的な制限や運転上の制限に関するデータ、及び、交通の移動に関するその他のデータを前提として、移動計画を作成する。列車の運行の場合、例えば、このような交通プランナは、鉄道のインフラストラクチャのデータ(例えば、線路、信号や切替器)、計画される個々の列車、列車のスケジュール、物理的な制限や運転上の制限に関するデータ、及び、列車の移動に関するその他のデータを用いる。
【０００５】
交通プランナで作成された移動計画を実行するために、これら移動計画が制御コマンドに変換されて、現場(field)の装置の状態が制御される。現場の装置は、乗物がどのように移動を許されるかを定める。列車の場合だと、制御コマンドは、信号灯の様子や切替器の位置を変化させる。信号灯は、列車が前方に向かってどのように移動すべきか(例えば、速度の維持、速度の減少、停止)を示し、切替器の位置(即ち、ノーマル又はリバース)は、列車が走る線路を定める。暗い(信号化されていない)区域では、前方への列車の移動は、マイル標(つまり、列車には責任者がいて、計画されたルートに沿って、現在位置から特定のマイル標に列車を移動させる)、ランドマーク又は地理的位置によって示される。制御コマンドを現場に送ることは、自動交通制御システム、又は簡単な制御システムによって行われ、それらは、交通プランナとインターフェイス接続される。鉄道に用いられる制御システムは、個々の列車の特徴に基づいて、又は線路のインフラストラクチャに基づいて列車の移動を制御する。コンピュータ支援処理(ＣＡＤ)システム、運行制御システム(ＯＣＳ)、ネットワーク管理センタ(ＮＭＣ)及び中央交通制御(ＣＴＣ)システムとして知られているような様々なシステムは、線路のインフラストラクチャが、一般的な固定ブロック制御を含んでいるか、特別な列車制御システムに支援された移動ブロック制御を含んでいるかに拘わらず、線路のインフラストラクチャに亘って進む列車の移動を制御するプロセスを自動化する。暗い区域では、列車の移動制御は、制御システムを監視する人間のオペレータと機関士との間で、声がやり取りされて行われる。制御システムは、交通プランナと、制御コマンドを受信及び実行する現場の装置との間のインターフェイスとして機能する。制御システムと現場の装置との間のインターフェイスは、現場の装置に直接接続されており、線路横にある電気制御器と通信する制御ラインを通じて行われ、暗い区間では、状態を変更する行為(例えば、通常行われる切替器の押下)を手動で行う人物とやり取りする声を通じて行われる。
【０００６】
交通プランナは、制御システムと情報を送受信する。交通プランナは、制御コマンドを送信して、信号及び切替器の実際の状態と、速度制限の変化と、列車の位置とに関する情報を、交通プランナが読めるメッセージフォームで受信する。移動計画は、複数のルートクリア、切替器位置変更及びその他の制御コマンドに変換されて、それらは、実行されるために制御システムに送られる。そして、制御システムは、現場の装置が読めるフォーマットで、それらコマンドを送信する。交通プランナは、制御システムに制御コマンドを適宜送信して、現場で起こると予測されている実際の変更に、制御コマンドが対応可能とされる。つまり、列車の動きをリアルタイムで制御するためには、コマンドは、列車の現在位置に合った方法で現場に送られる必要がある。例えば、列車の速度を維持するためには、信号は、列車の前でクリアされなくては(つまり、緑に変えられなくては)ならない。しかしながら、信号は、それがクリアされる列車の前で、別の列車が同じ線路を反対方向に移動している場合に、別の列車について計画された移動を妨げるほど前でクリアされてはならない。
【０００７】
ある種の交通プランナは、制御システムから受信した情報(つまり、現場のアップデート)を用いて、現在実行している移動計画が作成された時刻以後に起こった予期せぬ現場の変化に対処するために、現在実行している移動計画を変更する。即ち、唯一の理由ではないが、現在実行している移動計画を変更する主たる理由は、計画にない変化が現場で起こっているか否かである。行われるべきと計画が言う何もかもを実行可能とする(つまり、列車の配置によって、制御コマンドが予期したように働く)ために、計画された現場の状態は、現場の実際の状態に可能な限り一致する必要がある。現在実行されている移動計画に示されているような、さもなければそれに黙示的に示されているような、計画又は予期された動作に従って、列車及び現場の装置が動く場合、現場のアップデートが含められる必要はない。
【０００８】
人間のオペレータは、制御システムを利用して、列車の移動をほぼリアルタイムで図示するコンピュータインターフェイスを用いて、列車の移動を監視する。このようなインターフェイスにおける２つのタイプが一般的である。第１のインターフェイスは線路ダイアグラムであって、ノンスケールの非地図的(non-geographical)方法で線路を表示しており、線路上の列車の位置と、それらの移動権限(線で描かれたルート)と、線路の切替器及びそれらの位置と、信号灯及びそれらの色とに加えて、熱いホイールベアリングを検出するホットボックス検出器のようなその他の種々雑多の装置と、橋のようなランドマークとが示される。線路ダイアクラムの主要機能は、現場で起こっていることをほぼリアルタイムで表示することである。線路ダイアクラムは、列車の現在位置と、それらが移動権限を与えられた領域とを示す。
【０００９】
第２のインターフェイスは、鉄道の運行を監視するために人間のオペレータに使用される「ストリングライン(string-line)」であって、計画された列車の場所及び時刻に関する時間−距離グラフである。通常、このグラフの垂直軸には、(通常、駅名を示す)場所が示されており、水平軸には時刻が示されている。列車の移動は、移動方向に応じて下向き又は上向きに傾斜した対角線として表示される。従って、同じ期間内に相反する方向に同じ鉄道線路を移動する２つの列車のストリングラインは、Ｘ字に似た形になるだろう。時間−距離グラフは、通常、縮尺して描かれていないが、ストリングラインの傾きは、各々の列車の速度を概ね示している。例えば、列車が停止している間、そのストリングラインは水平であろう。列車が速く移動するほど、そのストリングラインの傾きの絶対値は大きくなる。ストリングライングラフの主要な特徴は、どれだけの列車の移動が将来に計画されているかを表現することである。列車の運転手は、２つの列車が会うことを計画された場所や、列車が特定の場所に到達することを計画された時刻を見ることが可能となっている。
【００１０】
交通プランニングは、非最適化又は最適化に区別される。非最適化交通プランニングは、性能基準(例えば、目的地に時間通りに到着すること、平均速度が比較的高いこと)に拘わらずにルートを決定することを含んでいる。
【００１１】
ある種の線路は、線路網に亘って列車の移動を最適化する能力がない非最適化交通プランナを採用するものとして知られている。それは、一定の規則の組に従って働くように制限されている。特に、それは、列車の特徴に関する一定の組に従って列車を計画する。優先順位が最も高い列車の移動が最初に計画され、優先順位が次に高い列車の移動が２番目に計画され、以後、最も優先順位が低い列車まで計画が行われる。衝突(conflict)がある場合(例えば、２つの列車が同時に線路の同じ部分を利用しようとする場合)、非最適化交通プランナは、問題になっている列車の優先順位に従って、衝突を解決する(つまり、最も優先順位の高い列車が、最初に線路を移動する)。非最適化交通プランナの一例には、ペンシルベニア州のピッツバーグにあるユニオンスイッチアンドシグナル株式会社(Union Switch & Signal, Inc)より販売されているオートルーター(AutoRouter(ART))がある。
【００１２】
反対に、最適化交通プランニングは、最適化目的を用いて計画プロセスを誘導しており、その結果得られる移動計画は、１又は２以上の性能基準を最高に満足する。サービスの要求(例えば、貨物の輸送)が増加しており、予見できる将来についても、このように続くと予測されることから、最適化交通プランニングは、貨物鉄道にとって興味深い。新しい線路を築くことは、サービス能力を増加させる一つの方法であるが、比較的非常に高価なので、鉄道は、それらが有している現存する線路インフラストラクチャの能力をより一層利用する方法を求めている。列車の移動を最適化する交通プランニングは、交通の密度を増加させて、それによって、現存する線路インフラストラクチャの能力をさらに利用する一方で、鉄道の利用者には非常に重要である時間通りの運行を高レベルで維持する。
【００１３】
交通プランニングは、最適化又は非最適化に拘わらずに、静的プランニング及び動的プランニングに区別される。静的プランニングは、線路インフラストラクチャのデータと、計画される個々の列車、列車のスケジュールと、物理的制限及び運行上の制限とに関するデータと、列車の移動に関するその他のデータとを用いて、最初の移動計画を作成する。最初の移動計画は、有限の期間に亘って、特定の地理的領域内で運行されるであろう全ての列車の移動を定めている。一度作成されると、最初の移動計画は上記のように実行され得る。静的プランニングは、最初の計画への変更が決してなされないことを暗に意味している。
【００１４】
動的プランニングは、予期されておらず、それ故に現在実行されている移動計画に含められていないような現場で起こった変化の結果として、現在実行している移動計画を新たな移動計画で置き換える。即ち、イベントは、計画されたようには現場で起こらなかった(例えば、列車が計画よりも遅く移動したり、ある線路区間で速度制限がされたり、装置の故障が起こった)。現場が計画に従って変化している(又は計画に非常に近い)場合にのみ、動的プランニングは必要とされない。予期又は計画されない変化が常に現場で起こるので、鉄道の交通プランニングは、効果的であろうとすると動的でなくてはならない。
【００１５】
公知の動的プランニングは、新たな移動計画が作成される方法に応じて、異なる２つのタイプに区別され得る。第１のタイプは、現在実行している計画に依存しない全く新しい計画を作成するものであり、現在実行している計画を新たな計画で置き換える。新しい計画を生成するために、現在実行している計画が変更されることはない。現在実行している計画の如何なるデータも、新たな移動計画の作成に利用されない。
【００１６】
第２のタイプの動的プランニングは、現在実行している計画を変更するものである。変更は、１つの交会(meet)ポイント(つまり、ある列車が、別の列車が通り過ぎるのを待つポイント)を移動させたり、既に計画された交会ポイントが維持されるように、個々の列車の速度を調節するような、非常に限定された変化である。これらの変更は、通常、１又は２本の列車と、インフラストラクチャにおける１又は２カ所とに影響を与えるが、移動計画の残りの部分は変化しない。
【００１７】
最適化交通プランニングの場合において、動的プランニングの第１のタイプは、現在実行している計画に関係なく、最適化された新しい移動計画を生成する。この動的プランニング方法は、利用される最適化方法に応じて、現在実行している計画を変更するのに要する時間よりも非常に長い時間を、最初の計画を作成するのに要することから、時間的にコスト高である。
【００１８】
第２タイプの動的プランニングは局所的な最適化を行うが、これは、全体的に最適化された計画に悪影響を与えるかも知れない。つまり、目的に対して評価される計画全体の最適化の程度は、より低くなるだろう。大抵の場合、局所的な最適化は、計画の全体としての最適度を改善しない。
【００１９】
米国特許第５,７９４,１７２号及び第６,１５４,７３５号は、複数の列車について移動計画を作成する様々な最適化方法を開示している。特許第５,７９４,１７２号に記載された方法は、(さらに高レベルの列車移動スケジュールを作成するための)粗い最適化のためのシミュレーテッドアニーリング(simulated annealing)と、(スケジュールから更に詳細な移動計画を作成するための)細かい最適化のための分岐限定(branch and bound)とである。特許６,１５４,７３５号は、最適化された移動計画を作成するために、制約伝播(constraint propagation)及びフォーカスド(focused)シミュレーテッドアニーリングを行う方法について記載してある。また、特許第５,７９４,１７２号は、予め定められた移動計画(現在実行している計画)に従っていない列車に調整を行うシステムについて記載してある。なお、このような調整は、それらの列車に伝えられる。また、同特許には、衝突(２本の列車が同じ時刻に同じ線路にアクセスしようと試みている)が生じると、分岐限定技術を用いて回避するシステムが記載されている。個々の電車の調整や特定の衝突の回避を組み入れているようなシステムは、第２タイプである動的プランニングの実施形態に該当するだろう。
【００２０】
米国特許第５,１７７,６８４号には、最適化された列車移動計画を作成するための分岐限定及びプロシージャベースの(procedure-based)推論方法と、ルールの緩和又は制約の緩和によって再スケジューリングを行う方法とが記載されている。ルールの緩和はルールベースの推論を、制約の緩和は制約ベースの推論を含んでいる。これら再スケジューリング方法を実施するシステムは、第２タイプである動的プランニングの一例と考えられるだろう。
【００２１】
米国特許第５,１７７,６８４号は、予め定められた列車のスケジュールから移動計画を作成する最適化列車移動プランナを開示している(つまり、スケジュールされた列車の出発及び到着時刻は一定である)。遅延コスト(ある乗物が別の乗物が通過可能なように遅れることで負担するコスト)で制限された縦型探索アルゴリズムは、実行不可能な列車の交会ポイント(つまり、交会ポイントが、単一の線路上で起こる)を、それらの交会が起こることが可能な場所に調整する。この列車移動計画最適化方法は、提案された交会ポイントで、列車の遅れによって如何なる大きなコストが加わることなく、スケジュール案が列車によって満足され得るか否かを判断する。
【００２２】
米国特許第６,３０４,８０１号及び第６,５４６,３７１号は、特に、線路の重要ルート(corridor)に亘って列車に移動を最適化するグラディエントサーチ(gradient search)方法を開示している。グラディエントサーチ方法はコスト関数に導かれており、コスト関数は、各交会ポイントを側線(siding)に移動させて、それで生じるコストを評価することで、出発する列車について、最適化スケジュールを決定することを可能としている。また、個々の列車のスケジュールは、列車の速度及び/又は列車の出発時刻(つまり、列車が重要ルートに入る時刻)を変化することで調整される。
【００２３】
米国特許第６,４５９,９６４号は、列車のスケジュールを粗く決めるシステムと、細かな移動計画を作成する方法とを記載している。また、米国特許第６,４５９,９６４号は、移動計画修正方法を記載しており、その方法は、上述した第２タイプの動的プランニングの一例である。そのシステムは、細かな移動計画に対して列車の進行を監視して、線路で使用されている列車の間の衝突を特定する。そして、それは、列車による重複した線路の利用を解決するために利用可能な交会ポイントのオプションを評価して、全体の移動計画に与える影響が最も少ないものを選択する(局所的な最適化)。選択されたオプションが実施された結果であるような衝突は、どれも検討されない。これは、問題が起こると、問題の修正(つまり、新たな交会ポイント)が時間内にさらに列車の衝突を起こす影響を考慮することなく、それらの問題を修正する。
【００２４】
交通プランニングの方法及び交通プランニングシステムには、改善する余地がある。
【発明の開示】
【００２５】
これら及びその他の要求は、本発明によって満たされる。本発明は、移動を、例えば、動的に変化する環境における鉄道網に亘った列車の移動を、動的に最適化する。例えば、コンピュータソフトウェアは、複数の列車移動計画を作成し、それら計画を変更して、予期した鉄道列車運行への予期しない変化に対処し、最適化された列車移動計画を選択する。ソフトウェアベースのこの方法及びシステムは、動的に変化している鉄道網のような動的な環境における列車の移動を再計画する。
【００２６】
第２のタイプの動的プランニングに似た第３のタイプの動的プランニングが開示されている。この動的プランニングは、現在実行している計画の変更を行うが、各変化が移動計画の残りの部分に影響を与えることを許される点で、第２のタイプと異なる。つまり、移動計画の残りの部分は、各変化に適応するように調整される。
【００２７】
最適化交通プランニングの場合、第３のタイプの動的プランニングは、現在実行している移動計画にされた変化を、それら変化を含めて現在実行している移動計画を全体的に最適化することに立脚している。また、これは、現在実行している移動計画の計画データが、新たな移動計画の作成に用いられる点で、第１のタイプの動的プランニングと異なっている。
【００２８】
本発明の特徴の１つとして、複数の交通と、複数の交通状態とを有する領域について、最適化された交通移動計画を作成する方法は以下の工程を含んでいる。領域の交通状態に基づいて、第１の計画境界(planning boundary)を決定する工程。第１の計画境界を使用して、領域の交通に関する第１の複数の交通移動計画を反復的に作成する工程。実行する第１の最適化された交通移動計画として、第１の複数の交通移動計画から１つを選択する工程。領域内の交通移動を制御するために、第１の最適化された移動計画を出力する工程。第１の計画境界をアップデートして現在の交通状態に基づいて第２の計画境界を与える工程。第２の計画境界を使用して、領域の交通に関する第２の複数の交通移動計画を反復的に作成する工程。実行する第２の最適化された交通移動計画として、第１及び第２の複数の交通移動計画から１つを選択する工程。領域内の交通移動を制御するために、第２の最適化された移動計画を出力する工程。
【００２９】
その方法は、第１の最適化された交通移動計画について、第１の複数の交通状態を使用してよく、第１の最適化された交通移動計画に関する第１の複数の交通状態と、現在の交通状態を比較してよく、第１の複数の交通移動計画にほぼ基づいて、第２の計画境界を反応良く計画し、領域の交通について第２の複数の交通移動計画を反復的に作成してもよい。
【００３０】
その方法は、第１の最適化された交通移動計画について、第１の複数の交通状態を使用してよく、第１の最適化された交通移動計画に関する第１の複数の交通状態と、現在の交通状態を比較してよく、第１の複数の交通移動計画にほぼ基づいて、第２の計画境界を反応良く再計画し、領域の交通に関する第２の複数の交通移動計画として、(a) 領域の交通に関する第１の複数の交通移動計画の幾つかにほぼ基づいた第３の複数の交通移動計画と、(b) 領域の交通に関する第１の複数の交通移動計画と独立な第４の複数の交通移動計画とを反復的に作成してもよい。
【００３１】
本発明の別の特徴として、複数の交通と、複数の交通状態とを有する領域に関する動的最適化交通プランニング装置は、交通状態を示す情報を入力する手段と、複数のルーチンを実行する手段とを具えている。それらルーチンは、領域の交通状態に基づいて、第１の計画境界を決定する計画監視部と、領域の現在の交通状態を確認する工程と、第１の計画境界をアップデートして、現在の交通状態に基づいて第２の計画境界を与える工程と、第１の計画境界を連続的に用いて、領域の交通について、第１の複数の交通移動計画を反復的に作成し、第２の計画境界を連続的に用いて、第２の複数の交通移動計画を反復的に作成する計画作成部と、実行する第１の最適化された交通移動計画として、第１の複数の交通移動計画から１つを選択する工程と、実行する第２の最適化された交通移動計画として、第１及び第２の複数の交通移動計画から１つを選択する工程と、第１及び第２の複数の最適化された交通移動計画を連続的に出力する工程と、第１及び第２の最適化された交通移動計画を、領域内の交通移動を制御する複数のコマンドに連続的に変換する計画実行部とを含む。
【００３２】
本発明の別の特徴として、複数の交通と、複数の交通状態とを有する領域に関する交通管理システムは、交通状態を示す情報を入力する手段と、複数のルーチンを実行する手段とを具えている。それらルーチンは、領域の交通状態に基づいて、第１の計画境界を決定する計画監視部と、領域の現在の交通状態を確認する工程と、第１の計画境界をアップデートして、現在の交通状態に基づいて第２の計画境界を与える工程と、第１の計画境界を連続的に用いて、領域の交通について、第１の複数の交通移動計画を反復的に作成し、第２の計画境界を連続的に用いて、第２の複数の交通移動計画を反復的に作成する計画作成部と、実行する第１の最適化された交通移動計画として、第１の複数の交通移動計画から１つを選択する工程と、実行する第２の最適化された交通移動計画として、第１及び第２の複数の交通移動計画から１つを選択する工程と、第１及び第２の複数の最適化された交通移動計画を連続的に出力する工程と、第１及び第２の最適化された交通移動計画を、領域内の交通移動を制御する複数のコマンドに連続的に変換する計画実行部とを含む。交通管理システムは、コマンドを実行して領域内の交通移動を制御する手段を含んでいる。
【発明を実施するための最良の形態】
【００３３】
地域的な鉄道ネットワークに亘る列車に関して、最適化された移動計画を作成する方法及びソフトウェアシステムについて本発明が開示されているが、本発明は、交通用途について広く適用可能である(例えば、鉄道、コミュータレール、運河がある。なお、これらに制限されない)。
【００３４】
図１を参照すると、動的最適化交通プランナシステム(ＤＯＴＰ)が示されている。ＤＯＴＰ(2)は、ソフトウェアシステムであって、鉄道網(10)(例えば、鉄道線路網)に亘って移動する列車(6)(8)について、計画(4)のような最適化された移動計画を作成する。そして、ＤＯＴＰ(2)は、その後、現在実行している移動計画(13)で仮定されている状態に対して、鉄道(12)の状態がある程度異なる場合に、再計画を行う。鉄道(12)の状態(68)は、継続的に監視されており、計画サイクル毎に計画作成部(56)のためにアップデートされる。ＤＯＴＰ(2)は、リアルタイムで列車(6)(8)の移動を制御することに関与するコンピュータ支援処理(ＣＡＤ)システム(14)のような、適切な交通制御システムにインターフェイスする。システムが動作を開始すると、ＤＯＴＰ(2)は、ソリューションのプール(172)(図５Ａ)を占める最初の移動計画を作成して、計画(4)のような最適化された移動計画を発行する。ＤＯＴＰ(2)が動作すると、システムは、最適化された移動計画を連続的に作成して、さらに、現在の現場の状態を示すような、現場(例えば、鉄道(12))から受信した実データを用いて、動的に再計画を行う。これによって、列車(6)(8)の移動のプランニングが自動化される。また、ＤＯＴＰ(2)は、(例えば、インターフェイス(16)(18)、列車グラフディスプレイ(20)(例えば、適当なサーバ及びユーザインターフェイス(図示せず))及び(列車ダイアグラム)マンマシーンインターフェイス(ＭＭＩ)ディスプレイ(22)の各々を通じて)列車(6)(8)を制御する人間に通知をしてもよい。代わりに、ＤＯＴＰ(2)は、その他の制御システム(図示せず)にインターフェイスしてもよい。
【００３５】
ＤＯＴＰ(2)は、複数のソリューション(移動計画)を作成して、最適化の背景にしている最適化基準(方針)に基づいて、「最良の」ソリューションを推奨する。このような基準は、例えば、オンタイム(on-time)性能、ベストタイム、全遅延の最小化、場所レベルで離散化された事業の目的関数の最小化、若しくはそれらの組合せ、及び/又はその他の最適化基準に関係してもよい。基準は、鉄道(12)のような、特定の鉄道の事業目的に応じて選択される。ＤＯＴＰ(2)は、通常、オンタイム性能と相まって稼働率を増加させる形態で、運転効率を大幅に改善させており、また、混雑を避けるように働くことから、安全でない列車配置を避けることで、安全レベルを増加させるだろう。
【００３６】
動的最適化プランニング(現場の変化への対処を含む)は、変化する環境にて最適化された移動計画(例えば、詳細な交会/通過列車計画)を作成する計画方法である。
【００３７】
本明細書で用いられているように、用語「予約(reservation)」は、進入日時から離脱日時まで、特定の列車による線路区間の計画された使用を明らかに含むものであるが、これに限定されない。進入日時は、列車の最初の車両(例えば、先頭の機関車、列車の前端)が特定の線路区間に入る日時である。離脱日時は、特定の線路区間から、列車の最後の車両(例えば、列車の後端)が出る日時である。予約は、プランニングの基本的なアーティファクト(artifact)である。計画される全ての列車に関する全ての予約を時間ベースで組み合わせたものが、移動計画を構成する。
【００３８】
[具体例１]  移動計画の作成では、様々な制限(例えば、線路の速度制限、恒常的な速度制限、一時的な速度制限)及び制約(例えば、旅客や貨物のような列車の種類、ディーゼル、ＡＣ、ＤＣのような動力タイプ、列車の高さ、長さや幅、危険物のようなその他の存在する特徴)が順守される。また、移動計画の作成では、移動計画の作成をさらに制限するであろう、鉄道の装置と、線路横(wayside)の装置(例えば、切替器やインターチェンジ)とに固有の特徴が順守される。例えば、線路区間の使用は、それに繋がっている又は繋がっていない別の線路区間の使用を制限する。もう一つの例では、線路区間は、通常位置にある切替器を含んでおり、その区間における使用に応じた期間について、同じ切替器が逆位置にあるような別の線路区間の使用を妨げる。インターチェンジにおける切替器の組合せは、個々の切替器に対して線路横から負わされた条件があるので、幾つかの線路区間の使用を制限する。例えば、幾つかの線路区間を使用する比較的広い列車は、平衡な線路区間の使用を妨げるかも知れない。これらは、如何なる交通計画作成装置も実行可能な計画を作るために従うべき状態である。また、全ての運行ルール及び制約が考慮されるべきである(例えば、幾つかの列車は、幾つかの線路を移動できないこと、運転及び列車間隔の制限、代わりのプラットフォームが使用可能)。これら全ては、以下で説明するような、移動計画を構成する予約の組と計画境界とに反映されるべきである。
【００３９】
(ｔｒａｃｋiに亘るｔｒａｉｎjの)予約、列車の運行(ｔｒａｉｎj)の予約の組み及び移動計画(Ｐｌａｎ)は、夫々、(式１)、(式２)及び(式３)で示される。
【式１】
【００４０】
2006511394.tif 000003
【００４１】
上述のように、列車の運行(ｔｒａｉｎj)の予約の組は、現在位置(ＴｒａｉｎＰｏｓＴｒａｃｋ)から始まってスケジュールの最後の目的地(ＦｉｎａｌＤｅｓｔＴｒａｃｋ)に至る線路区間(ｔｒａｃｋi)の全ての予約を含んでいる。列車運行における連続する２つの予約に関する予約間隔は、(式４)のように重なっている。
【式２】
【００４２】
2006511394.tif 000004
【００４３】
(同じ線路区間における)異なった２つの列車運行の予約間隔は、(例えば、鉄道の運行ルールと制約とによって)それら列車が同じ線路区間を同時に占めることが許されていない限り重ならない。
【００４４】
本明細書で使用されているように、用語「計画サイクル」は、ＤＯＴＰ(2)のような動的最適化交通プランナが、(例えば、それが集めている)最新の現場情報を得て、新しい計画の作成にその情報を適用する時刻後の時間量を示しており、又は、同じ交通及び交通状態下で、プランナが計画を作成するのに要する時間量を示している。例えば、(普通の)正常な計画サイクルの継続期間は、再計画サイクルの継続期間よりも短いであろう。再計画サイクルは、現在の計画サイクルを中断するかも知れない。計画サイクルの最後では、既に発行された計画よりも所定量だけ良いという条件下で、最適化された移動計画が発行されてよい。要求に応じて、移動計画は、サイクルの最後の前に発行されてもよい。
【００４５】
本明細書で用いられているように、用語「計画境界」(又は、「大規模な(deep)計画境界」)は、実行している先の予約と、実行予定である予約と、次の計画サイクルの間に実行予定になると予期される予約との集まりを明らかに含むだろうが、それらに限定されることはない。
【００４６】
本明細書で用いられているように、用語「反復的に作成する」又は「反復的に作成」は、対応する計画境界について、対応する計画サイクル、周期又はウィンドウ内で、複数の交通移動計画を逐次的に及び/又は平行して生成することを明らかに含むだろうが、それらに限定されることはない。
【００４７】
[具体例２]  例えば、図９に示すように、列車(24)(１本のみ示されている)のような様々な列車は、実行中の予約(30)(32)の線路区間(26)(28)を既に占めている。実行予定の予約(34)(36)(38)は、ＤＯＴＰ(2)によって既に割り当てられた予約を含む。これらのような実行予定の予約は、ＤＯＴＰ(2)で修正されない。しかしながら、その運行を実行することが安全であるならば、手動介入でそれらを修正してもよい。列車は、これら予約に従って、近い将来において移動すると想定されており、そのようにする「権限」も与えられている。通常、このことは、例えば、信号灯が、それらによって制御される線路区間(40)(42)(44)について、列車の移動を許す様相を示すことを意味する。列車が連続的に移動すると想定される場合、各列車に関する複数の予約は、この大規模な計画境界(45)に含まれるかも知れない。列車の停止所(例えば、駅の停止所、又は交通状態による停止所)は、実行予定の予約(さらに、実行予定になると予期される予約)の数を(例えば、ゼロに)減らすかも知れない。図９に示すように、その他の予約(46)(48)は、次の計画サイクルの間に実行予定になると予期される。さらなるその他の予約(50)(52)(54)は、次の計画サイクルの間に計画されるだろう。予約(50)(52)(54)と、列車運行の最後に至る、又は計画期間に至るその他全ての予約は、計画境界外であって、次の計画サイクルの間に計画又は変更され得る。
【００４８】
本明細書で用いられているように、用語「計画期間」は、計画境界を超えた時点を示しており、図１のＤＯＴＰ(2)のような動的最適化交通プランナは、その時点に向かって列車の移動を計画する。計画期間(例えば、図９の(55))は、計画境界を超えた適当な任意の時点であってよい。限定を目的としない例として、計画期間は、通常、現在の時刻から約１時間から約２４時間の間にされるが、時間範囲をよる広くすることも可能である。
【００４９】
本明細書で用いられているように、用語「交通」は、主として貨物列車及び旅客列車から構成される鉄道交通と、貨物列車を含んでようが、主として旅客列車から構成されるコミュータレール交通とを明らかに含むだろうが、それらに限定されることはない。
【００５０】
本明細書で用いられているように、用語「交通状態」は、例えば、線路障害、切替器障害、速度制限、列車位置の間隔(つまり、鉄道網における計画された列車位置と実際の列車位置との差)のような交通インフラストラクチャにおける状態変化を明らかに含むだろうが、それらに限定されることはない。
【００５１】
本明細書で用いられているように、用語「現在の交通状態」は、例えば、現在時刻と適当な計画期間の間のような、適当な計画ウィンドウについて決定されるのが好ましく、領域における交通状態について、現在知られている及び/又は予測される状態を明らかに含むだろうが、それらに限定されることはない。
【００５２】
本明細書で用いられているように、用語「再計画スコア」(例えば、数値)は、交通状態の変化と、スケジュール変化(スケジュール変化は、現在時刻近くではない)との数値表現を明らかに含むだろうが、それらに限定されることはない。例えば、種類が異なるイベントの貢献(変化)は、各イベントの詳細を考慮して評価されてよい。各種類のイベントの相対的な重要性は、対応付けられた重み係数を用いて定量化されてよい。
【００５３】
本明細書で用いられているように、用語「特別イベント」は、計画される領域に到着する列車の順序の変更、所定の移動計画に列車が従わないこと、現在時刻に対してかなり近くにおける列車スケジュールの変化、列車の中身の変化(例えば、車両に危険物を加える、列車を非常に長くする)のような、再計画スコアに含まれない運転上重要な交通状態を明らかに含むだろうが、それらに限定されることはない。
【００５４】
本明細書で用いられているように、用語「再計画サイクル」は、再計画スコアが所定の(例えば、設定された)再計画閾値に達した場合、又は、幾つかの特別イベントが起こる場合に引き起こされる計画サイクルを明らかに含むだろうが、それらに限定されることはない。再計画閾値は、環境の変化に対して望ましい対応に基づいて設定されてもよい。従って、計画を作成するプロセスで用いられた仮定が陳腐化するほど交通状態が大きく変化する場合、計画サイクルは、中断されて、新しい計画境界が与えられるだろう。
【００５５】
本明細書で用いられているように、用語「目的関数値」は、移動計画について目的関数の値で評価されるような、移動計画の「優良度」(例えば、移動計画が如何に最適化されているかを示す相対的な指標)を明らかに含むだろうが、それに限定されることはない。移動計画の目的関数値は、現場の最新状態を計画の優良度に反映する。さらに複雑な環境では、複数の目的が考慮されてよい。各目的がゴールと称される場合、目的関数が組み合わされて、１つの値が全ての目的を表してもよい。複数の目的が、全体的な１つの目的に明確に組み合わされない場合、目的関数値は、目的関数値のベクトルで置き換えられてもよい。この場合、ソリューション(つまり、移動計画)の適応度は、このベクトルに対して示される条件を用いて決定される。
【００５６】
[具体例３]  以下の(式５)は、目的関数の例である。目的は、評価ポイントを用いて不連続にモデル化された全体的な事業目的関数に従って、加重された遅れを最小にすることである。
【式３】
【００５７】
2006511394.tif 000005
【００５８】
[具体例４]  以下の(式６)は、複数の個々のゴールを含む全体的な目的関数の例を示す。
【式４】
【００５９】
2006511394.tif 000006
【００６０】
[具体例５]  （式７)は、線形関数を用いてゴールを組み合わせた全体的な目的関数の比較的簡単な例であって、個々の重みが個々のゴールに割り当てられている。
【式５】
【００６１】
2006511394.tif 000007
【００６２】
個々のゴールｆiが個々の列車グループに対応してもよい。例えば、ある列車グループ(つまり、列車の集まり)が、時間通りの(on time)到着を必要とする一方で、別の列車グループは、最終目的地に最も良い時刻(best time)に到着することを必要としてもよい。しかしながら、異なるゴールがある特定の列車グループに対応することも可能である。
【００６３】
本明細書で用いられているように、用語「実行する」及び「実行」は、自動的に実行すること、自動実行、手動で実行すること及び手動実行を明らかに含むだろうが、それらに限定されることはない。自動又は手動実行は、適当な交通制御システムのサポートによって達成される。
【００６４】
本明細書で用いられているように、用語「コマンド」は、列車の移動を制御するのに使用されるルートクリアやその他の制御コマンドを明らかに含むだろうが、それらに限定されることはない。現在実行している移動計画は、これらのようなコマンドに変換されて、現場に送られる。
【００６５】
[ＤＯＴＰ]  図１の参照を続けると、ＤＯＴＰ(2)は、計画作成部(56)と、計画監視部(58)と、計画実行部(60)とを含んでいる。計画作成部(56)は、鉄道(12)に関する入力(62)(例えば、線路の配置や速度制限)を受け取り、列車のスケジュールに関する入力(64)を受け取り、それが計画する領域について、計画(4)のような最適化された移動計画を作成する。また、図３に示すように、変動(perturbation)に関するメッセージ(66)は、ＣＡＤシステム(14)から計画監視部(58)を通って計画作成部(56)で受信される。
【００６６】
図１の計画監視部(58)は、動的プランニングに用いられており、計画作成部(56)によって再計画することが必要であるか否かを判断するために、現在実行している移動計画(70)(つまり、計画実行部(60)の計画(13))と、鉄道(12)の現在の状態(68)を比較する。例えば、列車の遅れ、列車の障害及び速度制限を含む現場(12)の変化、又はスケジュールの変更によって、再計画(72)が引き起こされてもよい。計画監視部(58)は、(例えば、図６及び図７と、(式１８)と共に以下で説明されるように)「間隔解析」を行って、計画境界(74)(図３)を定義し、再計画スコア(214)(図６)を計算する。
【００６７】
計画実行部(60)が、ルートクリアやその他の制御コマンドのリクエスト(76)に、現在の移動計画(13)を変換することで、それらコマンドは、ＣＡＤシステム(14)にて実行可能となる。手動実行が望ましい場合、計画実行部(60)は、近い将来に関する予約(78)の組の案をＭＭＩ(22)に与える。移動計画案(110)(図３)は、現在の(又は発行された)移動計画(4)の一部である。それは、(6)のような列車に関して実行予定にされた予約の先にある僅かな線路区間のみを含んでいる。移動計画案(110)の予約(78)に基づいて、人間のオペレータは、ルートクリアを手動でリクエストしてもよい(例えば、ＭＭＩ(22)を介してＣＡＤシステム(14)に送られるリクエスト)。
【００６８】
計画作成部(56)、計画監視部(58)及び計画実行部(60)は、データベースインターフェイス(80)を使用する。データベースインターフェイス(80)は、鉄道網(10)のインフラストラクチャの配置及び制御装置が示されている鉄道インフラストラクチャデータベース(82)へのアクセスをもたらし、また、ＣＡＤシステム(14)への直接的なアクセスをもたらしてもよい。このようなネットワークを作り上げる制御装置の状態が、同じデータベース(82)に維持されてもよい。加えて、ＣＡＤシステム(14)によって、装置の状態の変化を広める表示がされてもよい。
【００６９】
データベース(80)は、様々なデータベース実施形態を扱えるのが好ましく、これによって、異なるＣＡＤシステム(図示せず)及び/又はその他の適当な制御システム(図示せず)に、ＤＯＴＰ(2)がインターフェイス可能となる。このために、ＤＯＴＰ(2)は、線路区間、信号、切替器を含んでいるが、これらに限定されることがない主要なインフラストラクチャと、制御装置との表現を内部に保持するのが好ましい。データベース(82)でアクセスされる情報にインターフェイスして内部表現に送るために、必要ならば、分離可能な要素(図示せず)がデータベースインターフェイス(80)に加えられてもよい。例えば、本発明の譲受人である、ペンシルベニア州ピッツバーグのユニオンスイッチ＆シグナル株式会社のＣＡＤシステムでサポートされるインフラストラクチャ及び制御データベースに、データベースインターフェイス(80)がアクセスしてもよい。
【００７０】
ＤＯＴＰ(2)は、１又は２以上のヒューマンマシンインターフェース(16)(18)に、移動計画を出力するのが好ましい。例えば、列車グラフインターフェイス(16)は、スケジュールされる列車の計画された移動について、(図８に示す)(21)のような時間−距離(又は「ストリングライン」)列車グラフ表示をディスプレイ(20)に提供する。発行された完全な移動計画(84)は、時間−距離表示に必要である詳細な場所及び時間情報の全てを含んでおり、ディスプレイ(20)に送られる。ディスプレイ(20)は、それが発行される毎に、列車グラフ表示をサポートする。また、自動実行が機能していない場合、計画実行部(60)は、予約案(78)の短期の組を(例えば、列車(6)(8)のような一部又は全ての列車について)ＣＡＤグラフィカルインターフェイス(18)に送る。ＭＭＩ(22)の人間のオペレータが、この情報を用いて、必要なコマンドをＣＡＤシステム(14)に手動で送って、コマンドが実行されてもよい。
【００７１】
図２は、(6)(8)(図１)のような複数の交通と、(106)(図３)のような交通状態とを有する鉄道つまり現場(12)(図１)のような領域について、最適化された交通移動計画(4)(4')を生成する方法を示す。その方法では、(85)にて、領域の交通状態に基づいて、交通について第１の計画境界(74)が決定される。次に、(85-1)にて、第１の計画境界(74)が用いられて、その領域の交通について、第１の複数の交通移動計画(87)が反復的に作成される。そして、(85-2)にて、交通移動計画(87)の１つが、実行する第１の最適化された交通移動計画(4)として選択される。次に、(85-3)にて、第１の最適化された交通移動計画(4)は、領域における交通移動を制御するために出力される。そして、(85-4)にて、計画ウィンドウについて、領域における現在の交通状態が確認される。次に、(85-5)にて、現在の交通状態に基づいて第１の計画境界(74)がアップデートされて、交通について、新しい第２の計画境界(74')がもたらされる。そして、(85-6)にて、その新しい第２の計画境界(74')が用いられて、その領域の交通について、第２の複数の交通移動計画(87')が反復的に作成される。次に、(85-7)にて、交通移動計画(87)(87')の中の１つが、実行する第２の最適化された交通移動計画(4')として選択される。そして、(85-8)にて、第２の最適化された交通移動計画(4')が、領域における交通移動を制御するために出力される。
【００７２】
ステップ(85-4)からステップ(85-8)は、その後繰り返されるだろう。例えば、通常の計画サイクル(132)(図４)では、複数の交通状態が、最適化された交通移動計画(4)(4')と共に用いられて、(ステップ(85-4)からの)現在の交通状態が、最適化された交通移動計画(例えば、(4'))で仮定された対応する交通状態と比較される。プランニングは、新しくアップデートされた計画境界(例えば、(74'))を用いて、(87)のような以前の交通移動計画にほぼ基づいて継続されて、(87')のようなその後の交通移動計画が反復的に作成される。
【００７３】
また、再計画サイクル(152)(図４)では、(ステップ(85-4)からの)現在の交通状態が、最適化された交通移動計画(例えば、(4'))で仮定された対応する交通状態と大きく異なる場合、新しくアップデートされた計画境界(例えば、(74'))を用いて、再計画が繰り返し行われて、(ａ) (87)のような以前の交通移動計画の幾つかにほぼ基づいた複数(Ｎ１)の交通移動計画(157)(図５Ａ)と、(ｂ) 以前の交通移動計画と独立した複数(Ｎ２)の交通移動計画(174)(図５Ａ)とが作成される。
【００７４】
図３を参照すると、図１のＤＯＴＰ(2)の様々なデータ交換が示されており、現場(例えば、鉄道(12))を制御するＣＡＤシステム(14)を用いた交換も含んでいる。戦術的な計画を適切に行うために、計画監視部(58)及び計画実行部(60)は、ＣＡＤシステム(14)を通じて現場(12)を連続的に監視して、それらの付随する機能をリアルタイムで実行する。計画実行部(60)もまた、現在の移動計画(4)を受け取って、ＣＡＤシステム(14)からの入力のような情報(88)(例えば、現在の交通、交通状態及び現場の装置の状態)に従って、現在の移動計画(4)を実施する(例えば、それを適当なコマンド(86)に変換する)。このリアルタイムな特徴によって、列車移動が適切に制御される。
【００７５】
計画監視部(58)は、(90)にて交通状態を、(92)にて移動計画(4)に対する列車位置を、(94)にて列車のスケジュールの変化を取得して、必要に応じて、計画作成部(56)による再計画の実行を(図１の(72)に示すように)リクエストする。再計画の実行が必要となると、現在の計画サイクルは取って代わられる。計画監視部(58)は、普通の(正常な)計画サイクルに加えて再計画サイクルについて計画境界(74)を用意し、再計画サイクルについて再計画情報を用意する。(正常な)計画サイクル(又は再計画サイクル)について用いられる基本データは、計画境界(74)にパッケージ化されている。ＣＡＤシステム(14)からのさらなる情報(98)は、ＣＡＤインターフェイスコンポーネント(100)にバッファされて、計画サイクルの最初に、メッセージ(66)として計画作成部(56)に転送される。情報(98)は、障害の場所及び継続時間、速度制限のような詳細な交通状態情報やスケジュール変更を含むが、これらに限定されない。計画サイクルの最後には、計画実行部(60)によって実行されるために、選択された移動計画(4)が発行される。計画実行部(60)は、選択された移動計画(4)の自動及び/又は手動実行に適切なゲートウェイを提供する。また、(102)では、同じ移動計画が、ヒューマンインターフェイス(16)を通じた視角化のために発行される。計画監視部(58)はまた、発行された計画(図示せず)を受け取って、必要ならば、幾つかの列車について計画の実行を制御してよい(図示せず)。
【００７６】
計画作成部(56)は、現在のスケジュールに基づいた計画境界(74)のフォームで計画を行うために用いられるデータと、現場(12)の状態とを、計画サイクルの最初に受け取る。計画サイクルの残りでは、複数の移動計画(104)が、この情報に基づいて生成される。ここで、計画のソリューションを生成するための計算が厳しいので、真の「リアルタイム」応答は実現されない。計画境界(74)及びＣＡＤインターフェイス(バッファ)(100)は、計画監視部(58)に示されているが、一方又は両方が計画作成部(56)の一部であってもよい。
【００７７】
[具体例６]  計画サイクルは、移動計画(104)のような多数の計画ソリューションの計算をサポートすべきである。例えば、最大１００本までの列車と、様々な計画期間(例えば、約１から２４時間。計画期間は、図１の鉄道(12)のような対応する領域のインフラストラクチャの複雑さに基づいて定義される)とについて、ある１つのソリューションの決定は、例えば、２秒未満でなされるだろう。故に、通常の計画サイクルは、約３０秒から約１分を要するであろう。従って、ＤＯＴＰ(2)は、計画又は再計画の実行時に、比較的非常に短い期間で(例えば、１又は２分で)列車の移動を最適化して、動的な計画を行うのが好ましい。これらの時間は、計画期間、領域サイズを低減することで、及び/又は比較的強力なハードウェアを用いることで、及び/又は並列処理をすることで短くされるだろう。
【００７８】
まとめると、移動計画(104)の生成又はアップデートをする際に、ＤＯＴＰ(2)は、現場(12)の変化を考慮する。さらに、ＤＯＴＰ(2)は、ＣＡＤシステム(14)又はその他の適当な制御システム(図示せず)と通信して、交通状態(106)(98)、列車位置(108)、インフラストラクチャ装置の状態(98)等のアップデートされた現場情報を受信して、制御コマンド(86)を送信し、及び/又は、現在実行している移動計画(13)(図１)から作成された短期の移動計画案(110)を送信する。例えば、この情報交換は、ＣＡＤシステム(14)又はＭＭＩ(22)/列車グラフディスプレイ(20)と、計画監視部(58)と、計画実行部(60)との間で、適当なメッセージングシステム(112)を利用されて行われてよい。これと同じメッセージングシステム(112)、類似のシステム、又はその他の任意の適当な通信機構(例えば、シェアドメモリ)が、計画監視部(58)と計画ジェネレータ(56)の間で使用されてよい。
【００７９】
図４は、図３のＤＯＴＰ(2)及びＣＡＤシステム(14)で用いられる動作シーケンスを示している。図３の(114)で行われる計画作成部(56)によるソリューション作成(つまり、図３の交通移動計画(104))は、通常継続されており、(116)の交通及び交通状態のアップデートと、(118)での計画境界(74)のアップデートとで中断される。条件が満たされると、図３の(4)のような新しい移動計画が、(120)にて計画作成部(56)によって発行される。この選択された移動計画(4)は、(例えば、事業目的から導かれる)１又は２以上の目的関数に基づいて、以前に実行されている移動計画(図示せず)よりも良いソリューションを与える。
【００８０】
さらに図４を参照すると、(122)にてＤＯＴＰ(2)が実行を開始した後、計画作成部(56)及び計画監視部(58)は、(124)にて初期化を行う。例えば、ＤＯＴＰ(2)は、計画作成部(56)及び計画監視部(58)に関する第１プロセッサ(Ｐ１)(126)と、計画実行部(60)に関する第２プロセッサ(Ｐ２)(128)とを含んでいる。代わりに、１又は２以上のプロセッサ(図示せず)が、計画作成部(56)のルーチンを実行してもよく、計画監視部(58)の１つのプロセッサ(図示せず)、計画実行部(60)の１つのプロセッサ(図示せず)、又は３つのプロセッサ(図示せず)が、計画作成部(56)、計画監視部(58)及び計画実行部(60)のルーチンを実行してもよい。初期化の後、計画監視部(58)は、(130)にて計画境界(74)を定める。
【００８１】
図４は、データ及び処理動作を示しているが、説明の簡単化のために、同時に処理がされる模様を示していない。計画監視部(58)は、(116)、(118)、(130)、(150)及び(124)で動作を行う。計画作成部(56)は、(132)、(152)、(134)、(136)、(120)及び(124)で動作を行う。計画実行部(60)は、(140)及び(146)で動作を行う。(新しいサイクルの開始時と前のサイクルの終わりに)計画監視部(58)が、新しい境界及び交通状態を計画作成部(56)に送って、計画作成部(56)から新しい計画を受信する際に同期する場合を除いて、計画監視部(58)と計画作成部(56)とは、非同期で動作する。計画実行部(60)は、他の２つのコンポーネントに対して完全に非同期であり、新たに発行された計画の到着のようなイベントに応答する。
【００８２】
次に、(132)にて、計画作成部(56)は、通常の計画サイクルを開始する。後に、図５Ａ〜図５Ｂでさらに詳しく説明するように、計画作成部(56)は、複数の移動計画(104)(図３)を作成して、さらに評価される「最良の」計画(133)を選択する。次に、(134)では、計画作成部(56)は、計画境界(74)の最近のアップデートを用いて、先に発行された移動計画(4)(図３)を評価する。これは、発行された移動計画(4)は、通常の計画サイクルよりも非常に大きい期間で実行されてきているであろうということを理由とする。次に、(136)にて、計画作成部(56)は、新たな最適化された移動計画があるか否かを判断する。例えば、最良の計画(133)及び発行された移動計画(4)(図３)は、現在の条件下で適当な目的関数を用いて、例えば、(式５)〜(式７)を用いて先に説明されたように、又は図５Ａ〜図５Ｂと共に以下で説明されるように評価されてよい。そして、発行された計画の目的関数値に、発行された移動計画(4)の適当な閾値(例えば、３％。適当な値は、発行された計画の変化の数を減らして、人間のオペレータのためにさらに安定な環境を与える)を加えた値(目的関数が小さくされる場合は引いた値)よりも、最良の計画(133)の目的関数値が良い場合(例えば、目的関数が小さくされる場合は、値がより小さい)、(120)にて、上記の条件が受け入れられるならば、実行される新しい計画(4')が発行される。また、この計画(84)は、列車のグラフの形態であって、列車グラフインターフェイス(16)に出力される。最初の実行において、以前に発行された移動計画は存在せず、最良の計画(133)は、(12)にて発行される。初期化の間、初期ソリューションプール(104)(図３)は、初期の計画境界情報を用いて作成される。初期化プロセスが通常の計画サイクルの周期よりも長い場合、初期ソリューションプール(104)を作成する間、計画境界(74)はアップデートされてよい。
【００８３】
通常の計画サイクル(132)又は再計画サイクル(133)の何れかの最後にて、現在実行している移動計画(13)(図３)よりも所定の(例えば、設定された)比較量だけ良いならば、(120)にて「最良の」な計画(133)が発行される。新たに発行された計画(4')は、実行されるために、計画実行部(60)(図３)で用いられるデータを含む適当なフォーマット(138)で送られる。同じ計画(図１の(70))は、計画監視部(58)で受け取られて、新たな計画境界(74')を決定及び維持するために使用される。そして、新たな境界状態を用いて、(132)にて、計画サイクルが再開される一方で、発行された計画は、もし存在すれば(以下で説明するように)計画実行部(60)で考慮される。
【００８４】
新たに発行された計画(4')に応答して、計画実行部(60)(図３)は、領域の実行モードを判断する。例えば、計画実行部(60)は、領域、列車、インフラストラクチャの構成要素の状態を確認する。全領域が手動実行モードであってよく、幾つかの運行が手動実行モードであってよく、及び/又は、幾つかの信号が手動実行モードであってよい。さらに、計画実行部(60)は、(列車の計画又は線路区間レベルで)一部自動実行モードを行える。幾つかの列車は、手動実行モードとされてもよい。列車は自動実行モードにある場合でさえ、幾つかのコマンドは、提案された短期移動計画(110)(図３)に基づいて手動で発せされてもよい。手動実行モードでは、(例えば、選択的に短期である)対応する移動計画案(110)(図３)が、(142)にて、ＣＡＤグラフィカルインターフェイス(18)に出力されて、人間のオペレータによって、(144)にて手動で実行される。他方、(140)における判断が自動計画実行である場合、対応するコマンド(86)が、(146)にてＣＡＤシステム(14)に出力される。また、実行予定の予約(148)が、ＣＡＤグラフィカルインターフェイス(18)に出力される。
【００８５】
同時に、計画監視部(58)は、(116)にて、ＣＡＤシステム(14)からの交通及び交通状態をアップデートし、(118)にて、計画境界(74)をアップデートする。次に、(150)にて、計画監視部(58)は、再計画の実行が必要とされるか否かを判断する。例えば、図１と共に先述したように、計画監視部(58)は、現在実行している移動計画(70)に対して鉄道(12)の現在の状態(68)を常時比較して、計画作成部(56)による再計画の実行が必要であるか否かを判断する。(72)(図１)にて、再計画の実行が引き起こされると、計画作成部(56)の通常計画サイクル(132)が中断されて、(152)にて、(図５Ａ〜図５Ｂと共に後に説明されるように)再計画サイクルで置き換えられる。他方で、再計画が引き起こされない場合、計画作成部(56)の(図５Ａ〜図５Ｂと共に後に説明されるように)通常の計画サイクルが、(132)にて続けられる。
【００８６】
[計画作成部]  図３、図４及び図５Ａ〜図５Ｂを参照すると、ＤＯＴＰ(2)は、現場(12)又はオフィス(図示せず)からアップデートを受信して処理する。アップデートは、例えば、列車位置(108)と、列車ブロックや速度制限のような列車状態(106)と、列車のスケジュール(64)(図１)と、計画期間の進行や計画期間内の変化によって加えられる列車特性とを含んでいる。
【００８７】
計画作成部(56)は、現在のシステム時間で始まって計画期間で終わる設定自在な時間ウィンドウの間、複数の移動計画(104)(図３)を作成する。これら計画(104)の作成は周期的であって、各サイクルは、現存する計画を改良しようとし、現場(12)の新しい状態を処理する。アップデートに続いて、ＤＯＴＰ(2)は、(1) 図４の(132)にて通常の計画サイクルを継続するか、(2) 現場(12)の状態と、列車のスケジュール(64)との変化に応じて、(152)にて再計画サイクルを開始する。
【００８８】
計画作成部(56)は、特定の時間間隔に亘って、複数の列車の詳細な移動計画(104)(図３)を構築する。これら移動計画(104)は、計画される総線路のデータに基づいた実行可能な計画(つまり、実行可能な計画は、如何なる制約にも違反せず、線路の任意の区間の列車間に、解決されない如何なる衝突もない。行き詰まりは存在しない)である。
【００８９】
通常の計画サイクルの最初では、計画境界(74)(図３)が計画作成部(56)に転送される。計画監視部(58)でバッファリングされて、通常の計画サイクルの最初で転送されるメッセージからのさらなるデータ(例えば、一時的な速度制限及び装置の障害についての詳細なデータのような交通状態(106))もまた、移動計画作成プロセスにて使用されてよい。計画境界(74)は、計画監視部(58)で積極的に維持される。故に、発行された移動計画(4)(図３)は、発行時刻(publication time)にて現在の状態を満足する。計画作成プロセス(114)(図３)で使用された仮定が廃止されるように境界状態が変化する場合、図１の(72)にて通常の計画サイクルが中止されて、図４の(118)にて、新しい計画境界(74')が与えられる。
【００９０】
図３に示すように、計画作成部(56)は、移動モデル(154)を用いて、列車が線路の特定の区間を通るのに要する時間を計算する。移動モデル(154)は、メッセージ(66)からの列車の特性、領域情報及び変動(例えば、一時的な速度制限と線路の障害)を用いて走行時間を計算する。交通状態の動的変化は、計画作成部(56)にて観察及び検討される。変化の幾つか(例えば、一時的又は緊急の速度制限)は、移動モデル(154)にて取り上げられる。
【００９１】
計画作成部(56)は、次の手順を用いて、動的環境における計画の作成及び送出を行う。(1) 現場(12)(図３)における変化の重要性に基づいて再計画を行う(156)(158)(図５Ａ)。(2) ソリューションのマルチ作成プール(172)(172')(172'')(図５Ａ)を維持する。(3) 現在の計画境界(74)(74')(図４)と、交通及び交通状態とに基づいて、(図４の(134)(136)(120)と共に上述したように)移動計画を評価及び比較する。(4) 新たな運行及び新たな計画境界(74')に基づいてソリューションをアップグレードする。
【００９２】
図５Ａ〜図５Ｂを参照すると、通常の計画サイクルと再計画サイクルが示されている。通常、再計画サイクルは、ステップ(156)(158)を含んでいる点を除いて、通常サイクルと同じである。最初の計画サイクル(新たな開始)(図示せず)は再計画サイクルと似ているが、ステップ(158)のみを含んでいる。
【００９３】
最初のソリューションを生成すること、又はソリューションを変更若しくは破棄することは、(例えば、エージェント(185)のような)適当な「エージェント」が動作することで実現されてよい。さらに、幾つかの新しいイベントを考慮するために、(156)の再作成がなされて、(以下に説明するように)現存するソリューションに適合してもよい。ソリューションは、生成、変更又は再作成される毎に、目的関数を用いて評価される。目的関数は、(例えば、移動計画(166)(168)(170)を含む)ソリューションのプール(172)を順序付けするために用いられる。故に、ソリューションは、評価の後直ちに、プール(172)において順序付けされた適切な場所に挿入されるのが好ましい。
【００９４】
順序付け又はランク付けが行われて、相対的に低い目的関数値が、相対的に高い目的関数値よりも良いとみなされる。最も低い目的関数値を有するソリューション(例えば、図４の「最良の」計画(133))が、図４の(132)又は(152)にて暫定的に「最良」とみなされて、ソリューションプール(172)の極端な場所(例えば、最上又は底)に置かれてもよい。最小化(minimization)が開示されているが、代わりに、相対的に高い目的関数値が、相対的に低い目的関数値よりもよいとみなされてもよく、最も高い目的関数値を有するソリューションが、暫定的に「最良」とみなされて、ソリューションプール(172)の極端な場所所(例えば、最上又は底)に置かれてもよい。
【００９５】
計画サイクルは、(160)で開始して、その後(162)にて、列車のスケジュール(64)(図１)のアップデートと内部状態のアップデートを、新しい交通状態を用いて行って、(164)にて詳細な計画境界を生成する。計画境界(74)(図３)は、計画が与えられる各列車について、空間及び時間のポイントを計画作成部(56)に与える。また、それは、実行予定の予約で負わされる追加の制限を与える。例えば、列車のスケジュール(64)(図１)は、例えば、追加される新たな列車、除去される列車又は旅の終了、追加される列車の新しい目的地、列車の現在の目的地の除去又は完了、列車内容の変更などの変化を含んでよい。計画監視部(58)で既に決定されていない場合、(境界の最後の予約を列車が出る際における、列車先頭が出る時間とその速度を含む)追加の詳細が計画境界(74)に加えられて、移動計画の作成と再作成とのサポートの役に立つ。故に、ソリューションのプール(172)におけるソリューション(例えば、移動計画(166)(168)(170))が変更又は再作成される前であって、新しいソリューション(例えば、移動計画(174))が、再計画サイクル(つまり、ステップ(158))で、又はことによると通常計画サイクル(つまり、ステップ(176)(190)(192)の幾つかでの実行)で作成される前に、列車のスケジュール(64)と詳細な計画境界とがアップデートされる。次に、(178)では、図４の(150)にて判断されたように、再計画がリクエストされるか否かが判断される。否の場合、(180)にて通常の計画サイクルが継続される。他方で、再計画がリクエストされる場合、次に通常の計画サイクルが(180)で実行される前に、ステップ(156)(158)が実行される。
【００９６】
(156)では、ソリューションに関する現存するプール(例えば、ソリューションプール(172'))から複数(例えば、Ｎ１の数)の移動計画(157)が再作成される。例えば、上位Ｎ１に当たる最良のソリューションが用いられてよい。代わりに、それらソリューションに加えて、１又は２以上のソリューションが、ランダムに選択されてもよい。例えば、数Ｎ１は、(例えば、以下の(式１８)又は(式２０)による)再計画スコア(re-planning score)の関数(例えば、以下の(式８)のｆ(re-planning score))と、ソリューションのプール(172')のソリューションの数(例えば、プールサイズ(Pool Size))の積として定義されてもよい。
【００９７】
再計画サイクルに特有な活動は、現場(12)(図３)の変化と、再計画サイクルを起こさせた入力に対処することを主な理由とする。移動計画の再作成は、大きなスケジュール変化と、現場の変動との原因となる。再作成プロセスは、現存する移動計画から開始して、それを、現場の新しい状態と入力とに適合させる。少なくとも、新しい状態が考慮されて、可能ならば、与えられたソリューション内で変動が解決される(例えば、速度制限は、対応する予約間隔を変化させることで、又は、移動計画全体に大きな変化を与えることなく列車を迂回させることで対処される。他の全ての予約は、適宜調整される)。再作成の主要目的に加えて、新たなスケジュール及び境界状態に基づいて、少なくともソリューションの幾つかは、それらの現存する予約の少なくとも一部が調整される必要があるだろう(例えば、通常の計画サイクルで使用される全てのソリューションについて、それはなされる)。それらの再作成ソリューションは、ソリューションプール(172'')の(157)で示される。
【００９８】
どれか１つのソリューションが作成又は再作成された直後が好ましいが、個々の目的関数値(ＯＭＦ)(例えば、ＯＦＶ１、ＯＦＶ２、ＯＦＶ３)が判断される場合、ソリューションは、(172)(172')のような現存するプールに、個々に適当に分散されるのが好ましい。
【００９９】
次に、(158)にて、複数(Ｎ２の数)の新しい計画(例えば、(174))は、ソリューションの同じプール(例えば、アップデートされたソリューションプール(172''))の一部として、初めから作成される。例えば、数Ｎ２は、(以下の(式１８)又は(式２０)の)再計画スコアの関数(例えば、以下の(式９)のｇ(re-planning score))にソリューションプール(172')のソリューションの数(例えば、プールサイズ)を掛けた関数として決定されてよい。
【０１００】
例示した再計画戦略(図５Ａ〜図５Ｂ)は、計画監視部(58)で計算された再計画スコア(214)(図６)に、及び/又は、再計画の実行を起こした様々な変動タイプ(例えば、図３のメッセージ(66)の幾つか)に依存する。順番に、適当なアルゴリズムが、(180)にて変動タイプの各々に適用される。先述したように、(156)にて、ソリューションプール(172')の現存するＮ１個の最良のソリューションを、(162)(164)で決定される新しい状態を満足するように再作成し、(158)にて、((166)(168)(170)のような現存する古いソリューションに基づかない)新しいＮ２個のソリューション(174)を作成することで、現存するソリューションプール(172')は修正される。ソリューション(157)(174)は、作成又は再作成された各ソリューションのように、プール(172'')内でランク付けされるのが好ましい。
【０１０１】
[具体例７]  (式８)及び(式９)は、再作成スコアに基づいて再作成されるソリューションの数Ｎ１(＝ｆ(replanning score)＊プールサイズ)と、新たに再作成されるソリューションの数Ｎ２(＝ｇ(replanning score)＊プールサイズ)との決定に関する２つの関数の定義を夫々示す。
【式６】
【０１０２】
2006511394.tif 000008
【０１０３】
以下に示す(式１８)及び(式１９)にて特有の重みを較正することで、スケジュールの変化がない場合に、次式が保証されるのが好ましい。
【式７】
【０１０４】
2006511394.tif 000009
【０１０５】
[具体例８]  例えば、関数ｆ(replanning score)及びｇ(replanning score)は、図５Ａに示すような、ｘ＝replanning score(ＲＳ)、ｆ(ｘ)及びｇ(ｘ)の適当な離散的なマッピング(198)から決定されてよい。
【０１０６】
[具体例９]  代わりに、適当な任意の離散的、連続的、線形若しくは非線型の方程式、関数又はマッピングが用いられて、数Ｎ１及びＮ２が、再計画スコアと、現在のソリューションプール(例えば(172'))のサイズと関係づけられてよい。
【０１０７】
計画作成部(56)は、移動計画に関する適当な任意の作成部であってよく、例えば、多数のアルゴリズム、分岐限定法、及び/又は、ソリューション空間を探索する任意の再帰的(recursive)若しくは反復的方法を用いた協動的計算のようなタイムリーな方法で、このような計画を生成できる。オフラインで(つまり、非動的に)最適化される場合に、作成方法がソリューションプールに依存しないときでさえ、ソリューションプールは、異なる時点で構築される移動計画で占められてよい。
【０１０８】
もちろん、(例えば、以下の(式１８)又は(式２０)による)再計画スコアが適当な閾値未満であって、特別なイベントがない場合、図４のステップ(150)に関連して説明したように、再計画は開始されない。また、再計画が開始される場合、比較的小さい割合であるＮ１及びＮ２の値は、比較的小さい値である再計画スコアに対して与えられて、比較的大きい割合であるＮ１及びＮ２の値は、比較的大きな値である再計画スコアに対して与えられる。
【０１０９】
(158)の後、又は再計画がリクエストされなかった場合、(180)にて、種々の変動特有のエージェント(アルゴリズム)(185)が動作する。その後、このようなエージェント(185)が用いられて、例えば、(186)にて、障害のような状態に対処してもよい。幾つかの変動が、再計画の実行を引き起こす特別なイベントレベルに達しているが、その他の変動はそのレベルに達しなくてもよく、特有のエージェントの動作が、通常の計画サイクルについてでも行われてよい。これらエージェントが、現存するソリューションを変更するように試みることで、与えられたイベントタイプに対処される。ソリューションのアウトラインは、結果として変化してよい(例えば、それは、オリジナルのアウトライン内のイベントに対処することを試みる再作成とは異なっている)。
【０１１０】
次に、(182)にて、現在のソリューションプール(例えば、次の計画サイクルの前のプール(172)、ステップ(156)(158)に続くプール(172''))の目的関数値(183)が、(例えば、以下の(式１１)を用いることで)調整されて、目的関数値(183')で示されるように相対的に古いソリューションにダウングレードされる。ステップ(156)(158)で生成されるソリューションは、現在のものであってダウングレードされるべきではない。そして、(184)では、現在のソリューションプール(例えば、プール(172)(172'))が、新しく求められた目的関数値(183')に基づいて、再順序付けされる。ステップ(182)(184)は、全てのソリューションに適用されて、全てのソリューションが再順序付けされるよりも、ソリューション毎に適用されるのが好ましい。プール(172)にある計画は、例えば、全遅れが最小になること、最終目的地にベストタイムで着くこと等の目的を含むような１又は２以上の対応する目的関数によって評価されて、最良の計画(133)(図４)が決定される。
【０１１１】
この動的プランニング環境では、移動計画(つまり、ソリューション)のプール(172)は、マルチ作成プールである。プール(172)にあるこれらソリューション(例えば、計画(166)(168)(170))は、それらが変更される又はそれらの実行が要求される時はいつでも、新しい計画境界(74')(図４)についてアップデートされる。また、図１のスケジュール(64)がアップデートされる場合、運行が追加され、又は削除されることから、プール(172)のソリューションは、新しい列車のスケジュールに従うようにアップグレードされる。
【０１１２】
古いソリューションの目的関数は、以下の(式１１)及び(式１２)に従って、変更されてもよい。これは、移動計画(104)(図３)の作成において最近含まれていなかったソリューションがダウングレードされることを示している(例えば、それらの目的関数は、(式１１)で増加する。なぜなら、ソリューションは、この例においうて、その目的関数が低い場合に良く、計画作成部(56)は、目的関数をできるだけ小さくするからである)。計画期間で定められる時間ウィンドウよりも古いソリューションは、プール(172)から削除される(つまり、破棄される)のが好ましい。
【０１１３】
[具体例１０]  再作成は、ダウングレード化の後に最良の計画について行われてもよい。この例では、図５Ｂのステップ(182)(184)が、図５Ａのステップ(164)の直後に(図示せず)実施されるのが好ましい。好ましくは、ダウングレード化は計画サイクルの最初に行われて、新たにダウングレードされた目的関数値が、このような値を用いる動作に利用される。例えば、プール(172)の最良の計画が、(156)にて、再作成に選択されてよい。
【０１１４】
次に、図５Ｂの(186)にて、使用される計画作成に適した方法で(例えば、無制限、加重ランダム選択)、エージェントのリスト(185)から適当なエージェントが選択されて、エージェントが１つ(又は複数の)ソリューションをリクエストするならば、(176)にて、調整されたソリューションプール(172')から、利用される計画作成に適した方法(例えば、プール(172)のソリューションの目的関数値を考慮した方法。目的関数値を利用した加重ランダム選択)を用いて、ソリューションの１つ(又は複数)が選択される。エージェントのリスト(185)は、例えば、エージェントＡ１を含んでおり、それは、(必要に応じて)ダウングレードされた目的関数値に基づいて幾つかのソリューションを、又は類似のソリューションを破棄する。エージェントＡ２は、ソリューションを変更して、その目的関数値の改善を試みる。エージェントＡ３は、複数のソリューションを用いて、新しいソリューションを作成する。エージェントＡ４は、列車ブロックや速度制限のような変動の解決を試みる。エージェントＡ５は、現存するソリューションを用いることなく新たなソリューションを作成する。
【０１１５】
[具体例１１]  開示されたように、現存するソリューションが用いられて、新しいソリューションが用意される。適当なエージェント及びソリューションの選択が、複数のソリューションの調整及び適合を用意にして、新しい最適化計画を見つける機会を増加させてよい。計画作成の幾つかのケースでは、１つの「エージェント」(Ａ２)のみが、調整及び適合以外何も行わず、１つのエージェント(Ａ５)のみが、現存する計画を考慮することなく新しい計画を生成する。適当なアプローチでは、エージェント(185)のエージェントＡ１〜Ａ５の全てが利用されてもよい。
【０１１６】
そして、(188)にて、(176)で選択されたソリューションが無効(null)であるか否かが判断される。これは、現存するソリューションが、(186)で選択されたエージェントで必要とされない場合に起こる。無効でない場合、選択されたソリューションが、(190)にて、ステップ(162)からの新しいスケジュールについて、ステップ(164)からの新しい計画境界について調整される。選択された移動計画(ソリューション)は、エージェント(185)で用いられる前に、スケジュールにおける新しい又は変化した要素に対処するのに必要とされてよい。新しいスケジュール要素について、部分的な計画が作成される。また、削除されるスケジュール要素に対応する移動計画の部分は、移動計画から削除される。
【０１１７】
計画境界(74)(図３)における変化があると、現在の計画境界に対応していない支線に属する線路区間について、部分的な計画を除去することで、幾つかの移動計画が調整されてもよい。
【０１１８】
[具体例１２]  図１０に示すように、計画境界の変化によって、(図１０に示すように、選択されたソリューションにおける引き続く個々の予約に繋がらない境界又は内部境界(1001)の終わりから)現在の境界に対応していない支線に属する線路区間について、予約(1003)を含む部分的な計画を削除することで、幾つかの計画が調節されて、それが置き換えられてもよい。予約(1004)を含む新しい部分的な計画が、計画の残りの部分に良く合う(つまり、リソースの割付けの適当な順序に従う)一方で、現在の計画境界を考慮して線路区間を予約するように作成される。予約(1003)は、古い計画境界における列車計画(1002)に属する。除去される部分的計画は、先の列車計画(1002)に属している１本の列車についての予約(1003)のような複数の列車の予約を含んでよい。それら予約は、新しい部分的計画の予約(1004)で置き換えられる。各運行の部分的計画は、(図１０の垂直線で区分されるように)複数の線路区間について予約を含んでよく、信号灯(1005)のような複数の信号灯を対象としてよい(図１０は、一方向について僅かな信号灯を示している。それら信号灯は、示されている列車計画の計画境界について計画された移動方向にほぼ関している)。
【０１１９】
(176)のソリューションが無効であった場合、又は(190)の後、(186)で選択されたエージェントは、必要に応じて、(176)から選択されたソリューションを用いて、(192)にて適用される(つまり、実行される)。
【０１２０】
そして、(193)にて、(先計画リクエストによって)サイクルが中止されるべきか否かが、及び/又は、(194)にて、それが計画サイクルの終わりであるか否が判断される。(193)にてサイクルが中止されると、計画作成部(56)は(160)に続く(つまり、新しい状態下の新しい計画)。(193)にて、再計画のリクエストの判断は、図５Ａの(178)にて説明したものと同じである。これは、新しい移動計画を図４の(134)で評価して、図４の(120)にて発行することなく、通常計画サイクルが「中止される」のを許可する。他方で、サイクルの終わりを決定するために、(160)にて記録されたサイクル開始時間が、例えば、(194)にて現在時刻と比較されてよい。その差が所定の時間に達する場合、発行された移動計画(4)を再評価するために、(196)にて、図４のステップ(134)が再度行われる。さもなければ、(186)が再度行われて、別のエージェントの選択の後、別のソリューションの選択がされる。限定を意図しない例として、通常計画サイクルのサイクル時間は約６０秒に、再計画サイクルのサイクル時間は約９０秒にされてもよい。速い応答についてさえも、計画サイクルが終わる前に、計画が発行されてよい。また、必要な場合、縮小された計画ウィンドウ、及び/又はより小さい領域、及び/又は並列処理が行われて、応答時間が改善されてよい。
【０１２１】
[具体例１３]  ステップ(156)(158)(192)において、生成され(新しく作成され)、調整され、変更され、又は再作成されるソリューションが、ソリューションプール(172)に追加又はアップデートされる前に、対応する目的関数値が対応する移動計画について決定されるのが好ましい。
【０１２２】
[具体例１４]  サイクルの最後にて、ソリューションプール(172)の計画の数(例えば、５０。適切な数)は、先のサイクルの数と同じとされるのが好ましい。例えば、Ａ１のような廃棄エージェントを用いて計画を廃棄する他に、プール(172)は、ソリューションの最大数未満に維持されるのが好ましい。例えば、目的関数値が最も高い１又は２以上のソリューションが廃棄されてもよい。
【０１２３】
[具体例１５]  ステップ(182)(184)は、プール(172)の移動計画の各々に関する存在時間(age)を用い、その存在時間の関数として、プール(172)の対応する移動計画の対応する目的関数値をダウングレードして、そのダウングレード化に応じて対応する移動計画を再順序付けする。
【０１２４】
[具体例１６]  (166)(168)(170)のような古いソリューションの目的関数値は、(式１１)及び(式１２)に従って変更されてよい。
【式８】
【０１２５】
2006511394.tif 000010
【０１２６】
(式１１)によれば、ソリューションは、開示された方法でθ関数を用いることで、僅かなサイクル(ｎ0)についてその値を維持する。(式１２)の関数Ｄ(ｎ)は、ｎ0サイクルの後に累進的な高齢化(progressive aging)を行う。状態、ｎ＜Ｎ0＋Ｔ/Ｔc は、完全に計画ウィンドウが経過した後におけるソリューションの廃棄を与える。因子|ｆ(Ｎ)|/ｆ(Ｎ)が用いられることで、正及び負の目的関数値がＤ(ｎ)によって低減可能とされる。
【０１２７】
典型的な実施例では、目的関数値が、古いソリューションが「最良」であることを示す場合でさえ、古いソリューションは、発行について検討されない。開示された方法の何れかを用いて現在の計画サイクルで作成されたソリューションのみが、現在実行している計画と置き換わると考えられる。通常の計画サイクルでは、最良のソリューションが古いソリューションである場合、それは再作成されて、それがまだ最良である場合、それが、実行中の計画と置き換わると考えられる。
【０１２８】
[計画監視部]  計画監視部(58)は、図４の(130)(118)にて、各計画サイクルについて、計画作成部(56)に新しい計画境界(74)(74')を提供し、(150)にて、再計画の実行の必要性を判断する。(74)のような計画境界は、列車の位置を解析することで定められる一方で、再計画条件の評価も、例えば、装置の障害や速度制限等の現場の(現在、及び計画期間内の)変化に関する再検討を利用する。計画境界は適切に選択されて(例えば、それは、実行予定になると予期される予約(46)(48)(図９)の形態で、実行予定の予約(34)(36)(38)(図９)の終わりにて、一時的なバッファとして働く)、実施され得る新しいソリューションが効率的に決定される。計画境界のバッファのサイズは、計画サイクルと、実行予定の予約に関する運行上の要求とに依存する。予約を実行予定にすることは、その他の予約が実行予定にされることを必要としてよい(例えば、「ハイグリーン」で連続的な列車の移動を与えるために引かれる必要があるルートの数に等しい)。
【０１２９】
図６を参照すると、計画監視部(58)は、統一モデリング言語(ＵＭＬ)表記法を用いて示されており、比較的レベルが高いコンポーネントは、レベルの低いコンポーネント(例えば、階層的デザイン)に依存する。計画監視部(58)は、間隔解析モジュール(200)及び計画境界モジュール(208)の双方を含んでいる。モジュール(200)は、最後に発行された移動計画(4)(図３)と、現場(12)の状態(図３)との間の差を用いて、再計画の提案を生じる。モジュール(200)は、速度制限モジュール(202)、障害モジュール(204)及び列車間隔モジュール(206)を使用する。モジュール(208)はまた、列車間隔モジュール(206)を用いて、そのモジュール(206)で捕捉された列車位置に基づいて、計画境界(74)(図３)を決定する。列車の計画位置と、この列車の実際の位置との間隔は、計画境界(74)の要素を再定義するために用いられる。
【０１３０】
計画境界モジュール(208)は、各列車運行について境界を管理する。計画されて引かれたルートよりも境界がさらに延びることで、計画に大きな変化を起こすことなく(例えば、列車の経路の変化を起こすことなく)、近い将来の移動が可能にされる。列車の実際の速度が求められて、計画境界における予約の時間の決定が容易になる。速度は、例えば、現場の表示に基づいて求められてもよい(例えば、線路区間から線路区間への実際の移動)。精度は、列車の位置の入力に依存する。ＧＰＳを利用した技術のような進歩した技術を利用して、列車の位置及び速度の情報を非常に正確にすることで、予約の時間は、さらに精度よく計算されてよい。精度が低い情報であっても、計画境界の最も重要な特徴は近い将来の列車の経路であることから、システムは十分に機能する。
【０１３１】
列車間隔モジュール(206)及び発行計画モジュール(210)が、図７に示されている。間隔は、各列車運行について決定される。各列車の位置(図７に示さず)が各計画サイクルの最初に求められて、最近発行された移動計画(4)(図３)と比較される。この情報は、図６の間隔解析モジュール(200)及び計画境界モジュール(208)で用いられる。
【０１３２】
列車間隔モジュール(206)は、列車間隔解析コンポーネント(216)を含んでおり、それは、列車間隔運行解析コンポーネント(218)によって与えられる情報を集約する。列車間隔運行解析コンポーネント(218)は、各列車について、計画された列車位置と、実際の列車位置との間の間隔を確認する。
【０１３３】
発行計画モジュール(210)は、計画予約蓄積コンポーネント(220)を含んでおり、それは、運行計画予約蓄積コンポーネント(222)によって与えられて、維持された情報を集めることで、計画監視部(58)のために、発行された移動計画(4)の予約の完全な組を維持する。次に、運行計画予約蓄積コンポーネント(222)は、列車予約コンポーネント(224)を利用して、予約自体を維持する。
【０１３４】
通常の運行では、境界情報は、新しい移動計画の作成にて改変され得ないサブ計画(sub-plan)(例えば、計画境界を定める予約の集まり)を含むので、計画境界(74)(図３)で定義された経路は変化しない。実行予定の予約(34)(36)(38)(図９)で定義された経路を変更することは、手動の介入を必要とする。近い将来において実行予定になると予期される予定(46)(48)(図９)で定義される経路は、幾つかの変動の結果として変化し得る。計画監視部(58)は、計画境界(74)の外的変化に加えて、バッファ位置を変化する必要を認識する。これらケースの両方は、大抵の場合、再計画を実行すること(つまり、図５Ａのステップ(156)(158))によって達成される。
【０１３５】
固定された経路を考えると、関連する間隔情報は、図９の(26)(28)(40)のような幾つかの鉄道区間への入出時刻を含んでいる。図９の(24)のような列車がある線路区間を離れて、別の区間に入る時刻は、その列車の位置が求められる際に決定される。例えば、幾つかの線路区間に列車があると認められる場合に、(ＣＡＤシステム(14)内での幾らかの伝播遅延はあるが)列車位置(108)(図３)に関するメッセージが送られる。現場(12)における列車の移動に基づいて求められる時刻が、現在実行している移動計画(13)(図１)と比較されて、計画境界(74)は適切に調整される。
【０１３６】
遅延は、計画境界(74)の様々な予約に影響を与え得る。例えば、列車(例えば、図９の(24))が最後に入ったルートの予約(例えば、図９の(32))(現在位置)が用いられて、同じ列車についてその後の予約(例えば、図９の(40)(42)(44))について、遅延が見積もられる。計画された予約は、基本的にシフトされる。現在の位置について、計算は、そのシフトのほかに予約の全継続期間の延長(例えば、最初の車両で現在占められている線路区間で負わされた遅延)を行う。これは、列車の先頭車両が出る時刻に影響を与えるが、それが入る時刻には影響は与えない。
【０１３７】
以下の(式１３)〜(式１７)に示す遅延列車に関するその後の予約への影響は、最も楽観的なものである。現実的な影響については、計画境界(74)の列車間の相互作用が考慮されて、計画境界における占拠の計画が、その他の予約の相互作用に基づいて決定される。
【式９】
【０１３８】
2006511394.tif 000011
【０１３９】
ＬｏｃｏＥｎｔｒｙ/Ｅｘｉｔは、列車の先頭の進入/離脱であるとされる。(式１３)〜(式１７)は、列車が、現在の線路区間に遅れることに加えて、現在の予約でさらなる遅れ(つまり、延長)を得るかも知れないことを暗示する。これらの監視は、新しい計画境界(74')を決定する際に使用される。現在の線路区間に関した到着遅延とさらなる遅延とに加えて、各列車の実際の速度が判断される場合、計画境界はさらに正確に決定される。この情報は、計画境界における予約の間隔を再計算するのに使用される。
【０１４０】
早く到着する列車の影響も同様に判断されてよい。他の列車の依存状態は、(将来の計画に最も大きな影響を与える)このケースにおける内部境界への影響を制限してよい。大規模な計画境界内の予約の再評価は、現在実行している移動計画(13)(図１)の順序を維持し、恒常的な制限及び現在の一時的な制限(例えば、現在の速度制限)に従う。この方法は、列車の現在位置とその速度とを考慮する。
【０１４１】
間隔解析モジュール(200)(図６)は、(式１８)及び(式１９)に示す障害、速度制限及び列車位置間隔に基づいて、再計画スコア(214)を計算する。
【式１０】
【０１４２】
2006511394.tif 000012
【０１４３】
これら３つの特有の重みは、計画に予想される効果と、計画の作成とに基づいて較正されるのが好ましい。障害は、複数の列車における位置間隔によって、計画における同様な変化を生じ、対応する２つの固有の重みの実際の値を選択する方法を与える。異なる障害と、遅れた列車の数(位置間隔)について、試験が複数回繰り返されてよい。変動が加わる場合、計画を作成する困難に応じて、さらに様々な再計画への貢献が選択されてよい。速度制限間の相互関係は、以下に述べるように(式１８)に直接取り込まれる。しかしながら、通常、再作成及び再計画の困難さに応じた様々な重みが選択されてよい。
【０１４４】
速度制限νireducedがゼロに近づく場合、様々な重みがないと、速度制限項(つまり、(式１８)の第２ライン)は、障害項(つまり、(式１８)の第１ライン)と同じ結果を(効果的な変動は、両方の場合において、正確に同じ条件を与える仮定のもと)与えるように、(式１８)は工夫されている。変動の追加及び除去の両方は、(式１８)及び(式１９)を用いて両立されている。
【０１４５】
(式１８)では、項(Ｔ−Ｔi)/Ｔは、境界からの時間間隔に依存しており、現在発行されている移動計画の変動効果の減衰を示している。同様に、項ｎitrains/ｎhorizontrainsは、計画された列車総数に対した、変動領域を使用するように計画された列車数であって、相対的な変動効果の減衰を示している。(式２０)に示すように(式１８)の再計画スコアが調節されて、列車の変化に対処してもよい。
【式１１】
【０１４６】
2006511394.tif 000013
【０１４７】
再計画スコアの寄与は、変化する列車の相対的な数、ｎchangetrains/ｎhorizontrainsと、新しい列車の相対的な数、ｎnewtrains/(ｎhorizontrains＋ｎnewtrains)とに依存しており、それらは複雑な因子を示している。再計画スコアへの完全な寄与を得るには、これら２つの項に、変化した又は新しい列車のスケジュールの相対的な継続期間全体が掛けられる。
【０１４８】
(例えば、図４の(150)にて判断される際に)再計画スコア(214)(図６)に対応する閾値に達すると、(152)にて、再計画サイクルが起こる。計画監視部(58)は、再計画スコア(214)で生じた再計画リクエスト(72)(図１)と、新しい計画境界(74')(図４)とを計画作成部(56)に提示する。図５Ａのステップ(156)(158)について先述したように、再計画スコア(214)に応じて、再計画の様々なレベルが検討される。計画境界は何度も影響を受けるが、再計画の閾値に至ることは、計画境界の変化を意味しない。将来において起こると予期されるイベントは、計画境界に影響を与えないかも知れないが、計画境界を超えた移動計画への大きな影響をもたらしてもよい。故に、新しい移動計画が良質であることが保証されるためには、その新しい移動計画は、直ちに生成されなくてはならない。
【０１４９】
また、例えば、列車の順序の変化(例えば、計画領域に入る列車、計画領域の得駅で整列される列車)や、結果として計画された経路から列車を逸脱させる手動操作のような、例示した再計画スコア(214)、(式１８)で現在カバーされていない特別なイベントが起こる場合、計画監視部(58)は、再計画を引き起こしてもよい。上記の操作は、計画境界(74)を変化させる。
【０１５０】
また、特に、境界が無効にされる場合(例えば、計画境界(74)内のスケジュール変化、又は、多数の列車のスケジュールが大きく変更され、若しくは現在のスケジュールに加えられて、現在のスケジュールが大きく変更される場合)、幾つかの列車のスケジュールが、再計画の実行を直ちに引き起こしてもよい。他方、スケジュールの変化は、上述の(式２０)に示すように再計画スコアに寄与する。計画境界を変化しない、又は境界付近にないスケジュールの変化は、それら自体、再計画を引き起こすことを必要としないが、それらは、再計画スコアを増加させることで計画境界に寄与するだろう。代わりに、再計画の実行の決定が(計画作成部(56)によって)なされた後、計画サイクルの決定を導くために、再計画スコアが増加してもよい。
【０１５１】
現在の移動計画(4)の実行を継続することが、計画境界(74)の変化から望まれない場合、計画監視部(58)は、選択された列車運行(図示せず)の実行を計画実行部(60)が引き延ばすことを要求する。例えば、最近負わされた線路障害に向かう列車は、交通状態及び制約によって列車が次の目的地に達することを禁止される場合に、(例えば、スケジュール変更のような)オペレータの決定を待つために、駅又はジャンクションで停止されてよい。運行上のルールが許されているならば、変動が目的地へのアクセスを否定する場合には、ＤＯＴＰ(2)は、自動的に幾つかの駅を飛ばしてもよい(計画作成部(56)実行される)。
【０１５２】
[計画実行部]  計画実行部(60)(図３)は、ＣＡＤシステム(14)で実行される自動制御コマンド(86)と、及び/又は、(例えば、移動計画案に基づいてオペレータが作成するリクエストから)手動で実行される(110)のような短期移動計画案とを作成する。制御コマンド(86)と、短期の移動計画案(110)とは、計画作成部(56)で発行された移動計画(4)から生成される。計画実行部(60)は、(例えば、現場(12)の現在の状態に基づいて)計画実行ステップのシーケンスをタイムリーに引き起こすために、沿線の条件(例えば、内部情報と、ＣＡＤシステム(14)からの監視情報(88))を監視してよい。計画実行部(60)は、ＣＡＤシステム(14)からの監視情報(88)を用いて、計画の実行が短期の交通移動で妥協する(例えば、列車のルートが変化せず、それらの引き線は単に中断される)ことを防止する。計画実行部(60)は、移動計画を、再計算、中断又は変更すべきでない。
【０１５３】
計画実行部(60)は、計画作成部(56)で受け取られた移動計画(4)を、絶対的なタイミングよりも、運行の連続性に重点を置いて実行する。例えば、計画実行部(60)は、早さ(earliness)を抑制するために列車の移動を規制しないだろう。スケジュールの制約(例えば、列車の連関、出発時間制限)が違反されていない限り、早い列車の進行が許されて、その早さは維持される。第２に、相対時間を含む運行が尊重される。故に、列車が、特定の場所に滞在する必要がある場合、計画実行部(60)は、信号をさらに描く前に、その滞在の継続期間の間止まる。第３に、列車移動の順序は変更されない。故に、移動計画(4)(図３)が指示する場合、早い列車は、別の列車を待つ必要があるかも知れない。
【０１５４】
計画実行部(60)は、移動計画(4)の実行において４つのステップを用いる。第１に、交通状態と現場装置の状態とを含む情報(88)が、ＣＡＤシステム(14)(図３)から入力される。これによって、鉄道の状態変化、装置状態の遷移、又はオフィスで負わされた状態(例えば、線路障害)が捕捉される。第２に、移動計画(4)の実行における状態変化で起こり得る影響が評価されて、影響を受ける予約が判断される。第３に、現在の予約と移動計画全体の実行とについて起こり得る相互作用が、個々の交通用途の進行に沿って評価される。これは、列車の現在位置の下流側における線路状態(例えば、利用可能性)の確認を含んでいる。これによって、選択された列車に関する現在の移動計画(13)(図１)をさらに実行することが控えられて、現在の移動計画が変更されてもよい。第４に、制御コマンド(86)(図３)をリクエストし、及び/又は、適切な予約について短期の移動計画案(110)(図３)を用意することで、現在の移動計画(13)が実行される。
【０１５５】
[具体例１７]  図８のストリングライン列車グラフ(21)は、場所「Ｌｔｅｓｔ」(226)で線路障害を動的に加えた結果である移動計画を示している。例えば、障害の周囲を移動する列車は、ラインを切り替えることから、グラフ上で着目される(例えば、ストリングラインの線種や色(図示せず)を変えて描くことで、様々な鉄道のラインが表される。実線は、両方向について速いラインを示す。破線は、両方向について遅いラインを示す)。この例では、ある列車(234)を除いて、(228)(230)(232)のような全ての列車は、速いラインを使うことを最初に意図しており、Ｌｔｅｓｔ(226)の前で線路を切り替えて、それらの最初のラインに戻る(例えば、列車(228)(230)(232)について、ラインの線種は、実線(速い)から破線(遅い)に変化して、実線に戻る)。ある列車(234)は、自動的に障害の周囲を進む術がないので、障害の前で待っており(つまり、それは、障害があるライン上で障害の位置にて停止する必要がある)、障害の継続期間を示している(つまり、Ｌｔｅｓｔ(226)の近くにある略水平な線に対応した継続期間)。ここで、ラインは、制限された領域に亘って移動するために要する時間を示している(例えば、距離だと数マイルであって、限定された領域の前で待つことを含んでいる)。(242)のような列車は、反対方向から来ており、ラインが利用できないことで起こる混雑に対処するために、速度を落とす、又は場合によってはラインを切り替える必要があるかも知れない。
【０１５６】
同様にして、ほぼ似た結果が、一時的な速度制限から得られる(図示せず)。
【０１５７】
鉄道に関した最適化された交通プランニングが与え得る利益は大きい。開示された方法及びシステムによって、鉄道網に亘る列車移動を最適化することで、鉄道は、オンタイムの列車運行能力、資産活用を改善し、操業度、車両利益、列車の平均速度、スループットを増加させることが可能となる。
【０１５８】
開示を明確にするために、列車グラフや線路ダイヤグラムのような情報を表示するディスプレイ(20)(22)について言及されたが、このような情報は、記録され、ハードコピーされ、コンピュータで修正され、その他のデータと組み合わされてよい。このような全ての処理は、本明細書にて使用されている「ディスプレイ」又は「表示する」に含まれると当然にみなされるであろう。
【０１５９】
本発明の特定の実施例について詳細に説明したが、当該技術分野における通常の知識を有する者には、それらの詳細の様々な変更及び代替が、開示の教示を踏まえて行え得ることが理解されるであろう。それ故に、開示された特定の構成は、説明のみを目的としており、添付された特許請求の範囲の最大範囲と、そのあらゆる均等物とで与えられるべき本発明の技術的範囲を限定するものではない。
【図面の簡単な説明】
【０１６０】
本発明の完全な理解は、発明を実施するための最良の形態を、以下の添付の図面と共に参照することで得られる。
【図１】図１は、本発明の動的最適化交通プランナ(ＤＯＴＰ)の概要図である。
【図２】図２は、本発明の実施例である最適化された交通移動計画を生成する方法を示すブロック図である。
【図３】図３は、図１のＤＯＴＰと、コンピュータ支援処理(ＣＡＤ)システムとの間のインターフェイスを示す概略図であって、それらの間のインターフェイスを用いて、ＤＯＴＰは、リアルタイムな成分とほリアルタイムな成分とに分けられている。
【図４】図４は、計画作成部と、計画監視部と、計画実行部と、図３のＣＡＤシステムとの動作を示すフローチャートである。
【図５Ａ】図５Ａは、図４の計画サイクル及び再計画サイクルを示すフローチャートである。
【図５Ｂ】図５Ｂは、図４の計画サイクル及び再計画サイクルを示すフローチャートである。
【図６】図６は、図１の(現場の変化に関する)再計画スコアの計算に関するモジュールを含む計画監視部のブロック図である。
【図７】図７は、図６の計画監視部の列車間隔コンポーネント及び発行計画コンポーネントのブロック図である。
【図８】図８は、図１のＤＯＴＰで出力されるストリングライングラフの例を示しており、線路障害を動的に加えた結果である移動計画を示す。
【図９】図９は、計画境界と、様々な予約とを示す例である。
【図１０】図１０は、古い移動計画を新しい境界条件について調整する例を示す。
【図１】
2006511394.tif 000014
【図２】
2006511394.tif 000015
【図３】
2006511394.tif 000016
【図４】
2006511394.tif 000017
【図５Ａ】
2006511394.tif 000018
【図５Ｂ】
2006511394.tif 000019
【図６】
2006511394.tif 000020
【図７】
2006511394.tif 000021
【図８】
2006511394.tif 000022
【図９】
2006511394.tif 000023
【図１０】
2006511394.tif 000024
【手続補正書】
【提出日】平成17年8月23日(2005.8.23)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の交通と複数の交通状態とを有する領域について、最適化された交通移動計画を作成する方法であって、
領域の交通状態に基づいて、交通に関する第１の計画境界を決定する工程と、
第１の計画境界を用いて、領域の交通に関する第１の複数の交通移動計画を反復的に作成する工程と、
実行する第１の最適化された交通移動計画として、第１の複数の交通移動計画の１つを選択する工程と、
領域内の交通移動を制御するために、第１の最適化された交通移動計画を出力する工程と、
領域の現在の交通状態を確認する工程と、
現在の交通状態に基づいて、第１の計画境界をアップデートして、交通に関する第２の計画境界を与える工程と、
第２の計画境界を用いて、領域の交通に関する第２の複数の交通移動計画を反復的に作成する工程と、
実行する第２の最適化された交通移動計画として、第１及び第２の複数の交通移動計画の１つを選択する工程と、
領域内の交通移動を制御するために、第２の最適化された交通移動計画を出力する工程とを含む方法。
【請求項２】
第１の最適化された交通移動計画について、第１の複数の交通状態を用いる工程と、
第１の最適化された交通移動計画について、第１の複数の交通状態と現在の交通状態を比較し、第１の複数の交通移動計画にほぼ基づいて、第２の計画境界を用いて計画を続けて、領域の交通に関する第２の複数の交通移動計画を反復的に作成する工程とをさらに含む、請求項１の方法。
【請求項３】
第１の最適化された交通移動計画について、第１の複数の交通状態を用いる工程と、
第１の最適化された交通移動計画について、第１の複数の交通状態と現在の交通状態を比較し、第２の計画境界を用いて応答良く再計画を実行し、領域の交通に関する第２の複数の交通移動計画として、(ａ) 領域の交通に関する第１の複数の交通移動計画の幾つかにほぼ基づいた第３の複数の交通移動計画と、(ｂ) 領域の交通に関する第１の複数の交通移動計画に依存しない第４の複数の交通移動計画とを反復的に作成する工程とをさらに含む、請求項１の方法。
【請求項４】
第１及び第２の複数の交通移動計画の各々と目的関数値を関連付ける工程と、
計画を続ける際に、第２の計画境界を用いる工程と、
目的関数値に基づいて、第１の複数の交通移動計画の少なくとも１つを破棄する工程と、
第１の複数の交通移動計画の少なくとも１つを、その目的関数値を改善するために変更する工程と、
第１の複数の交通移動計画の中の複数の計画を用いて、第２の複数の交通移動計画の１つを作成する工程と、
現在の交通状態に関する少なくとも１つの変動に応答するように、第１の複数の交通移動計画の少なくとも１つを変更する工程と、
第１の複数の交通移動計画に依存しないように、第２の複数の交通移動計画の少なくとも１つを作成する工程とをさらに含む、請求項２の方法。
【請求項５】
第１及び第２の複数の交通移動計画について、目的関数値を決定する工程と、
目的関数値に基づいて、第２の最適化された交通移動計画として、第１及び第２の複数の交通移動計画の１つを選択する工程とをさらに含む、請求項１又は請求項３の方法。
【請求項６】
目的関数値に基づいて、第１及び第２の交通移動計画をランク付けする工程と、
ランクに基づいて、実行する第２の最適化された交通移動計画を選択する工程とをさらに含む、請求項５の方法。
【請求項７】
第１の計画境界を用いることを続けて、実行する第１の最適化された交通移動計画として第１の複数の交通移動計画の１つを選択する前に、所定の時間、領域の交通に関する第１の複数の交通移動計画を反復的に作成する工程をさらに含む、請求項１の方法。
【請求項８】
第１の計画期間を第１の計画境界と、より遅い第２の計画期間を第２の計画境界と関連付ける工程と、
スケジュール変更を入力する工程と、
第１の複数の交通移動計画の少なくとも１つを、第２計画期間及びスケジュール変更に合わせて調節する工程と、
第１の複数の交通移動計画の調節された少なくとも１つを用いて、第２の複数の交通移動計画の少なくとも１つを作成する工程とをさらに含む、請求項１又は請求項３の方法。
【請求項９】
第１及び第２の複数の交通移動計画の各々について、対応する目的関数値と対応する存在時間とを与える工程と、
第１の複数の交通移動計画の各々について、対応する存在時間の関数として、対応する目的関数値をダウングレードする工程とをさらに含む、請求項８の方法。
【請求項１０】
交通移動計画のプールに、第１の複数の交通移動計画と、第２の複数の交通移動計画の中の少なくとも幾つかの計画を含める工程をさらに含む、請求項１の方法。
【請求項１１】
プール内の交通移動計画の各々について、対応する目的関数値があり、
対応する目的関数値に基づいて、プール内の交通移動計画を順序付けする工程と、
順序に基づいて、実行する第２の最適化された交通移動計画として、プール内の交通移動計画の１つを選択する工程とをさらに含む、請求項１０の方法。
【請求項１２】
プール内における交通移動計画の各々に、対応する存在時間があり、
対応する存在時間の関数として、プールの交通移動計画の対応する１つの対応する目的関数値をダウングレードする工程と、
ダウングレードに応答して、プールの交通移動計画の対応する１つを再順序付けする工程をさらに含む、請求項１１の方法。
【請求項１３】
プール内の交通移動計画について所定の数を維持するために、第１の複数の交通移動計画の幾つかと、第２の複数の交通移動計画の幾つかとをプールから削除する工程をさらに含む、請求項１０の方法。
【請求項１４】
第１の最適化された交通移動計画について、第１の複数の交通状態と、現在の交通状態を比較して、再計画スコアを決定する工程と、
再計画スコアが所定の値を超える場合、再計画を実行する工程とをさらに含む、請求項３の方法。
【請求項１５】
列車のスケジュール変化を把握して、列車のスケジュール変化を含む再計画スコアを反応良く決定する工程と、
列車のスケジュール変化を含む再計画スコアが所定の値を超える場合、再計画を実行する工程とをさらに含む、請求項１４の方法。
【請求項１６】
第１の最適化された交通移動計画について、第１の複数の交通状態と、現在の交通状態を比較して、再計画スコアを決定する工程とをさらに含んでおり、
領域の交通状態には複数の種類があり、
再計画スコアが所定の値を超えた場合に、又は、交通状態の種類の少なくとも１つに応答して、再計画が実行される、請求項３の方法。
【請求項１７】
現在の交通状態に基づいて、第１の最適化された交通移動計画について第１の目的関数値を与える工程と、
第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定する工程と、
現在の交通状態に基づいて、最良の計画について第２の目的関数値を与える工程と、
第１の最適化された交通移動計画を最良の計画で置き換えるか否かを決定するために、第１の目的関数値を第２の目的関数値と比較する工程とをさらに含む、請求項１の方法。
【請求項１８】
第２の目的関数値が、第１の目的関数値と比較して所定の量小さいことを判断して、第１の最適化された交通移動計画を、最良の計画で応答良く置き換える工程をさらに含む、請求項１７の方法。
【請求項１９】
第１及び第２の複数の交通移動計画の各々について、対応する目的関数値と、対応する存在時間とを与える工程と、
第１の複数の交通移動計画の各々について、対応する存在時間の関数として、対応する目的関数値をダウングレードする工程と、
第１の複数の交通移動計画の各々に関しており、ダウングレードされた対応する目的関数値と、第２の複数の交通移動計画の各々に関した対応する目的関数値とに基づいて、最良の計画を決定する工程と、
第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の最適化された交通移動計画の対応する目的関数値を、最良の計画の目的関数値と比較する工程とをさらに含む、請求項１７の方法。
【請求項２０】
第１の最適化された交通移動計画について、第１の複数の交通状態と現在の交通状態を比較して、再計画スコアを決定する工程と、
再計画スコアが所定の値を超えたことを判断し、現在の交通状態を反応良く用いて、第２の交通移動計画を作成する工程と
現在の交通状態に基づいて、第１の最適化された交通移動計画について第１の目的関数値を与える工程と、
第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定する工程と、
現在の交通状態に基づいて、最良の計画について第２の目的関数値を与える工程と、
第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する工程とをさらに含む、請求項３の方法。
【請求項２１】
領域の交通状態には、複数の種類があり、
現在の交通状態において、領域の交通状態の少なくとも１つの種類の変化を確信して、現在の交通状態を反応良く用いて、第２の複数の交通移動計画を作成する工程と、
現在の交通状態に基づいて、第１の最適化された交通移動計画について第１の目的関数値を与える工程と、
第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定する工程と、
現在の交通状態に基づいて、最良の計画について第２の目的関数値を与える工程と、
第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する工程とをさらに含む、請求項３の方法。
【請求項２２】
領域内の鉄道網にある複数の列車について、第１の複数の交通移動計画を作成する工程と、
鉄道網における交通状態の変化を受けて、鉄道網に亘る列車の移動を動的に最適化する工程とを含んでおり、
鉄道網には、複数の線路区間があり、
複数の予約の各々は、線路区間の１区間における計画された使用を、１本の列車の進入日時から離脱日時で示しており、
予約を組み合わせて、第１及び第２の複数の交通移動計画を作成する工程を含む、請求項１の方法。
【請求項２３】
複数の交通とそれら交通の複数の交通状態とを有する領域について動的最適化交通プランニング装置であって、
交通状態を示す情報を入力する入力手段と、
複数のルーチンを実行する実行手段とを具えており、
それらルーチンは、
領域の交通状態に基づいて交通に関する第１の計画境界を決定し、領域の現在の交通状態を確認し、第１の計画境界をアップデートして、現在の交通状態に基づいて交通に関する第２の計画境界を与える計画監視部と、
領域の交通について、第１の計画境界を連続的に使用して、第１の複数の交通移動計画を反復的に作成し、第２の計画境界を連続的に使用して、第２の複数の交通移動計画を反復的に作成し、実行する第１の最適化された交通移動計画として第１の複数の交通移動計画の１つを選択し、実行する第２の最適化された交通移動計画として第１及び第２の複数の交通移動計画の１つを選択し、第１及び第２の最適化された交通移動計画を連続的に出力する計画作成部と、
第１及び第２の最適化された交通移動計画を、領域内の交通移動を制御する複数のコマンドに連続的に変換する計画実行部とを具える装置。
【請求項２４】
計画作成部は、第１の最適化された交通移動計画について、第１の複数の交通状態を採用し、
計画監視部は、第１の最適化された交通移動計画について、第１の複数の交通状態と現在の交通状態を比較し、
計画作成部は、第１の複数の交通移動計画にほぼ基づいて、所定の時間、第２の計画境界を用いて計画することを継続して、領域の交通に関する第２の複数の交通移動計画を反復的に作成する、請求項２３の動的最適化交通プランニング装置。
【請求項２５】
第１の最適化された交通移動計画は、複数の第１の交通境界を含んでおり、
入力手段は、現在の交通状態を用いて、交通状態を示す情報をアップデートし、
計画監視部は、第１の最適化された交通移動計画の複数の第１交通状態と、現在の交通状態を比較し、再計画スコアを決定し、再計画スコアが所定の値を超えたことを判断し、
計画作成部は、再計画スコアの関数として第１の数と第２の数とを決定し、第１の複数の交通移動計画における第１の数の計画を再作成し、第２の複数の交通移動計画における第２の数の計画を再作成する、請求項２３の動的最適化交通プランニング装置。
【請求項２６】
入力手段は、現在の交通状態を用いて、交通状態を示す情報をアップデートし、
計画作成部は、現在の交通状態に基づいて、第１の最適化された交通移動計画関する第１の目的関数値を与え、領域の交通に関する第２の複数の交通移動計画を作成し、第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定し、現在の交通状態に基づいて、最良の計画に関する第２の目的関数値を与え、第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する、請求項２３の動的最適化交通プランニング装置。
【請求項２７】
第１の最適化された交通移動計画は、複数の第１の交通状態を含んでおり、
入力手段は、現在の交通状態を用いて、交通状態を示す情報をアップデートし、
計画監視部は、第１の最適化された交通移動計画の複数の第１交通状態と、現在の交通状態を比較し、再計画スコアを決定し、再計画スコアが所定の値を超えたことを判断し、
計画作成部は、現在の交通状態を反応良く用いて第２の複数の交通移動計画を作成し、現在の交通状態に基づいて、第１の最適化された交通移動計画に関する第１の目的関数値を与え、第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定し、現在の交通状態に基づいて、最良の計画に関する第２の目的関数値を与え、第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する、請求項２３の動的最適化交通プランニング装置。
【請求項２８】
入力手段は、現在の交通状態を用いて、交通状態を示す情報をアップデートし、
計画監視部は、複数の種類の領域の交通状態を採用し、現在の交通状態における複数の種類の領域の交通状態の少なくとも１つの変化を検知し、
計画作成部は、現在の交通状態を反応良く用いて第２の複数の交通移動計画を作成し、現在の交通状態に基づいて、第１の最適化された交通移動計画に関する第１の目的関数値を与え、第１及び第２の複数の交通移動計画の何れかの中から最良の計画を決定し、現在の交通状態に基づいて、最良の計画に関する第２の目的関数値を与え、第１の最適化された交通移動計画を最良の計画で置き換えるか否かを判断するために、第１の目的関数値を第２の目的関数値と比較する、請求項２３の動的最適化交通プランニング装置。
【請求項２９】
複数の交通とそれら交通の複数の交通状態とを有する領域の交通管理システムであって、
交通状態を示す情報を入力する入力手段と、
複数のルーチンを実行する実行手段であって、それらルーチンは、
領域の交通状態に基づいて、交通に関する第１の計画境界を決定し、領域の現在の交通状態を確認し、第１の計画境界をアップデートして、現在の交通状態に基づいて、交通に関する第２の計画境界を与える計画監視部と、
領域の交通について、第１の計画境界を連続的に使用して、第１の複数の交通移動計画を反復的に作成し、第２の計画境界を連続的に使用して、第２の複数の交通移動計画を反復的に作成し、実行する第１の最適化された交通移動計画として第１の複数の交通移動計画を選択し、実行する第２の最適化された交通移動計画として第１及び第２の複数の交通移動計画の１つを選択し、第１及び第２の最適化された交通移動計画を連続的に出力する計画作成部と、
第１及び第２の最適化された交通移動計画を、領域内の交通移動を制御する複数のコマンドに連続的に変換する計画実行部とを具える実行手段と、
コマンドを実行して、領域内の交通移動を制御する実行手段とを具えるシステム。
【請求項３０】
領域は、複数の列車を有する鉄道網を含んでおり、
交通状態を示す情報は、鉄道網からの動的データを含んでおり、
計画作成部は、鉄道網について、複数の列車スケジュール、列車の特徴、及び線路の記述を入力し、第１及び第２の最適化された交通移動計画として、鉄道網の列車に関する複数の最適化された交会/通過計画を出力し、
コマンドを実行する実行手段は、鉄道網からの動的データを使用し、
交会/通過計画は、鉄道網からの動的データに基づいて、列車スケジュール、列車の特徴及び線路の記述の如何なる制限にも違反しない、請求項２９の交通管理システム。
【国際調査報告】
2006511394.tif 000025
2006511394.tif 000026