JP6671232B2 - スケジューリング装置及びスケジューリング方法 - Google Patents

Description

本発明は、共有リソースを使用する複数の移動体についてその使用に関するスケジューリングを行う情報処理技術に関する。

交通システムにおいては、航空機、船舶または車両などの複数の移動体は、共有リソースを使用して移動することが多い。この種の共有リソースの例としては、航空機の場合は、たとえば滑走路及びウェイポイント（航路上の特定の空域）が挙げられ、船舶の場合は、たとえば、複数の船舶が出入りする港湾が挙げられる。このような共有リソースを使用する複数の移動体が存在する状況に対し、これら移動体全体の総遅延時間または運用コストなどの評価値を最適化するように、共有リソースの使用に関して効率的なスケジューリングが要求される場合がある。スケジューリングの厳密な最適解を与える探索アルゴリズムとしては、従来より分岐限定法（ｂｒａｎｃｈ−ａｎｄ−ｂｏｕｎｄ ｍｅｔｈｏｄ）及び動的計画法（ｄｙｎａｍｉｃ ｐｒｏｇｒａｍｍｉｎｇ）が知られている。

また、厳密な最適解に代えて良質な近似解を与えるヒューリスティックス（ｈｅｕｒｉｓｔｉｃｓ：発見的手法）と呼ばれる探索アルゴリズムも多数提案されている。たとえば、下記の非特許文献１は、遺伝的アルゴリズム（ＧＡ：Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ）及びタブーサーチ（ＴＳ：Ｔａｂｕ Ｓｅａｒｃｈ）というヒューリスティックな探索アルゴリズムを用いて、複数の移動体による共有リソースの使用順序を決定することにより移動体全体の総遅延時間を最小化するスケジューリング技術を開示している。

澤田めぐみ，尾崎敦夫，白石將，松村寛夫：「最適化手法を用いた移動体の順序付け方式――公平性を考慮した遅延最小化」，情報処理学会論文誌，Ｖｏｌ．５６， Ｎｏ．１１， ｐｐ．２０７２−２０８２， ２０１５．

上述した分岐限定法及び動的計画法などの探索アルゴリズムを使用して厳密な最適解を演算により求める場合には、スケジューリング対象の移動体の個数が多いと、長大な演算時間が必要になるという課題がある。一方、遺伝的アルゴリズム及びタブーサーチなどのヒューリスティックな探索アルゴリズムの場合、明らかに無駄な組み合わせの解が評価されることにより、演算効率が悪化する可能性がある。

上記に鑑みて本発明の目的は、複数の移動体による共有リソースの使用に関するスケジューリングを効率的に行うことができるスケジューリング装置及びスケジューリング方法を提供することである。

本発明の一態様に係るスケジューリング装置は、共有リソースを使用する複数の移動体の順序を定める移動体識別子の配列である入力順列を取得し、前記複数の移動体に対して、予め決められた制約条件を満たす使用予定時刻の割り当てを前記入力順列の順番で実行することによりスケジュール候補を生成するとともに前記スケジュール候補の評価値を算出するスケジューリング処理部と、前記スケジュール候補に基づいて構成される移動体識別子の順列候補から部分列を選択する部分列選択部と、前記移動体のカテゴリを基準として前記部分列を構成する複数の移動体識別子の順序を並べ替えることで前記順列候補を新たな順列に変換する順列変換部と、前記スケジューリング処理部で生成された複数のスケジュール候補の中から、最大の評価値を有するスケジュール候補を選択するスケジュール選択部と、移動体識別子の初期順列を生成する初期順列生成部とを備え、前記スケジューリング処理部は、前記初期順列及び前記新たな順列の各々を前記入力順列として使用して前記複数のスケジュール候補を生成し且つ前記複数のスケジュール候補の評価値を算出することを特徴とする。

本発明によれば、複数の移動体による共有リソースの使用時刻を定めるスケジュールを効率的に生成することができる。

本発明に係る実施の形態１のスケジューリング装置の概略構成を示すブロック図である。 図２Ａは、共有リソースを通過して移動する複数の移動体を示す概略図であり、図２Ｂは、図２Ａに示した複数の移動体にそれぞれ割り当てられた通過予定時刻を示す図である。 実施の形態１の移動体情報記憶部に記憶されている移動体情報の例をテーブル形式で示す図である。 図４Ａ及び図４Ｂは、移動体に割り当てられた通過可能時間帯の例を示す図である。 図５Ａは、実施の形態１の制約条件記憶部に記憶されている制約条件の例をテーブル形式で示す図であり、図５Ｂは、図５Ａに示した制約条件を説明するための図である。 実施の形態１に係るスケジューリングの手順の例を概略的に示すフローチャートである。 図６のスケジュール生成処理の手順の例を概略的に示すフローチャートである。 図８Ａ〜図８Ｅは、スケジュール生成処理によって移動体に割り当てられた通過予定時刻の例を示す図である。 図９Ａ〜図９Ｃは、スケジュール生成処理によって移動体に割り当てられた通過予定時刻の例を示す図である。 図６の部分列選択処理の手順の一部を概略的に示すフローチャートである。 図６の部分列選択処理の手順の他の一部を概略的に示すフローチャートである。 移動体の初期順列の例を示す概略図である。 部分列に対応する複数の移動体に割り当てられた複数の通過可能時間帯のすべてが重複する状態を示す図である。 図１４Ａは、実施の形態１の部分列選択部で選択された部分列の例を示す図であり、図１４Ｂ及び図１４Ｃは、図１４Ａの部分列を並べ替えることで生成された新たな順列の例を示す図である。 実施の形態１のスケジューリング装置のハードウェア構成例である情報処理装置のブロック図である。 本発明に係る実施の形態２のスケジューリング装置で実行される部分列選択処理の手順の例を概略的に示すフローチャートである。 部分列に対応する複数の移動体に割り当てられた複数の通過可能時間帯が重複する状態を示す図である。 本発明に係る実施の形態３に係るスケジューリングの手順の例を概略的に示すフローチャートである。 本発明に係る実施の形態４のスケジューリング装置の概略構成を示すブロック図である。 実施の形態４に係るスケジューリングの手順の例を概略的に示すフローチャートである。 実施の形態４に係る好適情報の例をルックアップテーブル形式で示す図である。 図２２Ａは、部分列選択部で選択された部分列の例を示す図であり、図２２Ｂ及び図２２Ｃは、図２２Ａの部分列を並べ替えることで生成された新たな順列の例を示す図である。 本発明に係る実施の形態５に係るスケジューリングの手順の例を概略的に示すフローチャートである。 本発明に係る実施の形態６のスケジューリング装置の概略構成を示すブロック図である。 実施の形態６に係るスケジューリングの手順の例を概略的に示すフローチャートである。 実施の形態６に係る不適情報の例をテーブル形式で示す図である。 本発明に係る実施の形態７に係るスケジューリングの手順の例を概略的に示すフローチャートである。

以下、図面を参照しつつ、本発明に係る種々の実施の形態について詳細に説明する。なお、図面全体において同一符号を付された構成要素は、同一構成及び同一機能を有するものとする。

実施の形態１．
図１は、本発明に係る実施の形態１であるスケジューリング装置１の概略構成を示すブロック図である。このスケジューリング装置１は、Ｎ個（Ｎは２以上の整数）の移動体Ｚ_１〜Ｚ_Ｎに対して、予め決められた制約条件を満たす共有リソースの使用予定時刻τ_１〜τ_Ｎをそれぞれ割り当てることによりスケジュールを生成する機能を有するものである。

移動体Ｚ_１〜Ｚ_Ｎは、たとえば、交通システムにおける航空機、船舶または車両などの構成要素とすることができる。共有リソースは、複数の移動体Ｚ_１〜Ｚ_Ｎがスケジュールで定められた順番で使用する同一の共有領域である。共有リソースとしては、たとえば、航空機の場合は、滑走路または航路上の特定空域が挙げられ、船舶の場合は、複数の船舶が出入りする港湾が挙げられ、車両の場合は、複数経路の合流点が挙げられる。交通システムでは、複数の移動体がその種の同一の共有領域を移動に用いることが多い。

以下、移動体Ｚ_１〜Ｚ_Ｎによる共有リソースの使用態様として、移動体Ｚ_１〜Ｚ_Ｎによる共有リソースの「通過」を想定する。この場合、スケジューリング装置１は、移動体Ｚ_１〜Ｚ_Ｎに対して、予め決められた制約条件を満たす共有リソースの通過予定時刻τ_１〜τ_Ｎをそれぞれ割り当てることによりスケジュールを生成する。ただし、本発明に係る共有リソースの使用態様は「通過」に限定されるものではない。

図２Ａは、５つの移動体Ｚ_１〜Ｚ_５が右方に移動し、共有リソースＲＳで合流する状況を示す図である。また、図２Ｂは、共有リソースＲＳに対して設定されたスケジュールの一例を説明するための図である。図２Ｂの例では、５つの移動体Ｚ_１，Ｚ_５，Ｚ_３，Ｚ_２，Ｚ_４がこの順番でそれぞれ通過予定時刻τ_１，τ_５，τ_３，τ_２，τ_４に共有リソースＲＳを通過するようにスケジュールが定められている。

スケジュールの作成に際しては、予め決められた制約条件を満たす必要がある。本実施の形態における制約条件は、以下の第１の制約及び第２の制約を含む。第２の制約は、安全性の確保を目的としたものである。

・第１の制約：移動体Ｚ_１〜Ｚ_Ｎにそれぞれ共有リソースの通過可能時間帯（使用可能時間帯）が割り当てられており、通過予定時刻τ_１〜τ_Ｎはそれぞれ対応する通過可能時間帯の範囲内の時刻に設定される。

・第２の制約：共有リソースを通過する移動体Ｚ_１〜Ｚ_Ｎの移動体間の時間的または空間的な間隔が、予め決められた規定間隔以上となるように制約される。よって、時間的な間隔の制約を課す場合であれば、移動体Ｚ_１〜Ｚ_Ｎのうちの或る移動体Ｚ_ｎが共有リソースを通過した後、規定間隔に対応する時間帯が経過するまで次の移動体は共有リソースを通過することができない。共有リソースを通過することができない時間帯は、移動体Ｚ_ｎに対する前後の移動体のカテゴリに依存して定まるものとする。移動体Ｚ_１〜Ｚ_Ｎが航空機の場合、移動体のカテゴリは、たとえば、機体のサイズ、または、航空機の到着・出発区分（到着または出発のいずれか一方を表す区分）に基づいて設定されればよい。或る航空機（先行機）が滑走路を使用してから、次の航空機（後続機）がその滑走路を使用することが可能となるまでの時間は、先行機のカテゴリと後続機のカテゴリとの組み合わせに応じて設定することが可能である。以下、第２の制約を「規定間隔制約」とも呼ぶこととする。

図１に示されるように、本実施の形態のスケジューリング装置１は、複数のスケジュール候補を生成し且つ各スケジュール候補の評価値を算出する最適化部１０と、この最適化部１０による最適化処理を制御する最適化制御部１１と、最適化部１０で生成された複数のスケジュール候補の中から高い評価値を有するスケジュール候補をスケジュールとして選択するスケジュール選択部１２と、データ編集処理部１３と、表示部１５及び操作入力部１６などの外部機器に接続されたインタフェース部１４とを備えて構成されている。

インタフェース部１４は、表示部１５及び操作入力部１６に接続されている。表示部１５は、たとえば、液晶表示パネルまたは有機ＥＬ表示パネルなどの画像表示デバイスである。インタフェース部１４は、スケジューリング装置１により生成されたスケジュールを表示部１５に表示させることが可能である。また、インタフェース部１４は、外部通信機器との間で通信データを送受信する通信機能をも有するので、スケジューリング装置１により生成されたスケジュールを外部通信機器に送信することができる。

また、操作入力部１６は、ユーザによる操作入力を受け付ける入力ボタン及び入力キーを有している。データ編集処理部１３は、インタフェース部１４を介してユーザによる操作入力を受け付け、この操作入力に応じてデータ格納部２０に格納されている各種データの設定値を編集可能とする機能を有する。具体的には、データ編集処理部１３は、表示部１５にデータ編集用画面を表示させることができる。ユーザは、そのデータ編集用画面を視認しつつ操作入力部１６を操作してデータ編集処理部１３に情報を入力することが可能である。

最適化部１０は、図１に示されるように、移動体情報記憶部２１，スケジュール記憶部２２及び制約条件記憶部２３を含むデータ格納部２０と、複数のスケジュール候補を生成してこれらスケジュール候補をデータ格納部２０内のスケジュール記憶部２２に記憶させるスケジューリング処理部３０と、スケジューリング処理部３０に与えるべき移動体識別子の初期順列を生成する初期順列生成部３１とを備えている。最適化部１０は、更に、スケジュール記憶部２２に記憶されているスケジュール候補を基に構成される移動体識別子の順列（以下「順列候補」ともいう。）から部分列を選択する部分列選択部３２と、移動体のカテゴリを基準としてその部分列を並べ替えることで当該順列候補を新たな順列に変換する順列変換部３３とを備えている。

最適化制御部１１は、最適化部１０による最適化処理を制御する機能を有している。具体的には、最適化制御部１１は、最適化の終了判定を行うことができる。スケジュール選択部１２は、最適化が終了した時点で評価値の高いスケジュールを選択し、当該選択されたスケジュールをインタフェース部１４経由で表示部１５に出力することができる。あるいは、スケジュール選択部１２は、当該選択されたスケジュールをインタフェース部１４経由で外部通信機器に送信することもできる。

