(57)【特許請求の範囲】
【請求項１】
所定の期間毎及び輸送手段毎の運用を示す運用情報内の所定の属性値が一致する運用の集合である運用グループの識別情報を、前記所定の期間毎及び前記輸送手段毎に区別される割当対象項目に対して割り当てていく運用グループ割当手段と、
前記運用グループ割当手段により全ての割当対象項目に対して前記運用グループの識別情報が割り当てられた後、所定の制約条件に含まれる運用と運用グループとの関連性に係る制約条件に従って、前記所定の期間毎及び前記輸送手段毎に区別される割当対象項目に対して、前記運用の識別情報を割り当てていく運用割当手段とを有することを特徴とする運用割当装置。
【請求項２】
割当対象項目に割り当てられた運用グループの識別情報と、割当対象項目に割り当てられる運用の識別情報に示される運用が属する運用グループの識別情報とが、任意の前記所定の期間及び任意の前記輸送手段毎に夫々一致しているか否かを、前記制約条件に基づいて検査する制約検査手段を更に有し、
前記運用割当手段は、前記制約検査手段による検査結果に従って、割当対象項目に対して運用の識別情報を割り当てていくことを特徴とする請求項１に記載の運用割当装置。
【請求項３】
前記制約検査手段は、前記運用グループ割当手段が運用グループの識別情報を割当対象項目に割り当てる度に、割当対象項目内における以降の運用グループの識別情報の割り当て対象となる割当対象項目に対する割り当てる候補の運用グループの識別情報のうち、前記所定の制約条件を違反する運用グループの識別情報を検査し、前記運用グループ割当手段は、割当対象項目のうち、前記制約検査手段により前記所定の制約条件を違反すると判定された運用グループの識別情報を除く、割当対象項目に対して割り当て可能な運用グループの識別情報の数が少ない割当対象項目から先に運用グループの識別情報を割り当てていくことを特徴とする請求項２に記載の運用割当装置。
【請求項４】
前記運用グループ割当手段は、割当対象項目のうち、前記所定の期間当たりに割り当て可能な運用距離が短い割当対象項目から先に運用グループの識別情報を割り当てていくことを特徴とする請求項１乃至３の何れか１項に記載の運用割当装置。
【請求項５】
前記運用グループ割当手段は、各運用グループについて、該当する運用グループに属する運用の運用情報の一属性値である運用距離が最も短い運用を代表として選択し、選択した代表の運用のうち、運用距離が短い代表の運用が属する運用グループの識別情報から先に割当対象項目に対して割り当てていくことを特徴とする請求項１乃至４の何れか１項に記載の運用割当装置。
【請求項６】
前記制約検査手段は、前記運用割当手段が運用の識別情報を割当対象項目に割り当てる度に、割当対象項目内における以降の運用の識別情報の割り当て対象となる割当対象項目に対する割り当てる候補の運用の識別情報のうち、前記所定の制約条件を違反する運用の識別情報を検査し、前記運用割当手段は、割当対象項目のうち、前記制約検査手段により前記所定の制約条件を違反すると判定された運用の識別情報を除く、割当対象項目に対して割り当て可能な運用の識別情報の数が少ない割当対象項目から先に運用の識別情報を割り当てていくことを特徴とする請求項２乃至５の何れか１項に記載の運用割当装置。
【請求項７】
前記運用割当手段は、割当対象項目のうち、前記所定の期間当たりに割り当て可能な運用距離が短い割当対象項目から先に運用の識別情報を割り当てていくことを特徴とする請求項１乃至６の何れか１項に記載の運用割当装置。
【請求項８】
前記運用割当手段は、前記運用情報の一属性値である運用距離が長い運用の識別情報から先に割当対象項目に対して割り当てていくことを特徴とする請求項１乃至７の何れか１項に記載の運用割当装置。
【請求項９】
前記所定の属性値が一致する運用情報群に対応する運用グループの識別情報を、前記所定の期間毎に記録媒体に保持する保持手段を更に有し、
前記運用グループ割当手段は、前記記録媒体に保持される運用グループの識別情報を割当対象項目に対して割り当てていくことを特徴とする請求項１乃至８の何れか１項に記載の運用割当装置。
【請求項１０】
前記所定の期間毎に、前記所定の属性値が一致する運用情報群に対応して運用グループの識別情報を生成する識別情報生成手段を更に有し、
前記運用グループ割当手段は、前記識別情報生成手段により生成される運用グループの識別情報を割当対象項目に対して割り当てていくことを特徴とする請求項１乃至８の何れか１項に記載の運用割当装置。
【請求項１１】
前記所定の期間毎に前記運用情報を記録媒体に保持する保持手段を更に有し、
前記運用割当手段は、前記記録媒体に保持される前記運用情報を割当対象項目に対して割り当てていくことを特徴とする請求項１乃至１０の何れか１項に記載の運用割当装置。
【請求項１２】
前記所定の期間毎に前記運用情報を記録媒体に保持する保持手段を更に有し、
前記識別情報生成手段は、前記記録媒体に保持される前記運用情報に基づいて、前記所定の属性値が一致する運用情報群に対応して運用グループの識別情報を生成することを特徴とする請求項１０に記載の運用割当装置。
【請求項１３】
運用割当装置による運用割当方法であって、
所定の期間毎及び輸送手段毎の運用を示す運用情報内の所定の属性値が一致する運用の集合である運用グループの識別情報を、前記所定の期間毎及び前記輸送手段毎に区別される割当対象項目に対して割り当てていく運用グループ割当ステップと、
前記運用グループ割当ステップにより全ての割当対象項目に対して前記運用グループの識別情報が割り当てられた後、所定の制約条件に含まれる運用と運用グループとの関連性に係る制約条件に従って、前記所定の期間毎及び前記輸送手段毎に区別される割当対象項目に対して、前記運用の識別情報を割り当てていく運用割当ステップとを含むことを特徴とする運用割当方法。
【請求項１４】
コンピュータに、
所定の期間毎及び輸送手段毎の運用を示す運用情報内の所定の属性値が一致する運用の集合である運用グループの識別情報を、前記所定の期間毎及び前記輸送手段毎に区別される割当対象項目に対して割り当てていく運用グループ割当ステップと、
前記運用グループ割当ステップにより全ての割当対象項目に対して前記運用グループの識別情報が割り当てられた後、所定の制約条件に含まれる運用と運用グループとの関連性に係る制約条件に従って、前記所定の期間毎及び前記輸送手段毎に区別される割当対象項目に対して、前記運用の識別情報を割り当てていく運用割当ステップとを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所定の期間毎及び輸送手段毎に運用を決定するための技術に関する。
【背景技術】
【０００２】
従来、車両運用計画の作成は、担当者の経験と勘に基づいて行なわれていた。しかし、人の手による計画の作成では時間もかかり、特に、近年では、より多くの車両が導入されてきていることから限界があった。そうした中、最近では、車両運用計画の作成に必要な列車編成、ダイヤ、点検計画等のデータを入力し、所望の制約条件に従って計算機によって車両運用計画を作成するものが提案されている。
【０００３】
例えば、特許文献１には、運行機材の制約条件を入力して、運用接続コードを作成し、運用接続コードの初期実行可能解を生成し、運用接続コードの確率的な組み替え、運用接続コードの運用接続行列への変換、及び、運用接続行列の評価を繰り返すことにより最適解を探索するものが開示されている。
【０００４】
【特許文献１】特開平８−８５４５９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に開示される発明は、運用接続コードの確率的な組み替え、運用接続コードの運用接続行列への変換、及び、運用接続行列の評価の３つの処理を繰り返し行なう必要があるため、最適解を求めるまでの求解時間が長くなってしまう。
【０００６】
そこで、本発明の目的は、解空間における解候補の数を減らし、求解時間を短縮することにある。
【課題を解決するための手段】
【０００７】
本発明の運用割当装置は、所定の期間毎及び輸送手段毎の運用を示す運用情報内の所定の属性値が一致する運用の集合である運用グループの識別情報を、前記所定の期間毎及び前記輸送手段毎に区別される割当対象項目に対して割り当てていく運用グループ割当手段と、前記運用グループ割当手段により全ての割当対象項目に対して前記運用グループの識別情報が割り当てられた後、所定の制約条件に含まれる運用と運用グループとの関連性に係る制約条件に従って、前記所定の期間毎及び前記輸送手段毎に区別される割当対象項目に対して、前記運用の識別情報を割り当てていく運用割当手段とを有することを特徴とする。
本発明の運用割当方法は、運用割当装置による運用割当方法であって、所定の期間毎及び輸送手段毎の運用を示す運用情報内の所定の属性値が一致する運用の集合である運用グループの識別情報を、前記所定の期間毎及び前記輸送手段毎に区別される割当対象項目に対して割り当てていく運用グループ割当ステップと、前記運用グループ割当ステップにより全ての割当対象項目に対して前記運用グループの識別情報が割り当てられた後、所定の制約条件に含まれる運用と運用グループとの関連性に係る制約条件に従って、前記所定の期間毎及び前記輸送手段毎に区別される割当対象項目に対して、前記運用の識別情報を割り当てていく運用割当ステップとを含むことを特徴とする。
本発明のプログラムは、コンピュータに、所定の期間毎及び輸送手段毎の運用を示す運用情報内の所定の属性値が一致する運用の集合である運用グループの識別情報を、前記所定の期間毎及び前記輸送手段毎に区別される割当対象項目に対して割り当てていく運用グループ割当ステップと、前記運用グループ割当ステップにより全ての割当対象項目に対して前記運用グループの識別情報が割り当てられた後、所定の制約条件に含まれる運用と運用グループとの関連性に係る制約条件に従って、前記所定の期間毎及び前記輸送手段毎に区別される割当対象項目に対して、前記運用の識別情報を割り当てていく運用割当ステップとを実行させることを特徴とする。
【発明の効果】
【０００８】
本発明においては、運用情報内の所定の属性値が一致する運用の集合である運用グループの識別情報を割り当てた後、運用の識別情報を割り当てていくようにしているため、解空間における解候補の数を減らすことが可能となり、求解時間を短縮することができる。
【発明を実施するための最良の形態】
【０００９】
以下、本発明を適用した好適な実施形態を、添付図面を参照しながら詳細に説明する。
【００１０】
図１は、本発明の実施形態に係る運用割当装置１００の機能的な構成を示すブロック図である。運用割当装置１００は、例えばＰＣ等の情報処理装置等によって構成することができる。
【００１１】
本実施形態に係る運用割当装置１００は、図１に示すように、運用グループ割当部１０１、制約検査部１０２、運用割当部１０３、最適解導出部１０４、出力制御部１０５及び制約条件ＤＢ（データベース）１０６により構成される。
【００１２】
運用グループ割当部１０１は、日毎及び編成毎に区別される各割当対象項目（第１の割当対象項目）に対して、運用グループ識別情報（変数）を割り当てる。つまり、表１に示す日毎編成毎運用グループテーブル内の、日毎及び編成毎に区別される各割当対象項目に対して、運用グループ識別情報が割り当てられることになる。
【００１３】
【表１】
0005041942.tif 000002
【００１４】
ここでいう運用グループ識別情報とは、運用グループを識別するための情報であり、運用グループを一意に特定可能な例えば値等によって示される情報である。また、編成とは、後述する運用の決定対象となる単位車両のことをいう。運用グループとは、各日毎に、次の表２に示す全ての属性値が一致する運用を同一グループとしてまとめたものである。即ち、運用の内容を表す運用情報は、その属性値として、編成種別、始端駅、終端駅、始端番線、終端番線、始端接続、終端接続、始端位置及び終端位置を含む。その他に、運用の属性値として、走行キロ数（運用距離）等が含まれる。なお、表２は飽くまでも一例であって、特定の属性値が一致する運用であれば同一の運用グループとしてもよい。
【００１５】
【表２】
0005041942.tif 000003
【００１６】
なお、編成種別とは、当該編成の種別のことであり、本実施形態においては、２種類の編成種別“Ａ”、“Ｂ”を想定する。始端駅とは、当該運用における最初の出発地点となる駅や基地、終端駅とは、当該運用における最後の到着地点となる駅や基地のことをいう。始端番線とは、始端駅において編成が停車している番線、終端番線とは、終端駅において編成が停車している番線のことをいう。始端接続とは、始端駅における編成の接続状態、終端接続とは、終端駅における編成の接続状態のことをいう。始端位置、終端位置とは、始端駅、終端位置において編成がどの方向の位置に停止しているかを示すものであり、例えば北側に位置しているか、南側に位置しているかを示す。北側とは、終端駅又は始端駅において、当該運用の編成が線路上において北側に位置し、南側とは、終端駅又は始端駅において、当該運用の編成が線路上において南側に位置することを意味する。
【００１７】
同一グループ内の運用は、運用の連続性の観点から同一視することができる。ここで、運用グループ識別情報は、１〜最大運用グループ数までの値をとり得る。即ち、変数である運用グループ識別情報のドメインには、１〜最大運用グループ数までの値が含まれる。最大運用グループ数とは、日毎の運用グループの最大値である。
【００１８】
運用割当部１０３は、日毎及び編成毎に区別される各割当対象項目に対して、運用識別情報（変数）を割り当てる。つまり、表３に示す運用割当対象テーブル内の、日毎及び編成毎に区別される各割当対象項目（第２の割当対象項目）に対して、運用識別情報が割り当てられることになる。このように、本実施形態においては、日毎及び編成毎に区別される各割当対象項目に対して運用識別情報を割り当てることにより、各編成が日毎にどのような運用を行なうのかを決定することができる。
【００１９】
【表３】
0005041942.tif 000004
【００２０】
ここでいう運用識別情報とは、運用を識別するための情報であり、運用を一意に特定可能な例えば値等によって示される情報である。運用識別情報は、１〜運用数までの値をとり得る。即ち、変数である運用識別情報のドメインには、１〜運用数までの値が含まれる。運用数とは、日毎に想定している運用の数である。
【００２１】
なお、表１、表３に対応するデータは、例えばＣＰＵ３０１のワークエリアであるＲＡＭ３０２の一部記憶領域に格納されており、ここに、運用グループ割当部１０１、運用割当部１０３によって値が書き込まれる。
【００２２】
制約検査部１０２は、運用グループ割当部１０１によって表１のテーブルの各割当対象項目に運用グループ識別情報が割り当てられていく度に、以降の割当対象項目に割り当てられる運用グループ識別情報が制約条件を満たすか否かを検査する。また、制約検査部１０２は、運用割当部１０３によって表３のテーブルの各割当対象項目に運用識別情報が割り当てられていく度に、以降の割当対象項目に割り当てられる運用識別情報が制約条件を満たすか否かを検査する。
【００２３】
最適解導出部１０４は、制約検査部１０２によって制約違反が検知されることなく、表１、表３の全ての割当対象項目に対して運用グループ識別情報、運用識別情報が割り当てられた場合、そのときの表３に対する運用識別情報の割り当て結果を最適解として決定する。
【００２４】
出力制御部１０５は、最適解導出部１０４によって決定された最適解の内容を出力装置１０７によって出力させる。
【００２５】
制約条件ＤＢ１０６は、運用グループ割当部１０１や運用割当部１０３が値を割り当てる度に制約検査部１０２によって読み出される制約条件を格納している。制約検査部１０２は、制約条件ＤＢ１０６に格納される制約条件を読み出すことにより、上述した制約条件の検査を行なう。
【００２６】
図２は、本実施形態に係る運用割当装置１００による解探索処理について説明するための図であり、解空間である探索木を模式的に示している。この解探索処理は、運用グループ割当部１０１、制約検査部１０２及び運用割当部１０３によって行なわれる。
【００２７】
図２において、２０１は、運用グループ識別情報の割当対象、即ち、表１の各割当対象項目である。２０２は、探索木の枝であり、割り当てる運用グループ識別情報、即ち、運用グループ識別情報のドメインに含まれる、１〜最大運用グループ数までの何れかの値であることを示している。なお、２０２は、それぞれ異なる運用グループ識別情報である。
【００２８】
２０３は、運用識別情報の割当対象である。即ち、表３の各割当対象項目である。２０４は、探索木の枝であり、割り当てる運用識別情報を示している。即ち、運用識別情報のドメインに含まれる、１〜運用数までの何れかの値であることを示している。なお、２０４は、それぞれ異なる運用識別情報である。
【００２９】
運用グループ割当部１０１は、図２に示す探索木の上方から下方に向かって、割当対象項目２０１を選択し、選択した割当対象項目２０１に対して運用グループ識別情報２０２を割り当てるという処理を繰り返す。図２では、割当対象項目２０１は、２階層しか示されていないが、実際には、例えば表１の割当対象項目の数と同じ数の階層が存在する。このように運用グループ識別情報２０２が割り当てられる度に、制約検査部１０２は、以降の運用グループ識別情報２０２の割り当て対象となる各割当対象項目２０１のドメインに含まれる値のうち、制約条件を違反する値（割り当て不可能な値）を削除する（枝（解候補）を削除する）。その結果、割り当て可能な値が存在しなくなった割当対象項目が生じた場合（枝が全て削除された割当対象項目が存在する場合）、運用グループ割当部１０１は、一つ上の割当対象項目２０１に戻り、異なる運用グループ識別情報２０２を割り当てて、解探索処理を継続する。
【００３０】
また、運用割当部１０３は、運用グループ割当部１０１により表１の全ての割当対象項目２０１に対して運用グループ識別情報２０２が割り当てられた後、運用グループ割当部１０１と同様の解探索処理を開始する。図２では、割当対象項目２０３は、２階層しか示されていないが、実際には、例えば表３の割当対象項目の数と同じ数の階層が存在する。このように運用識別情報２０４が割り当てられる度に、制約検査部１０２は、以降の運用識別情報２０４の割り当て対象となる各割当対象項目２０３のドメインに含まれる値のうち、制約条件を違反する値（割り当て不可能な値）を削除する（枝（解候補）を削除する）。その結果、割り当て可能な値が存在しなくなった割当対象項目２０３が生じた場合（枝が全て削除された割当対象項目が存在する場合）、運用割当部１０３は、一つ上の割当対象項目２０３に戻り、異なる運用識別情報２０４を割り当てて、解探索処理を継続する。
【００３１】
ここで、運用グループ割当部１０１及び運用割当部１０３が割当対象項目２０１，２０３の選択順序を決定する際の基準について説明する。
【００３２】
運用グループ割当部１０１及び運用割当部１０３は、複数個ある割当対象項目の中から、どの割当対象項目から順に運用グループ識別情報や運用識別情報を割り当てていくかを次の観点から決める。
・割り当て可能な値の個数が少ない割当対象項目から先に選択する。
・検査（或いは０日（今日））と次の検査とに挟まれた期間の一日当たりに割り当てられる走行キロ数が小さい割当対象項目から先に選択する。
ここで、検査（或いは０日）は、表４中の○の部分に相当し、検査（或いは０日）と検査とに挟まれた期間は、表４中の斜線部分に相当する。また、検査（或いは０日）と次の検査とに挟まれた期間に割り当て可能な走行キロ数は、後述する運用ロック制約条件と検査取り込みキロ数制約条件とから割り出すことができる。即ち、運用ロック制約条件では、該当する日及び編成に割り当てなければならない運用が予め決まっており、検査取り込みキロ数制約条件では、上記期間における走行キロ数の和と、上記該当する日及び編成における走行キロ数とを足し合わせた走行キロ数に上限値を設けているため、上記期間における一日当たりに割り当てられる走行キロ数を求めることができる。
【００３３】
【表４】
0005041942.tif 000005
【００３４】
先ず、運用グループ割当部１０１及び運用割当部１０３は、複数個ある割当対象項目の中から、割り当て可能な値（割り当て候補の運用グループ識別情報）の個数が少ない割当対象項目から先に選択していき、もし、割り当て可能な値の個数が同じである割当対象項目が存在すれば、一日当たりに割り当て可能な走行キロ数が小さい方を先に選択する。なお、各割当対象項目に対する割り当て可能な値は、上述した制約条件を通じた枝の削除によってその数が減少していく。割当対象項目の選択の都度、その時点における割り当て可能な値の個数が少ないものから先に選択されることになる。
【００３５】
このように、割り当て可能な値の個数が少ない割当対象項目から先に選択していくことにより、解空間における解探索処理を高速に行なうことが可能となる。また本実施形態では、一日当たりに割り当て可能な走行キロ数が小さい方を先に選択している。一日当たりに割り当て可能な走行キロ数が小さい程、走行キロの制限を超過しないように運用グループを割り当てることに対する制限が厳しい。本実施形態では、そのような割り当てが困難な項目程先に割り当てを行うことにより、将来に禍根を残さないようにしている。
【００３６】
次に、選択された割当対象項目に対して割り当てる運用グループ識別情報の選択方法について説明する。
【００３７】
運用グループ割当部１０１が割り当てる運用グループ識別情報を選ぶ際の選択基準は、次の通りである。
・該当する運用グループに属する運用の運用情報の一属性値である走行キロ数の最小値の小さい順に運用グループ識別情報を選択する。
表５は、５つの運用について、それぞれの走行キロ数と運用グループ識別情報が対応付けられている。更に、表５には、各運用グループに属する運用の中からキロ数の最も小さい運用を代表として選び、代表に○印を付けた状態を表している。
【００３８】
【表５】
0005041942.tif 000006
【００３９】
表６は、運用グループ毎に、所属する運用の走行キロ数の最小値を対応付けた状態を表している。この例では、運用グループ識別情報“２”、“１”、“３”の順番で運用グループ識別情報が割り当てられることになる。
【００４０】
本実施形態では、一日当たりに割り当て可能な走行キロ数が小さい方の項目を先に選択しているので、運用グループを選ぶ際には走行キロ数の小さい運用が含まれている運用グループを先に割り当てるようにしている。即ちここでは、一日当たりに割り当て可能な走行キロ数が小さい項目の場合、後で運用を選ぶ段になったときに、走行距離が十分小さい運用が運用グループの中に含まれていないと、結局割り当てに失敗してしまうため、そのようなことを起こりにくくしている。
【００４１】
【表６】
0005041942.tif 000007
【００４２】
一方、運用割当部１０３が、選択された割当対象項目に対し、割り当てる運用識別情報を選ぶ際の選択基準は、運用情報の一属性値である走行キロ数の大きい順に運用識別情報を割り当てていく。表５に示す例では、対象となる割当対象項目に運用グループ識別情報“１”が割り当てられている場合、当該割当対象項目と同じ日及び編成に対応する割当対象項目に対して、運用識別情報“１”、“２”の順番で運用識別情報が割り当てられることになる。
【００４３】
このように本実施形態では、走行キロ数の大きい順に、割り当てる運用識別情報を選択している。割り当てが可能な限り、走行キロ数が大きい運用を割り当ててしまうと、同一の日の他の編成に割り当てるための運用としては、走行キロ数の小さい運用を残しておくことができる。即ちここでは、なるべく将来に禍根を残さないようにしている。
【００４４】
図３は、本実施形態に係る運用割当装置１００のハードウェア構成を示すブロック図である。
【００４５】
ＣＰＵ３０１は、システムバスに接続される各デバイスやコントローラを統括的に制御する。ＲＯＭ３０３又はＨＤ（ハードディスク）３０９には、ＣＰＵ３０１の制御プログラムであるＢＩＯＳ（ＢａｓｉｃＩｎｐｕｔ／０ｕｔｐｕｔＳｙｓｔｅｍ）やオペレーティングシステムプログラム、運用割当装置１００が実行する例えば図４に示す処理のプログラム等が記憶されている。
【００４６】
なお、図３の例では、ＨＤ３０９は運用割当装置１００の内部に配置された構成としているが、他の実施形態としてＨＤ３０９に相当する構成が運用割当装置１００の外部に配置された構成としてもよい。また、本実施形態に係る例えば図４に示す処理を行なうためのプログラムは、フレキシブルディスク（ＦＤ）やＣＤ−ＲＯＭ等、コンピュータ読み取り可能な記録媒体に記録され、それらの記録媒体から供給される構成としてもよいし、インターネット等の通信媒体を介して供給される構成としてもよい。
【００４７】
ＲＡＭ３０２は、ＣＰＵ３０１の主メモリ、ワークエリア等として機能する。ＣＰＵ３０１は、処理の実行に際して必要なプログラム等をＲＡＭ３０２にロードして、プログラムを実行することで各種動作を実現するものである。
【００４８】
ＨＤ３０９やＦＤ３０８は、外部メモリとして機能とする。ＣＰＵ３０１は、処理の実行に際して必要なプログラム等をＲＡＭ３０２にロードして、プログラムを実行することで各種動作を実現するものである。
【００４９】
ディスクコントローラ３０７は、ＨＤ３０９やＦＤ３０８等の外部メモリヘのアクセスを制御する。通信Ｉ／Ｆコントローラ３０６は、インターネットやＬＡＮと接続し、例えばＴＣＰ／ＩＰによって外部との通信を制御するものである。
【００５０】
ディスプレイコントローラ３１０は、ディスプレイ３１１における画像表示を制御する。
【００５１】
ＫＢコントローラ３０４は、ＫＢ（キーボード）３０５からの操作入力を受け付け、ＣＰＵ３０１に対して送信する。なお、図示していないが、ＫＢ３０５の他に、マウス等のポインティングデバイスもユーザの操作手段として本実施形態に係る運用割当装置１００に適用可能である。
【００５２】
図１に示す、運用グループ割当部１０１、制約検査部１０２、運用割当部１０３及び最適解導出部１０４は、例えばＨＤ３０９内に記憶され、必要に応じてＲＡＭ３０２にロードされるプログラム及びそれを実行するＣＰＵ３０１によって実現される構成である。
【００５３】
また、出力制御部１０５は、例えば、必要に応じてＲＡＭ３０２にロードされるプログラム、それを実行するＣＰＵ３０１及びディスプレイコントローラ３１０によって実現される構成である。出力装置１０７は、例えばディスプレイ３１１に相当する構成である。制約条件ＤＢ１０６は、ＨＤ３０９又はＲＡＭ３０２の一部記憶領域に格納されるものである。
【００５４】
次に、本実施形態に係る運用割当装置１００の動作を、図４のフローチャートを参照しながら説明する。
【００５５】
先ず、運用グループ割当部１０１は、表５、表６を用いて説明した方法によって、例えば表１の各割当対象項目を一つ選択する（ステップＳ４０１）。次に、運用グループ割当部１０１は、上述した運用グループ識別情報の選択方法によって運用グループ識別情報を選択し、ステップＳ４０１にて選択された割当対象項目に割り当てる（ステップＳ４０２）。
【００５６】
続いて、制約検査部１０２は、以降の解探索処理において対象となる各割当対象項目のドメインに含まれる値のうち、制約条件を違反する値を削除する（ステップＳ４０３）。
【００５７】
続いて、運用グループ割当部１０１は、表１の全ての割当対象項目に運用グループ識別情報を割り当てたか否かを判定する（ステップＳ４０４）。運用グループ識別情報が割り当てられていない割当対象項目が存在する場合、処理はステップＳ４０１に戻り、運用グループ割当部１０１は、次の割当対象項目を選び、運用グループ識別情報を割り当てる。但し、今回のステップＳ４０３において、以降の解探索処理の対象となる割当対象項目のうち、割り当てる値が存在しなくなった割当対象項目が生じた場合、一つ前の割当対象項目に戻り、他の運用グループ識別情報を割り当てることになる。
【００５８】
上述した処理を繰り返し、全ての割当対象項目に運用グループ識別情報が割り当てられると、運用割当部１０３が起動する。
【００５９】
運用割当部１０３は、同じく表５、表６を用いて説明した方法によって、例えば表３の各割当対象項目を一つ選択する（ステップＳ４０５）。次に、運用割当部１０３は、上述した運用識別情報の選択方法によって運用識別情報を選択し、ステップＳ４０５にて選択された割当対象項目に割り当てる（ステップＳ４０６）。
【００６０】
続いて、制約検索部１０２は、以降の解探索処理において対象となる各割当対象項目のドメインに含まれる値のうち、制約条件を違反する値を削除する（ステップＳ４０７）。
【００６１】
続いて、運用割当部１０３は、表３の全ての割当対象項目に運用識別情報を割り当てたか否かを判定する（ステップＳ４０８）。運用識別情報が割り当てられていない割当対象項目が存在する場合、処理はステップＳ４０５に戻り、運用割当部１０３は、次の割当対象項目を選び、運用識別情報を割り当てる。但し、今回のステップＳ４０５において、以降の解探索処理の対象となる割当対象項目のうち、割り当てる値が存在しなくなった割当対象項目が生じた場合、一つ前の割当対象項目に戻り、他の運用識別情報の割り当てることになる。
【００６２】
上述した処理を繰り返し、全ての割当対象項目に運用識別情報が割り当てられると、最適解導出部１０４は、その運用識別情報の割り当て結果を最適解として決定する。出力制御部１０５は、最適解導出部１０４によって決定された最適解の内容を出力装置１０７によって出力させる。
【００６３】
次に、制約検査部１０２で用いられる制約条件について説明する。本実施形態においては、次の制約条件を設けたものとする。これらの制約条件の情報は、制約条件ＤＢ１０６に格納されている。
（１）運用グループ制約条件
（２）運用グループ出現回数制約条件
（３）運用に対する排他制約条件
（４）運用ロック制約条件
（５）編成種別制約条件
（６）各種連続性制約条件
（７）位置連続性制約条件
（８）検査取り込みキロ数制約条件
【００６４】
先ず、（１）運用グループ制約条件について説明する。この制約条件の対象は、運用識別情報及び運用グループ識別情報である。この制約条件は、運用識別情報と運用グループ識別情報とを関連付けるための制約条件である。日毎、編成毎に次の式で表現される。
運用グループ識別情報［日、編成］＝運用グループ識別情報［日、運用識別情報［日、編成］］
この制約条件は、運用グループの定義から、運用グループの属性値としての編成種別と、運用の属性値としての編成種別とが一致している必要があるために設けられた制約条件である。ここでは、日毎、運用毎に、その運用の所属する運用グループの運用グループ識別情報を表す、表７に示すような定数配列が予め用意されているものとする。
【００６５】
【表７】
0005041942.tif 000008
【００６６】
なお、上記式の左辺の変数“運用グループ識別情報［日、編成］”は、日毎、編成毎に割り当てられる運用グループ識別情報の変数であり、表１の各項目に割り当てられる値である。
【００６７】
また、上記式の右辺の定数“運用グループ識別情報［日、運用識別情報［日、編成］］”のインデックスにおける“運用識別情報［日、編成］”は、日毎、編成毎に割り当てられる運用識別情報の変数であり、表３の各項目に割り当てられる値である。
【００６８】
即ち、本制約条件は、表１の割当対象項目に割り当てられた運用グループ識別情報と、表３の割当対象項目に割り当てられる運用識別情報に示される運用が属する運用グループ識別情報とが、任意の日及び任意の編成毎夫々一致しているか否かを検査するための制約条件である。
【００６９】
上述したステップＳ４０１においては、表７に日毎に記録されている運用グループ識別情報から各割当対象項目に割り当てることができる。さらに、運用識別情報も、ＲＡＭ３０２内等において別途設けられたテーブル内に予め日毎に登録されており、そのテーブルから読み出して、表３の各割当対象項目に対して割り当てることができる。運用グループの割り当て方法の他の例としては、同じくＲＡＭ３０２内等に予め登録される運用情報群のうち、表２に示す各属性値が一致するものを同一の運用グループとして日毎にまとめ、運用グループ識別情報を生成してもよい。この処理は、運用グループ割当部１０１による処理としてもよいし、ＨＤ３０９等に格納されるプログラム及びそれを実行するＣＰＵ３０１によって構成される他の機能構成によって実現してもよい。
【００７０】
次に、（２）運用グループ出現回数制約条件について説明する。この制約条件の対象は、運用グループ識別情報である。また、制約条件の内容は、運用グループ識別情報の変数に対して、同一の値を取る変数の個数に制約をかけるための制約条件である。日別にみると、同一の値を取る運用グループ変数の個数は、定数配列の表７から既知である。その個数は、当該運用グループに所属する運用の個数に等しい。次の表８は、或る日に着目した場合の、各運用グループ毎に、所属する運用の個数の例を表したものである。このような制約条件を設けたのは、運用グループの定義より、運用グループの出現回数は、所属する運用の数と等しいことが必要であるからである。
【００７１】
【表８】
0005041942.tif 000009
【００７２】
次に、（３）運用に対する排他制約条件について説明する。この制約条件の対象は、運用識別情報である。この制約条件は、ある日に着目すると、運用識別情報は編成毎に異なることを実現するための制約条件である。これは、同一の運用識別情報が複数の編成に紐つくことはないためである。
【００７３】
次に、（４）運用ロック制約条件について説明する。この制約条件の対象は、運用識別情報及び運用グループ識別情報である。この制約条件は、ある日のある編成に対し、運用が固定されていることを表現するための制約条件である。ここでは、広義の運用ロックを対象とする。広義の運用ロックとは、ある日のある編成に対して運用が予め決まっている、いわゆる運用ロック（狭義の運用ロック）だけではなく、仕業検査以外の検査や当日のように、事実上、ある日のある編成に対して運用が決まっているために、狭義の運用ロックと同様に扱うことができる場合も対象とする。また、運用が決まっているということは、運用グループも決まることになり、運用識別情報の変数だけでなく、運用グループ識別情報の変数に対しても、この制約が課せられることになる。表９は、運用ロックが課せられた日及び編成の組み合わせを○で示している。
【００７４】
【表９】
0005041942.tif 000010
【００７５】
次に、（５）編成種別制約条件について説明する。この制約条件の対象は、運用グループ識別情報である。この制約条件は、運用グループの一属性値である編成種別と編成の一属性値である編成種別とが一致していなければならないことを表現するための制約条件である。日毎、編成毎に次の式で表現される。下記の制約条件中に現れる変数は、運用グループ識別情報の変数のみであるが、既に述べた運用グループ識別情報の変数と運用識別情報の変数との関係から、運用識別情報の変数に対して同様の制約を課す必要がないことは明らかである。
編成種別［日、運用グループ識別情報［日、編成］］＝編成種別［編成］
ここでは、編成毎に、その編成種別を表す、表１０に示すような定数配列が予め用意されているものとする。
【００７６】
【表１０】
0005041942.tif 000011
【００７７】
また、日毎、運用グループ毎に、その運用グループの編成種別を表す、表１１に示すような定数配列が予め用意されているものとする。
【００７８】
【表１１】
0005041942.tif 000012
【００７９】
なお、上記式の左辺の変数“運用グループ識別情報［日、編成］”は、日毎、編成毎に割り当てられる運用グループ識別情報の変数であり、表１２の各項目に割り当てられる値である。
【００８０】
【表１２】
0005041942.tif 000013
【００８１】
次に、（６）各種連続性制約条件について説明する。この制約条件の対象は、運用識別情報及び運用グループ識別情報である。この制約条件は、連続する２日間において、同一の編成に割り当てられる運用識別情報が、ある日の終端駅における状態と次の日の始端駅における状態とが連続性を満たす（同じである）必要があることを表現するための制約である。以下の制約条件中に現れる変数は、運用グループ識別情報の変数のみであるが、既に述べた運用グループ識別情報の変数と運用識別情報の変数との関係から、運用識別情報の変数に対して同様の制約を課す必要がないことは明らかである。本制約条件は、日毎、編成毎に次の式で表現される。
終端駅［日−１、運用グループ識別情報［日−１、編成］］＝始端駅［日、運用グループ識別情報［日、編成］］
ここでは、日毎、運用グループ識別情報毎に、終端駅を表す定数配列が予め用意されていることを前提としている。また、日毎、運用グループ識別情報毎に、始端駅を表す定数配列が予め用意されていることを前提としている。即ち、本実施形態では、日毎、運用グループ識別情報毎に終端駅を表す表１３に示すような定数配列と、日毎、運用グループ識別情報毎に始端駅を表す表１４に示すような定数配列とが予め用意されている。
【００８２】
【表１３】
0005041942.tif 000014
【００８３】
【表１４】
0005041942.tif 000015
【００８４】
なお、上記式のインデックスにおける“運用グループ識別情報［日−１、編成］”、“運用グループ識別情報［日、編成］”は、日毎、編成毎に割り当てられる運用グループ識別情報の変数であり、表１の各項目に割り当てられる値である。
【００８５】
次に、上記連続性について番線を例に挙げて説明すると、日毎、編成毎に次の式で表現される。
終端番線［日−１、運用グループ識別情報［日−１、編成］］＝始端番線［日，運用グループ識別情報［日、編成］］
ここでは、日毎、運用グループ識別情報毎に、終端番線を表す定数配列が予め用意されていることを前提としている。また、日毎、運用グループ識別情報毎に、始端番線を表す定数配列が予め用意されていることを前提としている。即ち、本実施形態では、日毎、運用グループ識別情報毎に終端番線を表す表１５に示すような定数配列と、日毎、運用グループ識別情報毎に始端番線を表す表１６に示すような定数配列とが予め用意されている。
【００８６】
【表１５】
0005041942.tif 000016
【００８７】
【表１６】
0005041942.tif 000017
【００８８】
また、上記式のインデックスにおける“運用グループ識別情報［日−１、編成］”、“運用グループ識別情報［日、編成］”は、日毎、編成毎に割り当てられる運用グループ識別情報の変数であり、表１と同様の表の各項目に割り当てられる値である。なお、基地内においては、番線の概念はない。従って、始端駅、終端駅が基地であれば、全て同じ値を与えるものとする。但し、その値は、表１５、表１６に設定されている値とは異なる。
【００８９】
次に、上記連続性について接続を例に挙げて説明すると、日毎、編成毎に次の式で表現される。
終端接続［日−１、運用グループ識別情報［日−１、編成］］＝始端接続［日、運用グループ識別情報［日、編成］］
本制約条件では、日毎、運用グループ識別情報毎に次の表１７から該当するコードを選択し、上記式に適用する。
【００９０】
【表１７】
0005041942.tif 000018
【００９１】
また、上記式のインデックスにおける“運用グループ識別情報［日、編成］”は、日毎、編成毎に割り当てられる運用グループ識別情報の変数であり、上記表１の各項目に割り当てられる値である。
【００９２】
即ち、本制約条件は、次の制約を課している。例えば、ある日の当該運用グループの終端駅が基地、当該運用グループの編成種別が“Ａ”、そして、その終端駅における併結状態が“Ａ”単独である場合、上記式の左辺は“１”となる。また、次の日における当該編成の運用の始端駅が基地、当該運用グループの編成種別が“Ａ”、そして、その始端駅における併結状態が“Ａ”単独である場合、上記式の右辺は“１”となる。従って、連続する２日間において、このような接続状態である場合には、上記式を満たし、本制約条件を満たすこととなる。
【００９３】
ある日の終端駅における当該運用グループの編成種別が“Ａ”である場合について、制約条件を満たすか否かの結果の一部を以下に示す。
・ある日の当該運用グループの終端駅における併結状態が“Ａ”であり、また、次の日の当該編成の運用グループの編成種別が“Ａ”であって、且つ次の日の始端駅における当該編成の運用グループの併結状態が“Ａ”であれば、終端駅及び始端駅が基地であるか駅であるかに関わらず、制約条件を満たす。
・ある日の当該運用グループの終端駅における併結状態が“Ａ”であり、また、次の日の当該編成の運用グループの編成種別が“Ａ”であって、且つ次の日の始端駅における当該編成の運用グループの併結状態が“Ａ＋Ａ”であれば、次の日の始端駅が基地であれば、制約条件を満たし、次の日の始端駅が駅であれば、制約条件を違反する。
・ある日の当該運用グループの編成種別が“Ａ”であり、また、次の日の当該編成の運用グループの併結状態が“Ｂ”であって、且つ次の日の始端駅における当該編成の運用グループの併結状態が“Ａ＋Ｂ”であれば、次の日の始端駅が基地であるか駅であるかに関わらず、制約条件を違反する。
【００９４】
ここで、次の併結状態の関係に着目する。ある日の当該運用グループの終端駅が基地、当該運用グループの編成種別が“Ａ”、そして、その終端駅での併結状態が“Ａ＋Ｂ”であり、また、次の日における当該編成の運用グループの始端駅が基地、当該運用グループの編成種別が“Ａ”、そして、その始端駅での併結状態が“Ａ”単独や“Ａ＋Ａ”である場合、制約条件を違反となる。反対に、ある日の当該運用グループの終端駅が基地、当該運用グループの編成種別が“Ａ”、そして、その終端駅での併結状態が“Ａ”単独や“Ａ＋Ａ”であり、また、次の日における当該編成の運用グループの始端駅が基地、当該運用グループの編成種別が“Ａ”、そして、その始端駅での併結状態が“Ａ＋Ｂ”である場合も、制約条件を違反する。当該運用グループの編成種別が“Ｂ”である場合も同様である。
【００９５】
即ち、本制約条件においては、基地内では、連続する２日間において、ある日の併結状態が“Ａ＋Ｂ”以外の併結状態であるが、次の日に併結状態が“Ａ＋Ｂ”となることは制約違反となることを規定している。また、基地内において、ある日の併結状態が“Ａ＋Ｂ”であるが、次の日に併結状態が“Ａ＋Ｂ”以外の併結状態となることも制約違反としている。つまり、基地内では、日を跨いで、併結状態“Ａ＋Ｂ”の編成を分けて他の併結状態としたり、編成を併せて併結状態“Ａ＋Ｂ”とすることは制約違反としている（基地内分併不可パターン制約（Ａ＋Ｂ））。
【００９６】
ここで、次の併結状態の関係にも着目する。ある日の当該運用グループの終端駅が駅、当該運用グループの編成種別が“Ａ”、そして、その終端駅での併結状態が或る併結状態であり、また、次の日における当該編成の運用グループの始端駅が駅、当該運用グループの編成種別が“Ａ”、そして、その始端駅での併結状態が上記併結状態とは異なる併結状態である場合、制約違反となる。当該運用グループの編成種別が“Ｂ”である場合も同様である。
【００９７】
即ち、本制約条件においては、駅内では、連続する２日間において、ある日の併結状態から次の日に他の併結状態となることは制約違反であることを規定している。つまり、駅内では、日を跨いで、ある併結状態の編成を分けて他の併結状態としたり、編成を併せて他の併結状態とすることは制約違反としている（駅内分併不可制約）。
【００９８】
次に、（７）位置連続性制約条件について説明する。この制約条件の対象は、運用識別情報である。また、制約条件の内容は、日毎、運用識別情報毎に次の式で表現される。
終端位置［日−１、運用識別情報［日−１、編成］］＝０・・・（式１）
又は、
始端位置［日、運用識別情報［日、編成］］・・・（式２）
又は、
終端位置［日−１、運用識別情報［日−１、編成］］＝始端位置［日、運用識別情報［日、編成］］・・・（式３）
本制約条件では、日毎、運用識別情報毎に次の表１８から該当するコードを選択し、上記式に適用する。
【００９９】
【表１８】
0005041942.tif 000019
【０１００】
なお、上記式のインデックスにおける“運用識別情報［日−１、編成］”及び“運用識別情報［日、編成］”は、上記表３の各項目に割り当てられる値である。
【０１０１】
即ち、本制約条件では、次の制約を課している。ある日の当該運用の終端駅が基地又は駅、当該運用の編成種別が“Ａ”、そして、その終端駅における当該運用の併結状態が“Ａ＋Ａ´”である場合、式１、式３の左辺は“１”となる。ここで、“Ａ´”とは、当該運用以外の運用の編成種別“Ａ”と同じ編成種別である。従って、式１は満たさない。但し、次の日における当該編成の運用の始端駅が基地又は駅、当該運用の編成種別が“Ａ”、そして、その始端駅における当該運用の併結状態が“Ａ＋Ａ´”である場合、式２の左辺、式３の右辺は“１”となる。従って、式２は満たさないが、式３を満たし、本制約条件を満たすことになる。
【０１０２】
なお、ある日の当該運用の編成種別が“Ａ”であって、その日の終端駅における当該運用の併結状態が“その他（Ａ単独、Ａ＋Ｂ）”である場合や、次の日における当該運用の編成種別が“Ａ”であって、その日の始端駅における当該運用の併結状態が“その他”である場合には、終端駅又は始端駅が基地であるか駅であるかに関わらず、式１又は式２を満たすので、本制約条件を満たすことになる。
【０１０３】
また、ある日の当該運用の編成種別が“Ｂ”であって、その日の終端駅における当該運用の併結状態が“Ｂ”単独又は“Ａ＋Ｂ”である場合や、次の日における当該運用の編成種別が“Ｂ”であって、その日の始端駅における当該運用の併結状態が“Ｂ”単独又は“Ａ＋Ｂ”である場合には、終端駅又は始端駅が基地であるか駅であるかに関わらず、式１又は式２を満たすので、本制約条件を満たすことになる。
【０１０４】
表１８中、併結状態として“Ａ＋Ａ´”と“Ａ´＋Ａ”の表記の違いは、“Ａ＋Ａ´”は当該運用が例えば北側に位置し、他の運用が南側に位置することを意味し、“Ａ´＋Ａ”はその反対を意味する。例えば、併結状態“Ａ＋Ａ´”は、編成種別“Ａ”である当該運用の編成が北側、編成種別“Ａ´”である運用の編成が南側の位置で互いに接続された状態である。
【０１０５】
ある日の終端駅における当該運用の編成種別が“Ａ”である場合について、制約条件を満たすか否かの結果の一部を以下に示す。
・ある日の終端駅における併結状態が“Ａ＋Ａ´”であり、また、次の日の当該編成の運用の編成種別が“Ａ”であって、且つ次の日の始端駅における当該編成の運用の併結状態が“Ａ＋Ａ´”であれば、始端駅が基地であるか駅であるかに関わらず、制約条件（式３）を満たす。
・ある日の終端駅における併結状態が“Ａ＋Ａ´”であり、また、次の日の当該編成の運用の編成種別が“Ａ”であって、且つ次の日の始端駅における当該編成の運用の併結状態“Ａ´＋Ｐ”であれば、始端駅が基地であるか駅であるかに関わらず、制約条件を違反する。
・ある日の終端駅における併結状態が“Ａ＋Ａ´”であり、また、次の日の当該編成の運用の編成種別が“Ａ”であって、且つ次の日の始端駅における当該編成の運用の併結状態“その他”であれば、始端駅が基地であるか駅であるかに関わらず、制約条件を違反する。
・ある日の終端駅における併結状態が“Ａ＋Ａ´”であり、また、次の日の当該編成の運用の編成種別が“Ｂ”であって、且つ次の日の始端駅における当該編成の運用の併結状態“Ｂ”単独又は“Ａ＋Ｂ”であれば、始端駅が基地であるか駅であるかに関わらず、制約条件を違反する。
【０１０６】
次に、ある日の終端駅における当該運用の編成種別が“Ｂ”である場合について、制約条件を満たすか否かの結果を以下に示す。
・ある日の終端駅における併結状態が“Ｂ”単独又は“Ａ＋Ｂ”であり、また、次の日の当該編成の運用の編成種別が“Ａ”であって、且つ次の日の始端駅における当該編成の運用の併結状態“Ａ＋Ａ´”であれば、始端駅が基地であるか駅であるかに関わらず、制約条件を違反する。
・ある日の終端駅における併結状態が“Ｂ”単独又は“Ａ＋Ｂ”であり、また、次の日の当該編成の運用の編成種別が“Ａ”であって、且つ次の日の始端駅における当該編成の運用の併結状態“Ａ´＋Ａ”であれば、始端駅が基地であるか駅であるかに関わらず、制約条件を違反する。
・ある日の終端駅における併結状態が“Ｂ”単独又は“Ａ＋Ｂ”であり、また、次の日の当該編成の運用の編成種別が“Ａ”であって、且つ次の日の始端駅における当該編成の運用の併結状態“その他”であれば、始端駅が基地であるか駅であるかに関わらず、制約条件（式１）を満たす。
・ある日の終端駅における併結状態が“Ｂ”単独又は“Ａ＋Ｂ”であり、また、次の日の当該編成の運用の編成種別が“Ｂ”であって、且つ次の日の始端駅における当該編成の運用の併結状態“Ｂ”単独又は“Ａ＋Ｂ”であれば、始端駅が基地であるか駅であるかに関わらず、制約条件（式１）を満たす。
【０１０７】
ここで、次の併結状態の関係に着目する。ある日の当該運用の終端駅が基地、当該運用の編成種別が“Ａ”、そして、その終端駅での併結状態が“Ａ＋Ａ´”であり、また、次の日における当該編成の運用の始端駅が基地、当該運用の編成種別が“Ａ”、そして、その始端駅での併結状態が“Ａ´＋Ａ”である場合、制約違反になる。その反対に、ある日の当該運用の終端駅が基地、当該運用の編成種別が“Ａ”、そして、その終端駅での併結状態が“Ａ´＋Ａ”であり、また、次の日における当該編成の運用の始端駅が基地、当該運用の編成種別が“Ａ”、そして、その始端駅での併結状態が“Ａ＋Ａ´”である場合、制約違反になる。終端駅及び始端駅が駅である場合も同様である。
【０１０８】
即ち、本制約条件においては、基地及び駅内では、連続する２日間において、ある日の併結状態が“Ａ＋Ａ´”であるが、次の日に併結状態が“Ａ´＋Ａ”となることは制約違反であることを規定している。反対に、基地及び駅内において、ある日の併結状態が“Ａ´＋Ａ”であるが、次の日に併結状態が“Ａ＋Ａ´”となることは制約違反であることを規定している。つまり、本制約条件においては、基地又は駅内において、日を跨いで、“Ａ”と“Ａ´”との編成位置を入れ換えることを禁止している（編成位置制約）。
【０１０９】
次の併結状態の関係についても着目する。ある日の当該運用の終端駅が基地、当該運用の編成種別が“Ａ”、そして、その終端駅での併結状態が“Ａ＋Ａ´”や“Ａ´＋Ａ”であり、また、次の日における当該編成の運用の始端駅が基地、当該運用の編成種別が“Ａ”、そして、その始端駅での併結状態が“その他”である場合、制約違反となる。反対に、ある日の当該運用の終端駅が基地、当該運用の編成種別が“Ａ”、そして、その終端駅での併結状態が“その他”であり、また、次の日における当該編成の運用の始端駅が基地、当該運用の編成種別が“Ａ＋Ａ´”や“Ａ´＋Ａ”である場合、制約違反となる。
【０１１０】
即ち、本制約条件においては、基地内では、連続する２日間において、ある日の併結状態が“Ａ＋Ａ´”や“Ａ´＋Ａ”であり、次の日の併結状態が“その他”となることは制約違反であることを規定している。反対に、基地内において、ある日の併結状態が“その他”であり、次の日の併結状態が“Ａ＋Ａ´”や“Ａ´＋Ａ”となることは制約違反であることを規定している。つまり、本制約条件においては、基地内において、日を跨いで、併結状態“Ａ＋Ａ´”や“Ａ´＋Ａ”の編成を分けて他の併結状態にすることを禁止している（基地内分併不可パターン制約（Ａ＋Ａ））。
【０１１１】
次に、（８）検査取り込みキロ数制約条件について説明する。この制約条件の対象は、運用識別情報である。本制約条件の内容は、編成毎に、検査日（或いは０日）から次の検査日に挟まれた期間毎に、次の式で表現される。
期間の初期走行キロ＋Σ走行キロ［日、運用［日、編成］］≦上限値
ここで、Σは、検査日（或いは０日）と次の検査日とに挟まれた期間中の各日の和をとることを表している。検査日（或いは０日）は、表４の○で示されている。即ち、本制約条件は、上述した運用ロック制約条件に応じて、表１９に示すように、○の部分に割り当てられる運用の属性値である走行キロ数と、斜線部分に対して割り当てられる各運用の属性値である走行キロ数の和との足し合わせ、予め設定された上限値を超えないようにするための制約条件である。即ち、この制約条件は、次の検査日までの総走行キロ数に上限を設けるための制約条件である。
【０１１２】
制約検査部１０２は、運用グループ割当部によって運用グループ識別情報が割り当てられる度、及び、運用割当部によって運用識別情報が割り当てられる度に、以上に説明した（１）〜（８）の制約条件を制約条件ＤＢ１０６から読み出し、制約検査を行なう。これにより、最終的に得られる各制約条件を満たす最適解は、実際の運用に支障がない適切な解となる。
【０１１３】
【表１９】
0005041942.tif 000020
【０１１４】
以上のように、本実施形態においては、運用情報内の所定の属性値が一致する運用の集合である運用グループの識別情報（運用グループ識別情報）を割り当てた後、運用の識別情報（運用識別情報）を割り当てていくようにしている。運用の種類のみを解候補とした解探索方法に比べ、幾つかの運用をまとめた運用グループという概念を採用して探索することにより解空間における解候補（枝）の数を削減することができる。また、運用と運用グループとの関連性に係る制約条件等、上述した各制約条件に基づいて、運用の解候補も削減しているため、解空間全体としての解候補（枝）の数を大幅に削減することが可能となり、求解時間を短縮することができる。
【０１１５】
なお、本実施形態においては、車両の運用を対象とした場合を例に挙げたが、本発明は、これに限らず、船舶、航空機等、様々な輸送手段の運用に適用可能であることは勿論である。
【０１１６】
また、日毎に運用グループ識別情報や運用識別情報を割り当てるようにしているが、本発明は、これに限らず、２日毎、一週間毎等、様々な期間毎にこれらの値を割り当ててもよい。
【図面の簡単な説明】
【０１１７】
【図１】本発明の実施形態に係る運用割当装置の機能的な構成を示すブロック図である。
【図２】本発明の実施形態に係る運用割当装置による解探索処理について説明するための図である。
【図３】本発明の実施形態に係る運用割当装置のハードウェア構成を示すブロック図である。
【図４】本発明の実施形態に係る運用割当装置の動作を示すフローチャートである。
【符号の説明】
【０１１８】
１００：運用割当装置
１０１：運用グループ割当部
１０２：制約検査部
１０３：運用割当部
１０４：最適解導出部
１０５：出力制御部
１０６：制約条件ＤＢ
１０７：出力装置
３０１：ＣＰＵ
３０２：ＲＡＭ
３０３：ＲＯＭ
３０４：ＫＢ（キーボード）コントローラ
３０５：ＫＢ（キーボード）
３０６：通信Ｉ／Ｆコントローラ
３０７：ディスクコントローラ
３０８：ＦＤ
３０９：ＨＤ
３１０：ディスプレイコントローラ
３１１：ディスプレイ
【図１】
0005041942.tif 000021
【図２】
0005041942.tif 000022
【図３】
0005041942.tif 000023
【図４】
0005041942.tif 000024