(57)【特許請求の範囲】
【請求項１】
内部に遺伝的アルゴリズムの染色体の集団を有し、該遺伝的アルゴリズムのオペレーションを行うことにより、スケジュールの最適化を行う最適化装置であって、
染色体の集団を有し、評価関数の計算、選択、交差、突然変異のオペレーションを行い、該染色体をデコードした結果を、最適化対象の状態を一意に指定できるパラメータとして出力する遺伝的アルゴリズムを有するスケジューリング手段と、
前記スケジューリング手段からの前記パラメータに基づいて、スケジュールの時間順にシミュレーション指示を行うためのメッセージを送出し、該シミュレーションの結果を取得すると、該シミュレーションの結果が時系列的なスケジュール情報と適合しているかを判定し、モードに応じた問い合わせを行い、該問い合わせの回答に基づいて適応度の計算を行い、該スケジューリング手段に返却するスケジュール管理手段と、
前記スケジュール管理手段からの前記シミュレーションの指示のメッセージが渡されると、該メッセージに記載されたシミュレーション指示に基づいて、予め定められた条件に従ってシミュレーションを行うと共に、該メッセージに従ってオブジェクトの状態変数テーブルの内容を更新し、シミュレーション結果を前記スケジュール管理手段に渡すオブジェクト管理手段と、
を有し、
前記オブジェクト管理手段は、
前記シミュレーションの結果、メッセージに応じられない場合は、スケジュールの過剰な要求部分を指摘したメッセージを前記スケジュール管理手段に返却する手段を含む、
ことを特徴とするオブジェクト指向遺伝的アルゴリズムを用いた最適化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、オブジェクト指向遺伝的アルゴリズムを用いた最適化装置に係り、特に、空港等におけるフライトスケジュール作成処理等における複雑な制約条件下で作成するスケジュールの最適化を行うためのオブジェクト指向遺伝的アルゴリズムを用いた最適化装置に関する。
【０００２】
近年のコンピュータの性能の向上に伴い、従来のエキスパートシステム等で解決が困難であった問題を解決する手段として、確率的最適化手法（シミュレーテッド・アニーリング、遺伝的アルゴリズム）等が注目を浴び、最適化の実用化を行うための手法の研究がなされている。
様々な確立的最適化手法の中でも特に遺伝的アルゴリズムは特に注目されている。この遺伝的アルゴリズムは、昨今のコンピュータの低価格化に伴い、問題解決のために豊富なＣＰＵパワーをいかに有効に使いこなすかが課題となっており、この遺伝的アルゴリズムは困難な問題をコンピュータ・パワーで乗り切る有望な手法とされている。
【０００３】
【従来の技術】
従来、例えば、空港におけるフライトスケジュールの作成においては、各空港における駐機場（スポット）の管理や機材の運行システムに関する種々の制約条件（駐機場に入ってくる機体の準備時間、機材の整備時間、航空会社の便数指定条件等）を考慮して、人手によりスケジュールの作成を行っている。
【０００４】
また、エキスパートシステムを用いて、種々の条件を入力し、それらの条件に適合するスケジュールを選択し、人手により選択した基本的なスケジュールに修正等を加えてスケジュールを作成する方法等が用いられている。
さらに、遺伝的アルゴリズムを用いて最適化するシステムは、染色体のデコードと評価関数の計算を一体のものとして取り扱い、評価関数は最適化するシステムを全体的に評価するものを作成する枠組みとして用いている。
【０００５】
【発明が解決しようとする課題】
しかしながら、上記従来のスケジュール作成等における最適化の手法として、人手によるスケジュール作業は、各空港毎、または、機材毎の種々の制約条件を考慮して作業を行うために、ある条件は満たしても他の条件を満たしていない等の問題により試行錯誤を繰り返しながら作成することになり、人手による多大の労力を必要とし、人的コストが増大するという問題がある。
【０００６】
さらに、エキスパートシステムを用いる方法では、プログラマにより種々の条件に基づいてプログラムを作成していく処理が必要となる。例えば、フライトスケジュールにおける、機体の機種、航空会社におけるスポットの既得権、夜間駐機、空港使用可能時間等の種々の制約条件があり、これらの多岐に渡る条件に合致するプログラムの作成は困難であり、最終的には、実行されたプログラムの結果にさらに、修正等の作業や、航空会社間における調整等の処理が必要となり、種々の条件が変更になった場合には、再度プログラムを作成しなおさなくてはならず、多大な労力とコストが必要となる。
【０００７】
また、従来の遺伝的アルゴリズムを用いる方法では、染色体のデコードと評価関数の計算は一体のものとして取り扱われており、評価関数は最適化するシステムを全体的に評価するものを作る枠組みとなっている。このとき、複雑なシステムの評価関数を作る指針が無いため、問題の記述も恣意的に行っているだけである。このため、実用的問題の整合性のあるモデリングを行うことが難しく、改変に柔軟に対処できなくなるという問題があう。
【０００８】
実用的問題を扱う際には、最適化する系の能力限界近傍で解を探索するが、系の物理的限界を越えた要求をしてもその事がなかなか判らないという問題があう。実用問題を扱う場合の、最適解の存在や実行可能解を得るための条件は判らないことが殆どである。
さらに、評価関数をまとめて計算するため、最適化が不能であった場合の原因の追求が遺伝的アルゴリズムの枠内では非常に困難である。
【０００９】
本発明は、上記の点に鑑みなされたもので、遺伝的アルゴリズムの評価関数の計算部文をオブジェクト指向で統一的かつ簡素に記述することが可能なオブジェクト指向遺伝的アルゴリズムを用いた最適化装置を提供することを目的とする。
また、本発明の目的は、時系列的なスケジュールの不整合の原因を解明することが可能なオブジェクト指向遺伝的アルゴリズムを用いた最適化装置を提供することである。
【００１０】
さらなる本発明の目的は、スケジューラとオブジェクト・モデルを組み合わせることで、これまで困難であった不整合や過剰な要求やスケジュールの不適切な部分の指摘を可能とするオブジェクト指向遺伝的アルゴリズムを用いた最適化方法及び装置を提供することである。
【００１１】
【課題を解決するための手段】
本発明は、内部に遺伝的アルゴリズムの染色体の集団を有し、該遺伝的アルゴリズムのオペレーションを行うことにより、スケジュールの最適化を行う最適化装置であって、
染色体の集団を有し、評価関数の計算、選択、交差、突然変異のオペレーションを行い、該染色体をデコードした結果を、最適化対象の状態を一意に指定できるパラメータとして出力する遺伝的アルゴリズムを有するスケジューリング手段と、
スケジューリング手段からのパラメータに基づいて、スケジュールの時間順にシミュレーション指示を行うためのメッセージを送出し、該シミュレーションの結果を取得すると、該シミュレーションの結果が時系列的なスケジュール情報と適合しているかを判定し、モードに応じた問い合わせを行い、該問い合わせの回答に基づいて適応度の計算を行い、該スケジューリング手段に返却するスケジュール管理手段と、
スケジュール管理手段からのシミュレーションの指示のメッセージが渡されると、該メッセージに記載されたシミュレーション指示に基づいて、予め定められた条件に従ってシミュレーションを行うと共に、該メッセージに従ってオブジェクトの状態変数テーブルの内容を更新し、シミュレーション結果をスケジュール管理手段に渡すオブジェクト管理手段と、
を有し、
オブジェクト管理手段は、
シミュレーションの結果、メッセージに応じられない場合は、スケジュールの過剰な要求部分を指摘したメッセージをスケジュール管理手段に返却する手段を含む。
【００１４】
本発明によれば、オブジェクト・モデルを遺伝的アルゴリズムの評価関数の計算部として応用したことにより、整合のとれた統一的なインターフェースをもつモデルの記述が可能となる。
【００１５】
さらに、本発明によれば、スケジューラから不整合のない（多くの場合、時間的順序がある）メッセージ（全体のスケジュールの断片）がオブジェクト・モデルに渡されると、オブジェクト・モデルは、それに応じて内部の状態を変更し、然るべき応答を返す。これにより、もし、不適切なスケジュールによりそのメッセージオブジェクト・モデルが応じられない場合には、その旨が回答され、オブジェクト・モデルの状態は変化しないため、当該メッセージの回答を用いて、スケジュールの一部とモデルの状態不整合が検出され、不適切なスケジュールの場所を特定できる。
【００１６】
【発明の実施の形態】
図１は、本発明のオブジェクト指向遺伝的アルゴリズムを用いた最適化装置の構成を示す。
同図に示す最適化装置は、遺伝的アルゴリズム１、評価関数計算部２、スケジューラ４、最適化対象のオブジェクト・モデル５から構成される。
【００１７】
遺伝的アルゴリズム１は、一般的な遺伝的アルゴリズム（以下ＧＡと記す（Genetic Algorithms）であり、内部にＧＡの染色体の集団を持ち、評価関数計算部２、選択、交叉、突然変異等のＧＡの通常のオペレーションを行う。ＧＡ１の選択、交叉、突然変異のオペレーションは、染色体の集団に対して行われるものであるが、この評価関数計算部２における計算は、染色体について独立に行われる。当該評価計算部２は、１つの染色体をデコードした結果のシステムのパラメータ３を出力する。当該パラメータ３は、最適化対象の状態を一意的に指定できるように設定されている。
【００１８】
スケジューラ４は、システムのパラメータ３を不整合がないように整理して、最適化対象のオブジェクト・モデル５に投入し、結果を取得し、ＧＡ１の評価関数の値を計算する。
オブジェクト・モデル５は、最適化しようとするシステムをオブジェクト指向的に記述しているものであり、これには、受け取るメッセージと当該メッセージによる内部状態の更新、応答等が記述されており、システムのシミュレーションを行う。
【００１９】
【実施例】
以下、図面と共に本発明の実施例を説明する。
以下の実施例では、一つのＧＡの染色体がデコードされ、あるフライトスケジュールを生成する例を用いて説明する。なお、このフライトスケジュールは、時間時順にフライト・オブジェクトにメッセージとして投入される。
【００２０】
本実施例におけるフライトスケジュールを作成する際の制約条件を以下に示す。
１．使用可能機種の中で一つを遺伝子で指定する。
２．指定機種で、駐機スポット上に利用可能な機材があれば割り当てる。
３．指定機種がない場合、その便で利用可能な機種が駐機スポットにあれば割り当てる。
【００２１】
・同一機種で複数利用可能なものがあればスタック的に割り当てる。
４．指定機種で、夜間駐機割当用機材に余剰があり、その機種が利用可能な夜間駐機スポットがあれば、割り当てる。
５．指定機種がない場合、夜間駐機割当用機材にその便で利用可能な機種の余剰があり、その機種が利用可能な夜間駐機スポットがあれば割り当てる。
【００２２】
図２は、本発明の一実施例の最適化装置の構成を示す。
同図に示す最適化装置は、ＧＡ１０と機材スケジュール２０とを有するスケジューリング部４０、フライトスケジュール管理部３０、フライトオブジェクト５０から構成される。
ＧＡ１０は、図３に示すように、便毎に出発時間、割当機種を指定して、コーディング／デコードし、システムのパラメータをフライトスケジュール管理部３０に渡す。本実施例では、機材スケジュール２０により割当機種毎に予め便名が決定されているものとし、当該便名に出発空港、到着空港が設定されているものとして説明する。
【００２３】
図３は、本発明の一実施例のデコードされたシステムのパラメータ（染色体デコード結果）の例を示す。同図に示す染色体デコード結果は、発時刻、発空港、着空港、機種の組から構成される。
フライトスケジュール管理部３０は、フライトスケジュールを時系列（多くの場合時間的順序がある）に管理しており、スケジューリング部４０からデコードされたシステムのパラメータが渡されると、図３に示す当該パラメータに基づいて、フライトオブジェクト５０に対してシミュレーションを指示する。なお、シミュレーションの指示はメッセージとして扱われる。フライトオブジェクト５０から返却された結果に基づいて、当該結果がスケジュール情報と適合しているかを判定し、モード（機材等）に応じた問い合わせをフライトオブジェクト５０に発行し、当該フライトオブジェクト５０から問い合わせに関する回答を取得し、適応度の計算を行い、適応度をスケジューリング部４０のＧＡ１０に渡す。
【００２４】
適応度の計算は、以下の式により求めるものとする。
・フライトオブジェクト５０から『割当不能便がある』または、『朝夕の駐機機材が不一致』という回答が返却された場合：
【００２５】
【数１】
0003943663.tif 000002
【００２６】
・フライトオブジェクト５０から『割当不能便が無い』かつ『朝夕の駐機機材が一致した』という回答が返却された場合：
【００２７】
【数２】
0003943663.tif 000003
【００２８】
但し、上記の式において、
ｆi は、便番号ｉの割当不能数：
【００２９】
【数３】
0003943663.tif 000004
【００３０】
Ｍi は、空港ｉでの朝夕の駐機機材の不一致数：
Ｂi は、便ｉ（便テーブル番号）の収益、売上、費用：
売上／  ｍｉｎ（割当機材の定員、便の需要）×平均各単価
費用／  割当られた機材の路線に依存した費用を負数で表現
収益／  売上＋費用
フライトオブジェクト５０は、フライトスケジュール管理部３０からメッセージと共に、デコードされたシステムのパラメータが渡されると、当該パラメータに基づいてシミュレーションを行い、フライトスケジュール管理部３０に返却する。なお、スケジュール管理部３０から不整合のあるメッセージが渡された場合には、オブジェクトモデル５０の内部の状態は変更せずに、メッセージに不整合があることを応答する。さらに、フライトスケジュール管理部３０から発行されるモードに応じた問い合わせ（オブジェクトモデルが対応できない場合に対する問い合わせ）があると、当該モードに関する状態の表示を行い、問い合わせに関する回答をフライトスケジュール管理部３０に送信する。
【００３１】
フライトオブジェクト５０のスポットオブジェクトは、図４に示す状態変数のテーブルを有する。
スケジュール管理部３０からメッセージを受け取ると、当該フライトオブジェクト５０のスポットオブジェクトは、当該メッセージに従って、状態変数テーブルを更新する。当該状態変数テーブルは、スポットが駐機状態／空の状態及びスポットの使用可能時間、駐機している機材ＩＤから構成される。駐機スポットが駐機可能状態である場合には、当該駐機スポットに駐機している機材が使用する時間を使用可能時間欄に設定し、駐機している機材のＩＤを機材ＩＤ欄に設定する。また、スポットが空の状態である場合には、スポットが空いている時間を設定し、−１を機材ＩＤ欄に設定する。
【００３２】
状態変数テーブルへの設定は、フライトオブジェクト５０は、スケジュール管理部３０から渡されたメッセージが、『機材が到着』である場合には、状態変数テーブルの駐機状態欄に移行すると共に、機材ＩＤ欄に到着した機材ＩＤを記録し、駐機時刻にミニマムステイを加えて使用可能時間とし、駐機状態の使用可能時間欄に設定する。さらに、メッセージが『機材が出発』である場合には、空の状態に移行すると共に、機材ＩＤをスケジュール管理部３０に返却する。さらに、出発時刻に準備時間を加えて、使用可能時刻を更新する。さらに、『使用不可』のメッセージが渡された場合には、使用可能時間を変更する。
【００３３】
フライトオブジェクト５０の空港オブジェクトは、スケジュール管理部３０から『出発』メッセージを受け取ると、機材を割り当てる、夜間駐機機材を割り当てる、機材コントローラから機材を確保するのいずれかの処理を行う。また、『到着』メッセージを受け取ると、到着機材をスポットに入れる。さらに、夕刻におけるスポット溢れが生じた場合には、機材を格納庫に回し、スポットを空ける。さらに、『空港使用可／不可』メッセージを取得した場合には、当該メッセージに応じて空港を使用不可または、可能にする。
【００３４】
図５は、本発明の一実施例のフライトスケジュールを作成する手順を示すシーケンスチャートである。
ステップ１０１）  最初にＧＡ１０は、染色体のコーディング及びデコードを行う。図６は、本発明の一実施例のＧＡにおけるコーディング・デコードを説明するための図である。コーディングを行う場合には、単位時間間隔を指定し、例えば、希望出発時間、時間枠の範囲の指定を行う。図６の（Ａ）の出発時刻のコーディングの例では、単位時間間隔を５分とし、希望出発時間を１２：００とし、時間枠は±２０分として指定する。これにより、１１：４０から１２：２０までの時間枠が５分間隔で設定される。この状態において、デコードする場合には、
ｙ＝１１：４５＋（ｘ％９）＊５
を求める。上記において、ｘは、０〜ａ（ａ≧９）の遺伝子であり、ｙはスケジューリング時刻、ａ％ｂはａをｂで割った余りである。
【００３５】
また、図６（Ｂ）の割当機種のコーディングの例では、割当可能機種の中の１つを指定する。この例では、Ｂ４４，Ｂ４Ｓ、Ｂ７２，Ｂ６３が割当可能機種であるので、このうちの１つを指定する。なお、機種は、便名が予め決定されているものとする。この状態においてデコードする場合には、
ｙ＝ｘ％４
を求める。上記において、ｘは、０〜ａ（ａ≧４）の遺伝子であり、ｙは割当機種である。
【００３６】
このようにしてデコードされて生成されたフライトスケジュールが前述の図３の形態でスケジュール管理部３０に渡される。
ステップ１０２）  スケジュール管理部３０は、各便をキューで管理すると共に、空港／スポット使用不可情報も統合管理する。キューは時間順にソートされているものとし、先頭からフライトオブジェクト５０に投入する。さらに出発したら到着便としてキューに登録し、到着便はキューから抹消する。図７は、本発明の一実施例のスケジュール管理部の便のキューの時間変化を示す図である。スケジュール管理部３０は、ＧＡ１０から届いたフライトスケジュールを時間順にフライトオブジェクト５０にメッセージとして投入することによりシミュレーションを指示する。このとき、フライトスケジュールの先頭を外して投入するものとする。
【００３７】
ステップ１０３）  フライトオブジェクト５０は、各空港でのスポットの空き状況や機材の状況を管理しており、スケジュール管理部３０からメッセージ（全体スケジュールの断片）を取得した時点で割り当て可能な機材にフライトを割り振る処理を行う。詳しくは、スケジュール管理部３０から投入されたメッセージにより、前述の『到着』メッセージ、『出発』メッセージ、『使用不可』メッセージのいずれかに対応するスポットオブジェクトについて状態変数テーブルを更新し、空港オブジェクトについても、『出発』メッセージ、『到着』メッセージ、『夕刻のスポット溢れ』メッセージ、『空港使用可／不可』メッセージにより前述の所定の処理を行うことによりシミュレーションを行う。
【００３８】
ステップ１０４）  フライトオブジェクト５０は、シミュレーションの結果をスケジュール管理部３０に渡す。
ステップ１０５）  スケジュール管理部３０は、フライトオブジェクト５０から渡されたシミュレーションの結果に機材名が含まれており、当該シミュレーションの結果が出発便である場合には、機材が割り当てられているものと判定し、フライトリストの再編集を行う。一方、シミュレーション結果に機材名が指定されていない場合には、シミュレーションが失敗したものとして、ＮＧ個数をカウントする。
【００３９】
ステップ１０６）  スケジュール管理部３０は、モード（機種割当不可モード、駐機スポット割当不可モード等）に対応する問い合わせをフライトオブジェクト５０に対して行う。
ステップ１０７）  フライトオブジェクト５０は、問い合わせに対する回答を生成し、スケジュール管理部３０に返却する。例えば、機種割当不可モードによる問い合わせがあった場合には、『当該機種が指定空港に用意されていないため』等の回答を行うものとする。
【００４０】
ステップ１０８）  全フライトリストに関する処理が終了したらステップ１０９の適応度の計算を行う。
ステップ１０９）  スケジュール管理部３０は、前述の方法により適応度の計算を行い、その結果をＧＡ１０に渡す。
上記の実施例において、シーケンスチャートを用いて説明した内容をソフトウェア（プログラム）で構築し、フライトスケジュール生成装置のコンピュータに接続されたディスク装置等に格納しておき、必要に応じてインストールして実行させることが可能である。また、ソフトウェアをフロッピーディスクやＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、汎用的に用いることも可能である。
【００４１】
なお、本発明は、上記の実施例に限定されることなく、特許請求の範囲内で種々変更・応用が可能である。
【００４２】
【発明の効果】
上述のように、本発明によれば、ＧＡの評価関数の計算部分をオブジェクト指向で統一的かつ簡素に記述することが可能となり、その結果、評価対象の改変にも比較的容易にかつ柔軟に対応できる。
また、本発明によれば、スケジューラとオブジェクト・モデルを組み合わせることで、これまで困難であった不整合や過剰な要求やスケジュールの不適切な部分の指摘が容易になる。
【図面の簡単な説明】
【図１】本発明のシステム構成図である。
【図２】本発明の一実施例の最適化装置の構成図である。
【図３】本発明の一実施例のデコードされたシステムのパラメータ（染色体デコード結果）の例である。
【図４】本発明の一実施例の状態変数テーブルの例である。
【図５】本発明の一実施例のフライトスケジュールを作成する手順を示すシーケンスチャートである。
【図６】本発明の一実施例のＧＡにおける染色体のコーディング／デコードを説明するための図である。
【図７】本発明の一実施例のスケジュール管理部の便のキューの時間変化を示す図である。
【符号の説明】
１  遺伝的アルゴリズム
２  評価関数の計算部
３  システムのパラメータ
４  スケジューラ
５  最適化対象のオブジェクト・モデル
１０  遺伝的アルゴリズム（ＧＡ）
２０  機材スケジュール
３０  フライトスケジュール管理部
４０  スケジューリング部
５０  フライトオブジェクト
【図１】
0003943663.tif 000005
【図２】
0003943663.tif 000006
【図３】
0003943663.tif 000007
【図４】
0003943663.tif 000008
【図５】
0003943663.tif 000009
【図６】
0003943663.tif 000010
【図７】
0003943663.tif 000011