データ格納部２０においては、移動体情報記憶部２１は、スケジューリング対象となる移動体Ｚ_１〜Ｚ_Ｎの識別子（以下「移動体識別子」ともいう。）、移動体Ｚ_１〜Ｚ_Ｎのそれぞれのカテゴリ、及び、共有リソースの通過可能時間帯を含む移動体情報が予め記憶されている領域である。図３は、移動体情報の一例をテーブル形式で示す図である。図３に示されるように、移動体情報記憶部２１には、移動体識別子ＩＤ_１〜ＩＤ_５，…と、移動体のカテゴリＦ_１〜Ｆ_５，…と、共有リソースの通過可能時間帯Ｔ_１ａ，Ｔ_１ｃ，…，Ｔ_５ａ，Ｔ_５ｃ，…とが記憶されている。図３において、通過可能時間帯Ｔ_ｉａは、ｉ番目の移動体Ｚ_ｉの移動体識別子ＩＤ_ｉに対応して設けられた時刻ｔ_ｉａから時刻ｔ_ｉｂまでの通過可能時間帯を意味し、通過可能時間帯Ｔ_ｉｃは、移動体識別子ＩＤ_ｉに対応して設けられた時刻ｔ_ｉｃから時刻ｔ_ｉｄまでの時間帯を意味する。

１つの移動体識別子ＩＤ_ｉに対して単数または複数の通過可能時間帯を設定することが可能である。図４Ａは、移動体Ｚ_ｉに対して設定された単一の通過可能時間帯Ｔ_ｉａの例を示す図であり、図４Ｂは、移動体Ｚ_ｉに対して設定された３つの通過可能時間帯Ｔ_ｉａ，Ｔ_ｉｃ，Ｔ_ｉｅの例を示す図である。スケジューリング処理部３０は、上記した第１の制約に従い、移動体Ｚ_ｉに対して、図４Ａの通過可能時間帯Ｔ_ｉａの範囲内、または図４Ｂの通過可能時間帯Ｔ_ｉａ，Ｔ_ｉｃ，Ｔ_ｉｄの範囲内の通過予定時刻τ_ｉを割り当てる必要がある。

共有リソースの通過可能時間帯は、たとえば、移動体の現在位置、移動体のとり得る速度、移動体の現在位置から共有リソースに至るまでにとり得る経路、及び、移動体の燃料残量といった複数の要素によって決めることができる。移動体が航空機の場合に当該移動体が待機旋回可能な空域があるときは、図４Ｂに示したように、複数の通過可能時間帯Ｔ_ｉａ，Ｔ_ｉｃ，Ｔ_ｉｅを設定することができる。なお、後述する各移動体の遅延量の評価のために、通過可能時間帯全体の下限時刻（最早時刻）が基準時刻として使用される。図４Ａ及び図４Ｂの場合、基準時刻はｔ_ｉａである。

スケジュール記憶部２２は、移動体Ｚ_１〜Ｚ_Ｎの順序を定める移動体識別子ＩＤ_１〜ＩＤ_Ｎの配列である順列を記憶するとともに、スケジューリング処理部３０により生成されるスケジュール候補及びその評価値の組み合わせを示すスケジュール情報を記憶するための領域である。

制約条件記憶部２３は、上記した第２の制約すなわち規定間隔制約に関する制約情報が予め記憶されている領域である。図５Ａは、制約情報の一例をテーブル形式で示す図であり、図５Ｂは、先行移動体Ｚ_ｊと後続移動体Ｚ_ｋとの間の規定間隔Δ（ｊ，ｋ）を概略的に示す図である。スケジューリング処理部３０は、規定間隔制約に従い、共有リソースを通過する際の移動体間に規定間隔以上の時間間隔を設ける必要がある。図５Ａは、先行移動体のカテゴリと後続移動体のカテゴリとの組み合わせに対応する規定間隔の設定値を示している。本実施の形態の移動体は、ヘビー（Ｈｖ）、ミディアム（Ｍｄ）及びライト（Ｌｔ）という３種類のカテゴリのいずれかに分類される。図５Ａによれば、先行移動体Ｚ_ｊがヘビーに分類され、後続移動体Ｚ_ｋがライトに分類されている場合、スケジューリング処理部３０は、これら先行移動体Ｚ_ｊ及び後続移動体Ｚ_ｋにそれぞれ割り当てるべき通過予定時刻τ_ｊ，τ_ｋ間に１２０以上の時間間隔を空けなければならない。航空機の場合、規定間隔の具体的な値は、たとえば、カテゴリに属する機体により発生する後方乱気流の持続時間、及び、後方乱気流が機体に及ぼす影響の大きさに基づいて設定することが可能である。

なお、制約条件記憶部２３においては、図５Ａに示した制約情報の他に、たとえば、特定の共有リソースについて移動体間で一律に設定されるべき時間間隔などの制約が記憶されていてもよい。

初期順列生成部３１は、移動体情報記憶部２１からスケジューリング対象の移動体Ｚ_１〜Ｚ_Ｎの移動体情報の供給を受けると、この移動体情報に基づいて移動体識別子ＩＤ_１〜ＩＤ_Ｎの順序付き配列である初期順列を生成し、この初期順列のデータをスケジュール記憶部２２に記憶させる。初期順列は、移動体Ｚ_１〜Ｚ_Ｎによる共有リソースの通過順序を暫定的に定める配列である。たとえば、５個の移動体Ｚ_１，Ｚ_５，Ｚ_３，Ｚ_２，Ｚ_４がこの順番で共有リソースを通過する場合の初期順列は、たとえば、｛ＩＤ_１，ＩＤ_５，ＩＤ_３，ＩＤ_２，ＩＤ_４｝という移動体識別子の順序付き配列で構成される。

前述のとおり、各移動体に割り当てられている共有リソースの通過可能時間帯には幅があり、また、移動体間で共有リソースの通過可能時間帯が重複する場合がある。初期順列生成部３１は、先着順方式で初期順列を生成することができる。具体的には、初期順列生成部３１は、以下の第１の方法及び第２の方法のうち予め定められたいずれか一方の方法で初期順列を生成することができる。

・第１の方法：共有リソースの通過可能時間帯の下限時刻（図４Ａ及び図４Ｂの例の場合、最早時刻）の順序で移動体識別子の初期順列を生成する方法。
・第２の方法：共有リソースの通過可能時間帯の上限時刻（図４Ａ及び図４Ｂの例の場合、最遅時刻）の順序で移動体識別子の初期順列を生成する方法。

なお、ユーザは、データ編集処理部１３の機能を利用して初期順列を編集することができる。具体的には、ユーザは、操作入力部１６を操作してスケジュール記憶部２２に記憶されている初期順列を編集することが可能である。

スケジューリング処理部３０は、スケジュール記憶部２２から初期順列または後述する新たな順列を入力順列として取得し、移動体Ｚ_１〜Ｚ_Ｎに対して上記制約条件を満たす通過予定時刻の割り当てを当該入力順列の順番で実行することによりスケジュール候補を生成するとともに、このスケジュール候補の評価値を算出する。生成されたスケジュール候補とその評価値の組は、スケジュール記憶部２２に記憶される。スケジュール候補の具体的な生成方法については後述する。

なお、上記第１の制約及び第２の制約（規定間隔制約）だけでなく、第１の制約及び第２の制約以外の第３の制約が制約条件記憶部２３に記憶されている場合には、スケジューリング処理部３０は、第１〜第３の制約を満たすスケジュール候補を生成してもよい。

スケジュール候補の評価値Ｅ（ｐ）（ｐは、スケジュール候補の識別番号）は、たとえば、複数の移動体Ｚ_１〜Ｚ_Ｎのそれぞれの遅延量δ_ｐ（１）〜δ_ｐ（Ｎ）の総和の逆数として算出することができる。たとえば、ｎ番目の移動体Ｚ_ｎに割り当てられている通過可能時間帯全体の下限時刻を基準時刻ｔ_Ｒ（ｎ）とするとき、移動体Ｚ_ｎの遅延量δ_ｐ（ｎ）は、次式（１）によって定義可能である。
δ_ｐ（ｎ）＝τ_ｎ−ｔ_Ｒ（ｎ） （１）

また、評価値Ｅ（ｐ）は、たとえば、次式（２）によって与えられる。
Ｅ（ｐ）＝１／｛δ_ｐ（１）＋…＋δ_ｐ（Ｎ）＋ε｝ （２）

ここで、εは、微少な正の実数である。なお、式（２）の評価値Ｅ（ｐ）は、遅延量δ_ｐ（１）〜δ_ｐ（Ｎ）の総和の逆数で表現されているが、これに限定されるものではない。遅延量の逆数１／｛δ_ｐ（１）＋ε｝〜１／｛δ_ｐ（Ｎ）＋ε｝の総和が評価値Ｅ（ｐ）として算出されてもよい。

スケジュール候補は、評価値Ｅ（ｐ）が高いほど、高い評価を有する良い候補であるということができる。

また、公平性を評価するために、共有リソースへの先着順（たとえば、共有リソースの通過可能時間帯内の基準時刻の順、具体的には、その下限時刻または上限時刻のいずれかの順）を基準とした移動体Ｚ_１〜Ｚ_Ｎの追い越し発生数に基づいて評価値Ｅ（ｐ）が算出されてもよい。スケジューリング処理部３０が、或る入力順列に基づいてｐ番目のスケジュール候補を生成するとき、ｎ番目の移動体Ｚ_ｎの追い越し発生数Ｏ_ｐ（ｎ）は、先着順の順列と、ｐ番目のスケジュール候補を基に構成される順列候補との間の移動体Ｚ_ｎの順位の下降数または上昇数として定義可能である。たとえば、先着順の順列と順列候補との間に以下の関係が成立するものと考える。

・先着順の順列＝｛ＩＤ_１，ＩＤ_２，ＩＤ_３，ＩＤ_４，ＩＤ_５｝（ｔ_Ｒ（１）＜ｔ_Ｒ（２）＜ｔ_Ｒ（３）＜ｔ_Ｒ（４）＜ｔ_Ｒ（５））
・順列候補＝｛ＩＤ_１，ＩＤ_３，ＩＤ_４，ＩＤ_５，ＩＤ_２｝（τ_１＜τ_３＜τ_４＜τ_５＜τ_２）

この場合、先着順の順列と順列候補との間の移動体Ｚ_ｎの順位の下降数を追い越し発生数Ｏ_ｐ（ｎ）として定義すれば、移動体Ｚ_２は、３つの移動体Ｚ_３，Ｚ_４，Ｚ_５に追い越されているので、移動体Ｚ_２の順位の下降数は「３」である。移動体Ｚ_１，Ｚ_３，Ｚ_４，Ｚ_５は追い越されていないので、これら移動体Ｚ_１，Ｚ_３，Ｚ_４，Ｚ_５の追い越し発生数Ｏ_ｐ（１），Ｏ_ｐ（３），Ｏ_ｐ（４），Ｏ_ｐ（５）は零である。よって、追い越し発生数の総和は「３」となる。なお、先着順の順列と順列候補との間の移動体Ｚ_ｎの順位の上昇数を追い越し発生数Ｏ_ｐ（ｎ）として定義した場合も、同様の結果が得られる。

スケジュール候補は、追い越し発生数の総和が低いほど、公平性が高く、評価が高いものとすることが好ましい。追い越し発生数の総和または最大値をＯ_ｐで表すとき、たとえば、次式（３）に基づいて評価値Ｅ（ｐ）を算出することができる。
Ｅ（ｐ）＝１／｛δ_ｐ（１）＋…＋δ_ｐ（Ｎ）＋Ｏ_ｐ＋ε｝ （３）

部分列選択部３２は、部分列選択処理を実行する。すなわち、部分列選択部３２は、スケジュール記憶部２２から一のスケジュール候補を取得し、このスケジュール候補を基に構成される順列候補から部分列を選択する。順列変換部３３は、部分列選択部３２で選択された部分列に対して順列変換処理を実行する。すなわち、順列変換部３３は、部分列選択部３２で選択された部分列を、当該部分列に対応する移動体のカテゴリを基準として予め定められた規則に従って並べ替えることにより、順列候補を新たな順列に変換する。その新たな順列はスケジュール記憶部２２に記憶される。

スケジューリング処理部３０は、順列変換部３３で生成された新たな順列をスケジュール記憶部２２から読み出し、この新たな順列に対してスケジュール生成処理を実行する。すなわち、スケジューリング処理部３０は、スケジュール記憶部２２から当該新たな順列を入力順列として取得し、移動体Ｚ_１〜Ｚ_Ｎの１つ１つに対して上記制約条件を満たす通過予定時刻の割り当てを当該入力順列の順番で実行することによりスケジュール候補を生成するとともに、このスケジュール候補の評価値を算出する。生成されたスケジュール候補とその評価値の組は、スケジュール記憶部２２に記憶される。

更に、部分列選択部３２は、スケジュール記憶部２２から一のスケジュール候補を取得して部分列選択処理を実行する。次いで、順列変換部３３は、部分列選択部３２で選択された部分列に対して順列変換処理を実行して新たな順列を生成する。その新たな順列はスケジュール記憶部２２に記憶される。このようにして、スケジューリング処理部３０、部分列選択部３２及び順列変換部３３は、スケジュール生成処理、部分列選択処理及び順列変換処理を反復して実行することにより、複数のスケジュール候補とこれらの評価値とを生成することができる。

スケジュール選択部１２は、スケジュール記憶部２２に蓄積された複数のスケジュール候補の中から最大の評価値を有するスケジュール候補をスケジュールとして選択し、このスケジュールをインタフェース部１４に出力する。インタフェース部１４は、このスケジュールを表示部１５に表示させ、あるいは、リクエストを発した外部通信機器に送信することができる。

次に、本実施の形態のスケジューリング装置１の動作について詳細に説明する。図６は、スケジューリング装置１による最適化処理であるスケジューリングの手順の一例を概略的に示すフローチャートである。スケジューリング処理部３０は、インタフェース部１４に入力された操作入力または通信データのいずれかに含まれるリクエストを検出すると、このリクエストに応じて、移動体情報記憶部２１から初期順列生成部３１に移動体情報を供給することにより図６のスケジューリングを開始させる。

