(57)【要約】【課題】より少ないステップ数で各運用に対して効率的に各資源を割り当てる。【解決手段】最初に、制約１０３で一意的に決まる各運用を機材に割り当てる。次に、運用が一意的に割り当てられなかった機材の各日付に対して、原計画０２における未割り当ての運用のなかから割り当て可能な運用の組合せを、先の制約を参照して検索する。１つの運用の組合せのみが検索されたとき、この検索された１つの運用の組合せを該当機材の未割り当ての各日付に割り当てる。次に、複数の運用の組合せが検索されたとき、各運用の組合せを該当機材の未割り当ての各日付に割り当てた場合における、運用が未割り当の他の機材に対する割り当て可能な運用の組合せ数を検出する。そして、検出された組合せ数が多い運用の組合せを前記該当資源の未割り当ての各時間に割り当てる。【選択図】図１
2005084813.tif 000002
【特許請求の範囲】
【請求項１】
複数の運用を時間毎に各資源に割り当てる資源割り当て計画作成装置に用いられる資源割り当て計画作成プログラムであって、
前記割り当て計画作成装置のコンピュータを、
各資源に対する運用の割り当てを制約する制約情報を保持する情報保持手段と、
指定時間にて各資源に実際に割り当てられた運用を示す割当実績情報を入力する割当実績情報入力手段と、
この入力された割当実績情報における各資源の指定時間以降の各時間に対して前記制約情報に基づいて割り当て可能な運用を検索する検索手段と、
この検索手段で検索された運用を該当資源の未割り当ての時間に割り当てる第１の割当手段と
して機能させるための資源割り当て計画作成プログラム。
【請求項２】
前記割り当て計画作成装置のコンピュータを、
前記第１の割当手段で運用が割り当てられなかった資源の各時間に対して、未割り当ての運用のなかから割り当て可能な運用の組合せを検索する組合せ検索手段と、
この組合せ検索手段で１つの運用の組合せのみが検索されたとき、この検索された１つの運用の組合せを該当資源の未割り当ての各時間に割り当てる第２の割当手段と、
前記組合せ検索手段で複数の運用の組合せが検索されたとき、各運用の組合せを該当資源の未割り当ての各時間に割り当てた場合における、運用が未割り当の他の資源に対する割り当て可能な運用の組合せ数を検出する組合せ数検出手段と、
この組合せ数検出手段で検出された組合せ数が多い運用の組合せを前記該当資源の未割り当ての各時間に割り当てる第３の割当手段と
して機能させるための請求項１記載の資源割り当て計画作成プログラム。
【請求項３】
複数の運用を時間毎に各資源に割り当てる資源割り当て計画作成装置に用いられる資源割り当て計画作成プログラムであって、
前記割り当て計画作成装置のコンピュータを、
各時間の運用を各資源に割り当てた原計画情報と、各資源に対する運用の割り当ての条件を原計画情報との関係において制約する制約情報とを保持する情報保持手段と、
現在時間にて各資源に実際に割り当てられた運用を示す割当実績情報を入力する割当実績情報入力手段と、
この入力された割当実績情報における各資源の現在時間以降の各時間に対して前記制約情報に基づいて前記原計画情報のなかから割り当て可能な運用を検索する検索手段と、
この検索手段で検索された運用を該当資源の未割り当ての時間に割り当てる割当手段と
して機能させるための資源割り当て計画作成プログラム。
【請求項４】
複数の運用を時間毎に各資源に割り当てる資源割り当て計画作成装置に用いられる資源割り当て計画作成プログラムであって、
前記割り当て計画作成装置のコンピュータを、
各時間の運用を各資源に割り当てた原計画情報と、各資源に対する運用の割り当ての条件を原計画情報との関係において制約する制約情報とを保持する情報保持手段と、
現在時間にて各資源に実際に割り当てられた運用を示す割当実績情報を入力する割当実績情報入力手段と、
この入力された割当実績情報の現在時間以降の各時間における各資源に一意的に割り当てられる各運用を前記制約情報に基づいて前記原計画情報から検索して該当時間に割り当てる第１の割当手段と、
この第１の割当手段で運用が一意的に割り当てられなかった資源の各時間に対して、前記原計画情報における未割り当ての運用のなかから割り当て可能な運用の組合せを検索する組合せ検索手段と、
この組合せ検索手段で１つの運用の組合せのみが検索されたとき、この検索された１つの運用の組合せを該当資源の未割り当ての各時間に割り当てる第２の割当手段と
して機能させるための資源割り当て計画作成プログラム。
【請求項５】
前記割り当て計画作成装置のコンピュータを、
前記組合せ検索手段で複数の運用の組合せが検索されたとき、各運用の組合せを該当資源の未割り当ての各時間に割り当てた場合における、運用が未割り当の他の資源に対する割り当て可能な運用の組合せ数を検出する組合せ数検出手段と、
この組合せ数検出手段で検出された組合せ数が多い運用の組合せを前記該当資源の未割り当ての各時間に割り当てる第３の割当手段と
して機能させるための請求項４記載の資源割り当て計画作成プログラム。
【請求項６】
前記入力された割当実績情報における各資源の現在時間以降の割り当て可能な運用を検索する時間の数に一定の上限値を設けたことを特徴とする請求項３から５のいずれか１項記載の資源割り当て計画作成プログラム。
【請求項７】
複数の運用を時間毎に各資源に割り当てる資源割り当て計画作成方法において、
各時間の運用を各資源に割り当てた原計画情報と、各資源に対する運用の割り当ての条件を原計画情報との関係において制約する制約情報とを保持する情報保持工程と、
現在時間にて各資源に実際に割り当てられた運用を示す割当実績情報を入力する割当実績情報入力工程と、
この入力された割当実績情報の現在時間以降の各時間における各資源に一意的に割り当てられる各運用を前記制約情報に基づいて前記原計画情報から検索して該当時間に割り当てる第１の割当工程と、
この第１の割当工程で運用が一意的に割り当てられなかった資源の各時間に対して、前記原計画情報における未割り当ての運用のなかから割り当て可能な運用の組合せを検索する組合せ検索工程と、
この組合せ検索工程で１つの運用の組合せのみが検索されたとき、この検索された１つの運用の組合せを該当資源の未割り当ての各時間に割り当てる第２の割当工程と、
前記組合せ検索工程で複数の運用の組合せが検索されたとき、各運用の組合せを該当資源の未割り当ての各時間に割り当てた場合における、運用が未割り当の他の資源に対する割り当て可能な運用の組合せ数を検出する組合せ数検出工程と、
この組合せ数検出工程で検出された組合せ数が多い運用の組合せを前記該当資源の未割り当ての各時間に割り当てる第３の割当工程と
を備えたことを特徴とする資源割り当て計画作成方法。
【請求項８】
複数の運用を時間毎に各資源に割り当てる資源割り当て計画作成装置において、
各時間の運用を各資源に割り当てた原計画情報と、各資源に対する運用の割り当ての条件を原計画情報との関係において制約する制約情報とを記憶する情報記憶部と、
現在時間にて各資源に実際に割り当てられた運用を示す割当実績情報を入力する割当実績情報入力手段と、
この入力された割当実績情報の現在時間以降の各時間における各資源に一意的に割り当てられる各運用を前記制約情報に基づいて前記原計画情報から検索して該当時間に割り当てる第１の割当手段と、
この第１の割当手段で運用が一意的に割り当てられなかった資源の各時間に対して、前記原計画情報における未割り当ての運用のなかから割り当て可能な運用の組合せを検索する組合せ検索手段と、
この組合せ検索手段で１つの運用の組合せのみが検索されたとき、この検索された１つの運用の組合せを該当資源の未割り当ての各時間に割り当てる第２の割当手段と、
前記組合せ検索手段で複数の運用の組合せが検索されたとき、各運用の組合せを該当資源の未割り当ての各時間に割り当てた場合における、運用が未割り当の他の資源に対する割り当て可能な運用の組合せ数を検出する組合せ数検出手段と、
この組合せ数検出手段で検出された組合せ数が多い運用の組合せを前記該当資源の未割り当ての各時間に割り当てる第３の割当手段と
を備えたことを特徴とする資源割り当て計画作成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の運用を時間毎に各資源に割り当てる資源割り当て計画作成装置に適用される資源割り当て計画作成プログラム、資源割り当て計画計画作成方法、及び資源割り当て計画作成装置に関する。
【背景技術】
【０００２】
例えば、鉄道交通システム、航空交通システム、バス交通システム、貨物輸送システムにおいては、駅、空港、バスターミナル、物流拠点等の複数の基地相互間を列車、航空機、バス、トラック等の輸送機材（資源）を用いて運行している。各運行は各時間（日時）毎に細かく運行番号、便名等の「運用」が定められており、各時間（日時）毎の「運用」に対していかに効率的に各「資源」を割り当てるかが重要な課題となる。
【０００３】
各資源に対する運用の割り当の初期状態を与えて、割り当てに関する制約条件を満たすように運用を資源に割り当てていく問題を考える。  
従来の技術では、割り当て対象の資源を順番に選び、制約条件を満たす作業を検索し、検索結果を割り当ての候補として複数の候補の中から評価関数などを用いてその資源に適当と思われる作業を割り当てる割り当て方式がある。
【０００４】
例えば、特許文献１の「乗務員運用計画支援装置」は、乗務員運用計画において、未割付列車が割付可能な計画を探索する装置である。そして、割付可能な列車の候補が複数ある場合は、列車毎に評価関数により点数を算出して、各運用（列車ダイヤ）に割り付ける列車を決定する。
【０００５】
しかしながら、この特許文献１に記載された手法では、所定の優先順位に従って乗務員を割り当てることによって、他の未割り当ての列車で逆に制約条件が厳しくなり、その結果として、割り当てをやりなおすステップ数が必要以上に多くなる場合がある。
【０００６】
また、まず運用割り当てのパターンを作成して割り当てを行ない、制約条件に違反する箇所があれば割り当ての見直しを行なうという手続きを繰り返して、最終的な運用計画を完成させる方法がある。
【０００７】
例えば、特許文献２の「巡回系列スケジューリング方法」では、運用業務の理想的なパターンを表す運用ローテーションパターンの作成する段階と、制約により矛盾が生じる箇所などに対してパターンを調整しながら実際に車両に対して運用割り当てする段階との２段階で車両の運用計画立案を行なっている。
【０００８】
しかしながら、この特許文献２に記載された手法では、ローテーションパターンの作成によって割り当てのステップ数はある程度少なくなる。しかし、制約により矛盾が生じる箇所に対してパターンを調整する段階では、他の割り当て箇所との調整が必要となり、大規模な割り当て問題に対しては、割り当てに要するステップ数が多くなる。
【特許文献１】特開平９―２８２３７２号公報
【特許文献２】特開２００１―５８４６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明は、このような事情に鑑みてなされたものであり、制約条件を満たす割り当ての選択を工夫することにより、より少ないステップ数で各運用に対して効率的に各資源を割り当てることができる資源割り当て計画作成プログラム、資源割り当て計画計画作成方法、及び資源割り当て計画作成装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
第１の発明は、複数の運用を時間毎に各資源に割り当てる資源割り当て計画作成装置に用いられる資源割り当て計画作成プログラムである。  
そして、この資源割り当て計画作成プログラムは、割り当て計画作成装置のコンピュータを、各資源に対する運用の割り当てを制約する制約情報を保持する情報保持手段と、指定時間にて各資源に実際に割り当てられた運用を示す割当実績情報を入力する割当実績情報入力手段と、この入力された割当実績情報における各資源の指定時間以降の各時間に対して制約情報に基づいて割り当て可能な運用を検索する検索手段と、この検索手段で検索された運用を該当資源の未割り当ての時間に割り当てる第１の割当手段として機能させる。
【００１１】
このように構成された資源割り当て計画作成プログラムにおいては、各資源に対する運用の割り当てを制約する制約情報が保持されている。そして、指定時間にて各資源に実際に割り当てられた運用を示す割当実績情報が入力されると、この割当実績情報における各資源の指定時間以降の各時間に対して制約情報に基づいて割り当て可能な運用が検索され、この検索された運用が該当資源の未割り当ての時間に割り当てられる。
【００１２】
したがって、制約情報を工夫することにより、１回の割り当てステップで多数の割り当てが実現され、結果的に割り当てステップ数を減少できる。
【００１３】
また、第２の発明の資源割り当て計画作成プログラムは、コンピュータを、さらに、第１の割当手段で運用が割り当てられなかった資源の各時間に対して、未割り当ての運用のなかから割り当て可能な運用の組合せを検索する組合せ検索手段と、この組合せ検索手段で１つの運用の組合せのみが検索されたとき、この検索された１つの運用の組合せを該当資源の未割り当ての各時間に割り当てる第２の割当手段と、組合せ検索手段で複数の運用の組合せが検索されたとき、各運用の組合せを該当資源の未割り当ての各時間に割り当てた場合における、運用が未割り当の他の資源に対する割り当て可能な運用の組合せ数を検出する組合せ数検出手段と、この組合せ数検出手段で検出された組合せ数が多い運用の組合せを該当資源の未割り当ての各時間に割り当てる第３の割当手段として機能させる。
【００１４】
このように構成された資源割り当て計画作成プログラムにおいては、組合せ検索手段にて１つの運用の組合せのみが検索されたとき、この検索された１つの運用の組合せを該当資源の未割り当ての各時間に割り当てる。複数の運用の組合せが検索されたときに、各運用の組合せを該当資源の未割り当ての各時間に割り当てた場合における、運用が未割り当の他の資源に対する割り当て可能な運用の組合せ数が多い運用の組合せを該当資源の未割り当ての各時間に割り当てられる。
【００１５】
すなわち、制約情報を満たすように各運用を資源に割り当てていく際に、残された未割り当ての資源にできるだけ多くの運用に対する割り当ての可能性を残すように運用を割り当てていくことにより、少ないステップ数で効率的に各運用を資源に割り当て可能である。
【００１６】
第３の発明の資源割り当て計画作成プログラムは、割り当て計画作成装置のコンピュータを、各時間の運用を各資源に割り当てた原計画情報と、各資源に対する運用の割り当ての条件を原計画情報との関係において制約する制約情報とを保持する情報保持手段と、現在時間にて各資源に実際に割り当てられた運用を示す割当実績情報を入力する割当実績情報入力手段と、この入力された割当実績情報における各資源の現在時間以降の各時間に対して制約情報に基づいて原計画情報のなかから割り当て可能な運用を検索する検索手段と、検索手段で検索された運用を該当資源の未割り当ての時間に割り当てる割当手段として機能させる。
【００１７】
このように構成された資源割り当て計画作成プログラムにおいては、例えば予め計画された各時間の運用を各資源に割り当てた原計画情報と、例えばこの原計画に対する再割り当て時において、各資源に対する運用の割り当ての条件を原計画情報との関係において制約する制約情報とが保持されている。
【００１８】
そして、現在時間にて各資源に実際に割り当てられた運用を示す割当実績情報が入力されると、この割当実績情報における各資源の現在時間以降の各時間に対して制約情報に基づいて原計画情報のなかから割り当て可能な運用が検索され、この検索された運用が該当資源の未割り当ての時間に割り当てられる。
【００１９】
したがって、第１の発明と同様に、制約情報を工夫することにより、１回の割り当てステップで多数の割り当てが実現され、結果的に割り当てステップ数を減少できる。
【００２０】
また、第４の発明の資源割り当て計画作成プログラムにおいては、割り当て計画作成装置のコンピュータを、各時間の運用を各資源に割り当てた原計画情報と、各資源に対する運用の割り当ての条件を原計画情報との関係において制約する制約情報とを保持する情報保持手段と、現在時間にて各資源に実際に割り当てられた運用を示す割当実績情報を入力する割当実績情報入力手段と、この入力された割当実績情報の現在時間以降の各時間における各資源に一意的に割り当てられる各運用を制約情報に基づいて原計画情報から検索して該当時間に割り当てる第１の割当手段と、この第１の割当手段で運用が一意的に割り当てられなかった資源の各時間に対して、原計画情報における未割り当ての運用のなかから割り当て可能な運用の組合せを検索する組合せ検索手段と、この組合せ検索手段で１つの運用の組合せのみが検索されたとき、この検索された１つの運用の組合せを該当資源の未割り当ての各時間に割り当てる第２の割当手段として機能させる。
【００２１】
このように構成された資源割り当て計画作成プログラムにおいては、第１の割当手段で制約情報に基づいて各資源に一意的に割り当てられる各運用を割り当てた後に、未割り当ての資源の各時間に対して可能な運用の組合せが検索される。そして、１つの運用の組合せのみが検索されたとき、この検索された１つの運用の組合せを該当資源の未割り当ての各時間に割り当てられる。
【００２２】
また、第５の発明は、上述した発明の資源割り当て計画作成プログラムに対して、さらに、組合せ検索手段で複数の運用の組合せが検索されたとき、各運用の組合せを該当資源の未割り当ての各時間に割り当てた場合における、運用が未割り当の他の資源に対する割り当て可能な運用の組合せ数を検出する組合せ数検出手段と、この組合せ数検出手段で検出された組合せ数が多い運用の組合せを該当資源の未割り当ての各時間に割り当てる第３の割当手段とを備えている。
【００２３】
このように構成された資源割り当て計画作成プログラムにおいては、前述した第２の発明とほぼ同様の作用効果を奏すことが可能である。
【００２４】
また、第６の発明は、上述した発明の資源割り当て計画作成プログラムにおいて、入力された割当実績情報における各資源の現在時間以降の割り当て可能な運用を検索する時間の数に一定の上限値が設けられている。
【００２５】
また、第７の発明は、複数の運用を時間毎に各資源に割り当てる資源割り当て計画作成方法である。そして、各時間の運用を各資源に割り当てた原計画情報と、各資源に対する運用の割り当ての条件を原計画情報との関係において制約する制約情報とを保持する情報保持工程と、現在時間にて各資源に実際に割り当てられた運用を示す割当実績情報を入力する割当実績情報入力工程と、この入力された割当実績情報の現在時間以降の各時間における各資源に一意的に割り当てられる各運用を前記制約情報に基づいて原計画情報から検索して該当時間に割り当てる第１の割当工程と、この第１の割当工程で運用が一意的に割り当てられなかった資源の各時間に対して、原計画情報における未割り当ての運用のなかから割り当て可能な運用の組合せを検索する組合せ検索工程と、この組合せ検索工程で１つの運用の組合せのみが検索されたとき、この検索された１つの運用の組合せを該当資源の未割り当ての各時間に割り当てる第２の割当工程と、組合せ検索工程で複数の運用の組合せが検索されたとき、各運用の組合せを該当資源の未割り当ての各時間に割り当てた場合における、運用が未割り当の他の資源に対する割り当て可能な運用の組合せ数を検出する組合せ数検出工程と、この組合せ数検出工程で検出された組合せ数が多い運用の組合せを前記該当資源の未割り当ての各時間に割り当てる第３の割当工程とを備えている。
【００２６】
このように構成された資源割り当て計画作成方法においても、上述した資源割り当て計画作成プログラムと同様の作用効果が得られる。
【００２７】
また、第８の発明は、複数の運用を時間毎に各資源に割り当てる資源割り当て計画作成装置である。そして、各時間の運用を各資源に割り当てた原計画情報と、各資源に対する運用の割り当ての条件を原計画情報との関係において制約する制約情報とを記憶する情報記憶部と、現在時間にて各資源に実際に割り当てられた運用を示す割当実績情報を入力する割当実績情報入力手段と、この入力された割当実績情報の現在時間以降の各時間における各資源に一意的に割り当てられる各運用を前記制約情報に基づいて原計画情報から検索して該当時間に割り当てる第１の割当手段と、この第１の割当手段で運用が一意的に割り当てられなかった資源の各時間に対して、原計画情報における未割り当ての運用のなかから割り当て可能な運用の組合せを検索する組合せ検索手段と、この組合せ検索手段で１つの運用の組合せのみが検索されたとき、この検索された１つの運用の組合せを該当資源の未割り当ての各時間に割り当てる第２の割当手段と、組合せ検索手段で複数の運用の組合せが検索されたとき、各運用の組合せを該当資源の未割り当ての各時間に割り当てた場合における、運用が未割り当の他の資源に対する割り当て可能な運用の組合せ数を検出する組合せ数検出手段と、この組合せ数検出手段で検出された組合せ数が多い運用の組合せを前記該当資源の未割り当ての各時間に割り当てる第３の割当手段とを備えている。
【００２８】
このように構成された資源割り当て計画作成装置においても、上述した資源割り当て計画作成プログラムと同様の作用効果が得られる。
【発明の効果】
【００２９】
本発明の資源割り当て計画作成プログラム、資源割り当て計画作成方法、及び資源割り当て計画作成装置においては、より少ないステップ数で各運用に対して効率的に各資源を割り当てることができる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の実施形態を図面を用いて説明する。  
図１は、本発明の一実施形態に係わる資源割り当て計画作成プログラム、及び資源割り当て計画作成方法が適用される資源割り当て計画作成装置の概略構成を示すブロック図である。
【００３１】
コンピュータで構成された資源割り当て計画作成装置内には、図４Ａ、図４Ｂに示す原計画１０２と、図７に示す制約１０３と、図３に示す運用定義１０４とを記憶する記憶部１０１、割当済みメモリ１０５、組合せメモリ１１４、表示部１１２が設けられている。なお、割当済みメモリ１０５内には、この資源割り当て計画作成装置で、各時間としての各日付に対して、各資源としての各機材に割り当てられた各運用が順次書込まれる。
【００３２】
さらに、この資源割り当て計画作成装置内には、割当実績情報入力部１０６、第１の割当部１０７、組合せ検索部１０８、第２の割当部１０９、組合せ数検出部１１０、第３の割当部１１１が設けられている。これらの各部１０６〜１１１は、例えば、プログラムメモリ１１３内に書込まれている資源割り当て計画作成プログラムを起動することによって実現される。
【００３３】
この実施形態の資源割り当て計画作成装置における資源割り当て計画の対象システムとして、例えば、鉄道交通システム、航空交通システム、バス交通システム、貨物輸送シス等を想定している。図２に対象システムで扱う列車、航空機、バス、トラック等の資源としての機材の運用パターンを表す。図２はある１日に基地を出発する機材（資源）の運用を次に基地に帰着するまで示したものである。
【００３４】
図２において、アルファベットを○で囲んだ記号２０１はターミナルである。ターミナル２０１は航空交通システムの場合の空港に相当し、旅客サービスの拠点である。基地２０２では機材の検査などが行える。この例では基地にある機材は任意の運用に割り当てることができる。基地２０２はターミナル２０１の機能も備える。システムを構成する個々の運用（２〜１６）は、ターミナル間の移動を表す矢印２０３と運用名２０４によって表現される。
【００３５】
図３は記憶部１に記憶された個々の運用の定義１０４を示す図である。図３には各運用において、機材がターミナルを発着する時刻を示してある。時刻は、運用が１日で完結する場合には時刻のみ、２日以上にまたがる場合には、出発する日を「０」とする相対日付と時刻を '-' で結んだ形式で表現する。
【００３６】
また、各運用は略号で表されている。それらの略号も図３に示す。略号は、出発地、運用名、到着地の並びで表わす。さらに、午前中に終了する運用には、右端に ':' を付与する。午後から開始される運用には、左端に ':' を付与する。また、連続する日にまたがって運用が行なわれる場合は、'-' を付与してそれと分かるようにする。次の日に運用が続く場合は左端に、前の日から運用が続いている場合は右端に '-' を付与する。
【００３７】
例えば運用10は、次のような経路になる。略号 :b10- に相当する運用は、基地 b を初日の 20:00 に出発し、基地 c に 23:00 に到着する。また、略号 -10b: に相当する運用は、基地 c を翌日の 9:00 に出発し、再び 基地 b に 12:00 に到着する。
【００３８】
図４Ａ、図４Ｂは、記憶部１０１に記憶された各機材に対して予め割り当てられた運用を示す原計画１０２を示す図である。横軸が時間としての日付であり、縦軸は番号で示す各機材である。図４Ａ、図４Ｂにおける各行は機材に割り当てられる運用の並びを表わす。運用の表記は、図３に示した運用定義１０４における各運用の略号と対応している。また、この図4Ａ、図４Ｂにおいては、ターミナルの発着（運用の中途）は省略されている。
【００３９】
この図４Ａ、図４Ｂに示す原計画１０２では、1 から 16 までの運用が毎日開始される。また「予」は予備を表わし、基地に待機する機材を意味する。この原計画１０２では、常時２機が基地で待機する。具体的には機材 17 が日付 13 から日付 18 まで、機材 20 が日付 1 から日付 12 まで、基地 b で待機する。機材 18 は日付 8 から日付 17 まで、機材 19 は日付 1 から日付 7 までと日付 18 に基地 a に待機する。さらに、「休」は休みを表す。休みの期間は、点検などに用いられるため、該当機材に運用を割り当てることはできない。
【００４０】
図５は、対象システムにおいて、日付 1 で運用の実施中に乱れが生じて日付 2 以降の運用計画を修正する必要が発生した状態を表している。図５では、日付 1 の太字で示す運用が乱れの結果であり、原計画１０２と異なる。例えば、機材 1 の日付 1 では実績として a13a、すなわち基地 a を発着点とする運用 13 が実績となっている。その結果、日付 2 の午前中に基地 c に存在できずに、結果として原計画通りの運用 c3b を担当できなくなっている。
【００４１】
この日付 1 、すなわち、指定時間又は現在時間にて各機材に実際に割り当てられた運用を示す図５の割当実績情報が割当実績情報入力部１０６を介してこの資源割り当て計画作成装置内へ取り込まれる。この日付 1 の割当実績情報は、図１の割当済みメモリ１０５の日付 1 の欄に書込まれる。
【００４２】
この図５に示す日付 1 （指定時間又は現在時間）の割当実績情報に基づいて、日付 2 以降の各機材に割付ける各運用を調整して、早く、原計画１０２に復帰させる必要がある。
【００４３】
記憶部１０１に記憶された図７に示す制約１０３は、再割り当ての必要が発生した場合において、各機材に対する運用の割り当ての条件を原計画１０２との関係において制約する。この実施形態においては、下記に示す５項目が設定されている。
【００４４】
制約１：連続する運用の前後で基地が同じでなければならない。
【００４５】
制約２：休みは必ず原計画の通りに取らなければならない。休み以降は原計画通りとする。
【００４６】
制約３：連続する日にまたがる運用以降は、原計画通りとする。
【００４７】
制約４：修正計画初日に原計画通りに運用可能な機材は、全ての日で原計画通りとする。
【００４８】
制約５：休みを取らなければ割り当てられない場合を除いて、割り当ての期間で休みを２回以上取らない。ただし、終日の休みは２回と数える。
【００４９】
そして、図１に示す資源割り当て計画作成装置における各部１０６〜１１１は、図６に示す流れ図に従って、日付 2 以降の各機材に割り当てる各運用を調整して原計画１０２に復帰させる処理を実施する。
【００５０】
Ｓ（ステップ）601で処理を開始する。Ｓ（ステップ）602で初期データを入力する。初期データには、原計画１０２、この原計画１０２に復帰する日数で示した期限、割当実績入力部１０６で入力された、図５に示す運用の実績（修正計画初日の割当実績情報）、及び図７に示す制約１０３がある。入力した原計画１０２、制約１０３は記憶部１０１に書込まれる。
【００５１】
図５に示す運用の実績（割当実績情報）においては、日付 1 において、機材 1、2、6、7、8 および 13 が原計画１０２とは異なる実績となっている。さらに、機材 2、13 は乱れにより原計画１０２上の運用には存在しない運用を行ったため、単に帰着した基地名のみを記載している。
【００５２】
復帰計画の作成に関しては、原計画１０２に復帰する期限（復帰日付）を設定し、現時点からその期限までの期間で調整を試みるものとする。
【００５３】
Ｓ（ステップ）603で各機材において作業が未割り当ての期間をリストアップし、Ｓ（ステップ）604からＳ（ステップ）608までの間を、リストの全要素について繰り返す。なお、リストの要素を繰り返す順番は、実施形態では機材の番号順に行なうが、特にその順番に限定する必要はなく、未割り当ての期間の長さ（日数）等の、別の順番によって行なっても構わない。
【００５４】
Ｓ（ステップ）605では、対象としている未割り当ての期間に含まれる各日付に対して、割り当て可能な運用を検索する。１回の未割り当ての期間の各日付への運用割り当てにより、残された未割り当ての期間の各日付に割り当て可能な運用が変化する。そのため、Ｓ（ステップ）605に示すように、繰り返しの内部で毎回検索を行なう。
【００５５】
割り当て可能な運用の検索は、割り当て対象となる運用が、図７に示す制約１０３に違反しないように未割り当ての期間の各日付に対して割り当て可能かどうかを判定することにより行なう。複数の制約が存在して、それらが互いに矛盾する可能性があるが、そのような場合は、あらかじめ個々の制約に優先度を付与しておくなどの解決策により、割り当て時の不具合を回避する。
【００５６】
Ｓ（ステップ）606において、Ｓ（ステップ）605の検索結果を基にして、未割り当ての期間の中に割り当て可能な運用が１つしかない日付があれば、その運用を該当日付に割り当てる。  
具体的には、第１の割当部１０７が起動して、未割り当ての期間の各日付における各機材に一意的に割り当てられる各運用を制約１０３に基づいて原計画１０２から検索して該当日付に割り当てる。割り当て結果を割当済みメモリ１０５へ書込む。さらに、組合せ検索部１０８が起動して、第１の割当部１０７で運用が一意的に割り当てられなかった機材の各日付に対して、第1の割当部１０７で割当てられた運用を割当済みメモリ１０５から読み出して参照し、原計画情報１０２における未割り当ての運用のなかから制約１０３に基づいて割り当て可能な運用の組合せを検索する。次に、組合せ検索部１０８で１つの運用の組合せのみが検索されたとき、第２の割当部１０９が起動して、この検索された１つの運用の組合せを該当機材の未割り当ての各日付に割り当てる。割り当て結果を割当済みメモリ１０５へ書込む。
【００５７】
Ｓ（ステップ）607では、この時点で、未割り当ての期間の各日付に運用を割り当てる。このとき、残りの未割り当ての運用が最も多くの機材に割り当て可能になるような運用を選ぶ。  
具体的には、組合せ検索部１０８で複数の運用組合せが検索されたとき、組合せ検索部１０８は組合せメモリ１１４に複数の運用組合せを書込む。そして、組合せ数検出部１１０が起動して、組合せメモリ１１４に記憶されている複数の運用組合せを読出し、各運用組合せを該当機材の未割り当ての各日付に割り当てた場合における、運用が未割り当ての他の機材に対する割り当て可能な運用の組合せ数を検出する。そして、第３の割当部１１１が起動して、組合せ数検部１１０で検出された組合せ数が多い運用の組合せを該当資源の未割り当ての各日付に割り当てる。割り当て結果を割当済みメモリ１０５へ書込む。
【００５８】
Ｓ（ステップ）608では、各機材に対して未割り当ての運用が残っているかどうかを調べ、残っていればＳ（ステップ）605へ戻り、残っていなければＳ（ステップ）609へ進む。  
Ｓ（ステップ）609では、原計画１０２に含まれる全ての運用が割り当てられたかどうかを調べて、割り当てられていれば、Ｓ（ステップ）613へ行き、この割り当て処理を終了する。そうでなければ、Ｓ（ステップ）610以降の処理を行なう。
【００５９】
Ｓ（ステップ）610では、原計画１０２に含まれるが割り当てられなかった運用に関して、まず予備となっている機材に割り当てることを試す。それでも割り当てが不可能な場合は、既に割り当てられている運用を入れ替えることによって実行可能な運用計画に修正することを試す。なお、自動修正が不可能な場合は、操作者にその状態を報告し手動修正を求める。
【００６０】
Ｓ（ステップ）611では、Ｓ（ステップ）609と同様に、原計画１０２に含まれる全ての運用が割り当てられたかどうかを調べて、割り当てられていれば、Ｓ（ステップ）613へ行き、この割り当て処理を終了する。そうでなければＳ（ステップ）612以降の処理を行なう  。
【００６１】
Ｓ（ステップ）612では、原計画１０２に復帰する期限（日数）を長くとって、再度割り当ての作業を行なうためにＳ（ステップ）602へ戻る。
【００６２】
次に、この図６に示す各機材に対する各運用の割付処理の具体例を、図5に示した日付 1 における割り当実績に基づいて日付 2 の運用開始時点から原計画１０２への復帰を計画する過程を例にとって説明する。
【００６３】
図５に示した割り当実績の例では、図６のＳ（ステップ）602における期限を日付 5 の運用終了時点とする。図８から図３２までにおいて、割り当て対象の運用が図６のＳ（ステップ）604からＳ（ステップ）608の繰返しで、運用が機材にどのように割り当てられたかを示している。
【００６４】
なお、前述したように、リストの要素を繰り返す順番は、実施形態では機材の番号順に行なうが、特にその順番に限定する必要はなく、未割り当ての期間の長さ（日数）等の、別の順番によって行なっても構わない。
【００６５】
まず、図６のＳ（ステップ）605において、各機材に割り当て可能な運用を検索する。割り当て可能な運用の詳細を順次説明する。まず、図６のＳ（ステップ）606を適用することにより、割り当て可能な運用が１つしかない場合を処理する。
【００６６】
具体的には、図８に示すように、図７の制約２より、休み以降は原計画通りとする。また、制約３より、機材 3、4、10、11、12、14、15 は日付 2 以降で原計画の通りとする。機材 13 に関しては、日付 3 の午後の運用以降から原計画通りとする。機材 6、17 は日付 4 以降で原計画通りとする。機材 7、18 は日付 5 以降で原計画通りとする。さらに、制約 4 より、機材 9、12、17、18 は日付 2 以降で原計画通りとする。
【００６７】
このように、図７の制約１０３により、各機材の各日付に対して一意的に多数の運用が割り当てられる。この一意的な割り当て結果は図８に太字で示される。また、図９は、図８における割り当て状況を、縦軸を運用、横軸を日付の表形式で示したものである。図９において、太字の部分は図６のＳ（ステップ）606の割り当て処理によって運用が割り当てられた機材である。この図８、図９にて、この時点で日付 2 にて未割り当ての機材は、機材 1,2,6,7,8,13 である。
【００６８】
さらに、図６のＳ（ステップ）605の検索により、原計画１０２とこの時点で割り当て済みの運用から、機材 6、7、8 には割り当て可能な運用が１つしかないことが判明する。機材 6、7、8 に割り当て可能な各日付に対する運用の組合せをそれぞれ図１０、図１１、図１２に示す。
【００６９】
すなわち、機材 6 に関しては、図７の制約 1 により、日付 2 に基地 c を出発してその日のうちに基地 c に戻ってくる運用の組合せが必要である。図９によれば、そのような運用の組合せは c7b: と :b2c の組合せのみである。なお、日付 2 を「休」とする組合せも考えられるが、このような組合せのケースを頻繁に適用すると、全ての運用の割り当てが完了しないことが予想される。そこで、図７の制約 5 に示すように、割り当ての期間に運用が割り当てられるにもかかわらず「休」を割り当てるような運用の組合せは、考慮しないこととする。
【００７０】
また、機材 7 に関しては、日付 2 に基地 a を出発して日付 3 に基地 c に到達する運用の組合せが必要である。図９によれば、そのような運用の組合せは日付 2 が a14b、日付 3 が b15c の組合せのみである。
【００７１】
さらに、機材 8 に関しては、日付 2 に基地 b を出発して日付 4 に基地 c に到達する運用の組合せが必要である。図９によれば、そのような運用の組合せは日付 2 が b15c、日付 3 が c3b、日付 4 が b15c の組合せのみである。
【００７２】
このように、機材 6、7、8 の未割り当ての各日付に対して運用の組合せが決定される。機材 6、7、8 に運用を割り当てた後の日付／機材一覧と、日付／運用一覧をそれぞれ図１３、図１４に示す。図１３、図１４中の太字で示された箇所が今回割り当てた運用に相当する。
【００７３】
以上の図６のＳ（ステップ）606における割り当て処理により、未割り当ての期間の各日付に割り当て可能な運用が1つしかない日付に対して各運用を割り当てた。この図１３、図１４にて、この時点で日付 2 にて未割り当ての機材は、機材 1,2,13 である。
【００７４】
次に、図６のＳ（ステップ）607を適用することにより、残った未割り当ての機材における期間の各日付運用を割り当てる。  
前述したように、この時点で、未割り当ての期間が存在する機材は、順に機材 1、機材 2、機材 13 である。そこで、まず機材 1 の日付 2 から日付 4 までの期間で運用の割り当てを行なう。
【００７５】
機材 1 は、日付 2 に基地 a を出発し、日付 4 に基地 a に帰着する必要がある。一方、原計画１０２において、残された未割り当ての運用は、図１４の空欄になっている運用であり、日付 2 では、a1b:、c3b、:b8a、a13a である。同様に、日付 3 では b4a、a9b:、a14b であり、日付 4 では b4a、a5a である。
【００７６】
これらの未割り当ての運用で機材 1 が運用可能な組合せとして、図７の制約 1 および制約 5 に基づいて、図１５に示すように、５通りが検索される。さらに、この５通りの組合せのうち１つを実際に機材 1 に割り当てたときに、残りの他の機材 2、13 に割り当て可能な運用の組合せは、それぞれ、図１６、図１７、図１８、図１９、図２０のようになる。図１６〜図２０により、図１５における No.3 または No.5 の組合せを割り当てたときに、残りの他の機材 2、13 に割り当て可能な組合せ数が合計３通りになり、最も多くなる。
【００７７】
このように、最大の組合せ数となる割り当て方が複数ある場合は、あらかじめルールを決めておいてそのルールに従って自動的に割り当てる組合せを一意に決めるようにする。あるいは、割り当てを担当しているオペレータの判断で一意に決める。
【００７８】
実施形態ではオペレータの判断により機材 1 に図１５の No.5 の組合せを、該当する各日付に割り当てる。割り当て後の日付／機材一覧、日付／運用一覧を、それぞれ図２１、図２２に示す。この図２１、図２２にて、この時点で日付 2 にて未割り当ての機材は、機材 2、13 である。
【００７９】
次に、図６のＳ（ステップ）605に戻り、機材 2 の日付 2 から日付 5 までの期間で運用の割り当てを行なう。  
機材 2 は、日付 2 に基地 b を出発し、日付 5 に基地 a に帰着する必要がある。原計画１０２、図２１、図２２から、機材 2 が運用可能な組合せとして、図２３に示すように２通りが検索される。したがって、割り当て可能な運用の組合せは複数存在するので、図６のＳ（ステップ）606はスキップされる。
【００８０】
図６のＳ（ステップ）607において、図２３に示すNo.1、No.2の２通りの組合せの１つの組合せを実際に機材 2 に割り当てたときに、残りの他の機材 13 に割り当て可能な運用の組合せは、図２４、図２５のようになる。具体的には、No.1の組合せを指定した場合、他の機材 13に対する運用の割り当てが無くなる。この図２４、図２５に示すように、図２３の No.2 の組合せを割り当てたときに、機材 13 に割り当て可能な組合せ数が図２５に示す合計１通りになり、図２４に示す０通りよりも多くなる。
【００８１】
したがって、機材 2 には図２３の No.2 の組合せを割り当てる。割り当て後の日付／機材一覧、日付／運用一覧を、それぞれ図２６、図２７に示す。この図２６、図２７にて、この時点で日付 2 にて未割り当ての機材は、機材 13 のみとなる。
【００８２】
次に、図６のＳ（ステップ）605に戻り、機材 13 の日付 2 から日付 3 までの期間で運用の割り当てを行なう。  
機材 13 では、日付 2 に基地 a を出発し、日付 3 の午前中に基地 b に帰着する必要がある。原計画１０２、図２６、図２７から、機材 13 が運用可能な組合せとして、図２８に示すように１通りが検索される。
【００８３】
したがって、この機材 13 に割り当て可能な運用の組合せが１通りしかないので、図６のＳ（ステップ）606により、機材 13 の日付 2 、日付 3 に対して図２８の組合せを割り当てる。割り当て後の日付／機材一覧、日付／運用一覧を、それぞれ図２９、図３０に示す。
【００８４】
図２９にて、この時点で全ての機材に関して未割り当ての期間（日付）が無くなったので、図６のＳ（ステップ）604 からＳ（ステップ）609へ移る。さらに、図３０により、日付 2 において運用 c3b がまだ未割り当て状態であるので、図６のＳ（ステップ）609からＳ（ステップ）610に移る。
【００８５】
図６のＳ（ステップ）610では、日付 2 の運用 c3b に対して予備となっている機材への割り当てを試みる。すなわち、機材 20 が日付 1 から日付 12 まで基地 b で待機しているので、この運用 c3b を機材 20 に割り当てる。ただし、この運用 c3b は出発の基地が c である必要があるため、機材 20 に対して日付 1 に臨時の運用 bRc を同時に割り当てる。なお、日付 1 で乱れが発生した関係で、臨時運用の手配が間に合わなかった場合は、図６のＳ（ステップ）612へ移る。
【００８６】
この段階で全ての運用が各機材に割り当てられたので、図６のＳ（ステップ）611で「 yes 」となり、割り当て処理を終了する。最終的に得られる日付／機材一覧、日付／運用一覧は、それぞれ図３１、図３２のようになる。
【００８７】
以上のように、図５に示す各機材に割り当てた運用の原計画１０２からの乱れに対しては、図６に示す割り当て処理によって、Ｓ（ステップ）602で示す時点までに原計画１０２に復帰するように、運用を割り当てることができる。
【００８８】
このように構成された資源割り当て計画作成プログラム、資源割り当て計画作成方法が適用される資源割り当て計画作成装置においては、各機材に割り当てた運用の原計画１０２からの乱れが発生すると、この時点（日付 1 ）における図５に示す割当実績を用いて、日付 2 以降の各日付に対して、各運用を割り当てていく。
【００８９】
この場合、最初に、制約１０３で一意的に決まる各運用を機材に割り当てる。  
次に、運用が一意的に割り当てられなかった機材の各日付に対して、原計画１０２における未割り当ての運用のなかから割り当て可能な運用の組合せを、先の制約１０３を参照して検索する。１つの運用の組合せのみが検索されたとき、この検索された１つの運用の組合せを該当機材の未割り当ての各日付に割り当てる。
【００９０】
次に、複数の運用の組合せが検索されたとき、各運用の組合せを該当機材の未割り当ての各日付に割り当てた場合における、運用が未割り当の他の機材に対する割り当て可能な運用の組合せ数を検出する。そして、検出された組合せ数が多い運用の組合せを該当機材の未割り当ての各日付に割り当てる。
【００９１】
このように、制約１０３及び原計画１０２で決まる各運用を機材に割り当てる。その残りの未割り当ての各運用について、機材に運用を割り当てた後に残った運用が、未割り当ての機材に最も多く割り当てられるように順次割り当てを行うことによって、少ないステップ数で効率的に最終的な割り当を得ることができる。
【図面の簡単な説明】
【００９２】
【図１】本発明の一実施形態に係わる資源割り当て計画作成プログラム、及び資源割り当て計画作成方法が適用される資源割り当て計画作成装置の概略構成を示すブロック図
【図２】同装置が適用される対象システムで扱う機材の運用パターンを示す図
【図３】同装置の記憶部に記憶された個々の運用の定義を示す図
【図４Ａ】同装置の記憶部に記憶された原計画を示す図
【図４Ｂ】同じく同装置の記憶部に記憶された原計画を示す図
【図５】対象システムの運用の実施中に乱れが生じた場合の割当実績情報を示す図
【図６】同装置の割当処理動作を示す流れ図
【図７】同装置の記憶部に記憶された制約を示す図
【図８】同制約により一意的に決まる運用の割り当て後の日付／機材一覧を示す図
【図９】同制約により一意的に決まる運用の割り当て後の日付／運用一覧を示す図
【図１０】機材６に対して割り当て可能な運用の組合せ一覧を示す図
【図１１】機材７に対して割り当て可能な運用の組合せ一覧を示す図
【図１２】機材８に対して割り当て可能な運用の組合せ一覧を示す図
【図１３】機材６、７、８に運用を割り当てた後の日付／機材一覧を示す図
【図１４】機材６、７、８に運用を割り当てた後の日付／運用一覧を示す図
【図１５】機材１に対して割り当て可能な運用の組合せ一覧を示す図
【図１６】機材１にNo１の組合せを割り当てた場合の他の機材の運用組合せ一覧を示す図
【図１７】機材１にNo2の組合せを割り当てた場合の他の機材の運用組合せ一覧を示す図
【図１８】機材１にNo3の組合せを割り当てた場合の他の機材の運用組合せ一覧を示す図
【図１９】機材１にNo4の組合せを割り当てた場合の他の機材の運用組合せ一覧を示す図
【図２０】機材１にNo5の組合せを割り当てた場合の他の機材の運用組合せ一覧を示す図
【図２１】機材１にNo１の組合せを割り当てた後の日付／機材一覧を示す図
【図２２】機材１にNo１の組合せを割り当てた後の日付／運用一覧を示す図
【図２３】機材２に対して割り当て可能な運用の組合せ一覧を示す図
【図２４】機材２にNo１の組合せを割り当てた場合の他の機材の運用組合せ一覧を示す図
【図２５】機材２にNo2の組合せを割り当てた場合の他の機材の運用組合せ一覧を示す図
【図２６】機材２にNo2の組合せを割り当てた後の日付／機材一覧を示す図
【図２７】機材１にNo2の組合せを割り当てた後の日付／運用一覧を示す図
【図２８】機材１３に対して割り当て可能な運用の組合せ一覧を示す図
【図２９】機材１３にNo1の組合せを割り当てた後の日付／機材一覧を示す図
【図３０】機材１３にNo1の組合せを割り当てた後の日付／運用一覧を示す図
【図３１】最終的な日付／機材一覧を示す図
【図３２】最終的な日付／運用一覧を示す図
【符号の説明】
【００９３】
１０１…記憶部、１０２…原計画、１０３…制約、１０４…運用定義、１０５…割当済みメモリ、１０６…割当実績情報入力部、１０７…第１の割当部、１０８…組合せ検索部、１０９…第２の割当部、１１０…組合せ数検出部、１１１…第３の割当部、１１２…表示部
【図１】
2005084813.tif 000003
【図２】
2005084813.tif 000004
【図３】
2005084813.tif 000005
【図４Ａ】
2005084813.tif 000006
【図４Ｂ】
2005084813.tif 000007
【図５】
2005084813.tif 000008
【図６】
2005084813.tif 000009
【図７】
2005084813.tif 000010
【図８】
2005084813.tif 000011
【図９】
2005084813.tif 000012
【図１０】
2005084813.tif 000013
【図１１】
2005084813.tif 000014
【図１２】
2005084813.tif 000015
【図１３】
2005084813.tif 000016
【図１４】
2005084813.tif 000017
【図１５】
2005084813.tif 000018
【図１６】
2005084813.tif 000019
【図１７】
2005084813.tif 000020
【図１８】
2005084813.tif 000021
【図１９】
2005084813.tif 000022
【図２０】
2005084813.tif 000023
【図２１】
2005084813.tif 000024
【図２２】
2005084813.tif 000025
【図２３】
2005084813.tif 000026
【図２４】
2005084813.tif 000027
【図２５】
2005084813.tif 000028
【図２６】
2005084813.tif 000029
【図２７】
2005084813.tif 000030
【図２８】
2005084813.tif 000031
【図２９】
2005084813.tif 000032
【図３０】
2005084813.tif 000033
【図３１】
2005084813.tif 000034
【図３２】
2005084813.tif 000035