(57)【要約】【課題】  当初の運行終了時刻を過ぎても運行しなければならない必然性をなくし、その結果、運行終了時において車庫に格納される台数が当初予定された台数に略一致する解を得ることを可能とする。【解決手段】  変数定義記憶部１０３において、運行再開時に正規のダイヤから各車両に割り当てられるダイヤを表す変数を当該車両毎に設定し、解探索処理部１０５は、設定された変数群を含む解空間の解探索処理を行い、解空間から所定の制約条件を充足する解を検出する。【選択図】  図１
2005219538.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）や、本情報処理装置１０１を稼働するために必要な情報などを記憶する。
【００２３】
データ入出力を行うユニット群（以下、単にＦＤＤという）２０４は、フレキシブルディスクやＣＤ−ＲＯＭなど、取り外し可能な外部記憶媒体のデータ入出力を行う。ネットワークインタフェース（以下、単にＮＥＴＩＦという）２０５は、後述するモデム２０６を介して外部ネットワークに接続し、または後述するＬＡＮ２０７に接続する。ＮＥＴＩＦ２０５は、ネットワークを介して本情報処理装置１０１からのデータ転送を行うための制御や接続状況の診断を行う。
【００２４】
モデム２０６は、外部ネットワークと本情報処理装置１０１とを電話回線を介して接続するための機器であって、モデムやＩＳＤＮ接続用のターミナルアダプタを含む。ＬＡＮ２０７は、イーサネット（Ｒ）などのネットワークシステムである。本実施形態に係る情報処理装置１０１は、モデム２０６又はＬＡＮ２０７上に接続されているルータやゲートウェイ等の通信機器を用いて外部ネットワークに接続し、外部装置とのデータの送受信を可能とする。
【００２５】
ビデオＲＡＭ（以下、ＶＲＡＭという）２０８は、後述するＣＲＴ２０９に表示する画像データを展開し、表示の制御を行う。ＣＲＴ２０９は、ディスプレイなどの表示装置である。このＣＲＴ２０９は、情報処理装置１０１の内部に含む構成としても良いし、或いはその外部に接続した構成としても良い。
【００２６】
キーボードコントローラ（ＫＢＣ）２１０は、キーボード（ＫＢ）２１１およびマウス２１２からの入力信号を制御する。ＫＢ２１１は、情報処理装置１０１の利用者が入力操作を行うためのキーボードである。マウス２１２は、情報処理装置１０１の利用者が入力操作を行うためのポインティングデバイスである。このキーボード２１１及びマウス２１２は夫々、情報処理装置１０１の内部に含む構成としても良いし、その外部に接続した構成としても良い。
【００２７】
ハードディスクドライブ（ＨＤＤ）２１３は、アプリケーションプログラムや各種データなどの保存に用いられる。アプリケーションプログラムとは、例えば図３及び図４に示す本実施形態に係る情報処理方法を本情報処理装置１０１に実行させるためのソフトウェアプログラムのことをいう。また、上記各種データには、図３及び図４に示す処理を情報処理装置１０１に実行させるためのデータを含み、当該データは、例えばＲＡＭ２０２において記憶されている。当該データの具体例としては、変数／定数の定義、制約条件及び探索ルール（図３では、ステップＳ３０３、Ｓ３０４に相当）を含み、コンピュータ（ＣＰＵ２０１）は当該データを読み込んで、制約条件を満たしながら探索ルールに従って各変数への値の割り当てを行うものである。尚、当該データに含まれる探索ルールは、値の割り当てを行う変数の順序と変数へ割り当てる値の順序を規定するものである。
【００２８】
上記ソフトウェアプログラムの起動により、変数定義記憶部１０３及び制約条件記憶部１０４に上述した変数の定義や制約条件の定義等のデータが記憶される。外部ネットワーク等のデータの伝送媒体、ＣＤ−ＲＯＭ等のデータの記録媒体等を介して情報処理装置１０１がアプリケーションプログラムやデータを得る構成も本発明の技術的思想の範疇に含まれる。
【００２９】
コントローラ（ＩＯＣ）２１４は、外部に接続されるプリンタ（ＰＲＴ）２１５やスキャナ１１６等に対する情報の入出力制御を行うことを可能とする。また本図には示していないが、ＩＯＣ２１４は、プリンタ２１５やスキャナ２１６以外に、例えば、同様に外部に接続されるＨＤＤやＭＯドライブ等と情報の入出力制御を行うことが可能である。
【００３０】
次に、定数、変数及び制約条件の定義内容について詳細に説明する。
−定数／変数の定義−
割り当て対象の車両数をｎｃとすると、割り当て対象の車両のＩＤの集合をＣ＝｛０，１，２，・・・，ｎｃ｝と定義する。
【００３１】
割り当て対象のダイヤ数をｎｄとすると、割り当て対象のダイヤの集合をＤ＝｛０，１，２，・・・，ｎｄ｝と定義する。
【００３２】
ダイヤ変数をｖｄ［ｃ］∈Ｄ∪｛０｝，ｃ∈Ｃ∪｛０｝と定義する。但し、ｖｄ［ｃ］が０であることは、車両ｃに何れのダイヤも割り当てられていないことを意味するものとする。
【００３３】
車両変数をｖｃ［ｄ］∈Ｃ∪｛０｝,ｄ∈Ｄ∪｛０｝と定義する。但し、ｖｃ［ｄ］の値が０であることは、ダイヤｄに何れの車両も割り当てられていないことを意味するものとする。
【００３４】
ダイヤ毎に、そのダイヤが車両に割り当てられているかどうかを表す変数ｖａ［ｄ］∈｛０，１｝,ｄ∈Ｄを導入する。
【００３５】
各ダイヤｄ毎に、復旧後運行開始時点における位置を表す実数値定数ｓｄ［ｄ］が与えられる。後述の制約条件８を課す場合には、ｓｄ［０］＝０も与えられているものとする。値は適当な値でよいので、ここでは０としておく。
【００３６】
各車両ｃ毎に、復旧後運行開始時点における位置を表す実数値定数（ｓｃ［ｃ］）が与えられる。
【００３７】
車庫の個数をｎｙとすると、車庫のＩＤの集合をＹ＝｛１，２，・・・，ｎｙ｝と定義する。
【００３８】
ダイヤｄ毎に、その日の運行終了時点における車庫を表す定数ｙ［ｄ］（ｙ［ｄ］∈Ｙ）が与えられる。
【００３９】
各車庫ｙ毎に、復旧後運行開始時点における車両数を表す定数ｎｓ［ｙ］（ｎｓ［ｙ］∈｛０，１，２，・・・｝）が与えられる。
【００４０】
各車庫ｙ毎に、正常ダイヤであった場合のその日の運行終了時点における車両数を表す定数ｎｅ［ｙ］（ｎｅ［ｙ］∈｛０，１，２，・・・｝）が与えられる。
【００４１】
各車庫のその日の運行終了時点における車両の数を表す変数ｖｎ［ｙ］∈｛０，１，２，・・・｝,ｙ∈Ｙを導入する。
【００４２】
割り当てることができない車両とダイヤの組の集合Ｘは、Ｘ＝｛＜ｃ，ｄ＞|ｃ∈Ｃ，ｄ∈Ｄ,車両ｃとダイヤｄは割り当てられない｝として与えられる。
【００４３】
各車庫ｙ毎に、格納許容量を表す定数ｎｍ［ｙ］が与えられる。
【００４４】
−制約条件の定義−
・固定値制約（制約条件１）
ダイヤ変数、車両変数のインデックスが０の場合は固定値でよいので、次の制約を課す。
ｖｄ［０］＝０
ｖｃ［０］＝０
【００４５】
・ダイヤ変数の排他制約（制約条件２）
複数の異なる車両に対して、同一のダイヤが割り当てられることを防ぐための制約条件２を次のように定義する。
∀ｃ１，ｃ２∈Ｃ（ｃ１≠ｃ２⇒（ｖｄ［ｃ１］≠ｖｄ［ｃ２］∨ｖｄ［ｃ１］＝ｖｄ［ｃ２］＝０））
つまり、互いに異なる任意の２つの車両の組に対して、それらに対応するダイヤ変数の値は互いに異なるか、または両方とも０となる。ここで、一方が０で他方が０でない場合は、互いに異なる場合に包含される。
【００４６】
・車両変数の排他制約（制約条件３）
複数の異なるダイヤに対して、同一の車両が割り当てられることを防ぐための制約条件３を次のように定義する。
∀ｄ１，ｄ２∈Ｄ（ｄ１≠ｄ２⇒（ｖｃ［ｄ１］≠ｖｃ［ｄ２］∨ｖｃ［ｄ１］＝ｖｃ［ｄ２］＝０））
つまり、互いに異なる任意の２つのダイヤの組に対して、それらに対応する車両変数の値は互いに異なるか、または両方とも０となる。ここで、一方が０で他方が０でない場合は、互いに異なる場合に包含される。
【００４７】
・ダイヤ変数と車両変数間の関係を表す制約（制約条件４）
ダイヤ変数ｖｄ［ｃ］と車両変数ｖｃ［ｄ］との関係を表す制約条件４を次のように定義する。
∀ｃ∈Ｃ（Ｖｃ［ｖｄ［ｃ］］＝ｃ∨ｖｄ［ｃ］＝０）
この制約により、求解（解探索）の過程において、ｖｄ［ｃ］に値を割り当てることによりｖｃ［ｄ］の値が自動的に求められる。
∀ｄ∈Ｄ（ｖｄ［ｖｃ［ｄ］］＝ｄ∨ｖｃ［ｄ］＝０）
この制約により、求解（解探索）の過程において、ｖｃ［ｄ］に値を割り当てることによりｖｄ［ｃ］の値が自動的に求められる。
【００４８】
・車両数変数の定義（制約条件５）
制約条件５を次のように定義する。
∀ｙ∈Ｙ（ｖｎ［ｙ］＝ｎｓ［ｙ］＋Σ（ｄ∈Ｄ,ｙ［ｄ］＝ｙ）ｖａ［ｄ］）
上記の定義は、車庫ｙのその日の運行終了時点における車両の数は、復旧後の運行開始時点における車庫yの車両の数に、その日の運行終了時点における車庫がyであるダイヤのうち車両に割り当てられているものの個数を加えたものに等しいことを意味している。
【００４９】
・車両数に関する制約（制約条件６）
制約条件６を次のように定義する。
∀ｙ∈Ｙ(ｖｎ［ｙ］＝ｎｅ［ｙ］)
このように定義することにより、全ての車庫において、その日の運行終了時点における車両数が正常ダイヤであった場合と一致するため、翌日の始発以降の車両の運用に支障がない。上記の制約は完全な一致を要求しているが、完全に一致しなくても翌日の始発以降の車両の運用に支障がない場合は、この等式ｖｎ［ｙ］＝ｎｅ［ｙ］を不等式に緩和してもよい。例えば、正常ダイヤであった場合の運行終了時点と比較して車両数が１少なくても翌日の運行に支障がない場合は、
ｎｅ［ｙ］−１≦ｖｎ［ｙ］≦ｎｍ［ｙ］
とすればよい。
【００５０】
また、上記は車両の種類が１種類の場合について記述した。もし、車両の種類が複数である場合は、上記と同様の制約を車両の種類ごとに分けて課せばよい。
【００５１】
・割り当てられないダイヤについての制約（制約条件７）
制約条件７を次のように定義する。
例えば、特急にしか利用できない車両は特急として振る舞い続ける等の車両の種類に関する制限や、車両の進行方向とダイヤの進行方向が異なるという制限のために、車両とダイヤの組み合わせに対する制限がある場合は、次のような制約を課す。
∀＜ｃ，ｄ＞∈Ｘ（ｖｄ［ｃ］≠ｄ）
上記の定義は、割り当てることができない車両とダイヤの任意の組に対して、各車両ＩＤに対応するダイヤ変数の値とダイヤＩＤとが一致しないことを意味している。
【００５２】
・車両の位置関係と割り当てられるダイヤの位置関係との整合性に関する制約（制約条件８）
車両の位置関係と割り当てられるダイヤの位置関係との整合性に関する制約条件８を次のように定義する。
∀ｃ１，ｃ２∈Ｃ（ｓｃ［ｃ１］＜ｓｃ［ｃ２］⇒ｓｄ［ｖｄ［ｃ１］］＜ｓｄ［ｖｄ［ｃ２］］）∨（ｓｃ［ｃ１］＞ｓｃ［ｃ２］⇒ｓｄ［ｖｄ［ｃ１］］＞ｓｄ［ｖｄ［ｃ２］］∨ｖｄ［ｃ１］＝０∨ｖｄ［ｃ２］＝０）
上記の定義は、互いに異なる任意の２つの車両の組に対して、それらに対応する復旧後運行開始時点における位置を表す定数の値の大小関係は、各ダイヤ変数の値に対応する復旧後運行開始時点における位置を表す定数の値の大小関係と一致しなければならないことを意味している。なお、制約条件８を課す場合には、変数ｖｄ［ｃ１］の値が０となることがあるため、定数ｓｄ［０］＝０を用意しておく必要がある。
【００５３】
・割り当て変数の定義（制約条件９）
割り当て変数ｖａ［ｄ］の定義に関する制約条件９を次のように定義する。
∀ｄ∈Ｄ（ｖａ［ｄ］＝１⇔ｖｃ［ｄ］＞０）
上記の定義において、ｖａ［ｄ］の値は、ダイヤｄが車両に割り当てられていない場合は０を、割り当てられている場合は１を値として持つ変数であることを意味している。
【００５４】
次に、本実施形態に係る情報処理装置１０１の動作を、図３のフローチャートに基づいて説明する。
先ず、解探索処理部１０５は、入力情報記憶部１０２、変数定義記憶部１０３及び制約条件記憶部１０４から夫々記憶された情報を読み込み（ステップＳ３０１）、各変数のドメインを初期化して解探索処理を開始する。解探索処理部１０５の解探索処理の対象となる解空間を図６に示す。図６に示される解空間は探索木とも称される。図６に示すように、本解探索処理においてはダイヤ変数ｖｄ［ｃ］を求解対象としている。図６中、各階層の丸で表現されたノードは値を割り当てようとする変数を表しており、それらに連なる枝がその変数のドメインの要素（当該変数に割り当て可能な値）を表している。なお、本探索木において、ｖｄ［２］のドメインを表す枝に７がない理由は、制約条件２を介してｖｄ［２］のドメインから７が取り除かれたためである。
【００５５】
続いて、解探索処理部１０５は、全変数の値が既に決定されているか否かを判断する（ステップＳ３０２）。解探索処理部１０５は、この判断において、全変数の値が未だ決定されていないと判断した場合、値が決定されていない変数のうちインデックスの値が最も小さい変数を選択する（ステップＳ３０３）。
【００５６】
続いて、解探索処理部１０５は、選択した変数のドメインに含まれる値のうち、｜ｓｃ［ｃ］−ｓｄ［ｄ］｜の値を最も小さくするｄを順次選択し、その値を当該変数に割り当てる（ステップＳ３０４）。これにより、復旧後運行開始時点における車両とダイヤの位置が近くなる値を変数ｖｄ［ｃ］に優先的に割り当てるような解探索が可能となる。次に、解探索処理部１０５は、当該変数に割り当てた値が制約条件１〜９のうちの何れかに矛盾する場合は、割り当てた値を当該ドメインから取り除く（ステップＳ３０５、Ｓ３０６）。その結果、当該ドメインが空集合となれば、解探索処理部１０５は、現在値を割り当てようとしている変数が探索木のルートに位置する変数であるかを判断し、ルートにある変数でなければ、バックトラックを行う（ステップＳ３０７、Ｓ３０８、Ｓ３１０）。尚、ここでいう「バックトラック」とは、値を割り当てる対象の変数を探索木上の一つルートに近い変数に戻すことである。また、ステップＳ３０５における矛盾発生の判定方法としては、当該変数に当該値を割り当て、制約伝播が行われた結果、何れかの変数のドメインが空集合となった場合に矛盾が生じたものと判定される。
【００５７】
一方、変数に割り当てた値が制約条件１〜９の何れにも矛盾しない場合は、割り当てた値を当該変数の値として決定する。また、ステップＳ３０６において一旦割り当てた値を当該ドメインから取り除いても当該ドメインに未だ値が残っている場合には、その値が除かれた状態で当該ドメインに含まれる値のうち最も小さい値が当該変数に割り当てられることになる。
【００５８】
尚、ステップＳ３０７においてドメインが空集合と判断された変数が探索木のルートに位置する変数であれば、"解なし（ステップＳ３０９）"として解探索処理を終了することになる。上述した処理を繰り返すことにより、各変数の値を割り当てていき、全ての変数の値が決定した時点で"制約充足解あり（ステップＳ３１１）"として処理を終了する。
【００５９】
上記のように、本実施形態では、問題を制約充足問題として定式化し、制約伝播技術を用いて各変数への値の割り当て方を決めているので、解探索の過程において制約違反を解消することができる。
【００６０】
次に、図５に示す正規のダイヤの一部を用いて、本実施形態に係る解探索処理の動作を具体的に説明する。図５は、ダイヤの一部を示した図である。
図５には、車両ＩＤが１〜６の車両（以下、夫々車両１〜６と略す）、ダイヤＩＤが１〜８のダイヤ（以下、夫々ダイヤ１〜８と略す）、事故発生時刻及び運行再開時刻等が示されている。尚、車両ＩＤ３の車両は急行列車、その他の車両ＩＤ１〜２、４〜６の車両は各駅停車の車両であり、ダイヤＩＤ３、８のダイヤは急行列車のダイヤ、その他のダイヤＩＤ１、２、４〜７のダイヤは各駅停車のダイヤである。
【００６１】
先ず、ユーザは、キーボード等の入力手段を用いて次の情報が本情報処理装置１０１に入力されたものとする。即ち、車両数ｎｃ、ダイヤ数ｎｄ、ダイヤｄの復旧後運行開始時点における位置を表す定数ｓｄ［ｄ］、車両ｃの復旧後運行開始時点における位置を表す定数ｓｃ［ｃ］、車庫数ｎｙ、ダイヤ毎に、その日の運行終了時点における車庫を表す定数ｙ［ｄ］、復旧後の運行開始時点における各車庫の車両の数を表す定数ｎｓ［ｙ］、正常ダイヤであった場合のその日の運行終了時点における各車庫の車両数を表す定数ｎｅ［ｙ］、及び、割り当てることができない車両とダイヤの組の集合Ｘが入力され、入力情報記憶部１０２に記憶される。
【００６２】
ここで、上記各入力情報の具体的な数値としては、
＜車両数＞
ｎｃ＝６
即ち、車両１〜６の６台の車両が割り当ての対象であることを示している。
【００６３】
＜ダイヤ数＞
ｎｄ＝８
即ち、ダイヤ１〜８の８つのダイヤが割り当ての対象であることを示している。
【００６４】
＜ダイヤｄの復旧後運行開始時点における位置を表す定数＞
ｓｄ［１］＝１．３、ｓｄ［２］＝２、ｓｄ［３］＝２．３、ｓｄ［４］＝３、ｓｄ［５］＝４．３、ｓｄ［６］＝５、ｓｄ［７］＝５．８、ｓｄ［８］＝６．８
即ち、運行開始時点において、ダイヤ１の位置は駅１と２駅間の３／１０の距離だけ駅１から通過した位置、ダイヤ２の位置は駅２、ダイヤ３の位置は駅２と駅３間の３／１０の距離だけ駅２から通過した位置、ダイヤ４の位置は駅３、ダイヤ５の位置は駅４と駅５間の３／１０の距離だけ駅４から通過した位置、ダイヤ６の位置は駅５、ダイヤ７の位置は駅５と駅６間の８／１０の距離だけ駅５から通過した位置、ダイヤ８の位置は駅６と駅７間の８／１０の距離だけ駅６から通過した位置である。
【００６５】
＜車両ｃの復旧後運行開始時点における位置を表す定数＞
ｓｃ［１］＝７、ｓｃ［２］＝６、ｓｃ［３］＝５、ｓｃ［４］＝４、ｓｃ［５］＝３、ｓｃ［６］＝１
即ち、復旧後運行開始時点において、車両１（各駅停車）は駅７まで移動したところに位置し、車両２（各駅停車）は駅６まで移動したところに位置し、車両３（急行）は駅５まで移動したところに位置し、車両４（各駅停車）は駅４に位置し、車両５（各駅停車）は駅３に位置し、車両６（各駅停車）は駅１に位置していることを示している。
【００６６】
＜車庫数＞
ｎｙ＝２
即ち、車両１〜６を格納する対象となる車庫数が２つであることを示している。
【００６７】
＜ダイヤ毎に、その日の運行終了時点における車庫を表す定数＞
ｙ［１］＝１、ｙ［２］＝１、ｙ［３］＝２、ｙ［４］＝２、ｙ［５］＝１、ｙ［６］＝１、ｙ［７］＝２、ｙ［８］＝２
即ち、その日、ダイヤ１で運行される車両は車庫１に格納され、ダイヤ２で運行される車両は車庫１に格納され、ダイヤ３で運行される車両は車庫２に格納され、ダイヤ４で運行される車両は車庫２に格納され、ダイヤ５で運行される車両は車庫１に格納され、ダイヤ６で運行される車両は車庫１に格納され、ダイヤ７で運行される車両は車庫２に格納され、ダイヤ８で運行される車両は車庫２に格納されることを示している。
【００６８】
＜復旧後の運行開始時点における各車庫の車両の数を表す定数＞
ｎｃ［１］＝３、ｎｃ［２］＝２
即ち、復旧後運行開始時点において、車庫１には３台の車両が既に格納されており、車庫２には２台の車両が既に格納されていることを示している。
【００６９】
＜正常ダイヤであった場合のその日の運行終了時点における各車庫の車両数を表す定数＞
ｎｅ［１］＝５、ｎｅ［２］＝６
即ち、正常ダイヤであった場合には、その日の運行終了時点において車庫１には５台の車両が格納される予定にあり、車庫２には６台の車両が格納される予定にあったことを示している。
【００７０】
＜割り当てることができない車両とダイヤの組の集合＞
Ｘ＝｛＜１，３＞，＜１，８＞，＜２，３＞，＜２，８＞，＜４，３＞，＜４，８＞，＜５，３＞，＜５，８＞，＜６，３＞，＜６，３＞｝
【００７１】
−制約充足解−
以上の情報が本情報処理装置１０１に入力され、情報処理装置１０１が解探索処理を起動すると、図３に示す処理が開始され、制約条件１〜９の全てを充足する制約充足解が算出される。この解探索処理において得られる解を次に示す。本実施形態において求解対象となる変数はダイヤ変数ｖｄ［ｃ］のみであるので、次の制約充足解が得られる。
・ｖｄ［０］＝０、ｖｄ［１］＝７、ｖｄ［２］＝４、ｖｄ［３］＝３、ｖｄ［４］＝２、ｖｄ［５］＝１、ｖｄ［６］＝０
即ち、車両１にはダイヤ７が割り当てられ、復旧後、車両１はダイヤ７で運行を再開し、車両２にはダイヤ４が割り当てられ、復旧後、車両２はダイヤ４で運行を再開し、車両３にはダイヤ３が割り当てられ、復旧後、車両３はダイヤ３で運行を再開し、車両４にはダイヤ２が割り当てられ、復旧後、車両４はダイヤ２で運行を再開し、車両５にはダイヤ１が割り当てられ、復旧後、車両５はダイヤ１で運行を再開し、車両６には何れのダイヤも割り当てられず、運休となることを示している。
【００７２】
ダイヤ変数ｖｄ［ｃ］が求められたことに伴って、制約条件４から車両変数ｖｃ［ｄ］も自動的に求められる。即ち、
・ｖｃ［０］＝０、ｖｃ［１］＝５、ｖｃ［２］＝４、ｖｃ［３］＝３、ｖｃ［４］＝２、ｖｃ［５］＝０、ｖｃ［６］＝０、ｖｃ［７］＝１、ｖｃ［８］＝０
即ち、ダイヤ１には車両５が割り当てられ、ダイヤ２には車両４が割り当てられ、ダイヤ３には車両３が割り当てられ、ダイヤ４には車両２が割り当てられ、ダイヤ５、６、８には何れの車両も割り当てられず、ダイヤ７には車両１が割り当てられることを示している。
【００７３】
また、車両が割り当てられていないダイヤは、ダイヤ５、６、８であるので、変数ｖａ［ｄ］に関する定義から、ダイヤ毎に、そのダイヤが車両に割り当てられているかどうかを表す変数ｖａ［ｄ］の値が次のように決定される。
・ｖａ［１］＝１、ｖａ［２］＝１、ｖａ［３］＝１、ｖａ［４］＝１、ｖａ［５］＝０、ｖａ［６］＝０、ｖａ［７］＝１、ｖａ［８］＝０
【００７４】
さらに、ダイヤ毎に、その日の運行終了時点における車庫を表す定数ｙ［ｄ］、及び、復旧後の運行開始時点における各車庫の車両の数を表す定数ｎｓ［ｙ］から、各車庫のその日の運行終了時点における車両の数を表す変数ｖｎ［ｙ］の値が次のように決定される。
・ｖｎ［１］＝５、ｖｎ［２］＝５
即ち、上記の車両とダイヤの割り当ての結果、車庫１、車庫２には双方とも５台の車両が格納されることとなる。以上のように算出された解は、出力制御部１０６の制御により表示パネル上に表示され、ユーザが参照することが可能となる。
【００７５】
本実施形態では、上記車庫の車両数に関する制約条件６（制約条件６が等式と不等式のうち不等式の方である場合）を設けているため、各車庫において許容される車両数に収める解を算出することができ、次の日等に必要となる回送数を抑えることが可能となる。
【００７６】
＜第２の実施形態＞
次に、本発明の第２の実施形態について説明する。尚、本実施形態に適用される機能構成及びハードウェア構成は図１及び図２に示す構成と同様であるため、説明を省略する。本実施形態に係る情報処理装置１０１の処理フローは、図３及び図４を比較すれば明らかなように、ステップＳ４０４が第１の実施形態と異なり、ステップＳ４０３において選択された変数のドメインに含まれる値のうち、大きいものから変数に割り当てるように構成してもよい。
【００７７】
＜第３の実施形態＞
次に、本発明の第３の実施形態について説明する。本実施形態では、例えば、後日必要となる回送の数が少ない変数への値の割り当て方から先に試すような解探索を行う。
【００７８】
本実施形態でも、車両１〜６を割り当ての対象とすると、図３のステップＳ３０４、図４のステップＳ４０４の代わりに、全てのダイヤ１〜８に対応するｖａ［ｄ］の値を合計し（ｖａ［１］＋ｖａ［２］＋・・・＋ｖａ［８］）、その合計値がｎｄ（ここでは、８）に近いダイヤｄの値から優先してｖｄ［ｃ］に順次割り当てるように構成すればよい。即ち、本実施形態では、常にΣ（ｄ∈Ｄ）ｖａ［ｄ］と等しい値を持つように制約条件を課された変数ｖｔａを導入し、解探索時には変数ｖｔａへの値の割り当てを変数ｖｄ［ｃ］（ｃ∈Ｃ）よりも先に行う。ここで、変数ｖｔａに割り当てる値はｎｄ、ｎｄ−１、・・・、１とする。
尚、本実施形態に適用される機能構成及びハードウェア構成は図１及び図２に示す構成と同様であるため、説明を省略する。
【００７９】
上記実施形態では、鉄道車両を例に挙げて説明したが、本発明は、バス、航空機、船舶等の人や貨物を輸送する全ての輸送手段のダイヤ調整に適用可能である。
【図面の簡単な説明】
【００８０】
【図１】本発明の第１〜第３の実施形態に係る情報処理装置の機能構成を示すブロック図である。
【図２】本発明の第１〜第３の実施形態に係る情報処理装置のハードウェア構成を示すブロック図である。
【図３】本発明の第１の実施形態に係る情報処理装置の動作の流れを示すフローチャートである。
【図４】本発明の第２の実施形態に係る情報処理装置の動作の流れを示すフローチャートである。
【図５】正規のダイヤの一部を示す図である。
【図６】解探索処理の対象となる解空間を模式的に示した図である。
【符号の説明】
【００８１】
１０１  情報処理装置
１０２  入力情報記憶部
１０３  変数定義記憶部
１０４  制約条件記憶部
１０５  解探索処理部
１０６  出力制御部
【図１】
2005219538.tif 000003
【図２】
2005219538.tif 000004
【図３】
2005219538.tif 000005
【図４】
2005219538.tif 000006
【図５】
2005219538.tif 000007
【図６】
2005219538.tif 000008