図６を参照すると、初期順列生成部３１は、移動体情報記憶部２１から供給された移動体情報に基づいて初期順列を生成する（ステップＳＴ１０）。初期順列は、以下のような配列であると仮定する。
初期順列＝｛ＩＤ_ａ［１］，ＩＤ_ａ［２］，…，ＩＤ_ａ［Ｎ］｝

ここで、ｔ_Ｒ（ａ［ｉ］）＜ｔ_Ｒ（ａ［ｉ＋１］）の関係が成立する。ａ［ｉ］は、移動体識別子ＩＤ_ａ［ｉ］に一意に対応する番号（以下「移動体番号」という。）であり、１〜Ｎの範囲内の整数である。また、ｉは、初期順列における移動体識別子ＩＤ_ａ［ｉ］の順位を示す順序番号であり、１〜Ｎの範囲内の整数である。スケジュール生成処理の開始時点では、全ての移動体Ｚ_ａ［１］〜Ｚ_ａ［Ｎ］に対して通過予定時刻τ_ａ［１］〜τ_ａ［Ｎ］が未割当ての状態にある。

次に、スケジューリング処理部３０は、その初期順列を入力順列として使用するスケジュール生成処理を実行する（ステップＳＴ１１）。図７は、ステップＳＴ１１のスケジュール生成処理の手順の一例を示すフローチャートである。

図７を参照すると、スケジューリング処理部３０は、入力順列の順番に基づき、スケジューリング対象の移動体Ｚ_ａ［１］〜Ｚ_ａ［Ｎ］の中から、通過予定時刻τ_ａ［ｉ］が未だ割り当てられていない移動体Ｚ_ａ［ｉ］を１つ選択する（ステップＳＴ３１）。ここで、「移動体Ｚ_ａ［ｉ］を選択する」ことは、入力順列における移動体識別子ＩＤ_ａ［１］〜ＩＤ_ａ［Ｎ］の中から当該入力順列の順番に従って移動体識別子ＩＤ_ａ［ｉ］を１つ選択することを意味する。ステップＳＴ３１が最初に実行されるとき、入力順列の中で最も順番の早い（すなわち最も順位の高い）移動体識別子ＩＤ_{ａ［ｉ＝１］}が選択される。次いで、スケジューリング処理部３０は、移動体情報記憶部２１及び制約条件記憶部２３から制約条件を取得する（ステップＳＴ３２）。すなわち、スケジューリング処理部３０は、移動体情報記憶部２１から、共有リソースの通過可能時間帯に関する第１の制約のデータを取得し、制約条件記憶部２３から規定間隔制約のデータを取得する（ステップＳＴ３２）。

次に、スケジューリング処理部３０は、ステップＳＴ３１で選択された移動体Ｚ_ａ［ｉ］に対して当該制約条件を満たす通過予定時刻τ_ａ［ｉ］の割り当てを試みる（ステップＳＴ３３）。言い換えれば、スケジューリング処理部３０は、当該制約条件を満たしつつ、選択された移動体Ｚ_ａ［ｉ］の時間軸への割り当てを試みる（ステップＳＴ３３）。具体的には、制約条件を満たす通過可能時間帯内の最早時刻が当該移動体の通過予定時刻τ_ａ［ｉ］として割り当てられる。その理由は、移動体Ｚ_ａ［ｉ］の遅延量を最小化するためである。ステップＳＴ３３が最初に実行されるとき、先行して通過予定時刻が割り当てられた移動体が存在しないので、上記した第１の制約及び第２の制約のうち、共有リソースの通過可能時間帯に関する第１の制約のみが制約条件として使用される。

移動体Ｚ_ａ［ｉ］に対する通過予定時刻τ_ａ［ｉ］の割り当てが成功しなかった場合（ステップＳＴ３４のＮＯ）、スケジューリング処理部３０は、スケジュール生成が失敗したとの判定結果をインタフェース部１４に出力する（ステップＳＴ３７）。インタフェース部１４は、この判定結果を表示部１５に表示させる。その後、図６のステップＳＴ１３に処理が移行する。

一方、ステップＳＴ３３にて移動体Ｚ_ａ［ｉ］に対する通過予定時刻τ_ａ［ｉ］の割り当てが成功した場合（ステップＳＴ３４のＹＥＳ）、スケジューリング処理部３０は、全ての移動体Ｚ_ａ［１］〜Ｚ_ａ［Ｎ］に対する通過予定時刻τ_ａ［１］〜τ_ａ［Ｎ］の割り当てが成功したか否かを判定する（ステップＳＴ３５）。全ての移動体Ｚ_ａ［１］〜Ｚ_ａ［Ｎ］に対する割り当てが未だ成功していない場合（ステップＳＴ３５のＮＯ）、スケジューリング処理部３０は、順序番号ｉをｉ＋１にインクリメントして次の移動体Ｚ_ａ［ｉ］を選択する（ステップＳＴ３１）。その後、ステップＳＴ３２〜ＳＴ３４が実行される。

ステップＳＴ３３では、通過予定時刻τ_ａ［ｊ］（ｊ＜ｉ）が割り当てられた移動体Ｚ_ａ［ｊ］が既に存在するので、スケジューリング処理部３０は、上記第１の制約及び規定間隔制約の双方の制約を満たす通過予定時刻τ_ａ［ｉ］の割り当てを試みる（ステップＳＴ３３）。

最終的に、全ての移動体Ｚ_ａ［１］〜Ｚ_ａ［Ｎ］に対する通過予定時刻τ_ａ［１］〜τ_ａ［Ｎ］の割り当てが成功した場合（ステップＳＴ３５のＹＥＳ）、スケジューリング処理部３０は、それら割り当てにより生成されたスケジュール候補をスケジュール記憶部２２に出力する（ステップＳＴ３６）。

以上に説明したように、図７のスケジュール生成処理によれば、スケジューリング処理部３０は、移動体Ｚ_ａ［１］〜Ｚ_ａ［Ｎ］に対して、制約条件を満たす通過予定時刻τ_ａ［ｉ］の割り当てを入力順列の順番で実行することによりスケジュール候補を生成している。

図８Ａ〜図８Ｅは、移動体Ｚ_１〜Ｚ_３に割り当てられた通過予定時刻τ_１〜τ_３のいくつかの例を示す図である。図８Ａ〜図８Ｅの例では、入力順列は｛ＩＤ_１，ＩＤ_２，ＩＤ_３｝の配列で構成されるものとする。よって、最初は、図８Ａに示されるように、移動体Ｚ_１に通過予定時刻τ_１が割り当てられる。このとき、共有リソースの通過可能時間帯Ｔ_１ａ，Ｔ_１ｃが割り当て可能時間帯Ｐ_１ａ，Ｐ_１ｃとなる。通過予定時刻τ_１は、これら割り当て可能時間帯Ｐ_１ａ，Ｐ_１ｃ内の最早時刻に設定される。

次に、図８Ｂに示されるように、移動体Ｚ_２に通過予定時刻τ_２が割り当てられる。このとき、通過予定時刻τ_１の割り当てが既に完了しているので、時刻τ_１から後ろ方向に規定間隔Δ（１，２）以内の範囲内に通過予定時刻τ_２を設定することができない。図８Ｂの例では、割り当て可能時間帯Ｐ_２ａは、通過可能時間帯Ｔ_２ａとなる。通過予定時刻τ_２は、この割り当て可能時間帯Ｐ_２ａ内の最早時刻に設定される。

次に、図８Ｃに示されるように、移動体Ｚ_３に通過予定時刻τ_３が割り当てられる。このとき、移動体Ｚ_１，Ｚ_２に対する通過予定時刻τ_１，τ_２の割り当てが既に完了しているので、時刻τ_１から後ろ方向に規定間隔Δ（１，３）以内の範囲内、時刻τ_１から前方向に規定間隔Δ（３，１）以内の範囲内、時刻τ_２から後ろ方向に規定間隔Δ（２，３）以内の範囲内、及び、時刻τ_２から前方向に規定間隔Δ（３，２）以内の範囲内に通過予定時刻τ_３を設定することができない。よって、割り当て可能時間帯Ｐ_３ａ，Ｐ_３ｃは、通過可能時間帯Ｔ_３ａ，Ｔ_３ｃの中の制約された時間帯となる。通過予定時刻τ_３は、これら割り当て可能時間帯Ｐ_３ａ，Ｐ_３ｃ内の最早時刻に設定される。

図８Ｄ及び図８Ｅは、図８Ｃの場合とは異なる範囲に通過可能時間帯Ｔ_３ａ，Ｔ_３ｃが存在する場合の通過予定時刻τ_３を示す図である。また、図９Ａ〜図９Ｃは、図８Ａ〜図８Ｅの場合の入力順列とは異なる入力順列が与えられた場合に移動体Ｚ_１〜Ｚ_３に割り当てられた通過予定時刻τ_１〜τ_３の例を示す図である。図９Ａ〜図９Ｃの例では、入力順列は｛ＩＤ_３，ＩＤ_２，ＩＤ_１｝の配列で構成されているものとする。よって、移動体Ｚ_３，Ｚ_２，Ｚ_１の順番で通過予定時刻τ_３，τ_２，τ_１が割り当てられる。

さて、図７に示したスケジュール生成処理は、入力順列の順番に従い、制約条件下で可能な限り最早の時刻を通過予定時刻として移動体に割り当てる処理であるから、入力順列の順番と、スケジュール候補を基に構成される順列候補の順番（割り当てられた通過予定時刻の順番）とが互いに類似したものとなる性質がある。上記のとおり、初期順列は先着順方式で生成されるので、特にスケジュール候補の評価値に公平性を評価する指標値（たとえば、上記した追い越し発生数）が組み込まれている場合には、スケジュール生成対象となる入力順列について、基本的に前記の性質が成り立つと考えられる。ただし、図８Ｃ及び図８Ｅに示したように、入力順列の順番と順列候補の順番とは、必ずしも一致するものではない。

なお、入力順列の順番と順列候補の順番とが互いに一致するとの制約が採用されてもよい。この制約は、たとえば、上記ステップＳＴ３３において、割り当てられるべき通過予定時刻τ_ａ［ｉ］を、割り当て済みの全ての通過予定時刻τ_ａ［ｊ］（ｊ＜ｉ）の後の時間帯に限定することにより実現することができる。このように、入力順列の順番と、スケジュール候補を基に構成される順列候補の順番とを互いに一致させるスケジューリングを行うことにより、人間にとって理解しやすいスケジュールを生成することができる。

次に、図６を参照すると、上記したスケジュール生成処理（ステップＳＴ１１）の実行後、スケジューリング処理部３０は、当該生成されたスケジュール候補の評価値を算出する（ステップＳＴ１３）。評価値の算出方法は上述したとおりである。なお、スケジュール生成が失敗してスケジュール候補が存在しない場合には、評価値は算出されないものとする。

その後、スケジューリング処理部３０は、最適化を終了するか否かを判定する（ステップＳＴ１４）。具体的には、たとえば、スケジューリング処理部３０で生成されたスケジュール候補の数が予め定められた設定値を超えたとの条件（以下、条件Ａという。）が成立したときにスケジューリング処理部３０は最適化終了と判定すればよい（ステップＳＴ１４のＹＥＳ）。あるいは、スケジューリングの処理時間が予め定められた設定時間を超えたとの条件（以下、条件Ｂという。）が成立したときにスケジューリング処理部３０は最適化終了と判定してもよい（ステップＳＴ１４のＹＥＳ）。あるいは、ステップＳＴ１３で算出された評価値が或る規定の基準値を満足したとの条件（以下、条件Ｃという。）が成立したときにスケジューリング処理部３０は最適化終了と判定してもよい（ステップＳＴ１４のＹＥＳ）。あるいは、これらの条件Ａ〜Ｃのうちの２以上の条件の組み合わせが成立したときにスケジューリング処理部３０は最適化終了と判定することもできる。最適化終了との判定がなされたとき、ステップＳＴ２０に処理が移行する。

一方、最適化を終了しないとの判定がなされた場合（ステップＳＴ１４のＮＯ）、新たな順列を生成する処理が実行される（ステップＳＴ１５〜ＳＴ１７）。具体的には、部分列選択部３２が、スケジュール記憶部２２から一のスケジュール候補を取得し、このスケジュール候補を基に移動体識別子の順列候補を構成する（ステップＳＴ１５）。ここで、部分列選択部３２は、スケジュール記憶部２２に記憶されている単数または複数のスケジュール候補の中から最大の評価値を有するスケジュール候補を選択することが好ましい。その理由は、評価値が高いスケジュール候補に基づいて新たな順列を生成することにより、より評価値の高いスケジュール候補を得ることが期待できるためである。ステップＳＴ１５で構成された順列候補は、以下のような配列であると想定する。
順列候補＝｛ＩＤ_ｂ［１］，ＩＤ_ｂ［２］，…，ＩＤ_ｂ［Ｎ］｝（τ_ｂ［ｉ］＜τ_{ｂ［ｉ＋１］}）

ここで、ｂ［ｉ］は、移動体識別子ＩＤ_ｂ［ｉ］に一意に対応する移動体番号であり、１〜Ｎの範囲内の整数である。ｉは、順列候補における移動体識別子ＩＤ_ｂ［ｉ］の順位を示す順序番号であり、１〜Ｎの範囲内の整数である。

次に、部分列選択部３２は、順列候補に対して部分列選択処理を実行する（ステップＳＴ１６）。この部分列選択処理では、部分列選択部３２は、当該順列候補から、移動体識別子の連続的な配列である部分列を選択する。この部分列は、当該部分列を構成する複数の移動体識別子に対応する複数の通過可能時間帯のすべてが重複する配列である。言い換えれば、その部分列は、当該部分列を構成する複数の移動体識別子に対応する複数の通過可能時間帯のすべてが同一時間帯（以下「重複通過可能時間帯」ともいう。）を共有する配列である。

