(57)【要約】【課題】汎用性と性能面のスケーラビリティを両立可能な、実用性を重視した構内作業計画を提供する。【解決手段】本発明の方法は、各編成の作業計画に必要な基本情報と、作業工程の開始もしくは終了を示すノードをアークにより実行順序に従って結んだ複数の業務テンプレートと、作業工程において使用可能なリソース候補の集合を定義するリソース定義データと、を準備し、各前記編成について業務テンプレートの候補の選択、各作業工程へのリソースの割り当て、各ノードの上限時刻および下限時刻の決定を、全体ペナルティ値が低くなるように行う。全体ペナルティ値は、各前記編成に対する割り当てが行われた各リソースついて所定の時間間隔ごとの使用量のうち許容量を超えている量を集計したペナルティ値から計算される。構内作業計画を表す構内作業ネットワークに対し、選択された各前記業務テンプレートを統合可能であるかを順次検査し、統合可能な場合は統合する。【選択図】図１
2008007032.tif 000002
【特許請求の範囲】
【請求項１】
車両の編成が車両基地に入区してから作業を終えて出区するまでの前記車両の編成の構内作業計画を作成する構内作業計画作成システムであって、
各前記編成の作業計画に必要な基本情報を記憶する基本情報記憶手段と、
作業工程の開始もしくは終了を示すノードを、最小所要時間、最大所要時間またはこれらの両方で重み付けされたアークにより実行順序に従って結んだネットワークを表す業務テンプレートを複数記憶する業務テンプレート記憶手段と、
前記業務テンプレートごとに前記業務テンプレートにおける各作業工程において使用可能なリソース候補の集合を定義するリソース定義データを記憶するリソース定義データ記憶手段と、
業務テンプレートにおける各ノードの上限時刻および下限時刻を計算するネットワーク時刻計算手段と、
各前記編成について使用する業務テンプレートの候補を選択し、選択された各前記業務テンプレートにおける各作業工程にリソースを仮に割り当て、各前記編成の基本情報から前記ネットワーク時刻計算手段を用いて前記業務テンプレートにおける各ノードの時刻を仮決めする、業務テンプレート候補集合初期化手段と、
各前記編成から編成を選択し、選択した編成について、前記業務テンプレートの候補の変更、前記業務テンプレートにおける前記作業工程に仮に割り当てるリソースの変更、および、前記業務テンプレートにおける各ノードの仮決定された時刻の変更、の少なくともいずれかの変更を行う業務テンプレート候補集合変更手段と、
各前記編成に対する割り当てが行われた各リソースのそれぞれについて所定の時間間隔ごとの使用量を計算し使用量のうち許容量を超えている量を集計したペナルティ値を計算し、各前記リソースのペナルティ値に基づき全体ペナルティ値を計算するペナルティ演算手段と、
構内作業計画を表す構内作業ネットワークに対し、前記各編成の指定された業務テンプレートを統合可能であるか否かを順次検査し、統合可能な場合は前記業務テンプレートを前記構内作業ネットワークに統合し、前記業務テンプレートを統合するごとに前記ネットワーク時刻計算手段を用いて前記構内作業ネットワークにおける各ノードの上限時刻および下限時刻を更新する、ネットワーク逐次更新手段とを備え、
前記業務テンプレート候補集合変更手段および前記ペナルティ演算手段により、各前記編成で選択する業務テンプレートの候補の集合の一部をペナルティ値が次第に小さくなるように取捨選択する演算を反復し、取捨選択された前記業務テンプレート候補の集合を前記ネットワーク逐次更新手段により前記構内作業ネットワークに逐次統合することで構内作業計画を作成することを特徴とする、
構内作業計画作成システム。
【請求項２】
前記業務テンプレート候補初期化手段および業務テンプレート候補変更手段において業務テンプレートの各ノードの時刻を仮に決定する手段を有し、
前記業務テンプレートにおいて時刻指定対象ノードが複数指定されており、各時刻指定対象ノードには優先順位が設定されており、
優先度の高い時刻指定対象ノードから順に、上限時刻と下限時刻との間の値を当該ノードの時刻として仮に決定し当該ノードの上限時刻と下限時刻とを共に前記仮に決定された値に置換し、前記ネットワーク時刻計算手段を用いて前記ノード以外の各ノードの上限時刻と下限時刻を更新する処理を、全ての前記時刻指定対象ノードの時刻を仮に決定する処理が終わるまで反復することを特徴とする、請求項１に記載の構内作業計画作成システム。
【請求項３】
前記ネットワーク逐次更新手段において統合に失敗した編成の識別子を記憶する記憶手段をさらに備え、
結合に失敗した編成は、当該編成で統合に失敗した以外に他に利用可能な業務テンプレートを順次選択し構内作業ネットワークに統合を試行することを特徴とする、請求項１に記載の構内作業計画作成システム。
【請求項４】
車両の編成が車両基地に入区してから作業を終えて出区するまでの前記車両の編成の構内作業計画を作成する構内作業計画作成方法であって、
各前記編成の作業計画に必要な基本情報を基本情報記憶手段に記憶し、
作業工程の開始もしくは終了を示すノードを、最小所要時間、最大所要時間またはこれらの両方で重み付けされたアークにより実行順序に従って結んだネットワークを表す業務テンプレートを複数、業務テンプレート記憶手段に記憶し、
前記業務テンプレートごとに前記業務テンプレートにおける各作業工程において使用可能なリソース候補の集合を定義するリソース定義データをリソース定義データ記憶手段に記憶し、
業務テンプレートにおける各ノードの上限時刻および下限時刻をネットワーク時刻計算手段にて計算し、
業務テンプレート候補集合変更手段にて、各前記編成について使用する業務テンプレートの候補を選択し、選択された各前記業務テンプレートにおける各作業工程にリソースを仮に割り当て、各前記編成の基本情報から前記ネットワーク時刻計算手段を用いて前記業務テンプレートにおける各ノードの時刻を仮決めし、
各前記編成から編成を選択し、選択した編成について、前記業務テンプレートの候補の変更、前記業務テンプレートにおける前記作業工程に仮に割り当てるリソースの変更、および、前記業務テンプレートにおける各ノードの仮決定された時刻の変更、の少なくともいずれかを変更し、
ペナルティ演算手段にて、各前記編成に対する割り当てが行われた各リソースのそれぞれについて所定の時間間隔ごとの使用量を計算し使用量のうち許容量を超えている量を集計したペナルティ値を計算し、各前記リソースのペナルティ値に基づき全体ペナルティ値を計算し、
構内作業計画を表す構内作業ネットワークに対し、前記各編成の指定された業務テンプレートを統合可能であるか否かをネットワーク逐次更新手段にて順次検査し、統合可能な場合は前記業務テンプレートを前記構内作業ネットワークに統合し、前記業務テンプレートを統合するごとに前記ネットワーク時刻計算手段を用いて前記構内作業ネットワークにおける各ノードの上限時刻および下限時刻を更新し、
前記業務テンプレート候補集合変更手段および前記ペナルティ演算手段により、各前記編成で選択する業務テンプレートの候補の集合の一部をペナルティ値が次第に小さくなるように取捨選択する演算を反復し、取捨選択された前記業務テンプレート候補の集合を前記ネットワーク逐次更新手段により前記構内作業ネットワークに逐次統合することで構内作業計画を作成することを特徴とする、
構内作業計画作成方法。
【請求項５】
車両の編成が車両基地に入区してから作業を終えて出区するまでの前記車両の編成の構内作業計画を作成する構内作業計画プログラムであって、
各前記編成の作業計画に必要な基本情報を基本情報記憶手段に記憶するステップと、
作業工程の開始もしくは終了を示すノードを、最小所要時間、最大所要時間またはこれらの両方で重み付けされたアークにより実行順序に従って結んだネットワークを表す業務テンプレートを複数、業務テンプレート記憶手段に記憶するステップと、
前記業務テンプレートごとに前記業務テンプレートにおける各作業工程において使用可能なリソース候補の集合を定義するリソース定義データをリソース定義データ記憶手段に記憶するステップと、
業務テンプレートにおける各ノードの上限時刻および下限時刻をネットワーク時刻計算手段にて計算するステップと、
業務テンプレート候補集合変更手段にて、各前記編成について使用する業務テンプレートの候補を選択し、選択された各前記業務テンプレートにおける各作業工程にリソースを仮に割り当て、各前記編成の基本情報から前記ネットワーク時刻計算手段を用いて前記業務テンプレートにおける各ノードの時刻を仮決めするステップと、
各前記編成から編成を選択し、選択した編成について、前記業務テンプレートの候補の変更、前記業務テンプレートにおける前記作業工程に仮に割り当てるリソースの変更、および、前記業務テンプレートにおける各ノードの仮決定された時刻の変更、の少なくともいずれかを変更するステップと、
ペナルティ演算手段にて、各前記編成に対する割り当てが行われた各リソースのそれぞれについて所定の時間間隔ごとの使用量を計算し使用量のうち許容量を超えている量を集計したペナルティ値を計算し、各前記リソースのペナルティ値に基づき全体ペナルティ値を計算するステップと、
構内作業計画を表す構内作業ネットワークに対し、前記各編成の指定された業務テンプレートを統合可能であるか否かをネットワーク逐次更新手段にて順次検査し、統合可能な場合は前記業務テンプレートを前記構内作業ネットワークに統合し、前記業務テンプレートを統合するごとに前記ネットワーク時刻計算手段を用いて前記構内作業ネットワークにおける各ノードの上限時刻および下限時刻を更新するステップと、
前記業務テンプレート候補集合変更手段および前記ペナルティ演算手段により、各前記編成で選択する業務テンプレートの候補の集合の一部をペナルティ値が次第に小さくなるように取捨選択する演算を反復し、取捨選択された前記業務テンプレート候補の集合を前記ネットワーク逐次更新手段により前記構内作業ネットワークに逐次統合することで構内作業計画を作成するステップと、をコンピュータに実行させるための構内作業計画作成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鉄道の車両基地における列車（車両の編成）の整備作業計画、および駅構内における列車の入換計画の作成を計算機で支援する構内作業計画システム、方法およびプログラムに関する。
【背景技術】
【０００２】
車両基地の構内作業では、入区してくる車両を編成単位で検査番線・清掃番線・留置番線などに引き込み、それぞれの制約条件に従って作業を実施した後、出区させる。なお、編成とは、まとまって移動する（互いに連結された）複数の車両を指す。この構内作業計画は一般的な最適化手法の適用が極めて困難なタイプの問題な上、車両基地毎や車両編成の種類、運転士の作業形態毎に異なる独自の特殊制約への対応が難しく、現時点ではベテランの担当者が試行錯誤を繰り返しながら立案している。
【０００３】
従来方式として、下記特許文献のような方式が提案されている。
【０００４】
特開２０００−１９０８４９公報の方式は、入区から出区までの典型的な入換・作業の工程を「入区→  留置→  作業→  留置→  出区」に限定し、予め決められた編成の順番に従い、作業の使用番線を決定してから留置番線や時刻を決定することを反復する。
【０００５】
特開２０００−１７７５９０公報の方式は、駅構内の入換計画作成に問題を限定し、計画をＰＥＲＴというネットワーク形式のデータとして表現する。具体的には、各編成毎に各線路への到着ないし各線路からの発車を表すノードを、所要時間で重み付けしたアークにより実行順序に従って結んだネットワークを作成する。そして、リソース（番線）を競合する作業工程の競合順序に相当するアークの結合関係を逐次的に変更しては評価することを反復し探索を行うことで全ての制約を満たす計画を作成する。
【０００６】
特開２００５−１７８７４２公報の方式は、作業工程を「入換シーケンス」と呼ぶ形式で表現した後に制約プログラミングで処理できる形に数理モデルとして定式化し、計画の暫定解を作成する。制約を満足する解が見つからない場合は、入換シーケンスの一部を自動的に変更し、再び暫定解を発見することを反復する。
【特許文献１】特開２０００−１７７５９０公報
【特許文献２】特開２００５−１７８７４２公報
【特許文献３】特開２０００−１９０８４９公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来に提案されている構内作業計画の自動提案方式は、方式の汎用性と性能面のスケーラビリティを両立することが難しい。
【０００８】
例えば、特開２０００−１９０８４９公報の方式は、実際の車両基地では、上記の典型的な入換・作業の工程だけ利用される訳ではなく、複数の留置番線をまたがって迂回しながら待機を行ったり、留置した番線でそのまま作業を実施したりと、状況に応じて様々な手順を使い分ける必要があるが、本方式では対応が難しいことが予想され、汎用性に欠ける。
【０００９】
また、この特開２０００−１７７５９０公報の方式は、アークの結合関係の変更の仕方は駅構内で利用されるもの（引上線変更、２段入換、引上線使用順序変更、進路ポイント使用順序変更）に限定されており、駅構内の特定の作業工程を対象とした探索方式となっており、やはり汎用性に欠ける。
【００１０】
一方、特開２００５−１７８７４２公報の方式では、制約プログラミングの基本的な解法では、編成の数が多く相互の干渉が増える（混雑する）状況になると、それぞれの数理モデルを解くのにかなりの演算時間を要することが予想されるが、実際の車両基地では、作業工程（入換シーケンス）の組み合わせで作業計画の成否が決定することも多い。編成の数が多く混雑するような車両基地が対象の場合、作業工程（入換シーケンス）の組み合わせまで含めて最適化するまでには相当の演算時間を要することが予想され、性能面のスケーラビリティに欠ける。
【００１１】
本発明は、汎用性と性能面のスケーラビリティを両立可能な、実用性を重視した構内作業計画の自動提案を行う構内作業計画システム、方法およびプログラムを提供する。
【課題を解決するための手段】
【００１２】
本発明の一態様としての構内作業計画作成システムは、車両の編成が車両基地に入区してから作業を終えて出区するまでの前記車両の編成の構内作業計画を作成する構内作業計画作成システムであって、
各前記編成の作業計画に必要な基本情報を記憶する基本情報記憶手段と、
作業工程の開始もしくは終了を示すノードを、最小所要時間、最大所要時間またはこれらの両方で重み付けされたアークにより実行順序に従って結んだネットワークを表す業務テンプレートを複数記憶する業務テンプレート記憶手段と、
前記業務テンプレートごとに前記業務テンプレートにおける各作業工程において使用可能なリソース候補の集合を定義するリソース定義データを記憶するリソース定義データ記憶手段と、
業務テンプレートにおける各ノードの上限時刻および下限時刻を計算するネットワーク時刻計算手段と、
各前記編成について使用する業務テンプレートの候補を選択し、選択された各前記業務テンプレートにおける各作業工程にリソースを仮に割り当て、各前記編成の基本情報から前記ネットワーク時刻計算手段を用いて前記業務テンプレートにおける各ノードの時刻を仮決めする、業務テンプレート候補集合初期化手段と、
各前記編成から編成を選択し、選択した編成について、前記業務テンプレートの候補の変更、前記業務テンプレートにおける前記作業工程に仮に割り当てるリソースの変更、および、前記業務テンプレートにおける各ノードの仮決定された時刻の変更、の少なくともいずれかの変更を行う業務テンプレート候補集合変更手段と、
各前記編成に対する割り当てが行われた各リソースのそれぞれについて所定の時間間隔ごとの使用量を計算し使用量のうち許容量を超えている量を集計したペナルティ値を計算し、各前記リソースのペナルティ値に基づき全体ペナルティ値を計算するペナルティ演算手段と、
構内作業計画を表す構内作業ネットワークに対し、前記各編成の指定された業務テンプレートを統合可能であるか否かを順次検査し、統合可能な場合は前記業務テンプレートを前記構内作業ネットワークに統合し、前記業務テンプレートを統合するごとに前記ネットワーク時刻計算手段を用いて前記構内作業ネットワークにおける各ノードの上限時刻および下限時刻を更新する、ネットワーク逐次更新手段とを備え、
前記業務テンプレート候補集合変更手段および前記ペナルティ演算手段により、各前記編成で選択する業務テンプレートの候補の集合の一部をペナルティ値が次第に小さくなるように取捨選択する演算を反復し、取捨選択された前記業務テンプレート候補の集合を前記ネットワーク逐次更新手段により前記構内作業ネットワークに逐次統合することで構内作業計画を作成する。
【００１３】
本発明の一態様としての構内作業計画作成方法は、車両の編成が車両基地に入区してから作業を終えて出区するまでの前記車両の編成の構内作業計画を作成する構内作業計画作成方法であって、
各前記編成の作業計画に必要な基本情報を基本情報記憶手段に記憶し、
作業工程の開始もしくは終了を示すノードを、最小所要時間、最大所要時間またはこれらの両方で重み付けされたアークにより実行順序に従って結んだネットワークを表す業務テンプレートを複数、業務テンプレート記憶手段に記憶し、
前記業務テンプレートごとに前記業務テンプレートにおける各作業工程において使用可能なリソース候補の集合を定義するリソース定義データをリソース定義データ記憶手段に記憶し、
業務テンプレートにおける各ノードの上限時刻および下限時刻をネットワーク時刻計算手段にて計算し、
業務テンプレート候補集合変更手段にて、各前記編成について使用する業務テンプレートの候補を選択し、選択された各前記業務テンプレートにおける各作業工程にリソースを仮に割り当て、各前記編成の基本情報から前記ネットワーク時刻計算手段を用いて前記業務テンプレートにおける各ノードの時刻を仮決めし、
各前記編成から編成を選択し、選択した編成について、前記業務テンプレートの候補の変更、前記業務テンプレートにおける前記作業工程に仮に割り当てるリソースの変更、および、前記業務テンプレートにおける各ノードの仮決定された時刻の変更、の少なくともいずれかを変更し、
ペナルティ演算手段にて、各前記編成に対する割り当てが行われた各リソースのそれぞれについて所定の時間間隔ごとの使用量を計算し使用量のうち許容量を超えている量を集計したペナルティ値を計算し、各前記リソースのペナルティ値に基づき全体ペナルティ値を計算し、
構内作業計画を表す構内作業ネットワークに対し、前記各編成の指定された業務テンプレートを統合可能であるか否かをネットワーク逐次更新手段にて順次検査し、統合可能な場合は前記業務テンプレートを前記構内作業ネットワークに統合し、前記業務テンプレートを統合するごとに前記ネットワーク時刻計算手段を用いて前記構内作業ネットワークにおける各ノードの上限時刻および下限時刻を更新し、
前記業務テンプレート候補集合変更手段および前記ペナルティ演算手段により、各前記編成で選択する業務テンプレートの候補の集合の一部をペナルティ値が次第に小さくなるように取捨選択する演算を反復し、取捨選択された前記業務テンプレート候補の集合を前記ネットワーク逐次更新手段により前記構内作業ネットワークに逐次統合することで構内作業計画を作成する。
【００１４】
本発明の一態様としての構内作業計画作成プログラムは、車両の編成が車両基地に入区してから作業を終えて出区するまでの前記車両の編成の構内作業計画を作成する構内作業計画プログラムであって、
各前記編成の作業計画に必要な基本情報を基本情報記憶手段に記憶するステップと、
作業工程の開始もしくは終了を示すノードを、最小所要時間、最大所要時間またはこれらの両方で重み付けされたアークにより実行順序に従って結んだネットワークを表す業務テンプレートを複数、業務テンプレート記憶手段に記憶するステップと、
前記業務テンプレートごとに前記業務テンプレートにおける各作業工程において使用可能なリソース候補の集合を定義するリソース定義データをリソース定義データ記憶手段に記憶するステップと、
業務テンプレートにおける各ノードの上限時刻および下限時刻をネットワーク時刻計算手段にて計算するステップと、
業務テンプレート候補集合変更手段にて、各前記編成について使用する業務テンプレートの候補を選択し、選択された各前記業務テンプレートにおける各作業工程にリソースを仮に割り当て、各前記編成の基本情報から前記ネットワーク時刻計算手段を用いて前記業務テンプレートにおける各ノードの時刻を仮決めするステップと、
各前記編成から編成を選択し、選択した編成について、前記業務テンプレートの候補の変更、前記業務テンプレートにおける前記作業工程に仮に割り当てるリソースの変更、および、前記業務テンプレートにおける各ノードの仮決定された時刻の変更、の少なくともいずれかを変更するステップと、
ペナルティ演算手段にて、各前記編成に対する割り当てが行われた各リソースのそれぞれについて所定の時間間隔ごとの使用量を計算し使用量のうち許容量を超えている量を集計したペナルティ値を計算し、各前記リソースのペナルティ値に基づき全体ペナルティ値を計算するステップと、
構内作業計画を表す構内作業ネットワークに対し、前記各編成の指定された業務テンプレートを統合可能であるか否かをネットワーク逐次更新手段にて順次検査し、統合可能な場合は前記業務テンプレートを前記構内作業ネットワークに統合し、前記業務テンプレートを統合するごとに前記ネットワーク時刻計算手段を用いて前記構内作業ネットワークにおける各ノードの上限時刻および下限時刻を更新するステップと、
前記業務テンプレート候補集合変更手段および前記ペナルティ演算手段により、各前記編成で選択する業務テンプレートの候補の集合の一部をペナルティ値が次第に小さくなるように取捨選択する演算を反復し、取捨選択された前記業務テンプレート候補の集合を前記ネットワーク逐次更新手段により前記構内作業ネットワークに逐次統合することで構内作業計画を作成するステップと、をコンピュータに実行させる。
【発明の効果】
【００１５】
本発明により、汎用性と性能面のスケーラビリティを両立可能な、実用性を重視した構内作業計画の自動提案を行うことができる。
【発明を実施するための最良の形態】
【００１６】
（実施形態１）
本実施形態では、列車（車両の編成）の選択し得る作業工程と作業工程の際に守らなければならない時間的制約の候補とを表す業務テンプレートを列車ごとに単数または複数用意し、構内作業計画を作成する際には各列車について決定した業務テンプレートを一つの計画に統合する。各々の車両基地に依存する部分は業務テンプレートの変更のみで対応できるようにし、汎用性を実現する。以下、図面を参照しながら、本実施形態について説明する。
【００１７】
図１は、本発明による構内作業計画システムの一実施形態の構成を示す図である。
【００１８】
システム全体は、業務テンプレート入力・表示手段１、スケジュール表示手段２、データ記憶手段３、ネットワーク逐次更新手段４、業務テンプレート選択手段５から構成される。各手段による機能はプログラムをコンピュータに実行させることによって実現してもよいし、ハードウェア的に実現してもよい。
【００１９】
業務テンプレート入力・表示手段１は、ユーザが業務テンプレートを登録したり、各種指示を入力したりするためのインターフェースである。
【００２０】
データ記憶手段３は必要なデータを格納するためのデータベースであり、業務テンプレート候補データ記憶手段（業務テンプレートデータベース）３０、リソース定義データ記憶手段（リソース定義データベース）３１、編成情報・基本ダイヤ記憶手段（基本情報記憶手段あるいは基本情報データベース）３２、スケジュール記憶手段３３を有する。業務テンプレート候補データ記憶手段３０は複数の業務テンプレートを格納する。リソース定義データ記憶手段３１はリソース定義データを格納する。編成情報・基本ダイヤ記憶手段３２は、車両基地や駅への入区・出区が決まっている各編成について構内作業計画に必要な基本情報（編成ＩＤ、編成種別、入区・出区予定時刻、利用可能な業務テンプレートおよびリソース定義データの指定情報）を格納する。スケジュール記憶手段３３は、ネットワーク逐次更新手段４によって作成された構内作業計画（スケジュールあるいは構内作業ネットワーク）を格納する。
【００２１】
ネットワーク逐次更新手段４は、作業工程ペアノード挿入手段４０、ネットワーク時刻計算手段４１、ネットワーク一時記憶手段４２を有する。ネットワーク逐次更新手段４は、編成情報・基本ダイヤ記憶手段３２内の各編成についての作業計画を決定し、各編成についての作業計画を統合した構内作業計画（スケジュールあるいは構内作業ネットワーク）を作成する。業務テンプレート選択手段５は、編成情報・基本ダイヤ記憶手段３２から、次に追加する列車を設定された優先度に基づき決定し、決定した列車の利用可能な業務テンプレートを業務テンプレート候補データ記憶手段３０から１つずつ抽出し、該業務テンプレートに対応づけられたリソース定義データをリソース定義データ記憶手段３１から抽出し、ネットワーク逐次更新手段４にこれらのデータを渡す。業務テンプレートデータ、リソース定義データについては後述する。
【００２２】
スケジュール表示手段２は、ネットワーク逐次更新手段４により作成された構内作業計画（スケジュールあるいは構内作業ネットワーク）を確認するためのインターフェースである。
【００２３】
以下では、まずＰＥＲＴの概要、業務テンプレートおよびリソース定義データに関して説明する。
【００２４】
構内作業計画の自動提案は、プロジェクトの工程スケジューリング問題と多くの類似性がある。本実施形態では、プロジェクト管理分野で実績がある手法であるＰＥＲＴ  （Ｐｒｏｊｅｃｔ  Ｅｖａｌｕａｔｉｏｎ  ａｎｄ  Ｒｅｖｉｅｗ  Ｔｅｃｈｎｉｑｕｅ）に準じた形式で業務テンプレートを記述する。ＰＥＲＴでは、アローグラフ（または、アローダイヤグラム）というネットワーク構造として計画を表現する。一つの作業工程をアーク、アークの両端を作業工程の開始・終了を示すノードとして表現し、作業工程の時間的な因果関係  に応じて連結する。この様な表記に従い全作業工程を整理して記述すると、各々の業務毎の期限や着手可能日、余裕時間などを単純な反復演算処理で見積もることが可能になる。
【００２５】
以下、ＰＥＲＴの関連する部分のみを例を使って解説する。Ｗ１〜Ｗ８の作業の所要日数と作業間の前後関係が下表のように与えられるとする。ある作業が完了していないと着手できない作業がある場合、このある作業は先行作業という。例えばＷ４はＷ１が完了していないと着手できず，Ｗ１はＷ４の先行作業である。またＷ６はＷ２、Ｗ３、Ｗ４のすべてが完了しないと着手できず、Ｗ２、Ｗ３、Ｗ４はＷ６の先行作業である。
【表１】
2008007032.tif 000003
【００２６】
ＰＥＲＴでは，まず図２に示すようなネットワークを作成する。
【００２７】
ＰＥＲＴでは，作業を矢線で表し，それをアクティビティとし、その着手時点・完了時点をノードで表し，それをイベントとする。イベントには重複しないように番号をつける。１つのイベントに複数のアクティビティが流入したり１つのイベントから複数のアクティビティが流出することがあり、例えば図１のイベント４は，Ｗ３とＷ４が完了した点でもあり，Ｗ６とＷ７が開始する点でもある。
【００２８】
次に、このプロジェクトを最短で完了させるには，どの作業をいつから開始していつまでに完了するかを求める。ここで作業ｉ−ｊの所要時間をＴｉｊで表す。イベントｉから流出するアクティビティ（作業）のすべてが最も早く開始できる時刻を最早結合点時刻（ＥＴｉ）と称する。まず、プロジェクトの開始時点（ＥＴ１）を０日とする。すると，作業１−２の所要時間Ｔ１２が６のため，イベント２から始まる作業は最も早くても６日になる。すなわち，イベント２の最早結合点時刻（ＥＴ２）は６日になる。同様にイベント３では，ＥＴ３＝ＥＴ１＋Ｔ１３＝０＋７＝７日になる。イベント４では３つのアクティビティが流入しており、
作業１−４の完了日：ＥＴ１＋Ｔ１４＝０＋５＝  ５日
作業２−４の完了日：ＥＴ２＋Ｔ２４＝６＋４＝１０日
作業３−４の完了日：ＥＴ３＋Ｔ３４＝７＋０＝  ７日
になるが，イベント４以降の作業ができるのは，これらの作業がすべて完了した後なので，ＥＴ４はこれらの最大値である１０日になる。これらをまとめると，次の数式になる。
ＥＴ１＝０
ＥＴｊ＝ｍａｘ｛ＥＴｈ＋Ｔｈｊ｝
（ｈはイベントｉに流入する作業の開始イベント）
例えばイベント５では，
ＥＴ５＝ｍａｘ｛（ＥＴ３＋Ｔ３５），（ＥＴ４＋Ｔ４５）｝
＝ｍａｘ｛（７＋３），（１０＋８）｝
＝ｍａｘ｛１０，１８｝
＝１８
となる。このようにすべてのイベントについてＥＴｉ（最早結合点時刻）を計算すると図３のようになり、ＥＴ６から，このプロジェクトの最短完了時刻は２７日であることがわかる。
【００２９】
次に、最遅結合点時刻とは，プロジェクトを最短完了時刻で完了させるためには，イベントｊに流入するすべての作業が遅くてもこの時刻までに完了していなければならない時刻のことで，ＬＴｊで示す。これはプロジェクトの最後のイベントから順次計算していく。仮にプロジェクトの最終期限を３７日以内とすると、ＬＴ６は３７日となる。
【００３０】
ＬＴｊの演算は次の式で表現される。
ＬＴｎ＝ＥＴｎ  （ｎ：最終イベント）
ＬＴｉ＝ｍｉｎ｛ＬＴｋ−Ｔｉｋ｝  （ｋ：ｉから流出する作業のイベント）
例えばイベント４では，以下となる。
ＬＴ４＝ｍｉｎ｛（２８−８），（３７−１０）｝＝２０
すべてのイベントについてＬＴｉ（最遅結合点時刻）を計算すると図３のようになる。
【００３１】
次に業務テンプレートに関して説明する。
【００３２】
業務テンプレートでは、編成移動・留置や点検、清掃作業をアークと見なし、作業を開始する時点と終了する時点をそれぞれ開始・終了イベントのノードとして、実行する順番に連結する。アークには、イベントの間で守るべき時間制約として、最小時間間隔、最大時間間隔を示す情報が付加される。また、ノードには、イベント単体の制約として実行可能な最早実行時刻（下限時刻）制限、最遅実行時刻（上限時刻）制限を示す情報が付加される。最小時間間隔、最大時間間隔、最早実行時刻制限、最遅実行時刻制限は省略される場合もある。
【００３３】
各編成が利用可能な業務テンプレートは、編成を構成する車両の種類や割り当てられた整備作業などの組み合わせに応じて予め何種類かに決まっている。ユーザはこれらの業務テンプレートを予め基本データとして各編成に対応付けて登録しておく。
【００３４】
図４は、業務テンプレートの一例を示す。業務テンプレートは、ネットワーク構造のデータとして内部表現される。
【００３５】
本例では、本線から編成が入り、ポイントを通過して着発線に到着、しばらく待機、その後ポイントを通過して車庫番線に入庫し、車庫待機中に整備作業し、その後にポイントを通過して再び着発線に入りしばらく待機、ポイントを通過して本線に出ることを表している。
【００３６】
ノード０、１の間のアークは最小、最大時間間隔がそれぞれ１であり、これは本線から発着線へのポイント移動時間が１に固定されることを示す。
【００３７】
ノード０、２の間のアークは最小、最大時間間隔がそれぞれ０であり、これはポイント移動と着発線留置とが同時に開始されなければならない制約を示す。通常の列車制御では、安全性を重視し、編成が現在いる番線のみならず移動に関わる前後の番線を全てロックする「閉塞」と呼ばれる制御を行うが、上記制約は、この制御に対応したものである。
【００３８】
ノード２、３の間のアークは最小時間間隔が１０であり、これは最小１０時刻以上の留置時間を確保しなければならないことを示す。
【００３９】
ノード４、５の間のアークは最小、最大時間間隔がそれぞれ１であり、これは発着線から車庫番線へのポイント移動時間が１に固定されることを示す。
【００４０】
ノード３、４の間のアークは最小、最大時間間隔がそれぞれ−１であり、またノード４、６の間のアークは最小、最大時間間隔がそれぞれ０である。これは、発着線留置の終了より１時刻前に、ポイント移動と車庫番線留置とが同時に開始されなければならない制約を示す。この制約も上記「閉塞」に基づく制約である。
【００４１】
車庫番線留置の開始および終了を表すノード６とノード９のペアの中に、整備作業の開始および終了を表すノード７とノード８のペアがはさまる入れ子構造が存在する。
【００４２】
ノード６、７の間のアークは最小時間間隔が１０であり、これは車庫番線使用開始から整備作業の開始まで最小１０時刻確保しなければならないことを示す。
【００４３】
ノード７、８の間のアークは最小時間間隔が３０であり、これは整備作業の開始から終了まで最小３０時刻を確保しなければならないことを示す。
【００４４】
発着線留置の開始（入区）から一定時間以内に作業を終了しなければならない時間制約を示すため、ノード２からノード８の間にアークを追加し最大時間間隔制約５０を加えている。
【００４５】
ノード８、９の間のアークは最小時間間隔が１０であり、これは整備作業の終了から車庫  番線の留置終了まで最小１０時刻を確保しなければならないことを示す。
【００４６】
ノード１０、１１の間のアークは最小、最大時間間隔がそれぞれ１であり、これは車庫番線から発着線へのポイント移動時間が１に固定されることを示す。
【００４７】
ノード９、１０の間のアークは、最小、最大時間間隔がそれぞれ−１０であり、また、ノード１０、１２の間のアークは最小、最大時間間隔がそれぞれ０である。これは、車庫番線の留置終了より１０時刻前に、ポイント移動と着発線留置とが同時に開始しなければならない制約を示す。この制約も上記「閉塞」に基づく制約である。
【００４８】
ノード１２、１３の間のアークは最小時間間隔が１０であり、これは最小１０時刻以上の発着線の留置時間を確保しなければならないことを示す。
【００４９】
ノード１３、１４の間のアークは最小、最大時間間隔がそれぞれ−１であり、これは発着線留置の終了より１時刻前に発着線から移動を開始しなければならないことを示す。また、ノード１４、１５の間のアークは最小、最大時間間隔がそれぞれ１であり、これは、発着線から本線へのポイント移動時間が１に固定されることを示す。これらの制約も上記「閉塞」に基づく制約である。
【００５０】
次に、リソース定義データに関して説明する。
【００５１】
業務テンプレートの各作業工程で利用し得るリソース（番線、運転手、作業チーム等）は選択肢が複数用意されている。さらに、選択できるリソースの候補は作業工程毎に個別に決定できるとは限らず、路線構造で決まる相互依存関係がある場合が多い。例えば、図５のような路線構造を想定すると、車庫４，５を利用するか、車庫６を利用するかの選択に依存して、移動時に利用可能なポイントが変化する。依存関係を含むリソース候補を汎用的な形式で定義するため、各作業工程に対して利用可能なリソースグループ（１または複数のリソースからなる）を幾つか指定する。また、さらにグループ間の依存関係を示すネットワーク形式のデータとしてリソース定義データを内部表現する。
【００５２】
図６はリソース定義データの例を示す。本例は、図５の路線構造で、図４の業務テンプレートに従った場合の例である。例えば着発番線０しか利用できない場合、ポイント２、庫４，５のみ選択可能だが、着発番線１しか利用できない場合は、すべての車庫、ポイントが選択可能であると分かる。
【００５３】
業務テンプレートとリソース定義データとは相互に対応付けがなされており、業務テンプレートの各作業工程の開始ノードと、リソース定義データにおけるリソースグループを示すノードとは相互に参照が可能とするリンク情報が設定される。例えば、図４の業務テンプレートにおける車庫到着を示すノード６は、図６のリソース定義データにおける（庫４、庫５）および（庫６）の２つのグループに関連付けされている。
【００５４】
次に、ネットワーク逐次更新手段４について説明する。
【００５５】
ネットワーク逐次更新手段４では、個別の編成単位で登録された業務テンプレートを、リソースの競合状況に応じて、一つの構内作業計画として統合する。構内作業計画もネットワーク構造として表現される。例えば、図７の路線で図８のダイヤに従うとすると、構内作業計画（構内作業ネットワーク）は、図９のようなアローグラフで表現できる。
【００５６】
図９において、実線の矢印が列車（車両の編成）毎の作業工程を表す。同じ横一列には同一のリソースを利用する作業工程が配置され、作業工程同士は点線矢印でつながれる。点線の矢印は、各列車がそれぞれのリソースを利用する順序を表す。本例だと３つの点線矢印Ｙ１〜Ｙ３が示される。点線矢印Ｙ１は、列車１が車庫１を出発した後に列車２が車庫１を利用することを示す。点線矢印Ｙ２は、列車１が発着線１を出発した後に列車２が発着線１を利用することを示す。点線矢印Ｙ３は、列車１が発着線１を出発した後、再び列車１が発着線１を利用することを示す。
【００５７】
各作業工程がそれぞれどのリソースを利用するか、さらにどういう順番で利用するかは、事前に決まっていない。ネットワーク逐次更新手段４は、対象となる列車について、業務テンプレート候補データ記憶手段３０に記憶された業務テンプレートが表すネットワークデータ（図４参照）を受け取り、同時に対となるリソース定義データ（図６参照）を参照して、業務テンプレートにおける各作業工程へのリソース割付を行う。すなわち、業務テンプレートが表すネットワークを、構内作業計画を表すネットワーク（構内作業ネットワーク）に追加合成する。業務テンプレートの作業工程が、構内作業ネットワークの作業工程とリソース競合が発生する場合は、業務テンプレートの作業工程を、リソース競合が発生する作業工程とアーク接続する（図９の点線矢印参照）。ネットワーク統合後、ネットワーク時刻計算手段４１により、構内作業ネットワークにおける各ノードの時刻更新演算を行う。以上を、全ての列車について行う。
【００５８】
図１０は、ネットワーク逐次更新手段４の処理の流れを概略的に示すフローチャートである。
【００５９】
まず、編成情報・基本ダイヤ記憶手段３２から、次に追加する列車を決定する（Ｓ１）。
【００６０】
次に、決定した列車の利用可能な業務テンプレートを業務テンプレート候補データ記憶手段３０から１つ取り出し、また、該業務テンプレートに対応づけられたリソース定義データをリソース定義データ記憶手段３１から取り出す（Ｓ２）。Ｓ２は業務テンプレート選択手段の処理に対応する。
【００６１】
取り出した業務テンプレートおよびリソース定義データを元に、選択した列車のスケジュール（構内作業計画）への追加演算を行う（Ｓ３）。Ｓ３の詳細は後述する。
【００６２】
追加が成功した場合は（Ｓ４のＹＥＳ）、全ての列車について追加が完了したか否かをチェックし（Ｓ５）、全ての列車についての追加が完了した場合は（Ｓ５のＹＥＳ）、完成した構内作業計画（構内作業ネットワーク）をスケジュール記憶手段３３に出力する。一方、まだ追加すべき列車が残っている場合は（Ｓ５のＮＯ）Ｓ１に戻り次に追加する列車を決定する。
【００６３】
追加が成功しなかった場合は（Ｓ４のＮＯ）、選択した列車が利用可能な全ての業務テンプレートについて追加演算を試したか否かをチェックする（Ｓ６）。
【００６４】
まだ全ての利用可能な業務テンプレートについて追加演算を試してない場合は（Ｓ６のＮＯ）、業務テンプレートを変更することを決定し（Ｓ７）、既に試したのとは別の業務テンプレートを取り出す（Ｓ２）。
【００６５】
一方、全ての利用可能な業務テンプレートについて追加演算を試した場合は（Ｓ６のＹＥＳ）、予め設定した試行終了条件（試行回数上限や演算制限時間など）に達していれば終了し（Ｓ８のＹＥＳ）、試行終了条件に達していなければ（Ｓ８のＮＯ）、優先度を変更し（例えば列車を構内作業ネットワークに追加する順番を変える）、最初から処理をやり直す（Ｓ９）。
【００６６】
図１１は、Ｓ３で行われる手順を詳細に示すフローチャートである。
【００６７】
図１０のＳ２において一編成分の業務テンプレートと、これに対となるリソース定義データとをデータ記憶手段３から取り出したら、取り出した業務テンプレートに相当するネットワークを生成する（Ｓ１１）
生成したネットワークのノードＩＤのトポロジカルソートを行う（Ｓ１２）。トポロジカルソートとは、アークで結合されたノード間でアークの出ているノード（上流側のノード）が常に若い番号になるように順番（ＩＤ）を並べ直すことをいう。
【００６８】
生成したネットワークにおける各ノードのＥＴ（下限時刻）、ＬＴ（上限時刻）を、後述のネットワーク時刻計算手段４１を用いて計算する（Ｓ１３）。Ｓ１３はネットワーク時刻計算手段の処理に対応する。
【００６９】
現在の構内作業計画（構内作業ネットワーク）の複製を生成し、ネットワーク一時記憶手段４２に格納する（Ｓ１４）。現在の構内作業ネットワークもネットワーク一時記憶手段４２に格納されている。
【００７０】
現在の構内作業ネットワークに統合すべき上記生成したネットワークにおける各ノードを先頭から順番に選択し（Ｓ１５）、選択したノードの種別をチェックする（Ｓ１６）。
【００７１】
選択したノードが、作業工程の終了ノードの場合は（Ｓ１６のＮＯ）次のノードに処理を移す（Ｓ１５）。
【００７２】
選択したノードが、作業工程の開始ノードの場合は（Ｓ１６のＹＥＳ）、当該開始ノードで始まる作業工程にリソース競合が発生するか否かをチェックする（Ｓ１７）。
【００７３】
競合が発生しない場合は（Ｓ１７のＮＯ）リソース競合リスト管理テーブルに当該開始ノードのノードＩＤを先頭ノードとしてセットし（Ｓ１８）、次のノードに処理を移す（Ｓ１５）。
【００７４】
リソース競合リスト管理テーブル（後述する図１２参照）は各リソースとリソース競合リストとの対応を管理している。リソース競合リストとは、構内作業ネットワークのノードの内、特定のリソースを利用するノードに沿ってアークを辿った構内作業ネットワークの一部をいい、特定のリソースを使用する作業工程を利用順に並べたものに相当する。図９の場合、車庫１に関するリソース競合リストは、
「編成１車庫１着」  →  「編成１車庫１発」  →  「編成２車庫１発」  →  「編成２車庫１発」
のノードのリスト（横１列のノードのリスト）に相当する。
【００７５】
Ｓ１７において競合が発生する場合は（Ｓ１７のＹＥＳ）、該当するリソース競合リストの先頭から最適な挿入可能箇所（開始ノードと終了ノードとのペアを挿入すべき箇所）を検索する（Ｓ１９）。
【００７６】
挿入箇所が見つからなかった場合は（Ｓ２０のＮＯ）、構内作業ネットワークを、Ｓ１４で複製しておいたものに戻し（Ｓ２１）、処理を終了する（編成追加失敗）。そして、図１０のＳ４に進む。
【００７７】
挿入箇所が見つかった場合は（Ｓ２０のＹＥＳ）、リソース競合リスト（上述したように構内作業ネットワークの一部）における該当箇所に作業工程のノードのペアを挿入する（Ｓ２２）。
【００７８】
ここで、作業工程のノードのペア（開始ノードおよび終了ノード）の挿入は、作業工程ペアノード挿入手段４０が行う。図１２および図１３を用いて、図９のアローグラフに列車３のアローグラフを追加する場合を例に挿入方法を説明する。
【００７９】
図１２には「列車３着発１着」→「列車３着発１発」のノードのペアの挿入可能箇所の候補が示される。図中複数のマスが示されるが、これらはリソース競合リスト管理テーブルを概念的に示す。１つのマスが１つのリソースとリソース競合リストとの対応を示す。本例の場合は３箇所の挿入箇所の候補（候補１〜候補３）がある。挿入する箇所を決定する方法はいろいろ考えられるが、単純な方法として、最も挿入時の余裕時間の小さいと思われる箇所に挿入する。余裕時間は以下の式で見積もる。
Ｍｉｎ  （  ＬＴ＿ｎｅｘｔ＿ｓｔａｒｔ  −  ＥＴ＿ｅｎｄ  ，    ＬＴ＿ｓｔａｒｔ  −ＥＴ＿ｐｒｅ＿ｅｎｄ    ）
【００８０】
ここで、ＬＴ＿ｓｔａｒｔとＥＴ＿ｅｎｄはそれぞれ、挿入するノードペアにおける開始ノードの最早結合点時刻と終了ノードの最遅結合点時刻であり、ＥＴ＿ｐｒｅ＿ｅｎｄは挿入箇所の直前に位置するノード（終了ノード）の最早結合点時刻、ＬＴ＿ｎｅｘｔ＿ｓｔａｒｔは挿入箇所の直後に位置するノード（開始ノード）の最遅結合点時刻である。「列車３着発１着」→「列車３着発１発」のノードを候補２の箇所に挿入した例を図１３に示す。
【００８１】
ノードのペアの追加後、構内作業ネットワーク全体のトポロジカルソートを行い（Ｓ２３）、さらにノードＩＤ順に従い、ネットワーク時刻計算手段４１を用いて、時間更新演算（ＥＴ，ＬＴ更新）を行う（Ｓ２４）。ここで、ネットワーク時刻計算手段４１の機能について説明する。
【００８２】
構内作業計画で現れる時間制約には、従来のＰＥＲＴでは扱わない最大時間間隔制約が含まれ、本実施形態では、この最大時間間隔制約に対応するため、従来のＰＥＲＴにおける時刻更新演算に加え、以下の改良を加える。
【００８３】
図１４は時刻更新演算を説明する図である。イベント（ノード）が５つ示され、全てのアークが最小時間間隔１、最大時間間隔２を示すとする。
【００８４】
最小時間間隔制約（最小時隔制約）のみだと、ＰＥＲＴの説明で述べたように、最早結合点時刻ＥＴを決定するための順方向演算、最遅結合点時刻ＬＴを決定するための逆方向演算をそれぞれ一回ずつ実行すれば良い。この様子を図１５（Ａ）に示す。しかし、最大時間間隔制約（最大時隔制約）を処理するためには、図１５（Ｂ）に示すように、再度ＥＴ，ＬＴの更新演算を実施する必要がある。図１５（Ｂ）の処理では、最初の演算で求められたＥＴ，ＬＴを再利用すること、ＥＴを逆方向演算、ＬＴを順方向演算で更新することに注意されたい。
【００８５】
ここで、最大時間間隔制約があると、最小時間間隔制約との間で相互矛盾が発生することがあり、最大時間間隔および最小時間間隔として不適切な値を設定すると時間更新演算が収束しなくなる場合がある。このため、規定回数の順方向、逆方向演算を反復し、ＥＴ、ＬＴの値が収束するかを確認することで、設定した条件が間違っていないかどうかをチェックする。
【００８６】
時刻更新演算（Ｓ２４）を行ったら、Ｓ１５に戻って、次のノードを選択する。選択すべきノードがもはや存在しない場合は、処理を終了する。
【００８７】
以上のように、本実施形態により、汎用性と性能面のスケーラビリティを両立可能な、実用性を重視した構内作業計画の自動提案を行うことが可能となる。
【００８８】
（実施形態２）
実施形態１のように業務テンプレートを優先度に従い適当に選択し追加を試みるのでは、後から追加する編成に皺寄せが行き失敗する恐れがある。そこで本実施形態２では、ボトルネックになりそうな各リソースの利用状況がなるべく均等となるようにするため、スケジュールへの統合を行う前処理として、各編成が利用する業務テンプレートの組み合わせを１つの候補として予め選別した後に、実施形態１と同様に、各編成について決定した業務テンプレートを一つの計画に統合することを試みる。
【００８９】
以下、図面を参照しながら、本実施形態について説明する。
【００９０】
図１６は、本発明による構内作業計画システムの一実施形態の構成を示す図である。
【００９１】
システム全体は、業務テンプレート入力・表示手段１６０、スケジュール表示手段１６１、データ記憶手段１６２、業務テンプレート候補選択手段１６３、ネットワーク逐次更新手段１６４から構成される。各手段による機能はプログラムをコンピュータに実行させることによって実現してもよいし、ハードウェア的に実現してもよい。
【００９２】
業務テンプレート入力・表示手段１６０は、ユーザが業務テンプレートを登録したり、各種指示を入力したりするためのインターフェースである。
【００９３】
データ記憶手段１６２は必要なデータを格納するためのデータベースであり、業務テンプレート候補データ記憶手段１６２０、業務テンプレート付加データ記憶手段１６２１、リソース定義データ記憶手段１６２２、編成情報・基本ダイヤ記憶手段１６２３、スケジュール記憶手段１６２４を有する。
【００９４】
業務テンプレート候補データ記憶手段１６２０は複数の業務テンプレートの候補データを格納する。
【００９５】
業務テンプレート付加データ記憶手段１６２１は、業務テンプレートの組み合わせを予め選別する際に利用する付加データを記憶する。業務テンプレート付加データは、自身に対応する業務テンプレートデータにおいて時刻（ＥＴおよびＬＴ）を変更する対象となるノード（時刻指定対象ノード）のＩＤと、時刻指定対象指定ノードの優先順位のデータとを含む。また、業務テンプレート付加データは、自身に対応する業務テンプレートデータにおいてリソースを指定する対象となるノード（リソース指定対象ノードすなわち開始ノード）のＩＤと、リソース指定対象ノードの優先順位のデータとを含む。
【００９６】
リソース定義データ記憶手段１６２２は、実施形態１で述べたリソース定義データを格納する。
【００９７】
編成情報・基本ダイヤ記憶手段１６２３は、車両基地や駅への入区・出区が決まっている各編成について構内作業計画に必要な基本情報（編成ＩＤ、編成種別、入区・出区予定時刻、利用可能な業務テンプレートおよびリソース定義データの指定情報）を格納する。
【００９８】
スケジュール記憶手段１６２４は、ネットワーク逐次更新手段１６４によって作成された構内作業計画を格納する。
【００９９】
業務テンプレート候補選択手段１６３は、業務テンプレート候補ＩＤ記憶手段１６３０、割当失敗編成ＩＤ記憶手段１６３１、業務テンプレート候補集合初期化・変更手段１６３２、ペナルティ演算手段１６３３を有する。
【０１００】
業務テンプレート候補集合初期化・変更手段１６３２は、各編成について業務テンプレートの候補の選択および変更、業務テンプレートの各工程において利用するリソースの仮決定および変更、業務テンプレートにおける各ノードの上限時刻および下限時刻の仮決定および変更を行う。詳細は後述する。
【０１０１】
ペナルティ演算手段１６３３は、各編成の業務テンプレートについて仮決定された利用リソースおよび上下限時刻を元に、後述するペナルティ演算を実施して、リソースの種類ごとにペナルティ値を求め、さらにこれらのペナルティ値から全体ペナルティ値を求める。
【０１０２】
業務テンプレート候補選択手段１６３は、これら業務テンプレート候補集合初期化・変更手段１６３２とペナルティ演算手段１６３３を用いて、スケジュールへの統合を行う前処理として、ボトルネックになりそうなリソース（例えば番線）の利用状況がなるべく均等となるように、各編成が利用する業務テンプレートの組み合わせを予め選別する。例えば、それぞれの編成で選択する業務テンプレートを少しずつ変更しては、各リソースの許容量を越えている分をペナルティとし、ペナルティ総和（全体ペナルティ値）が次第に小さくなるように業務テンプレートの組み合わせの取捨選択を行う。詳細は後述する。
【０１０３】
業務テンプレート候補ＩＤ記憶手段１６３０は、上記前処理で選択された各業務テンプレート候補のＩＤを記憶する。
【０１０４】
割当失敗編成ＩＤ記憶手段１６３１は、スケジュール（構内作業ネットワーク）に対する、上記前処理で選択された各業務テンプレート候補の追加が失敗した場合に、追加失敗した編成のＩＤを記憶する。
【０１０５】
ネットワーク逐次更新手段１６４は、実施形態１と同様に、作業工程ペアノード挿入手段１６４０、ネットワーク時刻計算手段１６４１、ネットワーク一時記憶手段１６４２を有する。
【０１０６】
スケジュール表示手段１６１は、ネットワーク逐次更新手段１６４により作成された構内作業計画（スケジュールあるいは構内作業ネットワーク）を確認するためのインターフェースである。
【０１０７】
次に、本実施形態における全体の処理の流れについて図１７を用いて説明する。
【０１０８】
まず、業務テンプレートデータ、業務テンプレート付加データ、リソース定義データをデータ記憶手段１６２から読込む（Ｓ１７１）。
【０１０９】
次に、業務テンプレート候補選択手段１６３が業務テンプレート集合の選択演算を行って、各編成が利用する業務テンプレートの組み合わせを予め選別する（Ｓ１７２）。
【０１１０】
次に、Ｓ１７２で選択された業務テンプレートの集合の構内作業ネットワークへの追加演算をネットワーク逐次更新手段１６４を利用して実施する（Ｓ１７３）。Ｓ１７３で追加に失敗した編成については、さらに業務テンプレートの候補の変更、リソースの変更、または上下限時刻の変更を行って、構内作業ネットワークへの追加を再度試みる（Ｓ１７４）。
【０１１１】
全ての編成の追加に成功したか否かを判別し（Ｓ１７５）、成功した場合は処理を終了する。一方、失敗した場合は、反復数上限や制限演算時間などの試行終了条件に達したか否か判別し（Ｓ１７６）、試行終了条件に達していない場合は、Ｓ１７２に戻り、処理を反復する。
【０１１２】
次に、図１７の各ステップの処理に関し詳細に説明する。まず、図１７のＳ１７２の業務テンプレートの選択演算について、図１８、図１９のフローチャートおよび図２０〜図２３を用いて説明する。
【０１１３】
図１８は、業務テンプレートの選択演算を説明するフローチャートである。
【０１１４】
Ｓ１８１からＳ１８３までは初期化処理である。まず未処理の編成を選択し（Ｓ１８１）、業務テンプレートの仮決定処理（業務テンプレートの候補の選択、リソースの仮決定、および上下限時刻の仮決定）を行い（Ｓ１８２）、全編成についての処理が完了するまで反復する（Ｓ１８３）。
【０１１５】
初期化が終わると、初期状態についてペナルティ演算を行う（Ｓ１８４）。さらに、変更対象の編成をランダムに選択し（Ｓ１８５）、選択された編成の業務テンプレートの仮決定処理（業務テンプレートの候補の変更、リソースの変更、または上下限時刻の変更）を行い（Ｓ１８６）、変更後の状態についてペナルティ演算を行う（Ｓ１８７）。
【０１１６】
Ｓ１８６での仮決定処理により全体ペナルティ値が改善されるか否かを判別し（Ｓ１８８）、改善される場合は、変更内容を業務テンプレート候補ＩＤ記憶手段１６３０に記憶して、業務テンプレート集合に反映（業務テンプレート集合を更新）する（Ｓ１８９）。
【０１１７】
反復数上限、制限演算時間および全体ペナルティ値などに関する試行終了条件に達したか否か判別し（Ｓ１９０）、試行終了条件に達していない場合は、変更対象の編成を選び直し処理を反復する。試行終了条件に達した場合は、処理を終了する。この結果、業務テンプレート候補ＩＤ記憶手段１６３０には最も低い全体ペナルティ値が得られたとき（所定の基準が満たされたとき）の内容が記憶される。最も低い全体ペナルティ値が得られることの他、所定値以下の全体ペナルティ値が得られることを所定の基準として用いても良い。Ｓ１９０の処理は、例えば繰り返し制御手段による処理に相当する。
【０１１８】
図１９は、図１８のＳ１８２およびＳ１８６における業務テンプレートの仮決定処理について詳細に説明するフローチャートである。
【０１１９】
業務テンプレートの仮決定処理は、業務テンプレート候補集合初期化・変更手段１６３２で行われる処理に相当し、ペナルティ演算を行うための前処理として、業務テンプレートの候補の選択、業務テンプレートの各工程で利用するリソースの仮決定、各工程の開始時刻および終了時刻の仮決定を行う。
【０１２０】
まず、対象編成の利用可能な業務テンプレートの中から、業務テンプレートをランダムに選択する（Ｓ１９１）。業務テンプレートは各編成に対して利用可能な候補が予め指定されている。
【０１２１】
Ｓ１９２からＳ１９４はリソース仮決定の処理である。リソース指定対象ノード（作業工程の開始ノード）の中から、未処理のノードで最も優先度高いノードを選択し（Ｓ１９２）、リソース定義データを参照し、選択可能なリソースの中からランダムに決定する（Ｓ１９３）。全てのリソース指定対象ノードの処理が完了したか否かを判別し（Ｓ１９４）、全てのリソース指定対象ノードの処理が完了した場合は時刻仮決定の演算に進む。
【０１２２】
Ｓ１９５からＳ１９９までは時刻仮決定の演算である。まず、対象業務テンプレートのネットワークのＥＴ，ＬＴを元の値に初期化し（Ｓ１９５）、時刻指定対象ノード（時刻仮決定の演算において時刻の仮決定を行う対象とするノード）の中から未処理ノードで最も優先度高いノードを選択する（Ｓ１９６）。当該ノードの上下限時刻をＥＴとＬＴの間の値にそれぞれランダムに決定し（ＥＴとＬＴは同じ値であっても異なる値であってもよい）、  当該ノードのＥＴとＬＴを当該決定値に置換する（Ｓ１９７）。次に、ネットワーク時刻計算手段１６４１を利用して、業務テンプレートのネットワークの時刻更新演算（ＥＴ、ＬＴ更新演算）を行い、業務テンプレートの他のノードのＥＴ、ＬＴを一旦更新する（Ｓ１９８）。全ての時刻指定対象ノードの処理が完了したか否かを判別し（Ｓ１９９）、未完了の場合はＳ１９６に戻り処理を反復する。完了の場合は、業務テンプレートの各ノードのＥＴをペナルティ演算用に抽出する（Ｓ２００）。ペナルティ演算用にＥＴの代わりにＬＴを抽出してもよい。
【０１２３】
以上において、図１９のＳ１８２では、時刻仮決定の演算（Ｓ１９５からＳ１９８）において少なくともＳ１９５を実行すればよい。
【０１２４】
また、図１９のＳ１８６では、業務テンプレート選択処理（Ｓ１９１）、リソース仮決定の処理（Ｓ１９２からＳ１９４）、時刻仮決定の演算（Ｓ１９５からＳ１９８）のうちの少なくとも１つを実行すればよい。ただし業務テンプレートの選択（Ｓ１９１）を実行した場合は、リソース仮決定の処理（Ｓ１９２からＳ１９４）と、時刻仮決定の演算とを実行する（Ｓ１９５からＳ１９８のうち少なくともＳ１９５を実行する）こととする。すなわち、業務テンプレートの選択（Ｓ１９１）を実行する場合は、初期化処理（Ｓ１８２）と同じ処理を行うこととなる。
【０１２５】
図２０は、図１９のＳ１９５からＳ１９８までの処理を補足説明する例である。
【０１２６】
本例の業務テンプレートでは、図２０の（１）のＥＴ、ＬＴが初期値として与えられ（元の値に初期化され）、ノード１と２を結ぶアークは最小時隔１０、最大時隔１００、ノード２と３を結ぶアークおよびノード４と５を結ぶアークは最小最大時隔とも０、ノード３と４を結ぶアークは最小時隔１０、最大時隔５０、ノード５と６を結ぶアークは最小時隔１０、最大時隔は無限大が指定されている。ＥＴ、ＬＴの初期値は、対象となる編成の到着時刻、発車時刻から決定される。例えばＥＴ１、ＬＴ１の１００は基本情報に示される到着時刻であり、ＥＴ６、ＬＴ６の３００は基本情報に示される発車時刻である。
【０１２７】
図２０の（２）では、時刻指定対象ノードの中から最も優先度高いノードを選択する。ここではノード２を選択する。そして、ノード２の時刻を、ＥＴ２＝１１０とＬＴ２＝２００の間の値にランダムに決定する。ここでは１５０を選択したとし、ノード２のＥＴ２とＬＴ２の双方を１５０に置換する。
【０１２８】
しかる後、図２０の（３）で時刻更新演算を行うと、他のノードのＥＴ，ＬＴが、各アークの最小時隔、最大時隔を守る値に更新される。まだ時刻指定対象ノードが残っている場合は、更新されたＥＴ、ＬＴを利用し、同じ処理を反復する。例えば、図２０でノード４の時刻をさらに指定する場合は、ＥＴ４＝１６０とＬＴ４＝２００の間の値を選択しなければならない。
【０１２９】
次に、図２１〜図２３を用いて業務テンプレートの選択演算を補足説明する。
【０１３０】
図２１はサンプルの単純な路線、図２２は、業務テンプレートデータを例示したものである。ここでは、全部で３編成が計画対象となっているものとし、編成１用に２種類、編成２用に１種類、編成３用に２種類の業務テンプレートが選択可能である。図２３は、ペナルティ演算の仕組みを図示したものである。
【０１３１】
まず、編成１は候補２、編成２と編成３は候補１を選択したとする。図１９で示した業務テンプレート仮決定処理により、それぞれの工程で利用する番線と、それぞれの工程の開始・終了時刻が仮決定されている。ペナルティ演算時には、所定の時間区間（単位時間区間）ごとにおける、指定されたリソースの使用量を集計し、当該リソースの許容量を越えて重複してリソースが使用されている場合に、当該重複使用量をペナルティ値として計算する。
【０１３２】
図２３の例では、ペナルティの演算対象となるボトルネックとなるリソースが着発番線と車庫番線であり、それぞれの単位時間区間（図中における細かいピッチの縦線の間隔）における利用量の総和を計算し、各番線（リソース）の容量を超えた部分の面積をペナルティ値として計算する。斜め線ハッチングの部分はそれぞれのリソースのペナルティ値に相当する。着発番線は２つあるため容量２として計算しているが、それぞれの番線毎に容量１のリソースとして計算する場合もあり得る。
【０１３３】
各リソースのペナルティ値が演算できたら、それぞれのリソースのペナルティ値に重みをかけた値の総和を全体ペナルティ値とする。それぞれのリソースのペナルティ値のＮ乗和を全体ペナルティ値とする場合も有りうる。
【０１３４】
次に、図１７のＳ１７３の構内作業ネットワークへの追加演算について、図２４のフローチャートを用いて説明する。
【０１３５】
まず、次に追加する編成を決定し（Ｓ２４１）、対象編成の業務テンプレートデータ（各ノードの仮決定された上下限時刻を含むとする）と、これに対応するリソース定義データとをデータ記憶手段１６２より受け取る（Ｓ２４２）。
【０１３６】
編成の構内作業ネットワークへの追加演算を行い（Ｓ２４３）、追加に成功したか否かの判定を行う（Ｓ２４４）。追加に失敗した場合は、失敗した編成を割当失敗編成ＩＤ記憶手段１６３１に記録する。追加に成功した場合は、全ての編成について構内作業ネットワークへの追加演算処理を試行したか否かを判定する（Ｓ２４５）。全ての編成について試行完了した場合は処理を終了し、完了していない場合はＳ２４１に戻り処理を反復する。なお、Ｓ２４３の処理に関しては、実施形態１と同様の方法を利用する。ただし、業務テンプレート仮決定処理で仮決定されたリソースおよび上下限時刻は、そのまま利用する。
【０１３７】
最後に、図１７のＳ１７４の構内作業ネットワークへの再追加演算について、図２５のフローチャートを用いて説明する。Ｓ１７４の処理では、図２４の処理で構内作業ネットワークへの追加に失敗した編成につき、再度追加演算を試みる。より詳細には、図２４の処理で試行していない業務テンプレートの追加演算を試み、さらに図２４で利用した業務テンプレートについても事前に仮決定されたリソースおよび上下限時刻を変更して追加を試みる。このため図２４の処理で失敗した編成でも追加に成功する場合がある。
【０１３８】
まず、割当失敗編成ＩＤ記憶手段１６３１に記録されている割当失敗した編成の中で、次に追加するものを決定し（Ｓ２５１）、対象編成の業務テンプレートデータと、これに対応するリソース定義データとをデータ記憶手段１６２から受け取る（Ｓ２５２）。
【０１３９】
編成の構内作業ネットワークへの追加演算をリソースまたは上下限時刻またはこれらの両方を変更して行い（Ｓ２５３）、追加に成功したか否かの判定を行う（Ｓ２５４）。追加に失敗した場合は、対象となっている編成の全ての業務テンプレートの追加を試したか否かを判別し（Ｓ２５７）、まだ試していない業務テンプレートがある場合は業務テンプレートを変更し（Ｓ２５６）、Ｓ２５２に戻って処理を反復する、全ての業務テンプレートを試した場合は本編成の追加に失敗したため終了となる。
【図面の簡単な説明】
【０１４０】
【図１】本発明による構内作業計画システムの実施形態１の構成を示す図。
【図２】ＰＥＲＴで作成したネットワークの一例を示す図。
【図３】最早結合点時刻および最遅結合点時刻を図２のネットワークに追加した例を示す図。
【図４】業務テンプレートの一例を示す図。
【図５】路線構造の一例を示す図。
【図６】リソース定義データの例を示す図。
【図７】路線構造の一例を示す図。
【図８】列車のダイヤの一例を示す図。
【図９】構内作業計画をアローグラフで表現した例を示す図。
【図１０】ネットワーク逐次更新手段の処理の流れを概略的に示すフローチャート。
【図１１】図１０のＳ３で行われる手順を詳細に示すフローチャート。
【図１２】ノードペアの挿入箇所候補を示す図。
【図１３】ノードペアを挿入した状態を示す図。
【図１４】時刻更新演算を説明する図。
【図１５】時刻更新演算を説明する図。
【図１６】本発明による構内作業計画システムの実施形態２の構成を示す図。
【図１７】実施形態２における全体の処理の流れを説明するフローチャート。
【図１８】業務テンプレートの選択演算を説明するフローチャート。
【図１９】業務テンプレート仮決定処理を詳細に説明するフローチャート。
【図２０】時刻仮決定演算を補足説明する例を示す図。
【図２１】サンプルの単純な路線を示す図。
【図２２】業務テンプレートデータを例示した図。
【図２３】ペナルティ演算の仕組みを説明する図。
【図２４】構内作業ネットワークへの追加演算を説明するフローチャート。
【図２５】構内作業ネットワークへの再追加演算を説明するフローチャート。
【符号の説明】
【０１４１】
１、１６０：業務テンプレート入力・表示手段
２、１６１：スケジュール表示手段
３、１６２：データ記憶手段
４：ネットワーク逐次更新手段
３０、１６３：業務テンプレート候補データ記憶手段
３１、１６２２：リソース定義データ記憶手段
３２、１６２３：編成情報・基本ダイヤ記憶手段
３３、１６２４：スケジュール記憶手段
４０、１６４０：作業工程ペアノード挿入手段
４１、１６４１：ネットワーク時刻計算手段
４２、１６４２：ネットワーク一時記憶手段
１６２１：業務テンプレート付加データ記憶手段
１６３０：業務テンプレート候補ＩＤ記憶手段
１６３１：割当失敗編成ＩＤ記憶手段
１６３２：業務テンプレート候補集合初期化・変更手段
１６３３：ペナルティ演算手段
【図１】
2008007032.tif 000004
【図２】
2008007032.tif 000005
【図３】
2008007032.tif 000006
【図４】
2008007032.tif 000007
【図５】
2008007032.tif 000008
【図６】
2008007032.tif 000009
【図７】
2008007032.tif 000010
【図８】
2008007032.tif 000011
【図９】
2008007032.tif 000012
【図１０】
2008007032.tif 000013
【図１１】
2008007032.tif 000014
【図１２】
2008007032.tif 000015
【図１３】
2008007032.tif 000016
【図１４】
2008007032.tif 000017
【図１５】
2008007032.tif 000018
【図１６】
2008007032.tif 000019
【図１７】
2008007032.tif 000020
【図１８】
2008007032.tif 000021
【図１９】
2008007032.tif 000022
【図２０】
2008007032.tif 000023
【図２１】
2008007032.tif 000024
【図２２】
2008007032.tif 000025
【図２３】
2008007032.tif 000026
【図２４】
2008007032.tif 000027
【図２５】
2008007032.tif 000028