(57)【要約】【課題】  運行スケジュールを計画することを可能とするとともに、そのための解探索処理の過程において制約違反を解消することを可能とする。【解決手段】  解探索処理部１０５は、一又は複数のノード夫々における輸送手段の存在する時間帯を表すアクティビティの運行スケジュール上の配置位置を示し、輸送手段毎に設けられた変数の組合せの集合を含む解空間の解探索処理を行い、前記解空間から所定の制約条件を充足する解を検出する。【選択図】  図１
2005247058.tif 000002
【特許請求の範囲】
【請求項１】
運行スケジュール上に配置されることによって一又は複数のノード夫々における輸送手段の存在する時間帯を表し、輸送手段毎に設けられたアクティビティの運行スケジュール上への配置の仕方の組合せから成る解空間の解探索処理を行い、前記解空間から所定の制約条件を充足する解を検出する解探索処理手段を有することを特徴とする情報処理装置。
【請求項２】
同一のノードにおいて同時に存在し得る輸送手段の数を当該ノードの容量として各ノード毎に設定する容量値設定手段を更に有し、
前記所定の制約条件として、各アクティビティを運行スケジュール上に配置する際に配置位置に該当するノードの容量を１だけ使用しなければならない旨の制約条件、及び、各アクティビティを運行スケジュール上に配置した結果、配置されたアクティビティによって使用される容量が前記容量設定手段により設定された容量を越えるノードが存在してはならない旨の制約条件を含むことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記ノードには、一定区間の経路が複数のブロックに区切られた区間であって、同一区間内に複数の輸送手段が同時に存在することが許されない容量が１の閉塞区間が含まれることを特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記ノードには、一定区間の経路であって、当該一定区間の経路内に複数の輸送手段が同時に存在することが許される容量が２以上の経路が含まれることを特徴とする請求項２に記載の情報処理装置。
【請求項５】
前記解探索処理手段は、解探索処理の過程で運行スケジュール上へ配置可能な時刻のうち最も早い時刻に各アクティビティを運行スケジュール上に配置していくことを特徴とする請求項１乃至４の何れか１項に記載の情報処理装置。
【請求項６】
前記解探索処理手段は、運行スケジュール上に一度配置し、前記所定の制約条件に対して矛盾が生じた場合には、該当するアクティビティの運行スケジュール上へ配置可能な時刻のうち最も早い時刻が変更されるまで当該アクティビティを運行スケジュール上に配置しないことを特徴とする請求項５に記載の情報処理装置。
【請求項７】
前記解探索処理手段は、制約伝播技術による解探索処理を行うことを特徴とする請求項１乃至６の何れか１項に記載の情報処理装置。
【請求項８】
前記解探索処理手段は、前記所定の制約条件を充足する解のうち、最も遅い時刻に配置されたアクティビティの終了時刻が最も早い解を最適解として検出することを特徴とする請求項１乃至７の何れか１項に記載の情報処理装置。
【請求項９】
前記解探索処理手段は、各アクティビティの開始時刻を示す変数に値を割り当てていくことを特徴とする請求項１乃至８の何れか１項に記載の情報処理装置。
【請求項１０】
情報処理装置による情報処理方法であって、
運行スケジュール上に配置されることによって一又は複数のノード夫々における輸送手段の存在する時間帯を表し、輸送手段毎に設けられたアクティビティの運行スケジュール上への配置の仕方の組合せから成る解空間の解探索処理を行い、前記解空間から所定の制約条件を充足する解を検出する解探索処理ステップを含むことを特徴とする情報処理方法。
【請求項１１】
同一のノードにおいて同時に存在し得る輸送手段の数を当該ノードの容量として各ノード毎に設定する容量値設定ステップを更に含み、
前記所定の制約条件として、各アクティビティを運行スケジュール上に配置する際に配置位置に該当するノードの容量を１だけ使用しなければならない旨の制約条件、及び、各アクティビティを運行スケジュール上に配置した結果、配置されたアクティビティによって使用される容量が前記容量設定ステップにより設定された容量を越えるノードが存在してはならない旨の制約条件を含むことを特徴とする請求項１０に記載の情報処理方法。
【請求項１２】
前記ノードには、一定区間の経路が複数のブロックに区切られた区間であって、同一区間内に複数の輸送手段が同時に存在することが許されない容量が１の閉塞区間が含まれることを特徴とする請求項１１に記載の情報処理方法。
【請求項１３】
前記ノードには、一定区間の経路であって、当該一定区間の経路内に複数の輸送手段が同時に存在することが許される容量が２以上の経路が含まれることを特徴とする請求項１１に記載の情報処理方法。
【請求項１４】
前記解探索処理ステップでは、解探索処理の過程で運行スケジュール上へ配置可能な時刻のうち最も早い時刻に各アクティビティを運行スケジュール上に配置していくことを特徴とする請求項１０乃至１３の何れか１項に記載の情報処理方法。
【請求項１５】
前記解探索処理ステップでは、運行スケジュール上に一度配置し、前記所定の制約条件に対して矛盾が生じた場合には、該当するアクティビティの運行スケジュール上へ配置可能な時刻のうち最も早い時刻が変更されるまで当該アクティビティを運行スケジュール上に配置しないことを特徴とする請求項１４に記載の情報処理方法。
【請求項１６】
前記解探索処理ステップでは、制約伝播技術による解探索処理を行うことを特徴とする請求項１０乃至１５の何れか１項に記載の情報処理方法。
【請求項１７】
前記解探索処理ステップでは、前記所定の制約条件を充足する解のうち、最も遅い時刻に配置されたアクティビティの終了時刻が最も早い解を最適解として検出することを特徴とする請求項１０乃至１６の何れか１項に記載の情報処理方法。
【請求項１８】
前記解探索処理ステップでは、各アクティビティの開始時刻を示す変数に値を割り当てていくことを特徴とする請求項１０乃至１７の何れか１項に記載の情報処理方法。
【請求項１９】
請求項１０乃至１８の何れか１項に記載の情報処理方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、輸送手段の運行の乱れた状態から復旧するための計画を作成する技術に関するものである。
【背景技術】
【０００２】
従来、鉄道、バス、航空機、船舶等の人や貨物を輸送する輸送手段の運行の乱れを復旧させるための運行管理システムが種々提案されている。例えば、特許文献１や特許文献２においては、最新の在線状況に基づき各列車に対して仮シミュレーションを行い、そのシミュレーション結果とダイヤ作成判断ルールに基づいて列車運用を決定し、登録される列車全てが終着駅に到達するまでシミュレーションを繰り返し実行して復旧ダイヤを作成している。
【０００３】
ところで、例えば非特許文献１に開示される制約伝播技術とは、制約充足問題（最適化問題を含む）の求解を行う際に、探索の効率を高めるための技術である。制約充足問題の求解中に、ある変数ｘのドメイン（取り得る値の集合）が縮小された時に、変数ｘを含む制約を介して他の変数ｙのドメインが縮小される。変数ｙを含む制約を介してさらに他の変数のドメインが縮小される。同様のことが次々と連鎖的に行われていく。たとえば、変数ｘ、ｙ、ｚがあり、夫々のドメインが｛１，２｝、｛１，２，…，１０｝、｛１，２，…，５｝であるとする。制約として、５ｘ＋ｙ≦１５（制約１）、ｙ≧２ｚ（制約２）が課されているとする。変数ｘのドメインが｛１，２｝から｛２｝へと変化したとき（つまりｘ＝２となったとき）、制約１を介してｙのドメインから６，７，８，９，１０が取り除かれてｙのドメインは｛１，２，…，１０｝から｛１，２，…，５｝へと変化する。さらに制約２を介して、ｚのドメインから３、４、５が取り除かれてｚのドメインは｛１，２，…，５｝から｛１，２｝へと変化する。制約伝播技術の効果として、上記のように制約を介してある変数のドメインが縮小されることにより他の変数のドメインが縮小されることによって、探索木の中で本来であれば探索される可能性のあった枝が刈り取られ、探索空間が縮小し、結果的に探索時間の短縮が期待される。
【０００４】
【特許文献１】特許第２８９１０６６号明細書
【特許文献２】特開２００１−１９０４号公報
【非特許文献１】草刈 君子、外３名、「最適化の基盤としての制約伝播技術の利用について」、２０００年１１月９日、（社）日本オペレーションズリサーチ学会第１２回ＲＡＭＰシンポジウム論文集、ｐ．５３−６０、インターネット＜URL: HYPERLINK "http://www.e-optimization.com/resources/uploads/RAMPdoc.pdf" http://www.e-optimization.com/resources/uploads/RAMPdoc.pdf＞
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記従来例においては、シミュレーションにより時系列的に復旧ダイヤの意志決定が行われていくため、或る時点までに一度決定した事項を後で修正することができない。このために意志決定を行っていく過程において、或る制約条件に違反することが避けられない事態が発生した場合には最早その制約違反を解消する手段がない。
【０００６】
本発明は、上記問題点に鑑みてなされたものであり、運行スケジュールを計画することを可能とするとともに、そのための解探索処理の過程において制約違反を解消することが可能な情報処理装置、情報処理方法、データ及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
斯かる目的を達成するために、本発明の情報処理装置は、運行スケジュール上に配置されることによって一又は複数のノード夫々における輸送手段の存在する時間帯を表し、輸送手段毎に設けられたアクティビティの運行スケジュール上への配置の仕方の組合せから成る解空間の解探索処理を行い、前記解空間から所定の制約条件を充足する解を検出する解探索処理手段を有することを特徴とする。
【０００８】
本発明の情報処理方法は、情報処理装置による情報処理方法であって、運行スケジュール上に配置されることによって一又は複数のノード夫々における輸送手段の存在する時間帯を表し、輸送手段毎に設けられたアクティビティの運行スケジュール上への配置の仕方の組合せから成る解空間の解探索処理を行い、前記解空間から所定の制約条件を充足する解を検出する解探索処理ステップを含むことを特徴とする。
【０００９】
本発明のプログラムは、前記情報処理方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１０】
本発明によれば、アクティビティの運行スケジュール上への配置の仕方の組合せから成る解空間を解探索し、所定の制約条件を充足する解を検出することにより運行スケジュールの計画が可能となる。アクティビティは各輸送手段毎、各ノード毎に与えられるものであり、各アクティビティは、運行スケジュール上における配置位置を示すために、例えばその開始時刻、終了時刻、継続時間等を表す変数が対応付けられる。解探索を行うとは、これらの変数への値の割り当て方を決めることである。このような変数への値の割り当て方の組合せの集合からなる解空間を対象としているので例えば制約伝播技術による解探索処理を適用することが可能となり、解探索処理の過程において制約違反を解消することができる。
【発明を実施するための最良の形態】
【００１１】
以下、本発明を適用した好適な実施形態を、添付図面を参照しながら詳細に説明する。
【００１２】
−機能構成−
図１は、本発明の一実施形態に係る情報処理装置の機能構成を示すブロック図である。図１に示すように、本実施形態に係る情報処理装置１０１は、入力情報記憶部１０２、定義情報記憶部１０３、制約条件記憶部１０４、解探索処理部１０５、出力制御部１０６及び制約条件導出部１０７を備える。
【００１３】
入力情報記憶部１０２は、ユーザが例えばキーボード等の入力手段を用いて入力する情報を記憶する。記憶される情報としては、例えば、ダイヤ調整の対象となる期間（以下、スケジューリング期間と称す）の開始時刻及び終了時刻、スケジューリング期間に各列車が停車又は通過する駅及び閉塞区間の総数、ダイヤ調整の対象となる列車の数、ダイヤ調整の対象区間における始発駅への各列車の到着可能時刻、駅及び閉塞区間夫々の容量、並びに、各列車が夫々の駅又は閉塞区間を通過するための最低所要時間が挙げられる。駅及び閉塞区間夫々の容量は、予め情報処理装置１０１内部に記憶されていてもよい。
【００１４】
駅及び閉塞区間の容量とは、同じ駅又は閉塞区間に同時に存在し得る列車数の許容量である。例えば、或る駅に同時に２台までの列車が停車し得る場合や、１台の列車が或る駅に停車しているときにもう１台までの列車がその駅を通過できる場合等には、この駅の容量は"２"となる。また、或る区間の線路内を同時に２台までの列車が走行し得る場合には、この区間の線路の容量は"２"となる。ところで、上記では「閉塞区間」という概念を使用しているが、閉塞区間とは線路の一定区間が複数のブロックで区切られた区間であって、一閉塞区間内に複数の列車が同時に存在することが許されない区間である。
【００１５】
定義情報記憶部１０３は、変数の定義情報、ノード、アクティビティの識別情報の集合の定義情報等を記憶する。ここでは、駅又は閉塞区間を「ノード」と表現している。「アクティビティ」とは、列車がノードに存在する開始時刻、終了時刻及び継続時間等で各ノードにおける運行スケジュール上の存在時間帯を示す概念である。なお、「ノード」の概念には、駅又は閉塞区間以外に経路である線路自体も含むことができる。例えば、一定区間の上りの線路であって、その一定区間は複数の線路で構成され、同時に２台以上の列車が存在することが許されるならば、当該一定区間の線路に対するノードの容量はその線路に数に応じた値となる。
【００１６】
定義情報記憶部１０３に記憶される情報としては、例えば、ノードの識別情報（以下、ノードＩＤと称す）の集合の定義情報、アクティビティの識別情報（以下、アクティビティＩＤと称す）の集合の定義情報、列車の識別情報（以下、列車ＩＤと称す）の集合の定義情報、リソースの定義情報、継続時間の定義情報、及び、アクティビティの定義情報が挙げられる。尚、ここでいう「リソース」とは、「ノード」にさらにその容量を含む概念である。
【００１７】
制約条件記憶部１０４は、制約充足問題や最適化問題を解く上で用いられる制約条件の定義情報や目的関数を記憶する。制約条件として記憶される情報は、例えば、同一列車に関するアクティビティ間の時間的な制約条件（制約条件１）、各列車の始発駅への到着可能時刻に関する制約条件（制約条件２）、全てのアクティビティが終了する時刻、即ち最も遅い時刻に配置されたアクティビティの終了時刻（以下、全アクティビティ終了時刻と称す）に関する制約条件（制約条件３）、及び、各アクティビティのリソースの容量利用に関する制約条件（制約条件４）が挙げられる。
【００１８】
解探索処理部１０５は、全ての制約条件を充足するような各変数への値の割り当て方を決定することによって制約充足解或いは最適解を求める。出力制御部１０６は、解探索処理部１０５によって算出された制約充足解或いは最適解を表示パネル等の出力手段を用いて出力させる。尚、本実施形態において、求解対象となる変数は各アクティビティの開始時刻であり、全ての制約条件を充足する当該変数の組合せを算出することにより、各列車の運行スケジュール（運行ダイヤ）が定まる。
【００１９】
制約条件導出部１０７は、初期情報記憶部１０２に記録される初期情報や解探索処理部１０５の探索処理結果に基づいて制約条件を導出し、導出した制約条件を制約条件記憶部１０４に記憶させる。
【００２０】
次に、上述した「アクティビティ」の概念について、図５を参照しながら具体的に説明する。図５の左側には、列車１、列車２等の運行スケジュールを示すダイヤグラムが示され、右側には、各リソース（駅１、線路１２、駅２、・・・）における列車１、列車２のアクティビティの配置状況が示されている。また、本実施形態を説明する上での時刻は、図５上段に示すように、基準の時刻を"０"とし、その基準の時刻からの経過時間によって分刻みで表現するものとする。
【００２１】
列車１は、リソース駅１において時刻"５"から時刻"９"まで停車する。この列車１のリソース駅１におけるアクティビティは、開始時刻"５"、終了時刻"９"、継続期間"４"のアクティビティとなる。また、列車２は、リソース駅３において時刻"１８"から時刻"２２"まで停車する。この列車２のリソース駅３におけるアクティビティは、開始時刻"１８"、終了時刻"２２"、継続期間"４"のアクティビティとなる。
【００２２】
リソース線路３４において、列車１と列車２は時刻"２１"から時刻"２３"の間同時に存在する。これは、リソース線路３４の容量が２以上であることを意味し、リソース線路３４における列車１、列車２のアクティビティが同じ時間帯に重複して記されることが許される。
【００２３】
−ハード構成−
図２は、本実施形態に係る情報処理装置１０１のハードウェア構成を示した図である。本実施形態に係る情報処理装置１０１は以下に説明するようにＰＣ（パーソナル・コンピュータ）等によって構成可能である。
【００２４】
２００は、ユニット間のデータ並びに制御情報を伝送する伝送路であるシステムバスである。情報処理装置１０１の筐体内に存在する各ユニットはシステムバス２００によって接続される。以下、各ユニットについて説明する。中央処理装置（以下、ＣＰＵと称す）２０１は、本情報処理装置１０１の各種制御および演算などを行い、図１の解探索処理部１０５及び出力制御部１０６に相当する機能を担う。
【００２５】
ランダムアクセスメモリ（以下、ＲＡＭと称す）２０２は、ＣＰＵ２０１の主メモリとして、また実行プログラムの格納領域、プログラムの実行エリアならびにデータエリアとして機能する他、入力情報記憶部１０２、変数定義記憶部１０３及び制約条件記憶部１０４に相当する機能を有する。読み取り専用メモリ（以下、ＲＯＭと称す）２０３は、情報処理装置１０１内の各ユニットの制御を行う基本プログラム、すなわちＢＩＯＳ（Basic Input/Output System）や、本情報処理装置１０１を稼働するために必要な情報などを記憶する。
【００２６】
データ入出力を行うユニット群（以下、単にＦＤＤと称す）２０４は、フレキシブルディスクやＣＤ−ＲＯＭなど、取り外し可能な外部記憶媒体のデータ入出力を行う。ネットワークインタフェース（以下、単にＮＥＴＩＦと称す）２０５は、後述するモデム２０６を介して外部ネットワークに接続し、または後述するＬＡＮ２０７に接続する。ＮＥＴＩＦ２０５は、ネットワークを介して本情報処理装置１０１からのデータ転送を行うための制御や接続状況の診断を行う。
【００２７】
モデム２０６は、外部ネットワークと本情報処理装置１０１とを電話回線を介して接続するための機器であって、モデムやＩＳＤＮ接続用のターミナルアダプタを含む。ＬＡＮ２０７は、イーサネット（Ｒ）などのネットワークシステムである。本実施形態に係る情報処理装置１０１は、モデム２０６又はＬＡＮ２０７上に接続されているルータやゲートウェイ等の通信機器を用いて外部ネットワークに接続し、外部装置とのデータの送受信を可能とする。
【００２８】
ビデオＲＡＭ（以下、ＶＲＡＭと称す）２０８は、後述するＣＲＴ２０９に表示する画像データを展開し、表示の制御を行う。ＣＲＴ２０９は、ディスプレイなどの表示装置である。このＣＲＴ２０９は、情報処理装置１０１の内部に含む構成としても良いし、或いはその外部に接続した構成としても良い。
【００２９】
キーボードコントローラ（ＫＢＣ）２１０は、キーボード（ＫＢ）２１１およびマウス２１２からの入力信号を制御する。ＫＢ２１１は、情報処理装置１０１の利用者が入力操作を行うためのキーボードである。マウス２１２は、情報処理装置１０１の利用者が入力操作を行うためのポインティングデバイスである。このキーボード２１１及びマウス２１２は夫々、情報処理装置１０１の内部に含む構成としても良いし、その外部に接続した構成といても良い。
【００３０】
ハードディスクドライブ（ＨＤＤ）２１３は、アプリケーションプログラムや各種データなどの保存に用いられる。アプリケーションプログラムとは、例えば図３に示す本実施形態に係る情報処理方法を本情報処理装置１０１に実行させるためのソフトウェアプログラムであり、必要に応じてＨＤＤ２１３からＲＡＭ２０２にロードされ、ＣＰＵ２０１によって実行される。上記各種データは、図３に示す処理を情報処理装置１０１に実行させるためのデータを含み、当該データは、アプリケーションプログラムと同様にＣＰＵ２０１の処理実行時はＲＡＭ２０２に記録される。
【００３１】
当該データの具体例としては、変数／定数の定義、目的関数、制約条件及び探索ルール（図３のフローチャートによる解探索処理を規定するためのデータ）等が挙げられ、コンピュータ（ＣＰＵ２０１）は当該データを読み込んで、制約条件を満たしながら探索ルールに従って各変数への値の割り当てを行うものである。尚、当該データに含まれる探索ルールは、値の割り当てを行う変数の順序と変数へ割り当てる値の順序を規定するものである。つまり、ここでいうデータはコンピュータが果たす複数の機能を特定するものである。
【００３２】
上記ソフトウェアプログラムの起動により、定義情報記憶部１０３及び制約条件記憶部１０４に上述した変数の定義や制約条件の定義等のデータが記憶される。外部ネットワーク等のデータの伝送媒体、ＣＤ−ＲＯＭ等のデータの記録媒体等を介して情報処理装置１０１がアプリケーションプログラムやデータを得る構成も本発明の技術的思想の範疇に含まれる。
【００３３】
コントローラ（ＩＯＣ）２１４は、外部に接続されるプリンタ（ＰＲＴ）２１５やスキャナ１１６等に対する情報の入出力制御を行うことを可能とする。また本図には示していないが、ＩＯＣ２１４は、プリンタ２１５やスキャナ２１６以外に、例えば、同様に外部に接続されるＨＤＤやＭＯドライブ等と情報の入出力制御を行うことが可能である。
【００３４】
以下、本実施形態に係る情報処理装置１０１の動作について説明する。そのために、次のような例題を挙げる。
−例題−
本例題では、図６に示すように、下りダイヤのみを対象とし、駅Ａから駅Ｃ間における列車１〜３のスケジューリング問題を扱う。駅Ａには下り用線路が３線、駅Ｂには下り用線路が２線、駅Ｃには下り用線路が３線通っている。駅Ａから駅Ｂの間の線路には閉塞区間ＡＢ１、閉塞区間ＡＢ２の２つの閉塞区間が存在し、駅Ｂから駅Ｃの間の線路には閉塞区間ＢＣ１、閉塞区間ＢＣ２、閉塞区間ＢＣ３の３つの閉塞区間が存在する。列車１〜３は、下りの運行時において駅Ａ、駅Ｂ、駅Ｃの順序で通過するものとする。尚、駅Ａ〜Ｃには下り用線路夫々に対応してホームが設けられており、複数の列車が同時に同じ駅に停車した場合でも乗客は乗車／降車が可能であることを前提とする。
【００３５】
列車１は普通列車であり、時刻０以降に駅Ａに到着可能である。列車２も普通列車であり、時刻１０以降に駅Ａに到着可能である。列車３は急行列車であり、時刻Ｘ以降に駅Ａに到着可能である。
【００３６】
普通列車（列車１、列車２）は各区間を通過するのに最低でも次の時間を必要とする。普通列車（列車１、列車２）は、駅Ａを通過するためには１０分、閉塞区間ＡＢ１を通過するためには３分、閉塞区間ＡＢ２を通過するためには３分、駅Ｂを通過するためには５分、閉塞区間ＢＣ１を通過するためには３分、閉塞区間ＢＣ２を通過するためには３分、閉塞区間ＢＣ３を通過するためには３分、駅Ｃを通過するためには１０分を最低でも要する。
【００３７】
急行列車（列車３）は各区間を通過するのに最低でも次の時間を必要とする。急行列車（列車３）は、駅Ａを通過するためには１０分、閉塞区間ＡＢ１を通過するためには２分、閉塞区間ＡＢ２を通過するためには２分、駅Ｂを通過するためには１分、閉塞区間ＢＣ１を通過するためには２分、閉塞区間ＢＣ２を通過するためには２分、閉塞区間ＢＣ３を通過するためには２分、駅Ｃを通過するためには１０分を最低でも要する。
【００３８】
次に、上記例題を解く上で必要な定数、変数及び制約条件の定義内容について詳細に説明する。
−定数／変数の定義−
列車３の駅Ａの到着可能時刻Ｘ（定数"X"）として"２０"を与える。
X = 20
【００３９】
スケジューリング期間の開始時刻を"０"とし、それを基点としたスケジューリング期間の最終時刻（定数"horizon"）として"６０"を与える。以下では、スケジューリング期間中の全ての事象の時刻を"０"を基点とした時刻で表現することとする。
horizon = 60
【００４０】
駅Ａ〜Ｃと閉塞区間（閉塞区間ＡＢ１，閉塞区間ＡＢ２，閉塞区間ＢＣ１，閉塞区間ＢＣ２，閉塞区間ＢＣ３）の数（定数"nNodes"）として"８"を与える。
nNodes = 8
【００４１】
ノードＩＤの集合Nodesを次のように定義する。
Nodes＝｛１，２，・・・，nNodes｝
【００４２】
ノードＩＤの集合Nodesから最後のノードを除いた集合NodesMinusを次のように定義する。
NodesMinus＝｛１，２，・・・，nNodes-1｝
【００４３】
列車数（定数"nTrains"）として"３"を与える。
nTrains = 3
【００４４】
列車ＩＤの集合Trainsを次のように定義する。
Trains= [１，２，・・・，nTrains]
【００４５】
列車１〜３の駅Ａへの到着可能時刻（定数"startTime"）として夫々、"０"、"１０"、"Ｘ"を与える。
startTime[1] = [0], startTime[2] = [10], startTime[3] = [X]
【００４６】
駅Ａ、閉塞区間ＡＢ１、閉塞区間ＡＢ２、駅Ｂ、閉塞区間ＢＣ１、閉塞区間ＢＣ２、閉塞区間ＢＣ３及び駅Ｃの容量（定数"capacities"）として夫々、"３"、"１"、"１"、"２"、"１"、"１"、"１"、"３"を与える。
capacities[1] = [3]，capacities[2] = [1]，capacities[3] = [1]，capacities[4] = [2]，capacities[5] = [1]，capacities[6] = [1]，capacities[7] = [1]，capacities[8] = [3]
【００４７】
列車１〜３が駅Ａ〜Ｃ、各閉塞区間を通過するための最低所要時間（定数"minDurations"）を次のように与える。列車１については、駅１を通過するための最低所要時間１０分、閉塞区間ＡＢ１を通過するための最低所要時間３分、閉塞区間ＡＢ２を通過するための最低所要時間３分、駅Ｂを通過するための最低所要時間５分、閉塞区間ＢＣ１を通過するための最低所要時間３分、閉塞区間ＢＣ２を通過するための最低所要時間３分、閉塞区間ＢＣ３を通過するための最低所要時間３分、駅Ｃを通過するための最低所要時間１０分を与える。
列車２については、駅Ａを通過するための最低所要時間１０分、閉塞区間ＡＢ１を通過するための最低所要時間３分、閉塞区間ＡＢ２を通過するための最低所要時間３分、駅Ｂを通過するための最低所要時間５分、閉塞区間ＢＣ１を通過するための最低所要時間３分、閉塞区間ＢＣ２を通過するための最低所要時間３分、閉塞区間ＢＣ３を通過するための最低所要時間３分、駅Ｃを通過するための最低所要時間１０分を与える。
列車３については、駅Ａを通過するための最低所要時間１０分、閉塞区間ＡＢ１を通過するための最低所要時間２分、閉塞区間ＡＢ２を通過するための最低所要時間２分、駅Ｂを通過するための最低所要時間１分、閉塞区間ＢＣ１を通過するための最低所要時間２分、閉塞区間ＢＣ２を通過するための最低所要時間２分、閉塞区間ＢＣ３を通過するための最低所要時間２分、駅Ｃを通過するための最低所要時間１０分を与える。
minDurations[1,1] =
[10],minDurations[1,2] =[3], minDurations[1,3] =[3], minDurations[1,4] =[5], minDurations[1,5] =[10], minDurations[1,6] =[3], minDurations[1,7] =[3], minDurations[1,8] =[10], minDurations[2,1] =[10], minDurations[2,2] =[3], minDurations[2,3] =[3], minDurations[2,4] =[5], minDurations[2,5] =[3], minDurations[2,6] =[3], minDurations[2,7] =[3], minDurations[2,8] =[10], minDurations[3,1] =[10], minDurations[3,2] =[2], minDurations[3,3] =[2], minDurations[3,4] =[1], minDurations[3,5] =[2], minDurations[3,6] =[2], minDurations[3,7] =[2], minDurations[3,8] =[10]
【００４８】
各ノードＩＤに対応するリソースを次のように定義する。即ち、ノードＩＤ１（駅Ａ）に対応させて容量３（=capacities[1]）のリソース（駅リソース）、ノードＩＤ２に対応させて容量１（=capacities[2]）のリソース（閉塞区間リソース）、ノードＩＤ３に対応させて容量１（=capacities[3]）のリソース（閉塞区間リソース）、ノードＩＤ４に対応させて容量２（=capacities[4]）のリソース（駅リソース）、ノードＩＤ５に対応させて容量１（=capacities[5]）のリソース（閉塞区間リソース）、ノードＩＤ６に対応させて容量１（=capacities[6]）のリソース（閉塞区間リソース）、ノードＩＤ７に対応させて容量１（=capacities[7]）のリソース（閉塞区間リソース）、ノードＩＤ８に対応させて容量３（=capacities[8]）のリソース（駅リソース）を定義する。
DiscreteResource nodes[n in Nodes](capacities[n]);
【００４９】
各アクティビティにおける停車又は走行時間を示す継続時間変数（変数"durations"）をその下限値及び上限値とともに定義する。下限値は定数"minDurations"、上限値は定数"horizon"に基づいて定義される。
minDurations[t,n]≦ durations[t,n] ≦ horizon, t∈Trains,n∈Nodes
【００５０】
該当する変数"durations"と等しい値の継続時間をとるアクティビティtrainを定義する。アクティビティは列車１〜３毎に各リソース（駅リソース・閉塞区間リソース毎）について定義される。各t∈Trains,n∈Nodesについて、アクティビティtrain[t,n]の開始時刻、終了時刻、継続時間を表す変数を夫々train[t,n].start、train[t,n].end、train[t,n].durationとする。このとき、次のことが成り立つ。
∀t∈Trains, ∀n∈Nodes(0≦trains[t,n].start≦horizon, 0≦trains[t,n].end≦horizon, train.[t,n].duration=durations[t,n])
【００５１】
全アクティビティ終了時刻を示す全アクティビティ終了時刻変数（変数"endtime"）を定義する。
0≦endtime≦horizon
【００５２】
−目的関数の定義―
全アクティビティ終了時刻（endtime）ができるだけ早い時刻となる解（最適解）を導出するための目的関数をendtimeとし、これを最小化する。
【００５３】
−制約条件の定義−
＜制約条件１＞
同一の列車に関するアクティビティ間について、前のアクティビティの終了時刻（train[t,n].end）と次のアクティビティの開始時刻（train[t,n+1].start）は等しくなければならない。
∀t∈Trains, ∀n∈Nodes (trains[t,n].end=train[t,n＋1].start)
【００５４】
＜制約条件２＞
列車１〜３は、与えられた駅Ａの到着可能時刻以降にしか駅Ａに到着できない。即ち、駅Ａに関するアクティビティの開始時刻（train[t,1].start）は駅Ａの到着可能時刻（定数"startTimes[t]"）以降であることが課せられる。
∀t∈Trains (train[t,1].start≧startTimes[t])
【００５５】
＜制約条件３＞
全てのアクティビティは、全アクティビティ終了時刻以前に終了しなければならない。即ち、駅Ｃ（ノードＩＤ８）のアクティビティの終了時刻（train[t,8].end）は全アクティビティ終了時刻（endtime）以前となることが課せられる。
∀t∈Trains (train[t,nNodes].end≦endtime)
【００５６】
＜制約条件４＞
各アクティビティは、そのアクティビティの開始時刻から終了時刻まで、該当するリソースの容量１単位分だけ利用すること、及び、各アクティビティを運行スケジュール上に配置した結果、配置されたアクティビティによって使用される容量が予め設定された容量を越えるリソースが存在してはならないことが課せられる。
【００５７】
−探索手順−
次に、本実施形態に係る解探索処理による制約充足解演算方法の流れを、図３のフローチャートを参照しながら説明する。
【００５８】
先ず、解探索処理部１０５は、入力情報記憶部１０２、定義情報記憶部１０３及び制約条件記憶部１０４から夫々記憶された情報を読み込み、本解探索処理を開始する。本解探索処理において求解対象となる変数は、アクティビティの開始時刻を示す変数（train[t,n].start）である。
【００５９】
各開始時刻変数（train[t,n].start）のドメインは、一つ前のアクティビティ（train[t,n-1]）の開始時刻変数とそのアクティビティ（train[t,n-1]）の継続時間変数がとり得る夫々の値との加算値の集合で構成される。但し、元々変数（train[t,n].start）のドメインに含まれていない値は含まれない。例えば、変数(train[1,2].start)のドメインは[10,11,12,・・・,60]である。ドメインに含まれる値のうち最も小さい値は、一つ前のアクティビティ(train[t,n-1])の最早開始時刻(開始時刻変数train[t,n-1].startのドメインの要素の最小値)にそのアクティビティに該当する最低所要時間(minDuration[t,n-1])が加算された値であり、この値は当該アクティビティ(train[t,n])の最早開始時刻を意味する値である。
【００６０】
未だ、何れの開始時刻変数（train[t,n].start）にも値が割り当てられていない状態において、各変数のドメインの最小値を一部例示すると、train[1,1].start=0,train[1,2].start=10,train[1,3].start=13,・・・, train[2,1].start=10,train[2,2].start=20,train[2,3].start=23,・・・、train[3,1].start=0,train[3,2].start=10,train[3,3].start=12,・・・となる。
【００６１】
解探索処理部１０５は、未だ開始時刻変数に値が割り当てられていないアクティビティのうち、その最早開始時刻(開始時刻変数のドメインの要素の最小値)が最も小さいアクティビティを選択するとともに、その最小値ｍを保持する（ステップＳ３１）。上記のような何れのアクティビティの開始時刻変数にも値が割り当てられてない初めの段階では、アクティビティtrain[1,1]とアクティビティtrain[3,1]が選択されることになるので、それらのアクティビティの最早開始時刻"０"が保持される。尚、最早開始時刻に配置されなかったアクティビティは延期されたものとみなされる。それらのアクティビティは、その最早開始時刻が修正されるまで、延期された状態が続く。
【００６２】
続いて、解探索処理部１０５は、ステップＳ３１で選択されたアクティビティのうち延期されていないアクティビティtrain[1,1]を選択し、最小値"０"をアクティビティtrain[1,1]の開始時刻変数train[1,1].startに割り当てる（ステップＳ３２）。ここで、「延期」の意味は次の通りである。ステップＳ３２において、或るアクティビティの開始時刻変数に最早開始時刻を割り当てたことにより、結果的にバックトラックが起こった場合（ステップＳ３３）には、このアクティビティは延期される（ステップＳ３４）。延期されたアクティビティは、その最早開始時刻が修正されるまで、延期された状態が続く。これは、一度最早開始時刻に配置されることによって結果的に矛盾を招き、延期されたアクティビティは、将来同じ最早開始時刻に配置されたとしても、再び矛盾を招いてバックトラックするだけなので、無駄な探索を回避するためである。最早開始時刻が修正されるタイミングは、制約伝播により当該アクティビティの開始時刻変数の下限値が変化したときである。アクティビティtrain[1,1]とアクティビティtrain[3,1]は何れも延期されたアクティビティではないので、何れを選択してもよい。ここでは、アクティビティtrain[1,1]が選択されたものとする。
【００６３】
続いて、解探索処理部１０５は、アクティビティtrain[1,1]の開始時刻変数train[1,1].startに"０"を割り当てたことによって、制約条件１〜４の何れかに対する制約違反が生じたか否かを判断し、制約違反が生じた場合にはバックトラックする（ステップＳ３３）。一方、制約違反が生じなかった場合には、解探索処理部１０５はアクティビティ[1,1]の開始時刻変数train[1,1].startに"０"を割り当て、処理をステップＳ３５に移行する。尚、ここでいう「バックトラック」とは、解探索の過程で、値の割り当て方を決める対象の変数を一つ前に対象としていた変数に戻すことである。このように、本実施形態では制約伝播技術を用いて各変数への値の割り当て方を決めているので、或る制約条件に違反した場合、バックトラックすることにより解探索の過程において制約違反を解消することができる。
【００６４】
続いて、解探索処理部１０５は、全てのアクティビティの開始時刻変数に値が割り当てられているか、或いは、延期されたアクティビティのみが残っているかを判断する（ステップＳ３５）。全てのアクティビティの開始時刻変数に値が割り当てられている場合は、解ありとして処理を終了する。また、延期されたアクティビティのみが残っている場合には、解なしとして処理を終了する。いま、アクティビティtrain[1,1]の開始時刻変数train[1,1].startのみに値が割り当てられた状態にあるので、処理は再びステップＳ３１に戻ることになる。
【００６５】
次もステップＳ３１〜ステップＳ３５の処理を繰り返すことで変数train[3,1].startの値は"０"に設定される。この時点で、未だ開始時刻変数に値が割り当てられていないアクティビティのうち、最早開始時刻が最早開始時刻の最小値"１０"と等しいアクティビティは、アクティビティtrain[2,1]、アクティビティtrain[1,2]、アクティビティtrain[3,2]となる。従って、ステップＳ３１では、アクティビティtrain[2,1]、アクティビティtrain[1,2]、アクティビティtrain[3,2]が選択されるとともに、最小値"１０"が保持される。
【００６６】
続くステップＳ３２では、アクティビティtrain[1,2]が選択され、その開始時刻変数train[1,2].startに最小値"１０"が割り当てられ、その結果、制約伝播が起こり、アクティビティtrain[3,2]の最早開始時刻は"１３"となる。即ち、アクティビティtrain[1,2]の継続時間の最小値が"３"なので、閉塞区間ＡＢ１は少なくとも時刻"１０"から"１３"までアクティビティtrain[1,2]によって利用される。閉塞区間ＡＢ１の容量は"１"であるから、時刻"１０"から時刻"１３"まではアクティビティtrain[3,2]が閉塞区間ＡＢ１を利用することはできなくなる。そのためアクティビティtrain[3,2]の開始時刻変数のドメインから"１０"、"１１"、"１２"が取り除かれ、アクティビティtrain[3,2]の最早開始時刻は"１３"になる。
【００６７】
アクティビティtrain[1,2]を時刻"１０"から開始することによって、制約違反は検出されないので、ステップＳ３３、ステップＳ３５を介して処理は再びステップＳ３１に戻る。
【００６８】
ステップＳ３１では、残されたアクティビティ（未だ開始時刻変数に値が設定されていない変数）のうち開始時刻変数のドメインに最小値を含むアクティビティの集合を求める。いま、アクティビティtrain[2,1]のみが開始時刻変数のドメインに最小値"１０"を含むため、今回のステップＳ３２の処理ではアクティビティtrain[2,1]が選択され、その開始時刻変数train[2,1].startに最小値"１０"が割り当てられる。
【００６９】
開始時刻変数train[2,1].startに"１０"が割り当てられた結果、制約違反は検出されないので、ステップＳ３３、ステップＳ３５を介して処理は再びステップＳ３１に戻る。
【００７０】
続くステップＳ３２では、残されたアクティビティのうち開始時刻変数のドメインに最小値を含むアクティビティを求める。この時点における最小値ｍは"１３"であり、開始時刻変数のドメインに最小値"１３"を含むのは、アクティビティtrain[1,3]とアクティビティtrain[3,2]の２つである。続くステップＳ３２では、アクティビティtrain[1,3]が選択されたものとすると、その開始時刻変数train[1,3].startに"１３"が割り当てられる。その結果、特に制約違反は検出されず処理はステップＳ３３、ステップＳ３５を介して再びステップＳ３１に戻る。
【００７１】
いま、最小値"１３"を開始時刻変数のドメインに含むのはアクティビティtrain[3,2]のみであるため、ステップＳ３１では、最小値を開始時刻変数のドメインに含むアクティビティの集合としてアクティビティtrain[3,2]のみが求められる。続くステップＳ３２では、アクティビティtrain[3,2]が選択され、その開始時刻変数train[3,2].startに"１３"が割り当てられる。
【００７２】
以上説明した処理を全てのアクティビティに対して実行することにより、全アクティビティの開始時刻変数に値が割り当てられる。このように、本解探索処理では、アクティビティの開始時刻を示す変数train[t,n].startの値を設定することによって、各アクティビティのスケジューリング期間への配置を決定している。
【００７３】
アクティビティの終了時刻（train[t,n].end）は、その一つ後のアクティビティの開始時刻（train[t,n+1].start）と等しくなければならないという制約条件１から求められる。また、当該アクティビティの終了時刻（train[t,n].end）が定まることによって、その終了時刻と当該アクティビティの開始時刻（train[t,n].start）との差分から当該アクティビティの継続時間（durations[t,n]）が求められる。尚、アクティビティ（train[t,8]）については、継続時間（durations[t,8]）には、該当する列車のノードＩＤ８における最小所要時間minDuration[t,8]の値を割り当て、またその終了時刻（train[t,8].end）は当該アクティビティの開始時刻（train[t,8].start）に継続時間（durations[t,8]）を加算することによって求められる。
【００７４】
本探索手順においては、アクティビティの配置は常に最早開始時刻に配置される。従って、本探索手順は基本的にリソースの使用効率を高くする解の探索に好適であり、特に復旧時のように平常時より高い密度で列車を運行することが期待される局面において有効である。また、アクティビティがある時刻に配置された結果として矛盾が発生した後に、制約が緩和されることがないまま同一時刻に配置された場合には、再び矛盾が発生することは明らかである。そのような試行は探索空間を大きくし、探索時間を長くすることとなる。そこで、本探索手順においては、一度時間軸上に配置されて矛盾が発生したアクティビティは、制約伝播の結果としてその最早開始時刻が変更されるまで配置対象から外すことにより、必要以上に探索空間が大きくなり探索時間が長くなることを防いでいる。
【００７５】
次に、本実施形態に係る解探索処理による最適解演算方法の流れを、図４のフローチャートを参照しながら説明する。尚、制約充足解を求めるだけであれば、以下に説明する処理は不要であり、図３の処理によって例えば初めて制約充足解が得られた時点で処理を終了させればよい。
【００７６】
上記のように、図３のステップＳ３１〜ステップＳ３５の処理を経ることにより制約充足解が演算されると（ステップＳ４１）、解探索処理部１０５は、解有りと判断し（ステップＳ４２）、初めの制約充足解は、当該解＝「既知の最良の解」、当該解に基づく目的関数値（全アクティビティ終了時刻（endtime））として保持する。
【００７７】
このように、「既知の最良の解」及び「既知の最良の解の目的関数値」が一旦保持されると、以降の解探索処理においては、解の目的関数値が「既知の最良の解の目的関数値」より小さな値でなければならない、という制約条件５が制約条件導出部１０７によって導出される（ステップＳ４３）。従って、ステップＳ４１において次に算出される解は、初めの解（既知の最良の解）より小さい目的関数値をとる値となる。この場合、ステップＳ４４では、「既知の最良の解」及び「既知の最良の解の目的関数値」は次の解に基づく数値に更新され、制約条件５の内容も更新される。
【００７８】
上記処理の流れは、図３に示す制約充足解演算方法を終えるまで実行され、最後まで保持されている「既知の最良の解」が最適解とされる（ステップＳ４５、ステップＳ４６）。このように、本実施形態では、全アクティビティ終了時刻をできるだけ早い時刻とする変数の組合せを最適解として得ることが可能である。
【００７９】
上記解探索処理の結果、最適解とされた各変数train[t,n].startの値は次の通りである。
train[1,1].start=0
train[1,2].start=10
train[1,3].start=13
train[1,4].start=16
train[1,5].start=21
train[1,6].start=24
train[1,7].start=27
train[1,8].start=30
train[2,1].start=10
train[2,2].start=20
train[2,3].start=23
train[2,4].start=26
train[2,5].start=31
train[2,6].start=34
train[2,7].start=37
train[2,8].start=40
train[3,1].start=0
train[3,2].start=13
train[3,3].start=16
train[3,4].start=18
train[3,5].start=19
train[3,6].start=21
train[3,7].start=23
train[3,8].start=25
【００８０】
以下に、列車３の駅Ａの到着可能時間Ｘの値が０、１０、２０のそれぞれの場合に得られた解を示す。
＜Ｘの値が０の場合＞
駅Ａを列車１の後で列車３が出発し、駅Ｂで列車３が列車１を追い抜く解が得られる。列車３のアクティビティの継続時間の中で最低所要時間より長いのは次の２つである。
durations[3,1] = 13(最低所要時間minDurations[3,1]=10)
durations[3,2] = 3 (最低所要時間minDurations[3,2]=2)
【００８１】
durations[3,1]が最低所要時間の１０分より長い１３分となったのは、列車１が閉塞区間ＡＢ１から出ていくのを待ってから、列車３が閉塞区間ＡＢ１に入るため、列車３の駅Ａへの停車時間が長くなったためである。
【００８２】
durations[3,2]が最低所要時間の２分より長い３分となったのは、列車１が閉塞区間ＡＢ２を出ていくのを待ってから、列車３が閉塞区間ＡＢ２に入るため、閉塞区間ＡＢ１にいる時間が長くなったためである。
【００８３】
本処理例において、最適解導出時における目的関数値は"５０"となる。これは、全アクティビティ終了時刻"５０"であることを意味する。
【００８４】
本処理例において算出される各アクティビティの開始時刻及び終了時刻は次の通りである。
駅Ａ（ノードＩＤ１）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,1]）については開始時刻"０"、終了時刻"１３"となり、列車２のアクティビティ（train[2,1]）については開始時刻"１０"、終了時刻"２０"となり、列車１のアクティビティ（train[1,1]）については開始時刻"０"、終了時刻"１０"となる。
【００８５】
閉塞区間ＡＢ１（ノードＩＤ２）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,2]）については開始時刻"１３"、終了時刻"１６"となり、列車２のアクティビティ（train[2,2]）については開始時刻"２０"、終了時刻"２３"となり、列車１のアクティビティ（train[1,2]）については開始時刻"１０"、終了時刻"１３"となる。
【００８６】
閉塞区間ＡＢ２（ノードＩＤ３）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,3]）については開始時刻"１６"、終了時刻"１８"となり、列車２のアクティビティ（train[2,3]）については開始時刻"２３"、終了時刻"２６"となり、列車１のアクティビティ（train[1,3]）については開始時刻"１３"、終了時刻"１６"となる。
【００８７】
駅Ｂ（ノードＩＤ４）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,4]）については開始時刻"１８"、終了時刻"１９"となり、列車２のアクティビティ（train[2,4]）については開始時刻"２６"、終了時刻"３１"となり、列車１のアクティビティ（train[1,4]）については開始時刻"１６"、終了時刻"２１"となる。
【００８８】
閉塞区間ＢＣ１（ノードＩＤ５）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,5]）については開始時刻"１９"、終了時刻"２１"となり、列車２のアクティビティ（train[2,5]）については開始時刻"３１"、終了時刻"３４"となり、列車１のアクティビティ（train[1,5]）については開始時刻"２１"、終了時刻"２４"となる。
【００８９】
閉塞区間ＢＣ２（ノードＩＤ６）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,6]）については開始時刻"２１"、終了時刻"２３"となり、列車２のアクティビティ（train[2,6]）については開始時刻"３４"、終了時刻"３７"となり、列車１のアクティビティ（train[1,6]）については開始時刻"２４"、終了時刻"２７"となる。
【００９０】
閉塞区間ＢＣ３（ノードＩＤ７）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,7]）については開始時刻"２３"、終了時刻"２５"となり、列車２のアクティビティ（train[2,7]）については開始時刻"３７"、終了時刻"４０"となり、列車１のアクティビティ（train[1,7]）については開始時刻"２７"、終了時刻"３０"となる。
【００９１】
駅Ｃ（ノードＩＤ８）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,8]）については開始時刻"２５"、終了時刻"３５"となり、列車２のアクティビティ（train[2,8]）については開始時刻"４０"、終了時刻"５０"となり、列車１のアクティビティ（train[1,8]）については開始時刻"３０"、終了時刻"４０"となる。
【００９２】
全アクティビティ終了時刻は上記目的関数値"５０"となる。
endtime = 50
【００９３】
本処理例において算出される継続時間（durations[t,n]）は次の通りである。
durations[1,1] = 10
durations[1,2] = 3
durations[1,3] = 3
durations[1,4] = 5
durations[1,5] = 3
durations[1,6] = 3
durations[1,7] = 3
durations[1,8] = 10
durations[2,1] = 10
durations[2,2] = 3
durations[2,3] = 3
durations[2,4] = 5
durations[2,5] = 3
durations[2,6] = 3
durations[2,7] = 3
durations[2,8] = 10
durations[3,1] = 13
durations[3,2] = 3
durations[3,3] = 2
durations[3,4] = 1
durations[3,5] = 2
durations[3,6] = 2
durations[3,7] = 2
durations[3,8] = 10
【００９４】
本処理例において算出されるアクティビティの終了時刻（train[1,n].end）は次の通りである。
train[1,1].end = 10
train[1,2].end = 13
train[1,3].end = 16
train[1,4].end = 21
train[1,5].end = 24
train[1,6].end = 27
train[1,7].end = 30
train[1,8].end = 40
train[2,1].end = 20
train[2,2].end = 23
train[2,3].end = 26
train[2,4].end = 31
train[2,5].end = 34
train[2,6].end = 37
train[2,7].end = 40
train[2,8].end = 50
train[3,1].end = 13
train[3,2].end = 16
train[3,3].end = 18
train[3,4].end = 19
train[3,5].end = 21
train[3,6].end = 23
train[3,7].end = 25
train[3,8].end = 35
【００９５】
図７は、本処理例における結果表示画面の一構成を示す図である。出力制御部１０６は、図７に示すように、以上得られた各変数の値に基づいて、列車毎の夫々のリソースにおけるアクティビティを運行スケジュール上に配置した画面を表示パネルに表示させる。
【００９６】
＜Ｘの値が１０の場合＞
駅Ａを列車２の後で列車３が出発し、駅Ｂで列車３が列車２を追い抜く解が得られる。列車３のアクティビティの継続時間の中で最低所要時間よりも長いのは次の２つである。
durations[3,1] = 13（最低所要時間minDurations[3,1]=10）
durations[3,2] = 3 （最低所要時間minDurations[3,2]=2）
【００９７】
durations[3,1]が最低所要時間の１０分より長い１３分となったのは、列車２が閉塞区間ＡＢ１から出ていくのを待ってから、列車３が閉塞区間ＡＢ１に入るため、列車３の駅Ａへの停車時間が長くなったためである。
【００９８】
また、durations[3,2]が最低所要時間の２分より長い３分となったのは、列車２が閉塞区間ＡＢ２を出ていくのを待ってから、列車３が閉塞区間ＡＢ２に入るため、列車３が閉塞区間ＡＢ１にいる時間が長くなったためである。
【００９９】
本処理例において、最適解導出時における目的関数値は"５０"となる。これは、全アクティビティ終了時刻"５０"であることを意味する。
【０１００】
本処理例において算出される各アクティビティの開始時刻及び終了時刻は次の通りである。
駅Ａ（ノードＩＤ１）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,1]）については開始時刻"１０"、終了時刻"２３"となり、列車２のアクティビティ（train[2,1]）については開始時刻"１０"、終了時刻"２０"となり、列車１のアクティビティ（train[1,1]）については開始時刻"０"、終了時刻"１０"となる。
【０１０１】
閉塞区間ＡＢ１（ノードＩＤ２）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,2]）については開始時刻"２３"、終了時刻"２６"となり、列車２のアクティビティ（train[2,2]）については開始時刻"２０"、終了時刻"２３"となり、列車１のアクティビティ（train[1,2]）については開始時刻"１０"、終了時刻"１３"となる。
【０１０２】
閉塞区間ＡＢ２（ノードＩＤ３）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,3]）については開始時刻"２６"、終了時刻"２８"となり、列車２のアクティビティ（train[2,3]）については開始時刻"２３"、終了時刻"２６"となり、列車１のアクティビティ（train[1,3]）については開始時刻"１３"、終了時刻"１６"となる。
【０１０３】
駅Ｂ（ノードＩＤ４）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,4]）については開始時刻"２８"、終了時刻"２９"となり、列車２のアクティビティ（train[2,4]）については開始時刻"２６"、終了時刻"３１"となり、列車１のアクティビティ（train[1,4]）については開始時刻"１６"、終了時刻"２１"となる。
【０１０４】
閉塞区間ＢＣ１（ノードＩＤ５）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,5]）については開始時刻"２９"、終了時刻"３１"となり、列車２のアクティビティ（train[2,5]）については開始時刻"３１"、終了時刻"３４"となり、列車１のアクティビティ（train[1,5]）については開始時刻"２１"、終了時刻"２４"となる。
【０１０５】
閉塞区間ＢＣ２（ノードＩＤ６）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,6]）については開始時刻"３１"、終了時刻"３３"となり、列車２のアクティビティ（train[2,6]）については開始時刻"３４"、終了時刻"３７"となり、列車１のアクティビティ（train[1,6]）については開始時刻"２４"、終了時刻"２７"となる。
【０１０６】
閉塞区間ＢＣ３（ノードＩＤ７）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,7]）については開始時刻"３３"、終了時刻"３５"となり、列車２のアクティビティ（train[2,7]）については開始時刻"３７"、終了時刻"４０"となり、列車１のアクティビティ（train[1,7]）については開始時刻"２７"、終了時刻"３０"となる。
【０１０７】
駅Ｃ（ノードＩＤ８）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,8]）については開始時刻"３５"、終了時刻"４５"となり、列車２のアクティビティ（train[2,8]）については開始時刻"４０"、終了時刻"５０"となり、列車１のアクティビティ（train[1,8]）については開始時刻"３０"、終了時刻"４０"となる。
【０１０８】
全アクティビティ終了時刻は上記目的関数値"５０"となる。
endtime = 50
【０１０９】
本処理例において算出される継続時間（durations[t,n]）は次の通りである。
durations[1,1] = 10
durations[1,2] = 3
durations[1,3] = 3
durations[1,4] = 5
durations[1,5] = 3
durations[1,6] = 3
durations[1,7] = 3
durations[1,8] = 10
durations[2,1] = 10
durations[2,2] = 3
durations[2,3] = 3
durations[2,4] = 5
durations[2,5] = 3
durations[2,6] = 3
durations[2,7] = 3
durations[2,8] = 10
durations[3,1] = 13
durations[3,2] = 3
durations[3,3] = 2
durations[3,4] = 1
durations[3,5] = 2
durations[3,6] = 2
durations[3,7] = 2
durations[3,8] = 10
【０１１０】
本処理例において算出されるアクティビティの終了時刻（train[t,n].end）は次の通りである。
train[1,1].end = 10
train[1,2].end = 13
train[1,3].end = 16
train[1,4].end = 21
train[1,5].end = 24
train[1,6].end = 27
train[1,7].end = 30
train[1,8].end = 40
train[2,1].end = 20
train[2,2].end = 23
train[2,3].end = 26
train[2,4].end = 31
train[2,5].end = 34
train[2,6].end = 37
train[2,7].end = 40
train[2,8].end = 50
train[3,1].end = 23
train[3,2].end = 26
train[3,3].end = 28
train[3,4].end = 29
train[3,5].end = 31
train[3,6].end = 33
train[3,7].end = 35
train[3,8].end = 45
【０１１１】
図８は、本処理例における結果表示画面の一構成を示す図である。出力制御部１０６は、図８に示すように、以上得られた各変数の値に基づいて、列車毎の夫々のリソースにおけるアクティビティを運行スケジュール上に配置した画面を表示パネルに表示させる。
【０１１２】
＜Ｘの値が２０の場合＞
駅Ａが列車２の後に列車３が出発し、列車３はどの列車も追い抜くことなく駅Ｃに到達する解が得られる。列車３のアクティビティの継続時間の中で最低所要時間よりも長いのは次の１つである。
durations[3,6] = 3（最低所要時間minDurations[3,6]=2）
これは、列車２が閉塞区間ＢＣ３を出るまで待ってから、列車３が閉塞区間ＢＣ３に入るため、列車３は閉塞区間ＢＣ２にいる時間が長くなったためである。
【０１１３】
本処理例において、最適解導出時における目的関数値は"５２"となる。これは、全アクティビティ終了時刻"５２"であることを意味する。
【０１１４】
本処理例において算出される各アクティビティの開始時刻及び終了時刻は次の通りである。
駅Ａ（ノードＩＤ１）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,1]）については開始時刻"２０"、終了時刻"３０"となり、列車２のアクティビティ（train[2,1]）については開始時刻"１０"、終了時刻"２０"となり、列車１のアクティビティ（train[1,1]）については開始時刻"０"、終了時刻"１０"となる。
【０１１５】
閉塞区間ＡＢ１（ノードＩＤ２）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,2]）については開始時刻"３０"、終了時刻"３２"となり、列車２のアクティビティ（train[2,2]）については開始時刻"２０"、終了時刻"２３"となり、列車１のアクティビティ（train[1,2]）については開始時刻"１０"、終了時刻"１３"となる。
【０１１６】
閉塞区間ＡＢ２（ノードＩＤ３）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,3]）については開始時刻"３２"、終了時刻"３４"となり、列車２のアクティビティ（train[2,3]）については開始時刻"２３"、終了時刻"２６"となり、列車１のアクティビティ（train[1,3]）については開始時刻"１３"、終了時刻"１６"となる。
【０１１７】
駅Ｂ（ノードＩＤ４）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,4]）については開始時刻"３４"、終了時刻"３５"となり、列車２のアクティビティ（train[2,4]）については開始時刻"２６"、終了時刻"３１"となり、列車１のアクティビティ（train[1,4]）については開始時刻"１６"、終了時刻"２１"となる。
【０１１８】
閉塞区間ＢＣ１（ノードＩＤ５）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,5]）については開始時刻"３５"、終了時刻"３７"となり、列車２のアクティビティ（train[2,5]）については開始時刻"３１"、終了時刻"３４"となり、列車１のアクティビティ（train[1,5]）については開始時刻"２１"、終了時刻"２４"となる。
【０１１９】
閉塞区間ＢＣ２（ノードＩＤ６）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,6]）については開始時刻"３７"、終了時刻"４０"となり、列車２のアクティビティ（train[2,6]）については開始時刻"３４"、終了時刻"３７"となり、列車１のアクティビティ（train[1,6]）については開始時刻"２４"、終了時刻"２７"となる。
【０１２０】
閉塞区間ＢＣ３（ノードＩＤ７）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,7]）については開始時刻"４０"、終了時刻"４２"となり、列車２のアクティビティ（train[2,7]）については開始時刻"３７"、終了時刻"４０"となり、列車１のアクティビティ（train[1,7]）については開始時刻"２７"、終了時刻"３０"となる。
【０１２１】
駅Ｃ（ノードＩＤ８）における列車１〜３のアクティビティの開始時刻及び終了時刻は、列車３のアクティビティ（train[3,8]）については開始時刻"４２"、終了時刻"５２"となり、列車２のアクティビティ（train[2,8]）については開始時刻"４０"、終了時刻"５０"となり、列車１のアクティビティ（train[1,8]）については開始時刻"３０"、終了時刻"４０"となる。
【０１２２】
全アクティビティ終了時刻は上記目的関数値"５２"となる。
endtime = 52
【０１２３】
本処理例において算出される継続時間（durations[t,n]）は次の通りである。
durations[1,1] = 10
durations[1,2] = 3
durations[1,3] = 3
durations[1,4] = 5
durations[1,5] = 3
durations[1,6] = 3
durations[1,7] = 3
durations[1,8] = 10
durations[2,1] = 10
durations[2,2] = 3
durations[2,3] = 3
durations[2,4] = 5
durations[2,5] = 3
durations[2,6] = 3
durations[2,7] = 3
durations[2,8] = 10
durations[3,1] = 10
durations[3,2] = 2
durations[3,3] = 2
durations[3,4] = 1
durations[3,5] = 2
durations[3,6] = 3
durations[3,7] = 2
durations[3,8] = 10
【０１２４】
本処理例において算出されるアクティビティの終了時刻（train[t,n].end）は次の通りである。
train[1,1].end = 10
train[1,2].end = 13
train[1,3].end = 16
train[1,4].end = 21
train[1,5].end = 24
train[1,6].end = 27
train[1,7].end = 30
train[1,8].end = 40
train[2,1].end = 20
train[2,2].end = 23
train[2,3].end = 26
train[2,4].end = 31
train[2,5].end = 34
train[2,6].end = 37
train[2,7].end = 40
train[2,8].end = 50
train[3,1].end = 30
train[3,2].end = 32
train[3,3].end = 34
train[3,4].end = 35
train[3,5].end = 37
train[3,6].end = 40
train[3,7].end = 42
train[3,8].end = 52
【０１２５】
図９は、本処理例における結果表示画面の一構成を示す図である。出力制御部１０６は、図９に示すように、以上得られた各変数の値に基づいて、列車毎の夫々のリソースにおけるアクティビティを運行スケジュール上に配置した画面を表示パネルに表示させる。
【０１２６】
尚、上記実施形態では、列車を例に挙げて説明したが、本発明は、バス、航空機、船舶等の人や貨物を輸送する全ての輸送手段の運行スケジュール調整に適用可能である。
【図面の簡単な説明】
【０１２７】
【図１】本発明の一実施形態に係る情報処理装置の機能構成を示すブロック図である。
【図２】本発明の一実施形態に係る情報処理装置のハードウェア構成を示す図である。
【図３】制約充足解演算方法の流れを示すフローチャートである。
【図４】最適解演算方法の流れを示すフローチャートである。
【図５】アクティビティの概念を具体的に説明するための図である。
【図６】スケジューリング問題の例題を説明するための図である。
【図７】一処理例における結果表示画面の一構成を示す図である。
【図８】一処理例における結果表示画面の一構成を示す図である。
【図９】一処理例における結果表示画面の一構成を示す図である。
【符号の説明】
【０１２８】
１０１：情報処理装置
１０２：入力情報記憶部
１０３：定義情報記憶部
１０４：制約条件記憶部
１０５：解探索処理部
１０６：出力制御部
１０７：制約条件導出部
【図１】
2005247058.tif 000003
【図２】
2005247058.tif 000004
【図３】
2005247058.tif 000005
【図４】
2005247058.tif 000006
【図５】
2005247058.tif 000007
【図６】
2005247058.tif 000008
【図７】
2005247058.tif 000009
【図８】
2005247058.tif 000010
【図９】
2005247058.tif 000011