図１０及び図１１は、実施の形態１に係る部分列選択処理（ステップＳＴ１６）の手順の例を概略的に示すフローチャートである。図１０のフローチャートと図１１のフローチャートとは、結合子Ｃ１，Ｃ２を介して相互に接続されている。図１２は、当該順列候補、移動体のカテゴリ及び通過可能時間帯の間の対応関係の一例をテーブル形式で示す図である。図１２に示されるように、当該順列候補を構成する各移動体識別子に対して、移動体のカテゴリ（Ｈｖ，ＭｄまたはＬｔ）と移動体可能時間帯とが関連付けられている。

図１０を参照すると、先ず、部分列選択部３２は、当該順列候補に対応する移動体Ｚ_ｂ［１］〜Ｚ_ｂ［Ｎ］の中から、指定されたカテゴリに属する移動体Ｚ_ｂ［ｉ］を確率的に選択する（ステップＳＴ４１）。ここで、たとえば、図５Ａに示した規定間隔制約が使用される場合には、カテゴリとしてヘビー（Ｈｖ）を指定することが適切である。理由を以下に説明する。図５Ａから分かるように、ヘビー以外の異種カテゴリ（ミディアム及びライト）に属する移動体については、その異種カテゴリに属する移動体とヘビーに属する移動体との間の先行及び後続の位置関係によって規定間隔が大きく変わる。具体的には、ヘビーに属する移動体が先行移動体である場合、これ以外の場合と比べて、移動体間の規定間隔を大きくする必要があるため、他の条件が同じであれば、遅延量の大きなスケジュール候補が生成される可能性が高い。この場合、後述する部分列の並べ替え（図６のステップＳＴ１７）によって、ヘビーに属する移動体の順位（すなわち、ヘビーに属する移動体の移動体識別子の順序番号）が変化すると、スケジュール候補の遅延量が大きく変化する可能性が高い。このようにスケジュールの最適化において遅延量を大きく変化させるスケジュール候補に絞って探索を行うことにより、効率の良い探索が可能になることが期待できる。

なお、本実施の形態では、指定されたカテゴリに属する移動体Ｚ_ｂ［ｉ］の選択は確率的になされているが（ステップＳＴ４１）、これに限定されるものではない。予め定めたルールに基づいて移動体Ｚ_ｂ［ｉ］の選択が決定論的に行われてもよい。たとえば、部分列選択部３２は、順列候補に対し、最初の部分列選択処理の実行時は、指定されたカテゴリに属する移動体の中で先頭から１番目の移動体を選択し、２回目の部分列選択処理の実行時には、指定されたカテゴリに属する移動体の中で先頭から２番目の移動体を選択し、３回目の部分列選択処理の実行時には、指定されたカテゴリに属する移動体の中で先頭から３番目の移動体を選択し、・・・とのルールを使用することが考えられる。

次に、部分列選択部３２は初期設定を行う（ステップＳＴ４２，ＳＴ４３）。具体的には、部分列選択部３２は、重複通過可能時間帯を移動体Ｚ_ｂ［ｉ］の通過可能時間帯に設定し（ステップＳＴ４２）、また、重複移動体リストを、移動体Ｚ_ｂ［ｉ］のみが登録されているリストに設定する（ステップＳＴ４３）。ここで、「重複移動体リストに移動体が登録されている」とは、重複移動体リストに当該移動体の移動体識別子が登録されていることとを意味する。なお、重複通過可能時間帯及び重複移動体リストは作業用のデータである。

以下、部分列選択部３２は、重複通過可能時間帯が空集合とならない範囲内で、できるだけ長い部分列を構成する重複移動体リストを探す。そこで、まずは、部分列選択部３２は、順列候補において順序番号ｉが増大する方向へ、重複移動体リストを可能な限り伸ばすことを試みる（ステップＳＴ４４〜ＳＴ５２）。

すなわち、部分列選択部３２は、移動体番号ｃをｂ［ｉ＋１］に設定し（ステップＳＴ４４）、当該順列候補に対応する移動体Ｚ_ｂ［１］〜Ｚ_ｂ［Ｎ］の中に移動体Ｚ_ｃが存在するか否かを判定する（ステップＳＴ４５）。移動体Ｚ_ｃが存在すると判定された場合（ステップＳＴ４５のＹＥＳ）、部分列選択部３２は、重複通過可能時間帯と、移動体Ｚ_ｃの通過可能時間帯（移動体Ｚ_ｃに割り当てられている通過可能時間帯）との間の時間軸上で重複する共通部分の検出を試みる（ステップＳＴ４６）。共通部分が存在する場合（ステップＳＴ４７のＹＥＳ）、部分列選択部３２は、重複通過可能時間帯を当該共通部分に設定し（ステップＳＴ４８）、重複移動体リストに移動体Ｚ_ｃを追加登録する（ステップＳＴ４９）。

そして、部分列選択部３２は、順序番号ｉをｉ＋１にインクリメントし（ステップＳＴ５１）、部分列の長さが予め設定された上限に到達したか否かを判定する（ステップＳＴ５２）。ここで、部分列の長さは、重複移動体リストに登録されている移動体の個数、言い換えれば、重複移動体リストに登録されている移動体の移動体識別子の個数と一致する。部分列の長さが上限に到達したと判定された場合（ステップＳＴ５２のＹＥＳ）、部分列選択部３２は、処理負荷軽減のため、部分列の長さをこれ以上に延伸することを中止し、ステップＳＴ６９に処理を移行させる。一方、部分列の長さが上限に到達していないと判定された場合（ステップＳＴ５２のＮＯ）、ステップＳＴ４４に処理が戻る。

上記ステップＳＴ４５で移動体Ｚ_ｃが存在しないと判定された場合（ステップＳＴ４５のＮＯ）、あるいは、ステップＳＴ４７で共通部分が存在しないと判定された場合（ステップＳＴ４７のＮＯ）、図１１のステップＳＴ６１に処理が移行する。この場合は、部分列選択部３２は、順列候補において順序番号ｉが減少する方向へ、重複移動体リストを可能な限り伸ばすことを試みる（図１１のステップＳＴ６１〜ＳＴ６８）。

すなわち、部分列選択部３２は、移動体番号ｃをｂ［ｉ−１］に設定し（ステップＳＴ６１）、当該順列候補に対応する移動体Ｚ_ｂ［１］〜Ｚ_ｂ［Ｎ］の中に移動体Ｚ_ｃが存在するか否かを判定する（ステップＳＴ６２）。移動体Ｚ_ｃが存在すると判定された場合（ステップＳＴ６２のＹＥＳ）、部分列選択部３２は、重複通過可能時間帯と、移動体Ｚ_ｃの通過可能時間帯（移動体Ｚ_ｃに割り当てられている通過可能時間帯）との間の時間軸上で重複する共通部分の検出を試みる（ステップＳＴ６３）。共通部分が存在する場合（ステップＳＴ６４のＹＥＳ）、部分列選択部３２は、重複通過可能時間帯を当該共通部分に設定し（ステップＳＴ６５）、重複移動体リストに移動体Ｚ_ｃを追加登録する（ステップＳＴ６６）。

そして、部分列選択部３２は、順序番号ｉをｉ−１にデクリメントし（ステップＳＴ６７）、部分列の長さが予め設定された上限に到達したか否かを判定する（ステップＳＴ６８）。部分列の長さが上限に到達したと判定された場合（ステップＳＴ６８のＹＥＳ）、部分列選択部３２は、処理負荷軽減のため、部分列の長さをこれ以上に延伸することを中止し、図１０のステップＳＴ６９に処理を移行させる。一方、部分列の長さが上限に到達していないと判定された場合（ステップＳＴ６８のＮＯ）、ステップＳＴ６１に処理が戻る。

上記ステップＳＴ６２で移動体Ｚ_ｃが存在しないと判定された場合（ステップＳＴ６２のＮＯ）、あるいは、ステップＳＴ６４で共通部分が存在しないと判定された場合（ステップＳＴ６４のＮＯ）、図１０のステップＳＴ６９に処理が移行する。

最終的に、ステップＳＴ６９では、部分列選択部３２は、重複移動体リストに登録されている移動体の移動体識別子の配列を部分列として選択する（ステップＳＴ６９）。その後は、図６のスケジューリングに処理が戻る。

図１３は、同一の重複通過可能時間帯ＯＴａを共有する通過可能時間帯Ｔ_ｂ［３］，Ｔ_ｂ［４］，Ｔ_ｂ［５］，Ｔ_ｂ［６］の例を示す図である。図１３に示されるように、移動体Ｚ_ｂ［３］，Ｚ_ｂ［４］，Ｚ_ｂ［５］，Ｚ_ｂ［６］については、通過可能時間帯Ｔ_ｂ［３］，Ｔ_ｂ［４］，Ｔ_ｂ［５］，Ｔ_ｂ［６］のすべてが互いに重複する。しかしながら、通過可能時間帯Ｔ_ｂ［２］，Ｔ_ｂ［７］は、重複通過可能時間帯ＯＴａを共有しない。よって、図１３の場合、部分列は、｛ＩＤ_ｂ［３］，ＩＤ_ｂ［４］，ＩＤ_ｂ［５］，ＩＤ_ｂ［６］｝の配列で構成される。

たとえば、図１３に示す通過可能時間帯を有する順列候補に対し、図１０のステップＳＴ４１でヘビーに属する移動体Ｚ_ｂ［３］が選択された場合を考える。この場合、ステップＳＴ４４〜ＳＴ５２が実行されることにより、重複移動体リストには、移動体Ｚ_ｂ［３］，Ｚ_ｂ［４］，Ｚ_ｂ［５］，Ｚ_ｂ［６］が登録される（ステップＳＴ４９）。その後、重複通過可能時間帯と移動体Ｚ_ｂ［７］の通過可能時間帯との共通部分が空集合になるので（ステップＳＴ４７のＮＯ）、図１１のステップＳＴ６１に処理が移行する。その後のステップＳＴ６４で、重複通過可能時間帯と移動体Ｚ_ｂ［２］の通過可能時間帯との共通部分が空集合になる（ステップＳＴ６４のＮＯ）。したがって、最終的に、部分列選択部３２は、重複移動体リストに登録されている移動体Ｚ_ｂ［３］，Ｚ_ｂ［４］，Ｚ_ｂ［５］，Ｚ_ｂ［６］の移動体識別子ＩＤ_ｂ［３］，ＩＤ_ｂ［４］，ＩＤ_ｂ［５］，ＩＤ_ｂ［６］の配列を部分列として選択する（ステップＳＴ６９）。

図６を参照すると、部分列選択処理（ステップＳＴ１６）の実行後は、順列変換部３３は、移動体のカテゴリを基準として予め定められた規則に基づいて当該部分列を並べ替えることにより当該順列候補を新たな順列に変換する（ステップＳＴ１７）。具体的には、順列変換部３３は、当該部分列を、同種のカテゴリに分類されている２つ以上の移動体を連続的に順序付けする配列に並べ替えることができる。ここで、順列変換部３３は、予め定められたカテゴリの順序で当該部分列を並べ替えることが好ましい。

図１４Ａは、図１２に示した順列候補から選択された部分列ＰＳの一例を示す図である。図１４Ｂ及び図１４Ｃは、部分列ＰＳの並べ替えにより生成された部分列ＰＳ１，ＰＳ２の例を示す図である。図１４Ｂ及び図１４Ｃに示される部分列ＰＳ１，ＰＳ２では、同種のカテゴリ（Ｈｖ）に属する移動体の移動体識別子ＩＤ_ｂ［３］，ＩＤ_ｂ［５］が連続的に順序付けられている。また、図１４Ｂでは、予め定められたカテゴリの順序（Ｌｔ→Ｈｖ→Ｍｄ）で移動体識別子ＩＤ_ｂ［４］，ＩＤ_ｂ［３］，ＩＤ_ｂ［５］，ＩＤ_ｂ［６］が配列されている。一方、図１４Ｃでは、予め定められたカテゴリの他の順序（Ｌｔ→Ｍｄ→Ｈｖ）で移動体識別子ＩＤ_ｂ［４］，ＩＤ_ｂ［６］，ＩＤ_ｂ［３］，ＩＤ_ｂ［５］が配列されている。ここで、同種のカテゴリに属する移動体の移動体識別子の前後関係は入れ替えられない。

図５Ａに示した規定間隔制約が使用される場合には、異種のカテゴリに属する移動体の移動体識別子が連続して配列されると、移動体間の規定間隔の総和が大きくなる傾向がある。そのため、同種のカテゴリに属する移動体の移動体識別子が連続的に順序付けされるように部分列を並べ替えることにより、遅延量の小さなスケジュールが得られやすくなることが期待できる。その理由は、前述したとおり、スケジュール生成対象となる入力順列について、その入力順列の順番と順列候補の順番とが違いに類似したものとなるためである。また、カテゴリの好適な順序が先験情報として予め分かっている場合、その好適な順序を指定して部分列を並べ替えることにより、更に遅延量の小さなスケジュールが得られる可能性が高くなると期待される。

たとえば、図５Ａに示した規定間隔制約が適用される場合、ヘビーに属する先行移動体とライトに属する後続移動体間の規定間隔は１２０、ライトに属する先行移動体とヘビーに属する後続移動体間の規定間隔は６０、ヘビーに属する先行移動体とミディアムに属する後続移動体間の規定間隔は１２０であることから、図１４Ａに示す部分列ＰＳについては、規定間隔の総和は３００となる。一方、並べ替え後の部分列ＰＳ１については、規定間隔の総和は２７０となる。また、並べ替え後の部分列ＰＳ２については、規定間隔の総和は２１０となる。このように、並べ替え前の部分列ＰＳについての規定間隔の総和３００と比較して、並べ替え後の部分列ＰＳ１，ＰＳ２についての規定間隔の総和は減少するので、スケジュール候補の遅延量が小さくなる可能性が高いと期待することができる。

