(57)【要約】【課題】鉄道ダイヤのような様々な時間制約が原因として混在するスケジュールにおいて、制約違反の原因となる箇所を連鎖的に発見（クリティカルパスを発見）する。【解決手段】本発明の一態様としてのスケジュール検証支援装置は、複数のイベントに関するスケジュールを入力するスケジュール入力手段と、入力されたスケジュールにおける各イベントそれぞれを表すノードを、前記各イベント間の時間的依存関係を表すアークにより接続したネットワークを生成するネットワーク生成手段と、前記アークの重みとしてイベント間の時間間隔の最小値と最大値のいずれかもしくは双方を設定し、それぞれのノードにおけるイベントの実施時刻の上限値と下限値のいずれかもしくは双方を前記アークの重みに基づき計算するネットワーク時刻更新手段とを備えることを特徴とする。【選択図】図１
2009274664.tif 000002
【特許請求の範囲】
【請求項１】
複数のイベントに関するスケジュールを入力するスケジュール入力手段と、
入力されたスケジュールにおける各イベントそれぞれを表すノードを、前記各イベント間の時間的依存関係を表すアークにより接続したネットワークを生成するネットワーク生成手段と、
前記アークの重みとしてイベント間の時間間隔の最小値と最大値のいずれかもしくは双方を設定し、それぞれのノードにおけるイベントの実施時刻の上限値(最早時刻)と下限値(最遅時刻)のいずれかもしくは双方を前記アークの重みに基づき計算するネットワーク時刻更新手段と
を備えることを特徴とする、スケジュール検証支援装置
【請求項２】
前記ネットワーク時刻更新手段は、
前記ネットワークにおける各ノードを前記アークによる接続関係に基づきトポロジカルソートし、
ソート順に各ノード毎に、演算対象ノードの前方(上流側)に接続する各ノードの最早時刻に当該ノードと演算対象ノードの間の時間間隔の最小値を足した値と、演算対象ノードの最早時刻を比較し、最も大きい値に前記演算対象ノードの最早時刻の値を更新する演算手続きと、
ソート逆順に各ノード毎に、演算対象ノードの後方(下流側)に接続する各ノードの最早時刻から当該ノードと演算対象ノードの間の時間間隔の最大値を減じた値と、演算対象ノードの最早時刻を比較し、最も大きい値に前記演算対象ノードの最早時刻の値を更新する演算手続きと
を各ノードにおける最早時刻の値が収束するまで交互に反復し、
同様に、ソート逆順に各ノード毎に、演算対象ノードの後方(下流側)に接続する各ノードの最遅時刻から当該ノードと演算対象ノードの間の時間間隔の最小値を減じた値と、演算対象ノードの最遅時刻を比較し、最も小さい値に前記演算対象ノードの最遅時刻の値を更新する演算手続きと、
ソート順に各ノード毎に、演算対象ノードの前方(上流側)に接続する各ノードの最遅時刻に当該ノードと演算対象ノードの間の時間間隔の最大値を足した値と、演算対象ノードの最遅時刻を比較し、最も小さい値に前記演算対象ノードの最遅時刻の値を更新する演算手続きと
を各ノードにおける最遅時刻の値が収束するまで交互に反復する
ことを特徴とする、請求項１記載のスケジュール検証支援装置。
【請求項３】
前記ネットワークの各ノードにおける最早時刻と最遅時刻との初期値、およびイベント間の時間間隔の最小値と最大値、のいずれかもしくは全てを段階的に変更する制約変更手段と、
前記ネットワーク時刻更新手段において時刻更新された各ノードの中で所定の時刻制約条件を満足しないノードを検出する違反ノード検出手段と、
前記違反ノードを端とする違反原因パスを発見する違反原因パス発見手段と、
前記違反原因パスに対応するスケジュールの一部をユーザに分かる形で表示するスケジュール表示手段と
をさらに備えることを特徴とする、請求項２記載のスケジュール検証支援装置。
【請求項４】
前記制約変更手段は、
各ノードの守るべき最早時刻制約および最遅時刻制約、またはイベント間の時間間隔の最小値と最大値、のいずれかもしくは全てを規定の量だけ増減した値を各ノードの初期値として指定し、
当該初期値の増減値を反復回数に応じて段階的に拡大もしくは縮小することで初期値を変更する
ことを特徴とする請求項３記載のスケジュール検証支援装置。
【請求項５】
前記違反原因パス発見手段は、
前記違反ノードについて、
ネットワーク上流側のノードの最早時刻及び当該ノードからの接続アークの時間間隔の最小値が原因となっている場合と、
ネットワーク下流側のノードの最早時刻及び当該ノードへの接続アークの時間間隔の最大値が原因となっている場合と、
ネットワーク上流側のノードの最遅時刻及び当該ノードからの接続アークの時間間隔の最大値が原因となっている場合と、
ネットワーク下流側のノードの最遅時刻及び当該ノードへの接続アークの時間間隔の最小値が原因となっている場合と、
を検査してその原因となるノードを検出し、
同様に、検出したノードについても前記各場合を検査してその原因となるノードを検出し、該当するノードを順次探索していくことで前記違反原因パスを発見する
ことを特徴とする、請求項３記載のスケジュール検証支援装置。
【請求項６】
複数のイベントに関するスケジュールを入力するスケジュール入力ステップと、
入力されたスケジュールにおける各イベントそれぞれを表すノードを、前記各イベント間の時間的依存関係を表すアークにより接続したネットワークを生成するネットワーク生成ステップと、
前記アークの重みとしてイベント間の時間間隔の最小値と最大値のいずれかもしくは双方を設定し、それぞれのノードにおけるイベントの実施時刻の上限値と下限値のいずれかもしくは双方を前記アークの重みに基づき計算するネットワーク時刻更新ステップと
を備えることを特徴とする、スケジュール検証支援方法。
【請求項７】
前記ネットワーク時刻更新ステップは、
前記ネットワークにおける各ノードを前記アークによる接続関係に基づきトポロジカルソートし、
ソート順に各ノード毎に、演算対象ノードの前方(上流側)に接続する各ノードの最早時刻に当該ノードと演算対象ノードの間の時間間隔の最小値を足した値と、演算対象ノードの最早時刻を比較し、最も大きい値に前記演算対象ノードの最早時刻の値を更新する演算手続きと、
ソート逆順に各ノード毎に、演算対象ノードの後方(下流側)に接続する各ノードの最早時刻から当該ノードと演算対象ノードの間の時間間隔の最大値を減じた値と、演算対象ノードの最早時刻を比較し、最も大きい値に前記演算対象ノードの最早時刻の値を更新する演算手続きと
を各ノードにおける最早時刻の値が収束するまで交互に反復し、
同様に、ソート逆順に各ノード毎に、演算対象ノードの後方(下流側)に接続する各ノードの最遅時刻から当該ノードと演算対象ノードの間の時間間隔の最小値を減じた値と、演算対象ノードの最遅時刻を比較し、最も小さい値に前記演算対象ノードの最遅時刻の値を更新する演算手続きと、
ソート順に各ノード毎に、演算対象ノードの前方(上流側)に接続する各ノードの最遅時刻に当該ノードと演算対象ノードの間の時間間隔の最大値を足した値と、演算対象ノードの最遅時刻を比較し、最も小さい値に前記演算対象ノードの最遅時刻の値を更新する演算手続きと
を各ノードにおける最遅時刻の値が収束するまで交互に反復する
ことを特徴とする、請求項６記載のスケジュール検証支援方法。
【請求項８】
前記ネットワークの各ノードにおける最早時刻と最遅時刻との初期値、およびイベント間の時間間隔の最小値と最大値、のいずれかもしくは全てを段階的に変更する制約変更ステップと、
前記ネットワーク時刻更新ステップにおいて時刻更新された各ノードの中で所定の時刻制約条件を満足しないノードを検出する違反ノード検出ステップと、
前記違反ノードを端とする違反原因パスを発見する違反原因パス発見ステップと、
前記違反原因パスに対応するスケジュールの一部をユーザに分かる形で表示するスケジュール表示ステップと
をさらに備えることを特徴とする、請求項７記載のスケジュール検証支援方法。
【請求項９】
前記制約変更ステップは、
各ノードの守るべき最早時刻制約および最遅時刻制約、またはイベント間の時間間隔の最小値と最大値、のいずれかもしくは全てを規定の量だけ増減した値を各ノードの初期値として指定し、
当該初期値の増減値を反復回数に応じて段階的に拡大もしくは縮小することで初期値を変更する
ことを特徴とする請求項８記載のスケジュール検証支援方法。
【請求項１０】
前記違反原因パス発見ステップは、
前記違反ノードについて、
ネットワーク上流側のノードの最早時刻及び当該ノードからの接続アークの時間間隔の最小値が原因となっている場合と、
ネットワーク下流側のノードの最早時刻及び当該ノードへの接続アークの時間間隔の最大値が原因となっている場合と、
ネットワーク上流側のノードの最遅時刻及び当該ノードからの接続アークの時間間隔の最大値が原因となっている場合と、
ネットワーク下流側のノードの最遅時刻及び当該ノードへの接続アークの時間間隔の最小値が原因となっている場合と、
を検査してその原因となるノードを検出し、
同様に、検出したノードについても前記各場合を検査してその原因となるノードを検出し、該当するノードを順次探索していくことで前記違反原因パスを発見する
ことを特徴とする、請求項８記載のスケジュール検証支援方法。
【請求項１１】
請求項６ないし１０のいずれか一項に記載の各ステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時間制約を伴うスケジュール一般の作成、特に、列車ダイヤの作成を支援するためのスケジュール検証支援装置およびその方法ならびにスケジュール検証支援のためのプログラムに関する。
【背景技術】
【０００２】
鉄道の運行ダイヤは、白紙の状態から作成する機会は少なく、現状のダイヤを元に、微修正した試行ダイヤを作成し、走行シミュレーションや目視チェックによる走行可否検証を反復することで、試行錯誤的に作成している。試作したスケジュールが目標時刻などの時間制約を守れない場合に、修正すべき箇所のヒントとなる情報がないと、修正するのに時間がかかる。
【０００３】
修正すべき箇所のヒントを得るための手段の一つとして、プロジェクトスケジューリングの分野では、ＰＥＲＴ（Ｐｒｏｊｅｃｔ  Ｅｖａｌｕａｔｉｏｎ  ａｎｄ  Ｒｅｖｉｅｗ  Ｔｅｃｈｎｉｑｕｅ）により、納期を守るにあたってボトルネックとなる工程をいわゆるクリティカルパスとして検出することが行われている。鉄道分野でも、非特許文献１および特許文献１のように簡易的なシミュレーション手段としてＰＥＲＴを使用した事例や、非特許文献２のように、事故時のダイヤ遅延の際のダイヤ修正を行うべき部分の候補を発見するためにクリティカルパスを用いた研究事例もある。
【特許文献１】特許２００５−４１３３２号公報  「プログラム及び列車ダイヤ評価支援装置」
【非特許文献１】長崎、江口、古関「鉄道運行計画におけるグラフ理論の応用−理論の基礎と運転整理問題への適用可能性」、電気学会交通電気鉄道研究会資料、ＴＥＲ−０３−２３、Ｊｕｎ，２００３
【非特許文献２】富井他、「鉄道のスケジューリングアルゴリズム」、ＮＴＳ、２００５
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来のＰＥＲＴでは、イベント間で要する最小の時間間隔のみを制約として扱うため用途が制限され、クリティカルパスを用いた方法は基本的にスケジュールの遅延解析にしか使えない。しかし、ダイヤでは、目標とする時刻より許容幅を超えて早く到着するのは禁止、走行時間や途中駅停車時間が長すぎるのも禁止など、イベント間の最大経過時間に関する制約が多数あり、従来型のＰＥＲＴのクリティカルパス解析では扱い難いという問題がある。
【０００５】
例えば、例えば、図１４（Ａ）に示すダイヤで、中央の列車の駅１への到着時刻をＮ分後に変更した新たなダイヤを作成したいとする。従来のＰＥＲＴモデルでは、図１４（Ｂ）の様に駅間走行時間が延びたダイヤが計算されるだけであり、このため到着・発車ノードの間の時間間隔の上限を守るための変更を伴う時刻修正は不可能であり、クリティカルパス解析も出来ない。前記文献に示したＰＥＲＴをダイヤシミュレーション演算に適用した研究事例においても、この制限のため、事故時の遅延シミュレーションに用途が限定されていた。
【０００６】
本発明は、鉄道ダイヤのような様々な時間制約が原因として混在するスケジュールにおいて、制約違反の原因となる箇所を連鎖的に発見（クリティカルパスを発見）することを可能とし、遅延シミュレーションだけでなく、ダイヤの事前計画時などにも多目的に利用することを可能としたスケジュール検証支援装置およびその方法ならびにスケジュール支援検証のためのプログラムを提供する。
【課題を解決するための手段】
【０００７】
本発明の一態様としてのスケジュール検証支援装置は、
複数のイベントに関するスケジュールを入力するスケジュール入力手段と、
入力されたスケジュールにおける各イベントそれぞれを表すノードを、前記各イベント間の時間的依存関係を表すアークにより接続したネットワークを生成するネットワーク生成手段と、
前記アークの重みとしてイベント間の時間間隔の最小値と最大値のいずれかもしくは双方を設定し、それぞれのノードにおけるイベントの実施時刻の上限値(最早時刻)と下限値(最遅時刻)のいずれかもしくは双方を前記アークの重みに基づき計算するネットワーク時刻更新手段と
を備えることを特徴とする。
【０００８】
本発明の一態様としてのスケジュール検証支援方法は、
複数のイベントに関するスケジュールを入力するスケジュール入力ステップと、
入力されたスケジュールにおける各イベントそれぞれを表すノードを、前記各イベント間の時間的依存関係を表すアークにより接続したネットワークを生成するネットワーク生成ステップと、
前記アークの重みとしてイベント間の時間間隔の最小値と最大値のいずれかもしくは双方を設定し、それぞれのノードにおけるイベントの実施時刻の上限値と下限値のいずれかもしくは双方を前記アークの重みに基づき計算するネットワーク時刻更新ステップと
を備えることを特徴とする。
【発明の効果】
【０００９】
本発明により、最大時間間隔制約と最小時間間隔制約が混在することに起因した複雑なクリティカルパスを発見することが可能となり、試作したダイヤの修正すべき箇所を的確にユーザに指摘できる。
【発明を実施するための最良の形態】
【００１０】
図１は、本発明の一実施形態としてのスケジュール検証支援装置の構成を示す機能ブロック図である。機能はコンピュータにプログラムを実行させることによって実現しても良いし、ハードウェア的に実現してもよい。
【００１１】
図１において、スケジュール検証手段１は、本発明の機能を実現する部分である。スケジュール検証手段１は、複数のイベントに関するスケジュールの入力を受け、当該スケジュールが時間制約を満足するか否かを検証し、満たさない場合は制約違反の原因の候補となる部分を発見する。前記スケジュールはスケジュール入力手段３から入力されて、データ記憶手段２におけるスケジュール記憶手段２０に記憶される。スケジュール検証手段１は、スケジュール記憶手段２０から読み出すことによってスケジュールを取得する。
【００１２】
ネットワーク生成手段１０は、検証対象のスケジュールを、ＰＥＲＴに準じたネットワーク形式のモデルとして表現する。すなわち、スケジュールにおける各イベントそれぞれを表すノードを、各イベント間の時間的依存関係を表すアークにより接続したネットワークを生成する。ネットワーク生成手段１０は、ノード間（アーク）で要する時間間隔の最小・最大の双方を制約として指定する。
【００１３】
ネットワーク時刻更新手段１１は、各ノードにおけるイベントの実施時刻の上限値(最早時刻) ＥＴと下限値(最遅時刻) ＬＴを修正する演算を、それらの値が収束するまで反復実行する。
【００１４】
違反ノード検出手段１２は、ネットワーク時刻更新手段１１の演算中に、各ノードの最早・最遅時刻の大小関係が反転していないかチェックし、反転しているノードが発見されたら、それを違反ノードとして記憶する。
【００１５】
制約変更手段１３は、前記ネットワークの各ノードの守るべき最早時刻制約、最遅時刻制約を規定の量だけ増減した値を各ノードの初期値として指定する。また、制約変更手段１３は、増減値を順次変更する。
【００１６】
違反原因パス発見手段１４は、前記違反ノードから直接接続するノードを順次探索し、違反原因ノード検出手段１４０を用いて違反の生じる原因となるノードを検出し、違反原因ノード一時記憶手段１４１に検出ノードを記憶することを逐次反復する。これにより、クリティカルパスに相当する、違反の直接原因となるノードの系列を発見する。発見されたノードの系列（クリティカルパス）はスケジュールの修正候補箇所として、データ記憶手段２におけるスケジュール修正候補箇所記憶手段２１に記憶される。
【００１７】
データ記憶手段２は、スケジュール入力手段３から入力されたスケジュールを記憶するスケジュール記憶手段２０と、スケジュール検証手段１によって指摘された修正候補箇所（クリティカルパス）を記憶するスケジュール修正候補箇所記憶手段２１とを備える。
【００１８】
スケジュール表示手段４は、スケジュール修正候補箇所記憶手段２１に記憶された修正候補箇所を、適切なタイミングで表示する。
【００１９】
図２は、ネットワーク生成手段１０において、ダイヤ（スケジュール）をＰＥＲＴに準じたネットワーク形式で表現した単純な例を示す。
【００２０】
各丸印はノードを、矢印は有向アークを示す。太い矢印は列車の運行に沿った駅への到着、出発イベントの流れを示し、細い矢印は同じ番線を使用する列車の間における順番を示す。
【００２１】
各ノードには、変更前のダイヤの時刻を標準時刻として設定される他、イベント単体の制約条件として、実行可能な最早時刻ＥＴ（下限時刻）制限、最遅時刻ＬＴ（上限時刻）制限が付加される。
【００２２】
また、各アークには、変更前のダイヤに設定された時刻の差分（出発ノードと到着ノードに設定された標準時刻の差分）をイベントの間の標準時隔として設定する他、イベントの間で守るべき時間制約条件として、最小時間間隔、最大時間間隔が付加される。
【００２３】
それぞれの列車の種類ごとに、元のダイヤデータと各列車の時間制約から、ＰＥＲＴ形式のデータを生成し、対象とする路線の構造に応じて、新しく追加された列車や時間変更、種別変更された列車に相当する個別のネットワークを連結統合する。
【００２４】
より複雑な例として、図３（Ａ）の路線で図３（Ｂ）のダイヤに従うとすると、図４のようにダイヤのネットワークを表現できる。
【００２５】
図４において、実線のアークはそれぞれの編成の移動の時間制約に相当する。
【００２６】
各駅の出発ノードとその次の駅の到着ノードの間に張られるアークは駅間走行に相当するアークであり、アークの重みは、駅間走行時間の最小値と最大値の制約を示す。
【００２７】
各駅の到着ノードとその駅の出発ノードの間に張られるアークは駅停車に相当するアークであり、アークの重みは、駅停車時間の最小値と最大値の制約を示す。
【００２８】
鎖線のアークは、各駅の到着の順番、出発の順序を表現するアークであり、アークの重みは、到着の時隔、出発の時隔の、最小値、最大値を示す。
【００２９】
二点鎖線のアークは、各駅で同一番線を留置・通過で使用する順番を表現するアークであり、アークの重みは、到着の時隔、出発の時隔の、最小値、最大値の制約を示す。
【００３０】
なお、スケジュールをネットワークに変換する方式は本例に限ったものではなく、上記の最早時刻ＥＴ（下限時刻），最遅時刻ＬＴ（上限時刻）及び各アークの最小時間間隔、最大時間間隔が指定されていれば本発明は適用可能である。
【００３１】
図５はダイヤデータからのＰＥＲＴネットワークの初期生成手順の一例を示す。
【００３２】
ステップＳ１からＳ３までは、各編成の運行に従って各編成の物理的移動に相当するネットワークを順次生成する処理である。
【００３３】
編成ｎの運行に沿ってダイヤデータを読み出し（Ｓ１）、１運行の着・発ノードを生成する（Ｓ２）。各ノードには、変更前のダイヤの着発時刻を標準時刻として設定する。生成したノードを駅間走行アーク、駅停車アークで順次接続する。全ての編成の運行分の着・発ノードと駅間走行アーク、駅停車アークを生成すれば（Ｓ３のＹＥＳ）、Ｓ４に進む。
【００３４】
ステップＳ４からＳ７までは、各駅の編成の到着順序と到着時隔、発車順序と発車時隔を制約として加えるためのアークを追加する処理である。
【００３５】
生成した全ノードを検索し、各駅の発ノードから同一駅の着ノードに向かうノードのペアを抽出し（Ｓ４）、ペアを発ノードの初期時刻（標準時刻）の早い順にソートし（Ｓ５）、ソートした順番に従い、発ノード、着ノードのそれぞれを発順序アーク、着順序アークで接続し（Ｓ６）、全ての駅の発・着ノードの発順序アーク、着順序アークを接続完了であれば（Ｓ７のＹＥＳ）、Ｓ８に進む。前記Ｓ６において、同じ駅からの発車であっても行き先の駅が異なる場合は、駅間で通過する線路が異なるため、相互にアークを接続しない。
【００３６】
Ｓ２およびＳ６で生成された各アークには、変更前のダイヤに設定された標準時刻の差分を標準時隔として設定する。これらの処理はそれぞれＳ２およびＳ６において行ってもよいしＳ７の後に行ってもよい。
【００３７】
ステップＳ８からＳ１１までは、各駅において編成が同一番線及びホームを使用する順番及び使用時隔を制約として加えるためのアークを追加する処理である。
【００３８】
生成した全ノードを検索し、各駅の各番線ごとの着ノード、発ノードを抽出し（Ｓ８）、ノードを初期時刻（標準時刻）の早い順にソートし（Ｓ９）、ソートした順番に従い、異なる運行に属するノードの間を番線使用順序アークで接続する（Ｓ１０）。こちらの番線使用順序アークも、変更前のダイヤに設定された標準時刻の差分を標準時隔として設定する。全ての駅の全ての番線の発・着ノードの番線使用順序アークを接続完了であれば（Ｓ１１のＹＥＳ）、終了する。
【００３９】
ここで、本実施形態の目的を詳細に述べる。本実施形態を含むシステムでは、白紙の状態から完全なダイヤを自動作成することではなく、既存のダイヤをユーザが変更する作業を支援することを目的としている。ダイヤを一旦ネットワーク形式でモデル化すると、ネットワークの構造を変化させない範囲の変更であれば、設定された全ての時間制約（各発着ノードの実施時刻の上限値と下限値の制約や、ノード間の時間間隔の最小値と最大値の制約）を守るダイヤの到着・出発時刻を高速に求めることが可能である。
【００４０】
ネットワークの構造を変化させないとは、車両運用（スジの折り返しのつなぎ方）や駅の発着順序及び同一番線の使用順序を変更しないことであり、この範囲の変更であれば他の運行計画（車両運用、乗務員運用、構内作業計画など）にほとんど影響を与えない。このため、ユーザが試行錯誤を行う際にまず最初に試みるべき変更である、例えば、ダイヤ改正時や運行整理時（事故などによるダイヤ乱れの復旧時）に、他路線の主要列車との乗り換えの利便性などを考慮し、一部の列車の主要駅の到着・発車時刻や停車駅を変更したい場合などに、制約条件を守れるように、影響の及ぶ他の列車の発着時刻の変更を自動的に行うことが可能である。
【００４１】
ネットワークの構造を変化させない範囲で設定された全ての時間制約を守るのは不可能な場合、制約を一旦緩め、次第に厳しくしていくことで、最初に制約違反が発生するノードとその原因となるパスを発見し、修正すべき第一候補の箇所として検出する。
【００４２】
図６は、図１のスケジュール検証支援装置の処理全体の流れを概略的に示すフローチャートである。
【００４３】
まず、スケジュールをスケジュール入力手段３から入力し、ネットワーク生成手段１０が、当該スケジュールをネットワーク形式のデータに変換する（Ｓ１０１）。
【００４４】
次に、制約変更手段１３が最早時刻ＥＴと最遅時刻ＬＴの初期値や、ノード間の時間間隔の最大値・最小値を再設定する（Ｓ１０２）。
【００４５】
最遅時刻ＬＴを例にすると、例えば各ノードの守るべき最遅時刻制約ＬＴｍａｘを元に、以下のように繰り返し数に応じて次第に初期値ＬＴ０を更新する（次第に小さくする）ことで、段階的に制約を厳しくし、最もボトルネックとなるノードを検出する。ここでＤＴ１、ＤＴ２は修正値、反復数はステップＳ１０２を反復した回数である。
ＬＴ０＝ＬＴｍａｘ＋（ＤＴ１−反復数×ＤＴ２）
【００４６】
段階的に制約を厳しくする方法については様々な方法が考えられるが、最適な方法は対象とするダイヤの性質にも大きく依存するため、本発明では特に限定しない。
【００４７】
次に、ネットワーク時刻更新手段１１が、ＥＴ，ＬＴの更新演算を行う（Ｓ１０３）。最大時間間隔制約が含まれるため、本更新演算の内容は、従来のＰＥＲＴにおける時刻更新演算とは異なる。本更新演算については後で詳しく説明する。
【００４８】
次に、時刻更新によりＥＴ＞ＬＴとなったノードがないかどうかを検索し、そのようなノードがあれば（Ｓ１０４のＹＥＳ）、該当ノードを制約違反ノードして検出し（Ｓ１０５）、後に詳述する違反原因パス発見処理により違反原因パス（従来のＰＥＲＴにおけるクリティカルパスに相当）を検出して出力する（Ｓ１０６）。
【００４９】
ＥＴ＞ＬＴとなったノードがなければ（Ｓ１０４のＮＯ）、Ｓ１０２に戻り、最早時刻ＥＴと最遅時刻ＬＴの初期値や、ノード間の時間間隔の最大値・最小値を再設定しより厳しい制約とする。
【００５０】
次に、ネットワーク時刻更新手段１１のＥＴ，ＬＴの更新演算について詳細に説明する。
【００５１】
最小時隔制約と最大時隔制約の双方を処理するためには、ＥＴ，ＬＴのそれぞれにつき、以下の手順により、値が変化しなくなるまで時間更新演算を反復実施する必要がある。説明に使用する記号を以下のように定義する。
Ｔ（ｉ，ｊ）：ノードｉ−ノードｊの最小時間間隔
ｈ：ノードｉに流入する（先行する）ノード
ＥＴｍｉｎ（ｉ）：ノードｉの取りうる最も早い時刻の制約
ｋ：ノードｉから流出する（後発する）ノード
ＬＴｍａｘ（ｉ）：ノードｉの取りうる最も遅い時刻の制約
【００５２】
［１］ノードのトポロジカルソート
ＥＴはノードの先行する順番に値を演算していく必要があるため（ＬＴは逆方向）、事前にトポロジカル（ｔｏｐｏｌｏｇｉｃａｌ）ソートを実施する。トポロジカルソートとは、あるノードＡがノードＢに先行する時、必ずＡがＢの前になるような順番で全てのノードを並べ直すことである。
【００５３】
［２］初期化
全てのノードｉについて、以下の初期化を行う。なお、先に説明したように、制約違反ノードを検出する過程においては、制約変更手段１３により初期値が修正される。
ＥＴ０（ｉ）＝ＥＴｍｉｎ（ｉ）
ＬＴ０（ｉ）＝ＬＴｍａｘ（ｉ）
【００５４】
［３］ＥＴ更新演算
以下の式（１）、式（２）の演算を値が収束し変化しなくなるまで交互に反復する。
ここで、ＥＴｓ−１は更新前、ＥＴｓは更新後の値である。
【数１】
2009274664.tif 000003
【００５５】
［４］ＬＴ更新演算
以下の式（３）、式（４）の演算を値が収束し変化しなくなるまで交互に反復する。
ここで、ＬＴｓ−１は更新前、ＬＴｓは更新後の値である。
【数２】
2009274664.tif 000004
【００５６】
なお、ＥＴ、ＬＴの値はそれぞれ独立して演算可能であり、ＥＴ更新演算とＬＴ更新演算は順番が逆でも良いし、式（１）から（４）までの演算を反復演算の同じループ内で実施しても良い。
【００５７】
ＥＴ更新演算の詳細な処理フローを図７に示す。
【００５８】
ステップＡ１では、各ノードについて式（１）に従ってＥＴ（ｉ）の更新演算を行い（Ｓ２０１）、ＥＴ（ｉ）がＬＴ（ｉ）よりも大きくなったノードがあったときは（Ｓ２０２、Ｓ２０３のＹＥＳ）、エラーを返し（Ｓ２０４）、違反ノード検出手段１２では当該ノードを違反ノードとして検出する。
【００５９】
ステップＡ２では各ノードについて式（２）に従ってＥＴ（ｉ）の更新演算を行い（Ｓ２１１）、ＥＴ（ｉ）がＬＴ（ｉ）よりも大きくなったノードがあったときは（Ｓ２１２、Ｓ２１３のＹＥＳ）、エラーを返し（Ｓ２１４）、違反ノード検出手段１２では当該ノードを違反ノードとして検出する。
【００６０】
ＥＴの値が更新されたノードが１つもなかった場合は（Ｓ２２１のＮＯ）、更新演算が収束したとして処理を終了し、ＥＴの値が更新されたノードがあった場合は（Ｓ２２１のＹＥＳ）、反復回数が上限値に達したかどうかを判定し（Ｓ２２２）、達していない場合は、再度、ステップＡ１、Ａ２を繰り返す。反復回数が上限値に達した場合は（Ｓ２２２のＮＯ）、更新演算が収束しないとしてエラーを返す（Ｓ２２３）。
【００６１】
なお、フローチャート内に記述されたＣｍａｘは、式（１）により値が更新された最も下流のノードを記憶し、式（２）の演算を行う範囲をそのノードより上流に限定するために用いる。Ｃｍｉｎは、逆に式（２）により値が更新された最も上流のノードを記憶し、式（１）の演算を行う範囲をそのノードより下流に限定するために用いる。
【００６２】
ここではＥＴ更新演算の詳細フローについて示したが、ＬＴ更新演算についても、図７の処理フローに準じて、式（３）と式（４）を利用して交互に値を更新する手順を、値が収束するまで反復することで実行できる。
【００６３】
次に、図８〜図１２を用いて、図６のステップＳ１０６に相当する違反原因パスを発見する処理を詳細に説明する。図中で用いる記号を以下のように定義する。
ＥＴ（ｎ）：ノードｎの最早時刻
ＬＴ（ｎ）：ノードｎの最遅時刻
Ｔｍｉｎ（ｉ、ｊ）：ノードｉからｊの最小時間間隔
Ｔｍａｘ（ｉ、ｊ）：ノードｉからｊの最大時間間隔
【００６４】
図８は、違反原因パスを発見する処理の全体の流れを示すフローチャートである。
【００６５】
まず、制約違反ノードＰに、次の処理対象ノードであることを示すマークＥ，Ｌの双方を付与する（Ｓ３０１）。ここで、マークＥは、当該ノードの最早時刻ＥＴが制約違反ノードＰで制約違反が発生した原因であることを示し、マークＬは、当該ノードの最遅時刻ＬＴが原因であることを示す。
【００６６】
次に、Ｅがマークされた未処理のノードがネットワーク中に存在するか否かを検索し、存在しなければ（Ｓ３０２のＮＯ）、Ｓ３０６の処理に移る。存在すれば（Ｓ３０２のＹＥＳ）、ＥＴが原因である場合のネットワーク上流側の原因ノードの発見処理（Ｓ３０３）、ＥＴが原因である場合のネットワーク下流側の原因ノードの発見処理（Ｓ３０４）を行い、当該ノードに処理済フラグを付ける（Ｓ３０５）。
【００６７】
次に、Ｌがマークされた未処理のノードがネットワーク中に存在するか否かを検索し、存在しなければ（Ｓ３０６のＮＯ）、Ｓ３１０の処理に移る。存在すれば（Ｓ３０６のＹＥＳ）、ＬＴが原因である場合のネットワーク下流側の原因ノードの発見処理（Ｓ３０７）、ＬＴが原因である場合のネットワーク上流側の原因ノードの発見処理（Ｓ３０８）を行い、当該ノードに処理済フラグを付ける（Ｓ３０９）。
【００６８】
次に、マークＥ，Ｌいずれかの付けられた未処理ノードがネットワーク中に存在するか否かを確認し、存在しなければ（Ｓ３１０のＮＯ）、処理を終了し、存在すれば（Ｓ３１０のＹＥＳ）、Ｓ３０２以降の処理に戻る。
【００６９】
図９は、ＥＴが原因である場合のネットワーク上流側の原因ノードの発見処理（Ｓ３０３）の詳細を説明するフローチャートである。
【００７０】
まず、処理対象のノード（波及ノード）ｎに上流側から接続する（トポロジカルオーダーでｎより若いＩＤを有し、ノードｎに接続する）ノード群Ｓを抽出する（Ｓ４０１）。
【００７１】
抽出したノード群Ｓから未処理のノードｋを検索し（Ｓ４０２）、未処理ノードが存在すれば（Ｓ４０３のＹＥＳ）、ノードｋのＥＴが以下の式（５）の関係を満足するか否かを確認する。
ＥＴ（ｋ）＋Ｔｍｉｎ（ｋ，ｎ）＝ＥＴ（ｎ）          式（５）
【００７２】
式（５）が成立すれば（Ｓ４０４のＹＥＳ）、ノードｋがＥＴを大きくした直接原因ノードであるので、ノードｋにマークＥを付け次の処理対象としてノードｎとする（Ｓ４０５）。式（５）が成立する場合、ネットワーク時刻更新手段１１におけるＥＴ（ｎ）の更新演算において式（１）により値の最後の変更が行われたことになり、ＥＴ（ｎ）の値が増えた要因がノードｋにあることが分かる。
【００７３】
図１０、図１１および図１２に、ＥＴが原因である場合のネットワーク下流側の原因ノードの発見処理（Ｓ３０４）ＬＴが原因である場合のネットワーク下流側の原因ノードの発見処理（Ｓ３０７）、ＬＴが原因である場合のネットワーク上流側の原因ノードの発見処理（Ｓ３０８）に相当する処理の詳細を示す。処理の概要はＳ５０３と概ね同様であるため以下それぞれ簡単に説明する。
【００７４】
図１０に示す処理では、まず、処理対象のノード（波及ノード）ｎから下流側に接続するノード群Ｓを抽出し（Ｓ５０１）、抽出したノード群Ｓから未処理のノードｋを検索する（Ｓ５０２）。未処理ノードが存在すれば（Ｓ５０３のＹＥＳ）、ノードｋのＥＴが以下の式（６）の関係を満足するか否かを確認し、式（６）が成立すれば（Ｓ５０４のＹＥＳ）、ノードｋにマークＥを付け次の処理対象としてノードｎとする（Ｓ５０５）。
ＥＴ（ｋ）−Ｔｍａｘ（ｎ，ｋ）＝ＥＴ（ｎ）          式（６）
【００７５】
図１１に示す処理では、まず、処理対象のノード（波及ノード）ｎから下流側に接続するノード群Ｓを抽出し（Ｓ６０１）、抽出したノード群Ｓから未処理のノードｋを検索する（Ｓ６０２）。未処理ノードが存在すれば（Ｓ６０３のＹＥＳ）、ノードｋのＬＴが以下の式（７）の関係を満足するか否かを確認し、式（７）が成立すれば（Ｓ６０４のＹＥＳ）、ノードｋにマークＬを付け次の処理対象としてノードｎとする（Ｓ６０５）。
ＬＴ（ｋ）−Ｔｍｉｎ（ｎ，ｋ）＝ＬＴ（ｎ）          式（７）
【００７６】
図１２に示す処理では、まず、処理対象のノード（波及ノード）ｎに上流側から接続するノード群Ｓを抽出し（Ｓ７０１）、抽出したノード群Ｓから未処理のノードｋを検索する（Ｓ７０２）。未処理ノードが存在すれば（Ｓ７０３のＹＥＳ）、ノードｋのＬＴが以下の式（８）の関係を満足するか否かを確認し、式（８）が成立すれば（Ｓ７０４のＹＥＳ）、ノードｋにマークＬを付け次の処理対象としてノードｎとする（Ｓ７０５）。
ＬＴ（ｋ）＋Ｔｍａｘ（ｋ，ｎ）＝ＬＴ（ｎ）          式（８）
【００７７】
最後に違反原因パスの一例を図１３に示す。本例では、図１４（Ａ）のように一部のノードの時刻を強制的に変更した場合に駅４の発ノードで制約違反が発生し、許容される駅間走行時間の上限に相当する最大時間間隔制約による下流側の原因ノードと、列車の発着時刻間で空けるべき時間間隔に相当する最小時間間隔制約にかかる上流側の原因ノードが交互に出現する違反原因パスが発見された例である。このようなパスは、従来のＰＥＲＴのクリティカルパス解析の方法では発見されない。ユーザはこのような情報を頼りに、途中駅の違反原因パス上のノードの着発順番を入れ替えるなどの変更操作を行うことができる。
【００７８】
なお、以上に説明した本実施形態におけるスケジュール検証支援装置は、例えば、汎用のコンピュータ装置を基本ハードウェアとして用いることでも実現することが可能である。すなわち、スケジュール検証支援装置におけるスケジュール検証手段、ネットワーク生成手段、ネットワーク時刻更新手段、違反ノード検出手段、制約変更手段、違反原因パス発見手段、違反原因ノード検出手段は、上記のコンピュータ装置に搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、スケジュール検証支援装置は、上記のプログラムをコンピュータ装置にあらかじめインストールすることで実現してもよいし、ＣＤ−ＲＯＭなどの記憶媒体に記憶して、あるいはネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータ装置に適宜インストールすることで実現してもよい。
【図面の簡単な説明】
【００７９】
【図１】本発明の一実施形態としてのスケジュール検証支援装置の構成を示す機能ブロック図。
【図２】ダイヤ（スケジュール）をＰＥＲＴに準じたネットワーク形式で表現した単純な例を示す図。
【図３】路線とダイヤの一例を示す図。
【図４】ダイヤのネットワークの一例を示す図。
【図５】ダイヤデータからのＰＥＲＴネットワークの初期生成手順の一例を示すフローチャート。
【図６】図１のスケジュール検証支援装置の処理全体の流れを概略的に示すフローチャート。
【図７】ＥＴ更新演算の詳細な処理フローを示す図。
【図８】違反原因パスを発見する処理の全体の流れを示すフローチャート。
【図９】図８のステップＳ３０３の詳細を説明するフローチャート。
【図１０】図８のステップＳ３０４の詳細を説明するフローチャート。
【図１１】図８のステップＳ３０７の詳細を説明するフローチャート。
【図１２】図８のステップＳ３０８の詳細を説明するフローチャート。
【図１３】違反原因パスの一例を示す図。
【図１４】本発明の効果を従来技術と対比して示す図。
【符号の説明】
【００８０】
１：スケジュール検証手段
２：データ記憶手段
３：スケジュール入力手段
４：スケジュール表示手段
１０：ネットワーク生成手段
１１：ネットワーク時刻更新手段
１２：違反ノード検出手段
１３：制約変更手段
１４：違反原因パス発見手段
２０：スケジュール記憶手段
２１：スケジュール修正候補箇所記憶手段
１４０：違反原因ノード検出手段
１４１：違反原因ノード一時記憶手段
【図１】
2009274664.tif 000005
【図２】
2009274664.tif 000006
【図３】
2009274664.tif 000007
【図４】
2009274664.tif 000008
【図５】
2009274664.tif 000009
【図６】
2009274664.tif 000010
【図７】
2009274664.tif 000011
【図８】
2009274664.tif 000012
【図９】
2009274664.tif 000013
【図１０】
2009274664.tif 000014
【図１１】
2009274664.tif 000015
【図１２】
2009274664.tif 000016
【図１３】
2009274664.tif 000017
【図１４】
2009274664.tif 000018