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