上記したステップＳＴ１６では、部分列選択部３２は、図１０及び図１１の部分列選択処理を、ステップＳＴ４１で選択する移動体を変更しつつ複数回繰り返し実行してもよい。また、部分列選択部３２は、上記した部分列選択処理だけでなく、複数種の部分列選択処理（たとえば、本実施の形態に係る部分列選択処理と後述する実施の形態２に係る部分列選択処理）を実行してもよい。また、ステップＳＴ１７では、順列変換部３３は、複数の方法で部分列の並べ替えを実行してもよい。これにより、複数の新たな順列を生成することが可能となる。

図６を参照すると、上記ステップＳＴ１７の実行後は、ステップＳＴ１１に処理が移行する。このとき、スケジューリング処理部３０は、ステップＳＴ１７で生成された単数または複数の新たな順列を入力順列として使用するスケジュール生成処理を実行する（ステップＳＴ１１）。次いで、ステップＳＴ１３〜ＳＴ１７が実行される。

最適化終了との判定がなされたとき（ステップＳＴ１４のＹＥＳ）、ステップＳＴ２０の判定処理が実行される。スケジュール選択部１２は、スケジュール記憶部２２の中にスケジュール候補が存在しないと判定した場合には（ステップＳＴ２０のＮＯ）、上記スケジューリングを終了する。一方、スケジュール選択部１２は、スケジュール記憶部２２の中に少なくとも１つのスケジュール候補が存在すると判定した場合には（ステップＳＴ２０のＹＥＳ）、スケジュール記憶部２２に記憶されているスケジュール候補の中から最大評価値を有するスケジュールを選択する（ステップＳＴ２１）。ここで、最大評価値を有するスケジュールのみならず、比較的評価値の高いスケジュールも併せて選択されてよい。スケジュール選択部１２は、選択されたスケジュールをインタフェース部１４に出力する。

なお、上記したスケジュール生成処理（ステップＳＴ１１）から、新たな順列を生成する処理（ステップＳＴ１７）までの処理が一定回数反復されても評価値が改善されない場合には、最適化制御部１１は、更なる処理を反復しても評価値の改善は望めないと判定することができる。この場合、初期順列生成部３１は、初期順列を新たに生成してもよい。この新たに生成された初期順列について、スケジュール生成処理（ステップＳＴ１１）から、新たな順列を生成する処理（ステップＳＴ１７）までの処理が反復して実行されることが好ましい。あるいは、ユーザはデータ編集処理部１３の機能を利用して、比較的評価値の高いスケジュール候補に対応する順列候補を修正することにより、初期順列を新たに生成してもよい。具体的には、ユーザは、操作入力部１６を操作して、スケジュール記憶部２２に記憶されている評価値の高い上位のスケジュール候補を選択し、当該スケジュール候補に対応する順列候補を編集することで新たな初期順列を生成することが可能である。このとき、データ編集処理部１３は、複数のスケジュール候補が評価値の昇順または降順でソートされた状態を表す編集用画像を表示部１５に表示させることができる。ユーザは、その編集用画像に基づき、評価値の高い上位のスケジュール候補を簡便に選択することができる。

上記スケジューリング装置１のハードウェア構成は、たとえば、ワークステーションまたはメインフレームなどのＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）内蔵のコンピュータで実現可能である。あるいは、スケジューリング装置１のハードウェア構成は、ＤＳＰ（Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｏｒ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）またはＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）などのＬＳＩ（Ｌａｒｇｅ Ｓｃａｌｅ Ｉｎｔｅｇｒａｔｅｄ ｃｉｒｃｕｉｔ）により実現されてもよい。

図１５は、スケジューリング装置１のハードウェア構成例である情報処理装置１ＨＷの構成を概略的に示すブロック図である。図１５の例では、情報処理装置１ＨＷは、ＣＰＵ４０ｃを含むプロセッサ４０、メモリ４１、記録媒体４２、表示インタフェース部４３、入力インタフェース部４４及び通信インタフェース部４５で構成されている。プロセッサ４０、記録媒体４２、表示インタフェース部４３、入力インタフェース部４４及び通信インタフェース部４５は、バス回路などの信号路４６を介して相互に接続されている。プロセッサ４０は、メモリ４１を作業用メモリとして利用して、記録媒体４２から読み出されたスケジューリング用のコンピュータプログラムを実行することにより、本実施の形態のスケジューリングを実現することが可能である。

プロセッサ４０は、最適化制御部１１、スケジュール選択部１２、データ編集処理部１３、スケジューリング処理部３０、初期順列生成部３１、部分列選択部３２及び順列変換部３３のそれぞれの機能を実現するハードウェアである。また、インタフェース部１４の機能は、表示インタフェース部４３、入力インタフェース部４４及び通信インタフェース部４５によって実現可能である。表示インタフェース部４３は表示部１５と接続され、入力インタフェース部４４は操作入力部１６と接続されている。また、通信インタフェース部４５は、外部通信機器と通信可能である。データ格納部２０は、記録媒体４２により実現可能である。記録媒体４２としては、たとえば、ＨＤＤ（ハードディスクドライブ）またはＳＳＤ（ソリッドステートドライブ）などの不揮発性メモリを使用することができる。

次に、以上に説明した実施の形態１のスケジューリング装置１の効果について説明する。本実施の形態のスケジューリング装置１は、スケジュール候補に基づいて構成される移動体識別子の順列候補から部分列を選択し、移動体のカテゴリを基準として当該部分列を並べ替えることで当該順列候補を新たな順列に変換している。スケジューリング処理部３０は、初期順列及び当該新たな順列を入力順列として複数のスケジュール候補を生成し且つこれらスケジュール候補の評価値を算出する。スケジュール選択部１２は、これら複数のスケジュール候補の中から評価値の高いスケジュール候補をスケジュールとして選択することができる。したがって、本実施の形態のスケジューリング装置１は、評価の高いスケジュールが得られる方向に絞って複数のスケジュール候補を生成することができるので、従来技術と比べると、無駄な探索を行うことなく効率の良い最適化処理を実行することができる。

また、図１０及び図１１の部分列選択処理の際、すべての通過可能時間帯が互いに重複する時間帯（重複通過可能時間帯）が存在するように部分列が選択されるので、新たな順列の生成（図６のステップＳＴ１７）において当該部分列がどのように並び替えられたとしても、遅延量の少ない良好なスケジュールを得る可能性を高くすることができる。

また、図１０及び図１１の部分列選択処理の際、部分列の長さに上限が設けられているので（ステップＳＴ５２，ＳＴ６８）、部分列の長さが過度に長大にならない。これにより、当該部分列に対応するスケジュールが生成不可能となる可能性を抑制することができる。

また、図１０及び図１１の部分列選択処理の際、予め定めたカテゴリに属する移動体を含む部分列が選択される（ステップＳＴ４１）。そのため、先験情報に基づき、先行移動体及び後続移動体の位置関係によって遅延量が大きく変化するカテゴリ（たとえば、ヘビー）を設定しておくことにより、遅延量が大きく変化するスケジュール候補が生成される可能性を高くすることができる。したがって、そのような方向に絞って効率の良いスケジューリングを行うことが可能となる。

また、ステップＳＴ１７で新たな順列が生成される際、順列変換部３３は、ステップＳＴ１６で選択された部分列を、同種のカテゴリに分類されている移動体を連続的に順序付けする配列に並べ替えることができる。これにより、当該新たな順列に関する規定間隔の総和が小さくなる傾向を得ることができ、遅延量の小さなスケジュールを得る可能性を高くすることができる。更に、順列変換部３３は、予め定められたカテゴリの順序で当該部分列を並べ替えることができるので、先験情報に基づきカテゴリの適切な順序を設定しておけば、当該新たな順列に関する規定間隔の総和が小さくなる傾向を得ることができる。これにより、更に遅延量の小さなスケジュールを得る可能性を高くすることができる。

また、初期順列生成（図６のステップＳＴ１０）の際、通過可能時間帯の下限時刻の順番または通過可能時間帯の上限時刻の順番で先着順に初期順列が生成される。この初期順列の順番で制約条件を満たす通過予定時刻の割り当てが実行されるため、公平性の高いスケジュールを生成することができる。

また、スケジュール候補の評価値は、各移動体に割り当てられている通過可能時間帯全体の下限時刻を基準として算出されるので、遅延量の小さなスケジュールを得ることができる。更に、スケジュールの評価値が、先着順を基準とした移動体間の追い越し発生数に基づいて算出される場合には、移動体に対して公平性の高いスケジュールを得ることができる。

そして、入力順列の順番とスケジュール候補を基に構成される順列候補の順番とが互いに一致するとの制約が採用される場合には、入力順列の順番と順列候補の順番とを互いに一致させるスケジューリングを行うことにより、予め定めた規則を反映したスケジュールが得られる可能性が大きくなる。また、付随的な効果として、人間にとって理解しやすいスケジュールを生成することもできる。

実施の形態２．
次に、本発明に係る実施の形態２について説明する。図１６は、実施の形態２に係る部分列選択処理の手順の一例を示すフローチャートである。本実施の形態のスケジューリング装置の構成は、図１０及び図１１に示した部分列選択処理に代えて、図１６に示した部分列選択処理を実行する点を除いて、上記実施の形態１のスケジューリング装置１の構成と同じである。このため、以下、図１の符号を参照しつつ、本実施の形態に係る部分列選択処理について説明する。

本実施の形態の部分列選択部３２は、図６のステップＳＴ１５で構成された順列候補に対して部分列選択処理を実行する。この部分列選択処理では、部分列選択部３２は、当該順列候補から、移動体識別子の連続的な配列である部分列を選択する。本実施の形態では、この部分列は、当該部分列を構成する複数の移動体識別子に対応する複数の通過可能時間帯のすべてが必ずしも重複している必要はない。本実施の形態の部分列は、当該部分列を構成する複数の移動体識別子のうち隣接する移動体識別子に対応する通過可能時間帯が互いに重複する配列である。

本実施の形態の部分列選択部３２は、互いに隣接する移動体識別子に対応する通過可能時間帯が互いに重複する範囲内で、できるだけ長い部分列を構成する重複移動体リストを探す。

図１６を参照すると、先ず、部分列選択部３２は、上記ステップＳＴ４１と同様に、当該順列候補に対応する移動体Ｚ_ｂ［１］〜Ｚ_ｂ［Ｎ］の中から、指定されたカテゴリに属する移動体Ｚ_ｂ［ｉ］を確率的に選択する（ステップＳＴ７１）。次に、部分列選択部３２は、重複移動体リストを、移動体Ｚ_ｂ［ｉ］のみが登録されているリストとして設定する（ステップＳＴ７２）。なお、重複移動体リストは作業用のデータである。

次に、部分列選択部３２は、当該順列候補に対応する移動体Ｚ_ｂ［１］〜Ｚ_ｂ［Ｎ］の中に移動体Ｚ_{ｂ［ｉ＋１］}が存在するか否かを判定する（ステップＳＴ７３）。移動体Ｚ_{ｂ［ｉ＋１］}が存在すると判定された場合（ステップＳＴ７３のＹＥＳ）、部分列選択部３２は、互いに隣接して順位付けされている移動体Ｚ_ｂ［ｉ］，Ｚ_{ｂ［ｉ＋１］}の通過可能時間帯の間の時間軸上で重複する共通部分の検出を試みる（ステップＳＴ７４）。共通部分が存在する場合（ステップＳＴ７５のＹＥＳ）、部分列選択部３２は、重複移動体リストに移動体Ｚ_{ｂ［ｉ＋１］}を追加登録する（ステップＳＴ７６）。

その後、部分列選択部３２は、順序番号ｉをｉ＋１にインクリメントし（ステップＳＴ７７）、ステップＳＴ７３に処理を移行させる。ここで、上記実施の形態１の場合と同様に、部分列選択部３２は、部分列の長さが予め設定された上限に到達したか否かを判定し、部分列の長さが上限に到達している場合には、ステップＳＴ７８に処理を移行させてもよい。

上記ステップＳＴ７３で移動体Ｚ_{ｂ［ｉ＋１］}が存在しないと判定された場合（ステップＳＴ７３のＮＯ）、あるいは、ステップＳＴ７５で共通部分が存在しないと判定された場合（ステップＳＴ７５のＮＯ）、部分列選択部３２は、重複移動体リストに登録されている移動体の移動体識別子の配列を部分列として選択する（ステップＳＴ７８）。その後は、図６のスケジューリングに処理が戻る。

図１７は、互いに隣接する移動体識別子の通過可能時間帯が重複する状況の一例を概略的に示す図である。図１７の例では、通過可能時間帯Ｔ_ｂ［３］，Ｔ_ｂ［４］が互いに重複し、通過可能時間帯Ｔ_ｂ［４］，Ｔ_ｂ［５］が互いに重複し、通過可能時間帯Ｔ_ｂ［５］，Ｔ_ｂ［６］が互いに重複している。一方、通過可能時間帯Ｔ_ｂ［２］，Ｔ_ｂ［３］は互いに重複せず、通過可能時間帯Ｔ_ｂ［６］，Ｔ_ｂ［７］も互いに重複しない。このとき、本実施の形態の部分列選択処理では、移動体Ｚ_ｂ［３］，Ｚ_ｂ［４］，Ｚ_ｂ［５］，Ｚ_ｂ［６］の移動体識別子ＩＤ_ｂ［３］，ＩＤ_ｂ［４］，ＩＤ_ｂ［５］，ＩＤ_ｂ［６］の配列が部分列として選択される。

たとえば、図１７に示す通過可能時間帯を有する順列候補に対し、図１６のステップＳＴ７１でヘビーに属する移動体Ｚ_ｂ［３］が選択された場合を考える。この場合、ステップＳＴ７３〜ＳＴ７７が実行されることにより、重複移動体リストには、移動体Ｚ_ｂ［３］，Ｚ_ｂ［４］，Ｚ_ｂ［５］，Ｚ_ｂ［６］が登録される（ステップＳＴ７６）。その後、通過可能時間帯Ｔ_ｂ［６］，Ｔ_ｂ［７］間の共通部分が空集合になるので（ステップＳＴ７５のＮＯ）、ステップＳＴ７８に処理が移行する。

以上に説明したように実施の形態２では、部分列選択処理の際、順列候補において互いに隣接する移動体識別子の通過可能時間帯が互いに重複するように部分列が選択される。したがって、遅延量の少ない良好なスケジュールを得る可能性を高くすることができる。

実施の形態３．
次に、上記実施の形態１の変形例である実施の形態３について説明する。図１８は、実施の形態３に係るスケジューリングの手順の一例を示すフローチャートである。本実施の形態のスケジューリングの手順は、図６のステップＳＴ１５に代えて図１８のステップＳＴ１５Ｊを使用する点を除いて、上記実施の形態１に係るスケジューリングの手順と同じである。また、本実施の形態のスケジューリング装置の構成は、図６に示したスケジューリングに代えて、図１８に示したスケジューリングを実行する点を除いて、上記実施の形態１のスケジューリング装置１の構成と同じである。このため、以下、図１の符号を参照しつつ、本実施の形態に係るスケジューリングについて説明する。

ステップＳＴ１５Ｊにおいて、本実施の形態の部分列選択部３２は、スケジュール生成処理（ステップＳＴ１１）で使用された入力順列をスケジュール記憶部２２から取得する（ステップＳＴ１５Ｊ）。そして、順列候補ではなく、その入力順列に対して部分列選択処理を実行する（ステップＳＴ１６）。ここで、部分列選択部３２は、スケジュール記憶部２２に記憶されている単数または複数のスケジュール候補の中から最大の評価値を有するスケジュール候補に対応する入力順列を選択することが好ましい。その理由は、評価値が高いスケジュール候補に基づいて新たな順列を生成することにより、より評価値の高いスケジュール候補を得ることが期待できるためである。このようにスケジューリング処理部３０は、複数のスケジュール候補を生成し且つこれらスケジュール候補の評価値を算出することができる。スケジュール選択部１２は、これら複数のスケジュール候補の中から評価値の高いスケジュール候補をスケジュールとして選択することが可能である。したがって、本実施の形態も、上記実施の形態１と同様の効果を奏することができる。

なお、実施の形態１に係る部分列選択処理（図１０及び図１１）に代えて上記実施の形態２に係る部分列選択処理（図１６）が使用されてもよい。

実施の形態４．
次に、本発明に係る実施の形態４について説明する。図１９は、本発明に係る実施の形態４のスケジューリング装置１Ａの概略構成を示すブロック図である。このスケジューリング装置１Ａの構成は、上記実施の形態１の最適化部１０に代えて図１９の最適化部１０Ａを有する点を除いて、上記実施の形態１のスケジューリング装置１の構成と同じである。

本実施の形態の最適化部１０Ａは、図１９に示されるように、移動体情報記憶部２１，スケジュール記憶部２２、制約条件記憶部２３及び好適情報記憶部２４を含むデータ格納部２０と、複数のスケジュール候補を生成してこれらスケジュール候補をデータ格納部２０内のスケジュール記憶部２２に記憶させるスケジューリング処理部３０と、スケジューリング処理部３０に与えるべき移動体識別子の初期順列を生成する初期順列生成部３１とを備えている。最適化部１０Ａは、更に、スケジュール記憶部２２に記憶されているスケジュール候補を基に構成される順列候補から部分列を選択する部分列選択部３２Ａと、好適情報記憶部２４に記憶されている好適情報及び移動体のカテゴリを基準としてその部分列を並べ替えることで当該順列候補を新たな順列に変換する順列変換部３３Ａとを備えている。

この最適化部１０Ａの構成は、実施の形態１の部分列選択部３２及び順列変換部３３に代えて部分列選択部３２Ａ及び順列変換部３３Ａを有する点、及び好適情報記憶部２４を有する点を除いて、上記実施の形態１の最適化部１０の構成と同じである。

本実施の形態の部分列選択部３２Ａは、順列候補の中から、予め設定された一定数の移動体の移動体識別子からなる部分列を選択する。言い換えれば、部分列選択部３２Ａは、順列候補の中から、予め設定された所定の長さを有する部分列を選択するものである。たとえば、部分列の長さとして５が指定された場合、部分列選択部３２Ａは、当該順列候補に対応する移動体Ｚ_ｂ［１］〜Ｚ_ｂ［Ｎ］の中から、指定されたカテゴリに属する移動体Ｚ_ｂ［ｉ］を１つ確率的に選択し、更に、当該移動体Ｚ_ｂ［ｉ］を含み且つ連続的に順序付けされた５つの移動体の移動体識別子の配列を部分列として選択することができる。

好適情報記憶部２４には、複数種のカテゴリにそれぞれ割り当てられた移動体数の組み合わせと、カテゴリの好適な順序との間の対応関係を定める好適情報が記憶されている。好適情報は、たとえばルックアップテーブルの形で記憶されていればよい。好適情報の詳細については後述する。順列変換部３３Ａは、その好適情報を探索して当該好適情報の中から当該部分列に合致する移動体数の組み合わせに対応するカテゴリの好適な順序を見つけ出し、当該見つけ出された好適な順序で当該部分列を並べ替えることができる。

図２０は、実施の形態４に係る最適化処理であるスケジューリングの手順の一例を概略的に示すフローチャートである。図２０のフローチャートは、図６のステップＳＴ１６，ＳＴ１７に代えてステップＳＴ１６Ａ，ＳＴ１８，ＳＴ１９を有する点を除いて、図６
のフローチャートと同じである。

図２０を参照すると、部分列選択部３２Ａは、ステップＳＴ１５で構成された順列候補から、予め定められた一定数の長さの部分列を選択する（ステップＳＴ１６Ａ）。具体的には、部分列選択部３２Ａは、当該順列候補に対応する移動体Ｚ_ｂ［１］〜Ｚ_ｂ［Ｎ］の中から、指定されたカテゴリに属する移動体Ｚ_ｂ［ｉ］を確率的に選択し、更に、当該移動体Ｚ_ｂ［ｉ］を含み且つ連続的に順序付けされた一定数の移動体の移動体識別子の配列を部分列として選択することができる。

次に、順列変換部３３Ａは、好適情報記憶部２４から好適情報を取得し（ステップＳＴ１８）、この好適情報に基づいて当該部分列を並べ替えることにより順列候補を新たな順列に変換する（ステップＳＴ１９）。図２１は、カテゴリにそれぞれ割り当てられた移動体数の組み合わせとカテゴリの好適な順序との対応関係の一例をルックアップテーブル形式で示す図である。図２１には、ヘビー（Ｈｖ），ミディアム（Ｍｄ）及びライト（Ｌｔ）にそれぞれ割り当てられた移動体数の組み合わせ（２，２，１）と、これに対応する複数のカテゴリの好適な順序（Ｌｔ→Ｍｄ→Ｍｄ→Ｈｖ→Ｈｖ及びＨｖ→Ｈｖ→Ｍｄ→Ｍｄ→Ｌｔ）とが示されている。

図２２Ａは、図１２に示した順列候補から選択された部分列ＰＳａの一例を示す図である。図２２Ｂ及び図２２Ｃは、部分列ＰＳａの並べ替えにより生成された部分列ＰＳａ１，ＰＳａ２の例を示す図である。図２２Ｂでは、好適情報に含まれるカテゴリの好適な順序の１つ（Ｈｖ→Ｈｖ→Ｍｄ→Ｍｄ→Ｌｔ）で移動体識別子ＩＤ_ｂ［３］，ＩＤ_ｂ［５］，ＩＤ_ｂ［６］，ＩＤ_ｂ［７］，ＩＤ_ｂ［４］が配列されている。一方、図２２Ｃでは、好適情報に含まれるカテゴリの好適な順序の他の１つ（Ｌｔ→Ｍｄ→Ｍｄ→Ｈｖ→Ｈｖ）で移動体識別子ＩＤ_ｂ［４］，ＩＤ_ｂ［６］，ＩＤ_ｂ［７］，ＩＤ_ｂ［３］，ＩＤ_ｂ［５］が配列されている。ここで、同種のカテゴリに属する移動体の移動体識別子の前後関係は入れ替えられない。これらのカテゴリの好適な順序は、その順序に対応する規定間隔の総和が小さくなるように事前に計算されて設定されたものである。

たとえば、図５Ａに示した規定間隔制約が使用される場合には、図２２Ａに示す部分列ＰＳａについては、規定間隔の総和は３６０となる。一方、図２２Ｂに示す部分列ＰＳａ１については、規定間隔の総和は３３０となる。このように、カテゴリの好適な順序を適用することにより、元の部分列ＰＳａについての規定間隔の総和３６０と比較して、規定間隔の総和が減少するので、スケジュール候補の遅延量が小さくなる可能性が高いと期待することができる。

移動体のカテゴリに依存して定まる規定間隔制約が図５Ａに示す比較的単純なものであれば、実施の形態１の場合と同様に、ステップＳＴ１６Ａで選択された部分列を、同種のカテゴリに分類されている移動体を連続的に順序付けする配列に並べ替えることによって新たな順列が生成されればよい。しかしながら、移動体のカテゴリの複雑化により規定間隔制約が複雑化する場合には（たとえば、滑走路における航空機のスケジューリングにおいて、移動体のカテゴリが「到着・出発区分」と、「ヘビー」，「ミディアム」または「ライト」との組み合わせで指定される場合）、移動体のカテゴリの好適な順序を単純な規則で表現することが困難になり得る。このような場合には、移動体のカテゴリの好適な順序をルックアップテーブルの形式で保存して使用する方法が適切である。

また、移動体のカテゴリの好適な順序をルックアップテーブルの形式で保存して使用する場合、移動体数に制限がないと、好適情報のサイズが膨大なものになる可能性がある。このような場合、演算効率の低下が生ずるおそれがある。そこで、本実施の形態の部分列選択部３２Ａは、順列候補の中から所定の長さを有する部分列を選択している（ステップＳＴ１６Ａ）。これにより、好適情報のサイズの増大が回避されるので、演算効率の低下を抑制することができる。

なお、気象などの状況の変化に応じて移動体のカテゴリの好適な順序が変わる場合も想定される。そのような場合、ユーザはデータ編集処理部１３の機能を使用することができる。ユーザは、操作入力部１６を操作して好適情報記憶部２４の内容を編集することが可能である。また、ユーザは、予め、カテゴリの好適な順序を定める複数パターンの好適情報を用意し、データ格納部２０に格納しておくことが可能である。ユーザは、操作入力部１６を操作してそれら複数パターンの中から任意の１パターンの好適情報を選択することができる。あるいは、最適化制御部１１が状況に変化に合わせてそれら複数パターンの中から１パターンの好適情報を自動的に選択できるように最適化部１０が構成されてもよい。

上記ステップＳＴ１９の実行後は、ステップＳＴ１１に処理が移行する。このとき、スケジューリング処理部３０は、ステップＳＴ１９で生成された単数または複数の新たな順列を入力順列として使用するスケジュール生成処理を実行する（ステップＳＴ１１）。次いで、ステップＳＴ１３〜ＳＴ１５，ＳＴ１６Ａ，ＳＴ１８，ＳＴ１９が実行される。最適化終了との判定がなされたとき（ステップＳＴ１４のＹＥＳ）、ステップＳＴ２０の判定処理が実行される。スケジュール選択部１２は、スケジュール記憶部２２に記憶されているスケジュール候補の中から最大評価値を有するスケジュールを選択することができる（ステップＳＴ２１）。ここで、最大評価値を有するスケジュールのみならず、比較的評価値の高いスケジュールも併せて選択されてよい。スケジュール選択部１２は、選択されたスケジュールをインタフェース部１４に出力する。

以上に説明したように実施の形態４のスケジューリング装置１Ａでは、順列変換部３３Ａは、カテゴリの好適な順序を定める好適情報記憶部２４を利用して部分列を並べ替えて新たな順列を生成することができる。そのため、先験情報に基づき、カテゴリの好適な順序が適切に好適情報記憶部２４に設定されていれば、新たな順列における規定間隔の総和が小さくなるので、遅延量の小さなスケジュールを得る可能性を高くすることが可能となる。

また、図２０の部分列選択処理（ステップＳＴ１６Ａ）の際、部分列選択部３２Ａは、順列候補の中から、予め決められた一定数の移動体の移動体識別子からなる部分列を選択する。これにより、複数種のカテゴリに割り当てられる移動体数の組み合わせの数が限定されるため、好適情報のサイズを小さくすることができる。また、部分列の並べ替えに関する規則が少なくて済むので、効率的なスケジューリングが可能となる。

更に、データ編集処理部１３は、インタフェース部１４を介して入力された情報に基づき、好適情報を更新する機能を有している。これにより、状況変化に対して臨機応変に好適情報記憶部２４の内容を変更することが可能となる。

実施の形態５．
次に、上記実施の形態４の変形例である実施の形態５について説明する。図２３は、実施の形態５に係るスケジューリングの手順の一例を示すフローチャートである。本実施の形態のスケジューリングの手順は、図２０のステップＳＴ１５に代えて図２３のステップＳＴ１５Ｊを使用する点を除いて、上記実施の形態４に係るスケジューリングの手順と同じである。また、本実施の形態のスケジューリング装置の構成は、図２０に示したスケジューリングに代えて、図２３に示したスケジューリングを実行する点を除いて、上記実施の形態４のスケジューリング装置１Ａの構成と同じである。このため、以下、図１９の符号を参照しつつ、本実施の形態に係るスケジューリングについて説明する。

ステップＳＴ１５Ｊにおいて、本実施の形態の部分列選択部３２Ａは、スケジュール生成処理（ステップＳＴ１１）で使用された入力順列をスケジュール記憶部２２から取得する（ステップＳＴ１５Ｊ）。そして、順列候補ではなく、その入力順列から部分列を選択する（ステップＳＴ１６Ａ）。このような場合でも、スケジューリング処理部３０は、複数のスケジュール候補を生成し且つこれらスケジュール候補の評価値を算出することができる。スケジュール選択部１２は、これら複数のスケジュール候補の中から評価値の高いスケジュール候補をスケジュールとして選択することが可能である。したがって、本実施の形態も、上記実施の形態４と同様の効果を奏することができる。

実施の形態６．
次に、本発明に係る実施の形態６について説明する。本実施の形態は、上記実施の形態４の変形例である。図２４は、本発明に係る実施の形態６のスケジューリング装置１Ｂの概略構成を示すブロック図である。このスケジューリング装置１Ｂの構成は、上記実施の形態４の最適化部１０Ａに代えて図２４の最適化部１０Ｂを有する点を除いて、上記実施の形態４のスケジューリング装置１Ａの構成と同じである。

本実施の形態の最適化部１０Ｂは、図２４に示されるように、移動体情報記憶部２１，スケジュール記憶部２２、制約条件記憶部２３、好適情報記憶部２４及び不適情報記憶部２５を含むデータ格納部２０と、複数のスケジュール候補を生成してこれらスケジュール候補をデータ格納部２０内のスケジュール記憶部２２に記憶させるスケジューリング処理部３０と、スケジューリング処理部３０に与えるべき移動体識別子の初期順列を生成する初期順列生成部３１とを備えている。最適化部１０Ｂは、更に、スケジュール記憶部２２に記憶されているスケジュール候補を基に構成される順列候補から部分列を選択する部分列選択部３２Ａと、好適情報記憶部２４に記憶されている好適情報、不適情報記憶部２５に記憶されている不適情報及び移動体のカテゴリを基準としてその部分列を並べ替えることで当該順列候補を新たな順列に変換する順列変換部３３Ｂとを備えている。

この最適化部１０Ｂの構成は、実施の形態４の順列変換部３３Ａに代えて順列変換部３３Ｂを有する点、及び不適情報記憶部２５を有する点を除いて、上記実施の形態４の最適化部１０Ａの構成と同じである。

不適情報記憶部２５には、複数種のカテゴリにそれぞれ割り当てられた移動体数の組み合わせと、カテゴリの不適な順序との間の対応関係を定める不適情報が記憶されている。不適情報は、たとえばルックアップテーブルの形で記憶されていればよい。不適情報の詳細については後述する。順列変換部３３Ｂは、上記実施の形態４の順列変換部３３Ａと同様に、好適情報を探索して当該好適情報の中から当該部分列に合致する移動体数の組み合わせに対応するカテゴリの好適な順序を見つけ出し、当該見つけ出された好適な順序で当該部分列を並べ替えることができる。また、順列変換部３３Ｂは、不適情報を探索して当該不適情報の中から当該部分列に合致する移動体数の組み合わせに対応するカテゴリの不適な順序を見つけ出し、当該見つけ出された不適な順序以外の順序で当該部分列を並べ替えることができる。

図２５は、実施の形態６に係る最適化処理であるスケジューリングの手順の一例を概略的に示すフローチャートである。図２５のフローチャートは、図２０のステップＳＴ１８，ＳＴ１９に代えてステップＳＴ１８Ｂ，ＳＴ１９Ｂを有する点を除いて、図２０のフローチャートと同じである。図２５を参照すると、ステップＳＴ１６Ａで部分列が選択された後、順列変換部３３Ｂは、好適情報記憶部２４及び不適情報記憶部２５から好適情報及び不適情報を取得し（ステップＳＴ１８Ｂ）、これら好適情報及び不適情報に基づいて当該部分列を並べ替えることにより順列候補を新たな順列に変換する（ステップＳＴ１９Ｂ）。

図２６は、カテゴリにそれぞれ割り当てられた移動体数の組み合わせとカテゴリの不適な順序との対応関係の一例をルックアップテーブル形式で示す図である。図２６には、ヘビー（Ｈｖ），ミディアム（Ｍｄ）及びライト（Ｌｔ）にそれぞれ割り当てられた移動体数の組み合わせ（２，２，１）と、これに対応する複数のカテゴリの不適な順序（Ｈｖ→Ｌｔ→Ｈｖ→Ｍｄ→Ｍｄ、Ｈｖ→Ｍｄ→Ｈｖ→Ｌｔ→Ｍｄ及びＭｄ→Ｈｖ→Ｍｄ→Ｈｖ→Ｌｔ）とが示されている。これらのカテゴリの不適な順序は、その順序に対応する規定間隔の総和が大きくなるように事前に計算されて設定されたものである。

たとえば、図５Ａに示した規定間隔制約が使用される場合には、図２６に示す不適な順序のいずれについても、この順序で移動体が配列された場合の規定間隔の総和は３６０となる。このように、順列変換部３３Ｂは、図２６に規定された不適な順序とならないよう部分列を並び替えることにより、規定間隔の総和が増大することを回避できるので、スケジュール候補の遅延量が小さくなる可能性が高いと期待することができる。

このような不適情報と上記好適情報を利用して、順列変換部３３Ｂは、以下の手順ζ１〜ζ３に従って部分列を並べ替えることができる（ステップＳＴ１９Ｂ）。
・手順ζ1：順列変換部３３Ｂは、好適情報を探索して、この好適情報の中から、移動体のカテゴリにそれぞれ割り当てられた移動体数の組み合わせに対応する好適な順序を見つけ出すことができた場合は、当該好適な順序に基づいて部分列を並べ替える。
・手順ζ２：手順ζ1で好適な順序を見つけ出すことができなかった場合、順列変換部３３Ｂは、不適情報を探索して、この不適情報の中から、当該部分列に合致する移動体数の組み合わせに対応するカテゴリの不適な順序を見つけ出すことができた場合は、当該不適な順序以外の順序で当該部分列を並べ替える。
・手順ζ３：手順ζ２で不適な順序を見つけ出すことができなかった場合、順列変換部３３Ｂは、当該部分列を、同種のカテゴリに属する移動体が連続的に順序付けられるように並べ替える。

以上に説明したように実施の形態６のスケジューリング装置１Ｂでは、順列変換部３３Ｂは、カテゴリの不適な順序を定める不適情報記憶部２５を利用して部分列を並べ替えて新たな順列を生成することができる。そのため、先験情報に基づき、カテゴリの不適な順序が不適情報記憶部２５に設定されていれば、新たな順列における規定間隔の総和が大きくなることを回避することができるので、遅延量の小さなスケジュールを得る可能性を高くすることが可能となる。

また、移動体のカテゴリの不適な順序をルックアップテーブルの形式で保存して使用する場合、移動体数に制限がないと、不適情報のサイズが膨大なものになる可能性がある。このような場合、演算効率の低下が生ずるおそれがある。そこで、本実施の形態の部分列選択部３２Ａは、順列候補の中から所定の長さを有する部分列を選択している（ステップＳＴ１６Ａ）。これにより、不適情報のサイズの増大が回避されるので、演算効率の低下を抑制することができる。

なお、気象などの状況の変化に応じて移動体のカテゴリの不適な順序が変わる場合も想定される。そのような場合、ユーザはデータ編集処理部１３の機能を使用することができる。ユーザは、操作入力部１６を操作して不適情報記憶部２５の内容を編集することが可能である。また、ユーザは、予め、カテゴリの不適な順序を定める複数パターンの不適情報を用意し、データ格納部２０に格納しておくことが可能である。ユーザは、操作入力部１６を操作してそれら複数パターンの中から任意の１パターンの不適情報を選択することができる。あるいは、最適化制御部１１が状況に変化に合わせてそれら複数パターンの中から１パターンの不適情報を自動的に選択できるように最適化部１０が構成されてもよい。

更に、データ編集処理部１３は、インタフェース部１４を介して入力された情報に基づき、不適情報を更新する機能を有している。これにより、状況変化に対して臨機応変に不適情報記憶部２５の内容を変更することが可能となる。

実施の形態７．
次に、上記実施の形態６の変形例である実施の形態７について説明する。図２７は、実施の形態７に係るスケジューリングの手順の一例を示すフローチャートである。本実施の形態のスケジューリングの手順は、図２５のステップＳＴ１５に代えて図２７のステップＳＴ１５Ｊを使用する点を除いて、上記実施の形態６に係るスケジューリングの手順と同じである。また、本実施の形態のスケジューリング装置の構成は、図２５に示したスケジューリングに代えて、図２７に示したスケジューリングを実行する点を除いて、上記実施の形態６のスケジューリング装置１Ｂの構成と同じである。このため、以下、図２４の符号を参照しつつ、本実施の形態に係るスケジューリングについて説明する。

ステップＳＴ１５Ｊにおいて、本実施の形態の部分列選択部３２Ａは、スケジュール生成処理（ステップＳＴ１１）で使用された入力順列をスケジュール記憶部２２から取得する（ステップＳＴ１５Ｊ）。そして、順列候補ではなく、その入力順列から部分列を選択する（ステップＳＴ１６Ａ）。ここで、部分列選択部３２は、スケジュール記憶部２２に記憶されている単数または複数のスケジュール候補の中から最大の評価値を有するスケジュール候補に対応する入力順列を選択することが好ましい。その理由は、評価値が高いスケジュール候補に基づいて新たな順列を生成することにより、より評価値の高いスケジュール候補を得ることが期待できるためである。このようにスケジューリング処理部３０は、複数のスケジュール候補を生成し且つこれらスケジュール候補の評価値を算出することができる。スケジュール選択部１２は、これら複数のスケジュール候補の中から評価値の高いスケジュール候補をスケジュールとして選択することが可能である。したがって、本実施の形態も、上記実施の形態６と同様の効果を奏することができる。

以上、図面を参照して本発明に係る種々の実施の形態について述べたが、これら実施の形態は本発明の例示であり、これら実施の形態以外の様々な形態を採用することもできる。たとえば、上記実施の形態１〜７は、主に航空機のスケジューリングを例に挙げて説明されていたが、これに限定されるものではない。船舶などの他の種類の移動体の場合にも、複数の移動体が同一領域を使用して移動する状況があれば、本発明の構成を同様に適用することが可能である。

また、実施の形態１のスケジューリング装置１と同様に、実施の形態４，６のスケジューリング装置１Ａ，１Ｂも、ワークステーションまたはメインフレームなどのＣＰＵ内蔵のコンピュータで実現可能である。あるいは、スケジューリング装置１Ａ，１Ｂのハードウェア構成は、ＤＳＰ、ＡＳＩＣまたはＦＰＧＡなどのＬＳＩにより実現されてもよい。更に、スケジューリング装置１Ａ，１Ｂは、図１５に示した情報処理装置１ＨＷにより構成可能である。

なお、本発明の範囲内において、上記実施の形態１〜７の自由な組み合わせ、各実施の形態の任意の構成要素の変形、または各実施の形態の任意の構成要素の省略が可能である。

１，１Ａ，１Ｂ スケジューリング装置、１ＨＷ 情報処理装置、１０，１０Ａ，１０Ｂ 最適化部、１１ 最適化制御部、１２ スケジュール選択部、１３ データ編集処理部、１４ インタフェース部、１５ 表示部、１６ 操作入力部、２０ データ格納部、２１ 移動体情報記憶部、２２ スケジュール記憶部、２３ 制約条件記憶部、２４ 好適情報記憶部、２５ 不適情報記憶部、３０ スケジューリング処理部、３１ 初期順列生成部、３２，３２Ａ 部分列選択部、３３，３３Ａ，３３Ｂ 順列変換部、４０ プロセッサ、４０ｃ ＣＰＵ、４１ メモリ、４２ 記録媒体、４３ 表示インタフェース部、４４ 入力インタフェース部、４５ 通信インタフェース部、４６ 信号路、Ｚ_１〜Ｚ_５ 移動体、ＲＳ 共有リソース、ＰＳ 部分列。

Claims (24)

1. 共有リソースを使用する複数の移動体の順序を定める移動体識別子の配列である入力順列を取得し、前記複数の移動体に対して、予め決められた制約条件を満たす使用予定時刻の割り当てを前記入力順列の順番で実行することによりスケジュール候補を生成するとともに前記スケジュール候補の評価値を算出するスケジューリング処理部と、
   前記スケジュール候補に基づいて構成される移動体識別子の順列候補から部分列を選択する部分列選択部と、
   前記移動体のカテゴリを基準として前記部分列を構成する複数の移動体識別子を並べ替えることで前記順列候補を新たな順列に変換する順列変換部と、
   前記スケジューリング処理部で生成された複数のスケジュール候補の中から、最大の評価値を有するスケジュール候補を選択するスケジュール選択部と、
   移動体識別子の初期順列を生成する初期順列生成部と
   を備え、
   前記スケジューリング処理部は、前記初期順列及び前記新たな順列の各々を前記入力順列として使用して前記複数のスケジュール候補を生成し且つ前記複数のスケジュール候補の評価値を算出する、
   ことを特徴とするスケジューリング装置。
2. 共有リソースを使用する複数の移動体の順序を定める移動体識別子の配列である入力順列を取得し、前記複数の移動体に対して、予め決められた制約条件を満たす使用予定時刻の割り当てを前記入力順列の順番で実行することによりスケジュール候補を生成するとともに前記スケジュール候補の評価値を算出するスケジューリング処理部と、
   前記入力順列から部分列を選択する部分列選択部と、
   前記移動体のカテゴリを基準として前記部分列を構成する複数の移動体識別子を並べ替えることで前記入力順列を新たな順列に変換する順列変換部と、
   前記スケジューリング処理部で生成された複数のスケジュール候補の中から、最大の評価値を有するスケジュール候補を選択するスケジュール選択部と、
   移動体識別子の初期順列を生成する初期順列生成部と
   を備え、
   前記スケジューリング処理部は、前記初期順列及び前記新たな順列の各々を前記入力順列として使用して前記複数のスケジュール候補を生成し且つ前記複数のスケジュール候補の評価値を算出する、
   ことを特徴とするスケジューリング装置。
3. 請求項１または請求項２記載のスケジューリング装置であって、前記複数の移動体にそれぞれ割り当てられている当該共有リソースの使用可能時間帯と、移動体間の規定間隔とが記憶されているデータ格納部を更に備え、
   前記制約条件は、前記使用可能時間帯内に前記使用予定時刻が設定されるとの第１の制約と、前記複数の移動体の移動体間の間隔が前記規定間隔以上であるとの第２の制約とを有する条件であることを特徴とするスケジューリング装置。
4. 請求項１から請求項３のうちのいずれか１項記載のスケジューリング装置であって、前記順列変換部は、前記部分列が同種のカテゴリに分類されている２つ以上の移動体の移動体識別子の配列を含むとき、前記部分列を、当該２つ以上の移動体を連続的に順序付けする配列に並べ替えることを特徴とするスケジューリング装置。
5. 請求項４記載のスケジューリング装置であって、前記順列変換部は、予め定められたカテゴリの順序で前記部分列を構成する複数の移動体識別子を並べ替えることを特徴とするスケジューリング装置。
6. 請求項１または請求項２記載のスケジューリング装置であって、複数種のカテゴリにそれぞれ割り当てられた移動体数の組み合わせとカテゴリの好適な順序との間の対応関係を１つ以上定める好適情報が記憶されている好適情報記憶部を更に備え、
   前記順列変換部は、前記好適情報を探索して前記好適情報の中から前記部分列に合致する移動体数の組み合わせに対応するカテゴリの好適な順序を見つけ出し、当該見つけ出された好適な順序で前記部分列を構成する複数の移動体識別子を並べ替えることを特徴とするスケジューリング装置。
7. 請求項１、請求項２及び請求項５のうちのいずれか１項記載のスケジューリング装置であって、複数種のカテゴリにそれぞれ割り当てられた移動体数の組み合わせとカテゴリの不適な順序との間の対応関係を１つ以上定める不適情報が記憶されている不適情報記憶部を更に備え、
   前記順列変換部は、前記不適情報を探索して当該不適情報の中から前記部分列に合致する移動体数の組み合わせに対応するカテゴリの不適な順序を見つけ出し、当該見つけ出された不適な順序以外の順序で前記部分列を構成する複数の移動体識別子を並べ替えることを特徴とするスケジューリング装置。
8. 請求項６または請求項７記載のスケジューリング装置であって、前記部分列は、予め決められた一定数の移動体識別子の配列であることを特徴とするスケジューリング装置。
9. 共有リソースを使用する複数の移動体の順序を定める移動体識別子の配列である入力順列を取得し、前記複数の移動体に対して、予め決められた制約条件を満たす使用予定時刻の割り当てを前記入力順列の順番で実行することによりスケジュール候補を生成するとともに前記スケジュール候補の評価値を算出するスケジューリング処理部と、
   前記スケジュール候補に基づいて構成される移動体識別子の順列候補から部分列を選択する部分列選択部と、
   前記移動体のカテゴリを基準として前記部分列を構成する複数の移動体識別子を並べ替えることで前記順列候補を新たな順列に変換する順列変換部と、
   前記スケジューリング処理部で生成された複数のスケジュール候補の中から、最大の評価値を有するスケジュール候補を選択するスケジュール選択部と、
   移動体識別子の初期順列を生成する初期順列生成部と
   を備え、
   前記スケジューリング処理部は、前記初期順列及び前記新たな順列の各々を前記入力順列として使用して前記複数のスケジュール候補を生成し且つ前記複数のスケジュール候補の評価値を算出し、
   前記部分列選択部は、前記部分列の複数の移動体識別子に対応する複数の使用可能時間帯のすべてが重複している、または、前記部分列の複数の移動体識別子のうち隣接する移動体識別子に対応する使用可能時間帯が互いに重複しているように前記部分列を選択する、
   ことを特徴とするスケジューリング装置。
10. 共有リソースを使用する複数の移動体の順序を定める移動体識別子の配列である入力順列を取得し、前記複数の移動体に対して、予め決められた制約条件を満たす使用予定時刻の割り当てを前記入力順列の順番で実行することによりスケジュール候補を生成するとともに前記スケジュール候補の評価値を算出するスケジューリング処理部と、
    前記入力順列から部分列を選択する部分列選択部と、
    前記移動体のカテゴリを基準として前記部分列を構成する複数の移動体識別子を並べ替えることで前記入力順列を新たな順列に変換する順列変換部と、
    前記スケジューリング処理部で生成された複数のスケジュール候補の中から、最大の評価値を有するスケジュール候補を選択するスケジュール選択部と、
    移動体識別子の初期順列を生成する初期順列生成部と
    を備え、
    前記スケジューリング処理部は、前記初期順列及び前記新たな順列の各々を前記入力順列として使用して前記複数のスケジュール候補を生成し且つ前記複数のスケジュール候補の評価値を算出し、
    前記部分列選択部は、前記部分列の複数の移動体識別子に対応する複数の使用可能時間帯のすべてが重複している、または、前記部分列の複数の移動体識別子のうち隣接する移動体識別子に対応する使用可能時間帯が互いに重複しているように前記部分列を選択する、
    ことを特徴とするスケジューリング装置。
11. 請求項９または請求項１０記載のスケジューリング装置であって、前記部分列選択部は、予め設定された上限以下の長さを有する配列を前記部分列として選択することを特徴とするスケジューリング装置。
12. 請求項１から請求項１１のうちのいずれか１項記載のスケジューリング装置であって、前記部分列選択部は、予め定められたカテゴリに属する移動体の移動体識別子を含む配列を前記部分列として選択することを特徴とするスケジューリング装置。
13. 請求項３記載のスケジューリング装置であって、前記初期順列は、前記使用可能時間帯に基づいて生成されることを特徴とするスケジューリング装置。
14. 請求項１３記載のスケジューリング装置であって、前記初期順列は、前記使用可能時間帯の下限時刻または上限時刻のいずれか一方に基づいて生成されることを特徴とするスケジューリング装置。
15. 請求項３記載のスケジューリング装置であって、前記スケジューリング処理部は、前記各移動体に割り当てられている当該使用可能時間帯内の基準時刻と、当該各移動体に割り当てられた当該使用予定時刻との間の時間差を遅延量として算出し、前記遅延量を基に前記スケジュール候補の評価値を算出することを特徴とするスケジューリング装置。
16. 請求項１５記載のスケジューリング装置であって、前記基準時刻は、前記使用可能時間帯内の下限時刻であることを特徴とするスケジューリング装置。
17. 請求項１記載のスケジューリング装置であって、前記スケジューリング処理部は、前記共有リソースへの先着順の順列と前記順列候補との間の前記複数の移動体の追い越し発生数を算出し、前記追い越し発生数に基づいて前記スケジュール候補の評価値を算出することを特徴とするスケジューリング装置。
18. 請求項１から請求項１７のうちのいずれか１項記載のスケジューリング装置であって、前記制約条件は、前記複数の移動体のうちの一の移動体に対して割り当てられるべき使用予定時刻が、前記複数の移動体のうち当該一の移動体以外の他の移動体に対して既に割り当てられた使用予定時刻以後に限定されるとの第３の制約を有する条件であることを特徴とするスケジューリング装置。
19. 請求項１から請求項１８のうちのいずれか１項記載のスケジューリング装置であって、前記使用予定時刻は、前記各移動体が前記共有リソースを通過する予定時刻であることを特徴とするスケジューリング装置。
20. 情報処理装置において実行されるスケジューリング方法であって、
    共有リソースを使用する複数の移動体の順序を定める移動体識別子の初期順列を生成するステップと、
    前記初期順列に基づき、前記複数の移動体に対して、予め決められた制約条件を満たす使用予定時刻の割り当てを前記初期順列の順番で実行することによりスケジュール候補を生成するステップと、
    前記初期順列に基づいて生成された当該スケジュール候補の評価値を算出するステップと、
    前記スケジュール候補に基づいて構成される移動体識別子の順列候補から部分列を選択するステップと、
    前記移動体のカテゴリを基準として前記部分列を構成する複数の移動体識別子を並べ替えることで前記順列候補を新たな順列に変換するステップと、
    前記新たな順列に基づき、前記複数の移動体に対して前記制約条件を満たす使用予定時刻の割り当てを前記新たな順列の順番で実行することによりスケジュール候補を生成するステップと、
    前記新たな順列に基づいて生成された当該スケジュール候補の評価値を算出するステップと、
    前記初期順列に基づいて生成された当該スケジュール候補及び前記新たな順列に基づいて生成された当該スケジュール候補の中から、最大の評価値を有するスケジュール候補を選択するステップと
    を備えることを特徴とするスケジューリング方法。
21. 情報処理装置において実行されるスケジューリング方法であって、
    共有リソースを使用する複数の移動体の順序を定める移動体識別子の初期順列を生成するステップと、
    前記初期順列に基づき、前記複数の移動体に対して、予め決められた制約条件を満たす使用予定時刻の割り当てを前記初期順列の順番で実行することによりスケジュール候補を生成するステップと、
    前記初期順列に基づいて生成された当該スケジュール候補の評価値を算出するステップと、
    前記初期順列から部分列を選択するステップと、
    前記移動体のカテゴリを基準として前記部分列を構成する複数の移動体識別子を並べ替えることで前記初期順列を新たな順列に変換するステップと、
    前記新たな順列に基づき、前記複数の移動体に対して前記制約条件を満たす使用予定時刻の割り当てを前記新たな順列の順番で実行することによりスケジュール候補を生成するステップと、
    前記新たな順列に基づいて生成された当該スケジュール候補の評価値を算出するステップと、
    前記初期順列に基づいて生成された当該スケジュール候補及び前記新たな順列に基づいて生成された当該スケジュール候補の中から、最大の評価値を有するスケジュール候補を選択するステップと
    を備えることを特徴とするスケジューリング方法。
22. 請求項２１記載のスケジューリング方法であって、
    前記新たな順列から部分列を選択するステップと、
    前記移動体のカテゴリを基準として、前記新たな順列から選択された当該部分列を構成する複数の移動体識別子を並べ替えることで前記新たな順列を別の新たな順列に変換するステップと、
    前記別の新たな順列に基づき、前記複数の移動体に対して前記制約条件を満たす使用予定時刻の割り当てを前記別の新たな順列の順番で実行することによりスケジュール候補を生成するステップと、
    前記別の新たな順列に基づいて生成された当該スケジュール候補の評価値を算出するステップと、
    前記初期順列に基づいて生成された当該スケジュール候補、前記新たな順列に基づいて生成された当該スケジュール候補、及び前記別の新たな順列に基づいて生成された当該スケジュール候補の中から、最大の評価値を有するスケジュール候補を選択するステップと
    を更に備えることを特徴とするスケジューリング方法。
23. 情報処理装置において実行されるスケジューリング方法であって、
    共有リソースを使用する複数の移動体の順序を定める移動体識別子の初期順列を生成するステップと、
    前記初期順列に基づき、前記複数の移動体に対して、予め決められた制約条件を満たす使用予定時刻の割り当てを前記初期順列の順番で実行することによりスケジュール候補を生成するステップと、
    前記初期順列に基づいて生成された当該スケジュール候補の評価値を算出するステップと、
    前記スケジュール候補に基づいて構成される移動体識別子の順列候補から部分列を選択するステップと、
    前記移動体のカテゴリを基準として前記部分列を構成する複数の移動体識別子を並べ替えることで前記順列候補を新たな順列に変換するステップと、
    前記新たな順列に基づき、前記複数の移動体に対して前記制約条件を満たす使用予定時刻の割り当てを前記新たな順列の順番で実行することによりスケジュール候補を生成するステップと、
    前記新たな順列に基づいて生成された当該スケジュール候補の評価値を算出するステップと、
    前記初期順列に基づいて生成された当該スケジュール候補及び前記新たな順列に基づいて生成された当該スケジュール候補の中から、最大の評価値を有するスケジュール候補を選択するステップと
    を備え、
    前記部分列の複数の移動体識別子に対応する複数の使用可能時間帯のすべてが重複している、または、前記部分列の複数の移動体識別子のうち隣接する移動体識別子に対応する使用可能時間帯が互いに重複している
    ことを特徴とするスケジューリング方法。
24. 情報処理装置において実行されるスケジューリング方法であって、
    共有リソースを使用する複数の移動体の順序を定める移動体識別子の初期順列を生成するステップと、
    前記初期順列に基づき、前記複数の移動体に対して、予め決められた制約条件を満たす使用予定時刻の割り当てを前記初期順列の順番で実行することによりスケジュール候補を生成するステップと、
    前記初期順列に基づいて生成された当該スケジュール候補の評価値を算出するステップと、
    前記初期順列から部分列を選択するステップと、
    前記移動体のカテゴリを基準として前記部分列を構成する複数の移動体識別子を並べ替えることで前記初期順列を新たな順列に変換するステップと、
    前記新たな順列に基づき、前記複数の移動体に対して前記制約条件を満たす使用予定時刻の割り当てを前記新たな順列の順番で実行することによりスケジュール候補を生成するステップと、
    前記新たな順列に基づいて生成された当該スケジュール候補の評価値を算出するステップと、
    前記初期順列に基づいて生成された当該スケジュール候補及び前記新たな順列に基づいて生成された当該スケジュール候補の中から、最大の評価値を有するスケジュール候補を選択するステップと
    を備え、
    前記部分列の複数の移動体識別子に対応する複数の使用可能時間帯のすべてが重複している、または、前記部分列の複数の移動体識別子のうち隣接する移動体識別子に対応する使用可能時間帯が互いに重複している
    ことを特徴とするスケジューリング方法。

Images