(57)【特許請求の範囲】
【請求項１】
遺伝的アルゴリズムにより求められた染色体として表現された求解データを問題モデルに適用した結果得られる解の評価値を、前記染色体の適応度として受け取り、前記染色体を遺伝的アルゴリズムにより進化させることにより、求解データの最適化を進行させる求解データ提示手段と、
該求解データ提示手段から受け取る前記求解データから、少なくとも局所探索手法と確率的探索手法の併用により、前記問題モデルの解を求める求解手段と、
該求解手段により求められた解の評価値を算出し、それを前記求解データ提示手段に出力する評価値算出手段と、
前記求解データ提示手段、前記求解手段、及び前記評価値算出手段を制御して、前記問題モデルの最終的な解を求める解取得手段と、を備え、
前記問題モデルは、ある単位の作業の一連の繋がりから成る１日単位の複数の第１のスケジュールを、複数日にまたがって接続することにより得られる複数日に跨がる第２のスケジュールの解を求める制約充足最適化問題のモデルであり、
前記作業は航空機の便の乗務であり、前記第１のスケジュールは１日の乗務パターンであり、前記第２のスケジュールは複数日に跨がる乗務パターンであり、
前記局所探索手法は、期割れとなった便の残りの運航日に運航可能な接続便を探索する際に使用され、
前記確率的探索手法は、次に接続する便を探索するために使用され、
前記求解手段は、前記染色体の第１の遺伝子と、各シップライン毎に設けられた、該各シップラインの分割方法を確率的に決定するための情報が格納されているセグメンテーション確率テーブルとを使用して、各シップラインをセグメントに分割し、該分割されたセグメントを接続することにより前記複数日に跨がる乗務パターンを作成すると共に、前記染色体の第２の遺伝子と、各便毎に設けられた、該各便に接続すべき便に関する接続確率値が格納されているセグメント接続確率テーブルとを使用して、次に接続すべきセグメントを確率的に探索することを特徴とする最適化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、最適化装置に関する。
【０００２】
【従来の技術】
最適化は、高度なコンピュータ利用における知的処理の根幹をなすものであり、スケジューリング問題、配車計画問題、パターン推定、時間割り自動割りつけ、乗員配置問題等の具体的な応用分野がある。しかしながら、計算量や記憶装置の記憶容量の制限から、このような大規模な最適化問題を、直接、全解探索で解くことは現実的ではない。
【０００３】
近年のコンピュータの性能の向上に伴い、従来のエキスパートシステム等で解決が困難であった問題を解決する手段として、確率的最適化手法（ジミュレーティド・アニーリング、ＧＡ（遺伝的アルゴリズム））等が注目をあび、その実用化のための研究がなされている。様々な最適化手法の中でも、特に、ＧＡは、その手法の単純さから注目されている。
【０００４】
また、全ての産業において、人員のスケジュールは根本的な問題であるが、これは、最適化問題の１つとして捉えることができる。この問題は、あらゆる産業分野で、コスト削減に決定的な影響を与える。
【０００５】
例えば、航空分野では、世界的に、燃料代の次に人件費が大きいといわれており、この人件費の削減が大きな課題となっている。
組み合わせ問題を解く一般的手法として、ＬＰ（Linear Progrming) やＩＰ（Integere Programing)のような、連立方程式によるモデル化と数学的求解が用いられ、問題をＳｅｔ  ＰａｒｔｉｏｎｉｎｇまたはＳｅｔ  Ｃｏｖｅｒｉｎｇ問題として解いている。
【０００６】
しかし、これらの手法では、複雑な問題を解く場合、定式化そのものが難しく、例え、定式化できたとしても、大規模問題では定義性や組み合わせ数が増大し、実用的な時間内に解が得られない。しかも、何時間実行させても、結局、解が見つからない場合がある等の難点がある。
【０００７】
また、高速化のためにカラムジェネレーション等の手法も用いられているが、カラムの生成時間やメモリ容量の制限等の問題から、大規模な問題では様々な限界に直面する。
【０００８】
このような従来手法を解決する手段として注目されたのがＧＡ(Genetic Algorithms)である。ＧＡでは問題をモデル化し、そのパラメータを染色体で表現する。ＧＡで最適化を行う際には、染色体をデコードしてパラメータに変換し、そのパラメータを問題モデルに投入してその評価を行い、その評価値を染色体の適応度として用いることで、個体（染色体）を進化させ、最適化を進展させる。
【０００９】
【発明が解決しようとする課題】
１．  問題の記述性の問題
ＩＰ／ＬＰでは、問題の記述を行列の形式で表現しなけらばならず、この方式では、個別の条件を詳細に反映するのは困難である。
【００１０】
カラムジェネレーションで解く一つの解法では、問題をルール化し、カラムジェネレーション時の生成ルールとして問題の詳細を記述するものもあるが、問題を如何にルールで表現するか、ルールの網羅性や妥当性の検証、ルール間の無矛盾性の確保等、様々の問題を抱えている。
２．  探索手法の問題
従来手法にはない長所を持つＧＡであっても、解空間が膨大になると求解能力にも、以下のような限界が生じてくる。
【００１１】
１）  ＧＡの染色体が、解空間の全てをカバーできない。
２）  解空間を一様に覆うようなコーディングをすると、制約違反がある領域や、解としては不適当な領域が非常に多くなり、最適化が効率的に行えない。
【００１２】
３）  解生成ルールを用いた解生成が望ましい場合があるが、単純にルールだけを用いて解を生成すると、求解手法の硬直化を招き、良質の解が得られなくなる。
３．  スケジュール期間と作業の規則性の問題
実際にスケジュールを行わればならない対象は、日によって特定の作業があったり、なかったりするかなり複雑なものであるが、従来手法ではこれを直接に扱うことが困難であるため、同じ作業が連日続く事を暗黙の前提として、数日に渡るスケジュールを組んでいる。これを、Ｄａｉｌｙ  Ｍｏｄｅｌという。
【００１３】
スケジュール対象の作業は、今後、ますます不定期になるので、Ｄａｉｌｙ  Ｍｏｄｅｌのような解法は、ますます実体に則さないスケジューリングになっている。
【００１４】
ところで、米国の航空乗務員スケジュールのように、週末だけ一部の作業のないようなものが考えられ、これをＷｅｅｋｌｙ  Ｍｏｄｅｌという。
更に、全ての不定期なスケジュール対象を取り入れ、スケジュール期間が１〜２ヵ月程度になるものをＦｕｌｌｙ  Ｄａｔｅｄ  Ｍｏｄｅｌといい、これを直接扱った例は知られていない。
【００１５】
本発明の目的は、従来は解を得ることが不可能であった、Ｆｕｌｌｙ Ｄａｔｅｄ Ｍｏｄｅｌのような、広範囲な探索空間を有し、かつ制約条件の多い制約充足最適化問題の解を自動生成可能な最適化装置を実現することである。
【００１６】
【課題を解決するための手段】
本発明の最適化装置は、以下の各手段を備える。
求解データ提示手段は、遺伝的アルゴリズムにより求められた染色体として表現された求解データを問題モデルに適用した結果得られる解の評価値を、前記染色体の適応度として受け取り、前記染色体を遺伝的アルゴリズムにより進化させることにより、求解データの最適化を進行させる。
【００１７】
求解手段は、該求解データ提示手段から受け取る前記求解データから、少なくとも局所探索手法と確率的探索手法の併用により、前記問題モデルの解を求める。
【００１８】
評価値算出手段は、該求解手段により求められた解の評価値を算出し、それを前記求解データ提示手段に出力する。
解取得手段は、前記求解データ提示手段、前記求解手段、及び前記評価値算出手段を制御して、前記問題モデルの最終的な解を求める。
【００２２】
前記問題モデルは、ある単位の作業の一連の繋がりから成る１日単位の複数の第１のスケジュールを、複数日にまたがって接続することにより得られる複数日に跨がる第２のスケジュールの解を求める制約充足最適化問題のモデルである。
【００２３】
このような構成において、前記作業は、航空機の便の乗務であり、この場合、前記第１のスケジュールは１日の乗務パターンであり、前記第２のスケジュールは複数日に跨がる乗務パターンである。この場合、前記局所探索手法は、期割れとなった便の残りの運航日に運航可能な接続便を探索する際に使用される。また、前記確率的探索手法は、次に接続する便を探索するために使用される。
【００２４】
また、前記求解手段は、前記染色体の第１の遺伝子と、各シップライン毎に設けられた、該各シップラインの分割方法を確率的に決定するための情報が格納されているセグメンテーション確率テーブルとを使用して、各シップラインをセグメントに分割し、該分割されたセグメントを接続することにより前記複数日に跨がる乗務パターンを作成すると共に、前記染色体の第２の遺伝子と、各便毎に設けられた、該各便に接続すべき便に関する接続確率値が格納されているセグメント接続確率テーブルとを使用して、次に接続すべきセグメントを確率的に探索する。
【００２８】
このような態様において、前記求解手段は、前記染色体の第２の遺伝子と各便毎に設けられた、該各便に接続すべき便に関する接続確率値が格納されているセグメント接続確率テーブルとを使用して、次に接続すべきセグメントを確率的に探索する。
【００３１】
【発明の実施の形態】
以下、図面を参照しながら本発明の実施形態を説明する。
図１は、本発明の実施形態の原理を説明する図である。尚、図１では、最適化機構としてＧＡ(Geneteic Algorithms) を採用しているが、本発明の最適化機構はＧＡに限定されるものではない。
【００３２】
ＧＡ処理部１は、適応度計算器１−１、選択操作器１−２、交叉操作器１−３、及び突然変異操作器１−４から構成される。
適応度計算器１−１は、自らが管理する、ある世代の染色体集団２内の各染色体２−１の適応度を計算する。選択操作器１−２は、適応度計算器１−１の計算結果に基づき、適応度の高い染色体２１−が、より多く次世代の親として選ばれるように選択操作を行う。
【００３３】
交叉操作器１−３は、選択操作器１−２によって選択された染色体２−１をランダムに２個ずつ組み合わせ、ある確率（交叉率）で、２つの染色体２−１の遺伝子列を部分的に交換する。
【００３４】
突然変異操作器１−４は、ある確率（突然変異率）で、染色体２−１の各遺伝子座の遺伝子を他の対立遺伝子と入れ換える。
適応度計算器１−１は、突然変異操作器１−４により得られた染色体２−１により、染色体集団２内のＮ個の染色体２−１を次世代に置き換える。
【００３５】
染色体２−１は、ｍ個（ｍは任意の整数）の遺伝子から構成されている。各遺伝子座の遺伝子は文字列、ビット列、整数配列等で表現される。各染色体２−１は、解２−２と適応度２−３を有する。解２−１は、デコード処理器３により、問題モデル計算部４内部の問題モデルのパラメータに変換された染色体２−１が問題モデルで評価される際に生成される問題の解である。適応度２−３は、解２−２の問題モデルでの評価値（目的関数値）によって決定される染色体２−１の適応度である。
【００３６】
デコード処理部３は、染色体集団２から染色体２−１を順次取り出し、染色体２−１の各遺伝子を、問題モデル計算部４で計算される問題のパラメータ３−１にデコードする。このデコード処理において、一部の遺伝子について、確率テーブル（不図示）が利用されることが、本発明の特徴の一つである。
【００３７】
問題モデル計算部４は、デコード処理部３から問題のパラメータ３−１を受け取り、それを基に、対象の問題の解を生成し、その解の評価値を算出する。この評価値は、例えば、染色体２−１の適応度に等しい。
【００３８】
問題モデル計算部４は、コントーラ４−１、局所探索手法器４−２、ＧＡ探索器４−３、確率的探索器４−４、制約違反判定器４−５、制約違反処理器４−６、及び解・適応度算出器４−７を備えている。
【００３９】
コントーラ４−１は、問題モデル計算部４全体を制御し、解の生成過程において、その時の条件に応じて、局所探索手法器４−２、ＧＡ探索器４−３、または確率的探索器４−４を起動する。例えば、局所探索手法により新たな解の候補を探索する必要が生じた場合には、局所探索手法器４−２を起動して、新たな解の候補を探索する。また、染色体２−１の遺伝子のデコードにより新たな解の候補を探索可能なときは、ＧＡ探索器４−３を起動して、新たな解の候補を検索する。また、さらに、確率的探索器４−４により新たな解の候補を検索可能なときは、確率的探索器４−４を起動して、新たな解の候補を探索する。
【００４０】
局所探索手法器４−２、ＧＡ探索器４−３、または確率的探索器４−４の処理が繰り返し行われることにより、最適解または準最適解が求められるが、その過程で、得られた途中の解が制約違反を起こしていないか否かが制約違反判定器４−５によって判定される。
【００４１】
制約違反判定器４−５によって制約違反が判定されると、制約違反処理器４−６が起動され、局所探索手法器４−２、ＧＡ探索器４−３、または確率的探索器４−４によって追加された解の一部を除去する等の処理がなされ、処理はコントーラ４−１に移行する。コントーラ４−１は、解の作成処理が終了したか判断し、まだ、終了していなければ、上述したような判断を行い、局所探索手法器４−２、ＧＡ探索器４−３、または確率的探索器４−４を起動する。
【００４２】
以上のようなループ処理を続けながら、コントーラ４−１が解の生成の終了を判断すると、解・適応度算出器４−７はコントーラ４−１から生成された解を受け取り、その解の評価値（染色体２−１の適応度）を算出する。そして、解・適応度算出器４−７は、デコード処理部３によってデコードされた染色体２−１の解２−２及び適応度２−３を染色体集団２に返す。
【００４３】
本発明の原理の要点を簡単に説明する。
〔１〕  デコード処理部３のデコードにより得られた問題パラメータ３−１が問題モデル計算部４に投入されると、問題モデル計算部４はその問題パラメータ３−１を基に、問題モデル計算部４によって問題の解を生成する。
【００４４】
問題モデル計算部４内部の問題モデルは、予め組み込まれたパラメータによって、問題を正しく記述できる状態になっている。
〔２〕  問題モデル計算部４は、コントーラ４−１の制御によって、局所探索手法器４−２、ＧＡ探索器４−３、または確率的探索器４−４を起動しながら、問題モデルの解を生成する。問題モデル計算部４で生成された解は、制約違反判定器４−１によって制約違反を起こしていないかチェックされ、制約違反がなければ、問題モデル計算部４で処理は続行される。一方、制約違反が発見された場合には、制約違反処理器４−６によって、局所探索手法器４−２、ＧＡ探索器４−３、または確率的探索器４−４によって新たに付加された解の一部を除去する処理がなされる。
【００４５】
〔３〕  局所探索手法器４−２は、局所探索手法により解の候補を探索する。例えば乗務パターンの生成において、期割れの便が生じた場合、その便の期割れを補完する接続便を探索する。
【００４６】
〔４〕  ＧＡ探索器４−３は、例えば、染色体２−１の一部の遺伝子の情報を基に、解の候補を探索する。
〔５〕  確率的探索器４−４は、解の候補を、確率テーブル（不図示）を参照して探索する。確率テーブルにおいては、予め計算された解候補の確率と、これまでに生成した解と解の候補との関係から、新たな確率が計算され、この確率に応じて解の候補を提示する。確率テーブルから解候補として提示されるものには、単純な確率だけではなく、問題の特質に合わせたものも含まれる。
【００４７】
確率的探索器４−４は、例えば、ＧＡ探索器４−３による処理が不可能になった場合に起動される。
〔６〕  問題モデル計算部４により、最終的な解の生成が終了した後に、その解の適応度の計算を行い、染色体集団２に、〔１〕でデコードされた染色体２−１の解２−２とその適応度２−３を返す。
【００４８】
〔７〕  〔１〕〜〔６〕が、染色体集団２内の全ての染色体２−１に対して実施され、それらに対応する解２−２と適応度２−３が求められると、適応度計算器１−１は、染色体集団２の世代交代を行い、全体の最適化を進行させる。
【００４９】
図２は、図１の最適化装置の処理アルゴリズムを説明するフローチャートである。尚、このフローチャートは１つの染色体２−１を対象としたフローチャートである。
【００５０】
まず、デコード処理部３が染色体集団２から染色体２−１を一つ取り出し、それをデコードする（ステップＳ１）。このデコードによって、探索の開始点、探索順等のデータ（染色体情報）が得られる（ステップＳ２）。これらのデータは、例えば、後述する染色体４０の遺伝子４１〜４３をデコードすることによって得られる。
【００５１】
次に、問題モデル計算部４が、上記デコードによって得られた染色体情報に従って解の生成を開始する。問題モデル計算部４は、求解の状態判定を行い（ステップＳ３）、その判定結果に応じて、解の生成処理を実施する。
【００５２】
解の生成処理は、「ＧＡ探索器４−３に従った解の付加処理」（ステップＳ４）、「確率的探索器４−４を用いた解の付加処理」（ステップＳ５）、及び「局所探索手法器４−２による解の付加処理」（ステップＳ６）のいずれかから成る。
【００５３】
ステップＳ４、Ｓ５またはＳ６の処理によって生成された解は、制約違反判定器４−１によって制約条件を満足しているか否か判定される（ステップＳ７）。そして、ステップＳ７で制約条件を満足していると判定された場合、ステップＳ３に戻り、ステップＳ３において解の生成処理の続行または終了が判断される。
【００５４】
一方、ステップＳ７において、ステップＳ４、Ｓ５またはＳ６で生成された解が制約違反を起こしていると判定されると、その解からステップＳ４、Ｓ５，またはＳ６で付加された部分が除去され（ステップＳ８）、ステップＳ３に戻り、他の解の探索に移行する。
【００５５】
以上のようにして、ステップＳ３〜Ｓ８の処理が繰り返され、ステップＳ３で、所定の評価値以上の解（最適解または準最適解）が得られたと判定されると処理を終了する。また、処理の続行が困難になったときにも処理を終了する。また、さらに、探索回数が所定数を越えても満足する解が得られない場合にも、処理を終了する場合がある。
【００５６】
次に、本発明を、航空機の乗務員(Crew)の長期に渡る乗務パターンの生成に適用した実施形態について説明する。
乗務パターン作成は、制約充足最適化問題（与えられた制約条件を全て満足し、目標とする評価指標を最適化する問題）の一種であり、特に、自動化が困難とされる時系列スケジュール問題である。
【００５７】
まず、本実施形態で取り使う乗務パターン作成業務の概要について説明する。
便の航空機の乗務員は、事務所がある空港（基地空港）発の便から乗務を開始し、１日最大４回まで、いくつかの便を乗り継いで乗務した後、その日の乗務を終え、どこかの空港で宿泊する。そして、翌日は、その空港を出発する別の便から乗務を開始する。このようにして、何日かの乗務を繰り返し後、３日以内に最初の乗務の基地空港に戻ってくる。この一連の便の乗り継ぎのパターンを「乗務パターン」と呼ぶ。乗務パターンの作成業務では、ダイヤ上の全ての便が、いずれかのパターンに含まれるように、乗務パターンを複数作成する必要がある。
【００５８】
航空機の便には、特定の日のみ運航する「期割れ便」という便が存在する。乗務パターンの作成の際には、このような期割れ便を、運航日付に不整合が生じないように、乗務パターンにうまく組み込む必要があり、このことが、問題をさらに複雑にしている。
【００５９】
機種（基幹路線に利用される機種、ローカル路線に利用される機種）によって問題の複雑性は異なるが、問題の規模は、おおまかには、乗務パターンを作成する際に取り扱う便数に依存する。１９９７年に運用されたデータによれば、最小規模の問題（機種がボーイング７７７）では対象便数は３８便、最大規模の問題では３６４便となっている。該最大規模の問題では、３６４の各便のそれぞれに対して、次に乗り継ぐ便を、平均１５０の便から選択できるので、これだけで、組み合わせ数は、１５０の３６４乗（＝１０の７８０乗）となる。
【００６０】
さらに、最大２か月間のダイヤに対して、日毎に異なった乗務パターンを作成する必要があるので、最大では、１０の７８０乗のさらに６０乗の組み合わせ数となる。実際には、毎日、できるだけ同じパターンで運航するように乗務パターンを作成しているため、そこまで巨大な探索空間にはならないが、それでも探索空間が巨大（１０の７８０乗の３〜４乗）であることに変わりはない。
【００６１】
以上述べたことから、明らかなように、乗務パターンの作成の困難さの本質は、以下の点にある。
１）  探索空間（組み合わせ数）が巨大である。
【００６２】
２）  制約条件が多く、問題が複雑である。
制約条件は、３０種類以上もあり、最適解どころか制約充足解を得るだけでも困難である。
【００６３】
これらの制約条件の中には、個々の乗務パターンを作成していく途中で判定できる局所的条件と、全ての乗務パターンを完成させないと判定できない大域的条件がある。局所的条件に関しては、処理の途中で回避できる場合もあるが、大域的条件に関してはそのような工夫ができない。
【００６４】
３）  解の品質に対する要求レベルが高い
制約充足解の導出が困難な上に、解の最適化に対する要求も高度である乗務パターンによって、ダイヤを運航するのに必要になる乗務員ののべ人数が決定される。一人の乗務員が、一日になるべく多くの便に乗務できるようなパターンを作成すれば、必要とされる乗務員ののべ人数が削減される。
【００６５】
以下に述べる実施形態は、上述した乗務パターンの自動作成に本発明を適用したものであり、下記の１）〜３）のような特長をもつＧＡに対して独自に拡張を施し、そのＧＡをシステムに組み込むことにより、今まで、解決不可能であったＦｕｌｌ  Ｄａｔｅｄ  Ｍｏｄｅｌでの解を得ることに成功したものである。
【００６６】
１）  問題解決のための知識獲得が必ずしも必要ではない。
２）  広い範囲の探索が可能である。
３）  動作の並列性が高く、複数のＣＰＵによる処理の高速化が可能である。
【００６７】
本実施形態で、ＧＡの一般的な枠組みに対して施した拡張は、以下の通りである。
１．  便接続に関する確率テーブルの適用
本実施形態では、ある便から次の便への接続を変数とし、接続可能な候補を選択肢として探索する。このような選択肢は一般に複数存在するが、個々の選択肢が採用される望ましさはかならずしも同等ではない。そこで、専門家が乗務パターンを作成する際に接続している便の組み合わせを分析し、望ましい組み合わせの便同士が持つ特徴を抽出し、これを、各選択肢の選択確率に反映させる確率テーブルを作成するようにした。この確率テーブルを用いることにより、望ましい接続状態が出現する頻度が高くなり、質の良い解が短時間で得られるようになった。
【００６８】
２．  セグメンテーション
いくつかの変数をグループ化し、それらの値を選択肢とする上位変数を用意することで、探索空間を制限した。実際には、専門家が、同じ機材で運航している便には、できる限り同じ乗務員が乗務するように便を接続している点に着目し、同じ機材で運航している複数の便をグループ（セグメント）として、まとめて扱うようにした。この際、グループを決定的に作成するのではなく、グループ化（セグメンテーション）の選択肢を変数として設定し、これをＧＡによって探索するようにした。尚、このセグメンテーションの選択のための確率テーブルを用意し、ＧＡをデコードする際に、この確率テーブルを参照して、セグメンテーションを決定するようにした。
【００６９】
これにより、平均３便程度の便をまとめて扱うことができるようになり、同質の問題に対しては、問題規模（便数）が約３分の１である問題とほぼ同程度の処理時間で求解が可能になった。さらに、求解時間の短縮のみならず、従来の方式では解を得ることができなかった問題に対する求解可能性を向上させることができるようになった。実際に、この手法の導入により探索空間を劇的に縮小させることができ、大規模問題に対しても解を得ることができるようになった。
【００７０】
図３は、本発明の実施形態のＧＡ・クルー・ペアリング・システムの全体構成を示すブロック図である。
ＧＵＩ（グラフィカル・ユーザ・インタフェース）装置１０は、例えば、パーソナルコンピュータであり、ソフトウェアであるクルー・ペアリング・エディタ１１と制約条件エディタ１２を実行する。
【００７１】
制約条件エディタ（Constraint Condition Editor)１１は、プリプロセスで必要となるプリプロセス情報（制約条件やＧＡパラメータ等）の作成用のエディタである。制約条件エディタ１１によって作成・変更されたプリプロセス情報は、ファイル１３に格納される。ファイル１３に格納されたプリプロセス情報は、プリプロセッサ２１により読みだされる。
【００７２】
また、クルー・ペアリング・エディタ（Crew Pairing Editor)１２は、ＧＡクルー・ペアリング・最適化装置２０の最適化部２２により生成された乗務パターンを入力し、それを表示装置（不図示）にグラフィカルに表示する。また、クルー・ペアリング・エディタ１２は、ファイル１４に格納されている便データを表示装置に表示する。この便データは、乗務パターンの作成に必要な、各便の情報（便名、機種、機材番号、出発空港、出発時刻、到着空港、到着時刻、運航パターン等）である。
【００７３】
ファイル１４に格納されている便データは、ＧＡクルー・ペアリング・最適化装置２０内のプリプロセッサ２１により読みだされる。
ＧＡクルー・ペアリング・最適化装置２０は、プリプロセッサ(Pre Processor) ２１と最適化部(0ptimizer) ２２を備える。
【００７４】
最適化部２２は、ＧＡ実行部２２ａとクルー・ペアリングモデル計算部２２ｂを備える。ＧＡ実行部２２ａは図１のＧＡ処理部１、染色体集団２及びデコード処理部３に相当し、クルー・ペアリングモデル計算部２２ｂは図１の問題モデル計算部４に相当する。
【００７５】
プリプロセッサ２１は、乗務パターンを作成する際の前処理（プリプロセス処置）を行う。前処理としては、以下のようなものがある。
１）  プリプロセス情報（全ての便データ、制約条件、ＧＡパラメータ等）の読み込み
２）  各乗務便について、乗り継ぎ可能な全ての便と、デッドヘッドをリストアップする。尚、デッドヘッドとは、パイロットを該パイロットが次に乗務する便の出発空港まで輸送することであり、この輸送には、通常の一般運航便や鉄道が利用される。デッドヘッドには当日接続用と翌日接続用の２種類がある。したがって、このリストアップは、当日と翌日の接続便まで含む（接続情報セットアップ処理）。
【００７６】
３）  各シップラインについて、可能な切断を全てリストアップする（シップライン設定セットアップ処理）。尚、シップラインとは、ある１日に１つの機種で連続して運航している便を、時間の順序に連ねたものである。
【００７７】
上記接続情報セットアップ処理においては、上述したように、各乗務便について、乗り継ぎ可能な全ての便と、デッドヘッドをリストアップする。そして、接続状況からヒューリスティクスに導出した評価基準に従って、各接続の望ましさを計算・設定しておく（接続確率テーブルの作成）。
【００７８】
上記シップライン設定セットアップ処理においては、シップラインの全ての可能な切断を行い、各切断（セグメンテーション）が制約に違反していないかをチェックする。さらに、各切断方法についてヒューリスティクスに導出した評価を予め行い、記録しておく。
【００７９】
図４は、上記シップライン設定セットアップ処理の一例を示す図である。
同図は、flight１，flight2 ，flight3 ，及びflight4 の４便を接続したシップラインの切断（セグメンテーション）の例であり、「０」〜「７」の番号で識別される８種類の切断方法が示されている。同図において、“illegal ”が制約違反の切断を示している。したがって、「０」と「４」の切断が制約違反に該当する。
【００８０】
制約違反でない切断については、“point ”で示された評価値が設定されており、例えば、「２」の切断に対しては、最高の評価値“５００”が設定されている。また、「７」の切断に対しては、最低の評価値“１”が設定されている。制約違反を起こしていない６種類のセグメンテーションについて、その評価値に応じて、セグメンテーション確率テーブルが作成される。このセグメンテーション確率テーブルの作成方法については後述する。
【００８１】
以下に、最適化部２２の動作を簡単に説明する。
〔１〕  クルー・ペアリングモデル計算部２２ｂは、ＧＡ実行部２２ａから入力される染色体集団２の個々の個体をデコードし、問題（クルー・ペアリングモデル）のパラメータに変換する。尚、ここでは、個体と表現しているが、これは図１の染色体２−１（個体の表現型）に該当するものである。
【００８２】
〔２〕  クルー・ペアリングモデル計算部２２ｂは、〔１〕で得られた第１のパラメータと前記セグメンテーション確率テーブルを用いて、シップライン切断（セグメント）を設定する。
【００８３】
〔３〕  クルー・ペアリングモデル計算部２２ｂは、各セグメントの割り付け順位を、〔１〕で得られた第２のパラメータにしたがって決定する。
〔４〕  クルー・ペアリングモデル計算部２２ｂは、セグメントの後端の便について、次の接続情報（セグメント接続確率テーブル）を設定する。
【００８４】
〔５〕  クルー・ペアリングモデル計算部２２ｂは、
（ａ）  セグメントを、〔３〕で得られた割り付け順位に従って順番に取り出し、それらのセグメントを、〔１〕で得られた第３のパラメータまたは［４〕で得られたセグメント接続確率テーブルに従って接続する。
【００８５】
（ｂ）  セグメントを接続する際に、その接続が制約違反を起こしていないかチェックする。
（ｃ）  制約違反を起こしていた場合は、（ａ）で接続したセグメントを取り除き、新たなセグメントを接続するために（ａ）に戻る。
【００８６】
（ｄ）  予め設定した条件を満足する解が生成されるまで、（ａ）〜（ｃ）の処理を繰り返す。
〔６〕  クルー・ペアリングモデル計算部２２ｂは、〔５〕で生成された解について、その適応度を計算する。
【００８７】
〔７〕  上記解と上記適応度を、ＧＡ実行部２２ａに返す。
〔８〕  ＧＡ実行部２２ａは、クルー・ペアリングモデル計算部２２ｂから、全ての個体（染色体２−１）の解と適応度を入力すると、遺伝的アルゴリズムにより、染色体集団２の世代交代を行う。
【００８８】
〔９〕  クルー・ペアリングモデル計算部２２ｂは、この世代交代により得られた個体（染色体２−１）について、〔１〕〜〔７〕を繰り返し、最適解または準最適解を生成する。
【００８９】
〔１０〕  最適化部２２は、上記最適解または上記準最適解を、クルー・ペアリング・エディタ１２に出力する。
図５は、本実施形態で使用する制約条件の事例を示す図である。本実施形態で作成する乗務パターンは、同図に示された、「乗務便数」（４便以下）、「乗務時間」（６時間以上）、「勤務時間」（１１時間以下）、「乗務前準備時間」（６０分）、「乗務後整理時間」（３０分）、「日中の乗換え時間」（９０分以上）、「宿泊禁止空港」（空港名を指定）、「基地比率」（東京６０％：大阪４０％）、「基地空港」（空港名を指定）、「連続勤務日数上限」（３日）、「固定パターン指定」（便のリストで指定）等の制約条件を満足しなければならない。
【００９０】
図６は、シップラインの具体例を示す図である。
シップライン（Ship line ）１〜３は、以下のようになっており、全て、４つの便を連結したものとなっている。
【００９１】
シップライン１：ＨＮＤ（羽田）→ＩＴＭ（伊丹）→ＳＰＫ（札幌）→ＩＴＭ（伊丹）→ＨＮＤ（羽田）
シップライン２：ＳＰＫ（札幌）→ＴＯＹ（富山）→ＨＮＤ（羽田）→ＫＭＯ（熊本）→ＳＰＫ（札幌）
シップライン３：ＳＰＫ（札幌）→ＴＯＹ（富山）→羽田（ＨＮＤ）→広島（ＨＩＪ）→ＳＰＫ（札幌）
図６の各シップライン１〜３の各便に付与されたｆ１〜ｆ１２は便名である。また、シップライン１は連日(through days)運航する便となっているが、シップライン２は奇数日のみ運航する期割れ便、シップライン３は偶数日のみ運航する期割れ便となっている。同図の左端に示すビット列は、運航日程（operating days) を示すものであり、各ビットが１日に対応している。そして、“１”のビット値が運航を、“０”のビット値が非運航を示している。
【００９２】
ところで、便は「通月便」と「期割れ便」に分類される。通月(regular) 便は、スケジュール期間中、連日運航する便である。期割れ(irregular) 便は、スケジュール期間中、連日運航しない不規則な便である。
【００９３】
次に、図７を参照して、図６の各シップライン（Ship line ）１〜３のセグメント接続確率テーブルの作成方法の一例を説明する。ここでは、理解を容易なものとするために、１日の乗務便数は「２」という制約条件が設定されているものとする。また、以下のような加点のルールを定める。この加点ルールはヒューリスティクスに定めたものである。
【００９４】
・  シップラインが２つに分かれたら１００点
・  シップラインが３つに分かれたら２０点
・  シップラインが４つに分かれたら０点
・  ＨＡＤ，ＩＴＭで切断されたら１０点
・  ＳＰＫで切断されたら５点
図７に、上記規則に従って、シップライン１〜３の各切断（セグメンテーション）に付けた点数（point ）を示す。同図（ａ）〜（ｃ）が、それぞれ、シップライン１〜３に対応している。シップライン１〜３のいずれにおいても、５種類の切断（○印が右側に付与された切断）が制約条件を満足している。
【００９５】
各シップラインについて、制約条件を満足する切断を、その点数に応じて、予め設定された幅（図７の例の場合は０〜２５６）にマッピングして、セグメンテーション確率テーブル３０ａ〜３０ｂを作成する。
【００９６】
図７に示す例では、点数の高いセグメンテーション（Segmentation) から順に、セグメンテーション確率テーブル３０ａ〜３０ｃに登録するようにしている。また、各セグメントの登録数は点数に比例配分したものとなっている。したがって、セグメンテーション確率テーブル３０ａ〜３０ｃにおいては、点数の高いセグメント程、選択される確率が高くなる。よって、遺伝子のセグメントメント探索値（セグメンテーション情報）が０〜２５６まで無作為に選ばれる場合、各シップライン１〜３について，セグメンテーション確率テーブル３０ａ〜３０ｃを参照してセグメントを選択すれば、適切なセグメント選択が実現できる。尚、図７のセグメンテーション（Segmentation) においては、制約条件として、最大離陸数＝２、最大飛行時間＝１８０分、最大労働時間＝３６０分が設定されている。なお、図７のセグメンテーション確率テーブル３０ａ〜３０ｃのセグメンテーションの格納方法は，あくまでも一例であり、その格納方法には各種形態が考えられる。
【００９７】
図８は、シップライン１のセグメンテーション情報Ｓ１０〜Ｓ１７を表現するデータ構造の一例を示す図である。セグメンテーションＳ１０〜Ｓ１７は３ビットのビット列で表され、先頭のビットがｆ１とｆ２を、２番目のビットがｆ２とｆ３を、３番目のビットがｆ３とｆ４を切断するか否かを示す。これらのビットが“１”であれば切断を、“０”であれば非切断を示す。
【００９８】
図９は、本実施形態で使用する染色体２−１の構成例を示す図である。
同図に示す染色体４０は、図６のシップライン１〜３から、乗務パターンを作成するためのものである。染色体４０は、便１（ｆ１）〜便１２（ｆ１２）の割り付け順序情報を格納する遺伝子４１、各シップライン１〜３のセグメンテーション情報を格納している遺伝子４２、及び各便１（ｆ１）〜便１２（ｆ１２）について接続候補便情報（接続候補リスト）を格納している遺伝子４３（４３−１〜４３−１２）から構成されている。
【００９９】
この染色体４０は、遺伝子４２、遺伝子４１、遺伝子４３の順にデコードされる。遺伝子４２は３個の整数型のデータの配列であり、順に、シップライン１（sl1 ）、シップライン２（sl2 ）、及びシップライン３（sl3 ）の各シップラインのセグメンテーション（segmentation) 情報〔整数値〕を格納している。この遺伝子４２の各シップライン１、シップライン２、及びシップライン３の各整数値は、それぞれ、上述したセグメンテーション確率テーブル３０ａ，３０ｂ，３０ｃのアドレス値である。
【０１００】
遺伝子４２の各シップライン１〜３に割り当てられた値は、シップライン１、２、３の順に、個別にデコードされる。このデコードの際、各シップラインの割当値は、対応するセグメンテーション確率テーブルのアドレスを示すポインタとして使用され、該アドレスからセグメンテーション情報を取得するために利用される。
【０１０１】
上述したように、セグメンテーション確率テーブル３０ａ，ｂ，ｃには、有効な（illegal)なセグメンテーション情報が格納されている。したがって、遺伝子４２をデコードすることにより、各シップライン１〜３のセグメンテーション情報を取得できる。そして、このセグメンテーション情報を基に、各シップライン１〜シップライン３について、１または複数のセグメントが得られる。該セグメントは、上述したように、１便または複数の便の接続であり、各セグメントは先頭の便（最初に出発する便）と最後の便（最後に到着する便）よって規定される。
【０１０２】
このようにして得られた各セグメントから、まず、先頭の便が取得される。この取得された先頭の便は、遺伝子４１のデコードに利用される。遺伝子４１は１２個の整数型のデータの配列であり、便１（ｆ１）〜便１２（ｆ１２）の順に、割り付け順序情報を格納している。上述した遺伝子４２のデコード処理の結果、上記先頭の便に該当する便のみが有効便として抽出され、その有効便が遺伝子４１の対応値に従ってソートされる（遺伝子４１の整数値が小さい有効便から順にソートされる）。このソートの結果、まず、先頭にソートされた便が先頭の便となっているセグメントを先頭する乗務パターンの作成が開始される。また、上記有効便を先頭の便とするセグメントの後尾の便についてセグメント接続確率テーブルが作成される。このセグメント接続確率テーブルは、後述するように乗務パターンを作成する際のセグメント接続に利用される。
【０１０３】
遺伝子４３は、便１〜便１２の各便に対応する１２個の配列４３（４３−１〜４３−１２）を有し、各配列４３には、各便の接続候補リストが格納されている。各配列４３の要素は便の識別子を示す整数値である。この遺伝子４３は、乗務パターンのセグメント接続に利用される。すなわち、該セグメント接続の際、配列４３から配列順に（接続候補リストのリスト順に）、配列要素（接続候補となるセグメントの先頭の便）を取り出し、それまでに作成されている乗務パターンにそのセグメントを接続する。そして、このセグメント接続が制約違反であるか判断される。
【０１０４】
そして、制約違反である場合には、そのセグメントの接続は破棄され、配列４３から次のセグメントが選択される。一方、該セグメント接続が制約違反でない場合は、乗務パターンの作成は続行される。また、各配列４３−１〜４３−１２の要素数（接続候補便数）は、各便毎に可変であり、最終要素の後には“−１”（強制終了）が設定される。
【０１０５】
次に、本実施形態の全体動作を図１０のフローチャートを参照しながら説明する。同図において、ステップＳ２１〜Ｓ２５がプリプロセッサ２１が実行するプリプロセス処理を示している。
【０１０６】
まず、プリプロセッサ２１がファイル１３から制約条件、ＧＡパラメータ等を読み込み、それらをメモリ（不図示）上に展開する（ステップＳ２１）。
該ＧＡパラメータは、例えば、染色体集団２の染色体２−１の個数、選択操作器１−２の選択操作率、交叉操作器１−３の交叉率、及び突然変異操作器１−４の突然変異率等である。
【０１０７】
次に、プリプロセッサ２１はファイル１４から便データを一式読み込み、それを該メモリ上に展開する（ステップＳ２２）。
続いて、上記ファイル１４から読み込んだ便データを基に、便接続を調べ、各乗務便について後述する接続テーブルを作成する（ステップＳ２３）。
【０１０８】
次に、上記ファイル１３から読み込んだ情報を基に、シップラインを抽出し、各シップラインについて図７に示すようなセグメンテーション確率テーブルを作成する（ステップＳ２４）。
【０１０９】
続いて、ステップＳ２１で読み込んだＧＡパラメータの計算を行い、ＧＡ２２ａを構築する（ステップＳ２５）。以上の処理により、プリプロセス処理が終了する。
【０１１０】
次に、最適化部２２が図２のフローチャートに示すアルゴリズムを実行し、ＧＡ実行部２２ａとクルー・ペアリングモデル計算部２２ｂを駆使しながら、問題の解の探索を行う（ステップＳ２６）。クルー・ペアリングモデル計算部２２ｂは、ＧＡ探索器４−３、局所探索手法器４−２、または確率的探索器４−４により解の探索を行う。
【０１１１】
局所探索手法器４−２においては、例えば以下のような処理を行う。
例１）  連日運航する通月便に対して、偶数日に運航する期割れ便（０１０１０１０１の乗務パターン）を割り当てた後に、それを補完する奇数日に運航する期割れ便（１０１０１０１０の乗務パターン）を探して、それを上記通月便の残りの運航日に割り当てる処理を行う。
【０１１２】
例２）  乗務パターンの開始が期割れ便であった場合に、それを補完する期割れ便が無く、かつ、最初の乗務パターンの２日目が基地からデッドアヘッドで接続できる場合、そのようなパターンを生成する。
【０１１３】
また、各染色体２−１の適応度（評価値）は、例えば、以下の式により設定する。
適応度＝α・（乗務パターンに組み込まれていない便数）＋β・（乗務パターン数）＋γ・（移動費用）＋δ・（基地比率からの逸脱）＋・・・
上記比例定数α、β、γ、δ等は、例えば実験を繰り返しながら決定する。そして、作成した解に対して上記式を適用し、その適応度を算出する。尚、α、β、γ、δは正の定数である。
【０１１４】
ステップＳ２６の処理は、処理の実行の中断の指令があったか、指定回数の探索を終了したか、または指定の条件を満足する解が得られたかのいずれかの判断がなされるまで（ステップＳ２７）、クルー・ペアリングモデル計算部２２ｂ内のセグメント接続コントローラ（図１のコントーラ４−１に相当）の制御により、繰り返し行われる。
【０１１５】
そして、ステップＳ２７で、セグメント接続コントローラにより上記いずれかの判断がなされると（ステップＳ２７，Ｙｅｓ）、クルー・ペアリングモデル計算部２２ｂは、それまでに得られた解（最良の解等）をクルー・ペアリング・エディタ１１に出力する（ステップＳ２８）。
【０１１６】
図１１及び図１２は、ステップＳ２３で作成される接続テーブルのデータ構造を示す図である。
図１１は、接続テーブルの全体構成を示す図である。
【０１１７】
同図に示すように、接続テーブル５０は、「対象の便情報５０ａ」、「同一機材の次接続の便情報５０ｂ」、「当日乗換便情報５０ｃ」、「当日デッドヘッド情報５０ｄ」、「翌日の乗務便情報５０ｅ」、「翌日乗換便情報５０ｆ」、「翌日デッドヘッド情報５０ｇ」、「セグメント接続テーブル５０ｈ」、「基地空港からの出発情報５０ｉ」、及び「基地空港への到着情報５０ｊ」から成る。
【０１１８】
図１２は、上記情報５０ａ〜５０ｊの内、セグメント接続テーブル５０ｈ以外の情報のデータ構造を示す図である。
同図に示すように、これらの情報は、「便名６０ａ」、「機材番号６０ｂ」、「出発空港６０ｃ」、「出発時刻６０ｄ」、「到着空港６０ｅ」、「到着時刻６０ｆ」、「運航パターン６０ｇ」、及び「乗務時間６０ｈ」の各フィールドから構成されるレコード６０として、接続テーブル５０に格納される。運航パターン６０ｇは、例えば、一ヵ月の運航日程を示す３１ビットの２値のビット列で構成される。この場合、“１”が運航日を、“０”が非運航日を示す。
【０１１９】
図１３は、本実施形態の最適化部２２による解の生成処理（複数の乗務パターンの作成処理）の全体フローを説明する図である。尚、このフローチャートは、一つの染色体２−１（染色体４０）による解の生成処理を説明するフローチャートである。
【０１２０】
まず、染色体４０の遺伝子４３の各シップラインのセグメンテーション情報について、それぞれに対応するセグメンテーション確率テーブルを用いてデコードする（ステップＳ４１）。これにより、遺伝子４３に登録された各シップラインが、そのセグメンテーション情報に応じて、１または複数のセグメントに分割される。
【０１２１】
次に、ステップＳ４１で得られた各セグメントの先頭の便の遺伝子４１の値を参照し、上述した先頭の便のソート処理を行い、セグメントの割り付け順を設定する（ステップＳ４２）。すなわち、ソート順位の高い先頭便を有するセグメント程、割り付け順位を高く設定する。
【０１２２】
例えば、染色体４０の場合、遺伝子４２による各シップライン１(sl1) 〜３(sl3) のセグメント分割により、図６のシップライン１〜３が、図１４で破線で示すようにセグメント分割されたとする。すなわち、シップライン１がセグメントＳ１とＳ２に、シップライン２がセグメントＳ３とＳ４に、シップライン３がセグメントＳ５とＳ６に分割されたとする。この結果、遺伝子４１が参照されて、図１５に示すようなソート結果（ｆ１，ｆ３，ｆ７，ｆ５，ｆ１１，ｆ）が得られる。そして、最終的に、図１６に示すようにセグメントの割り付け順位（Ｓ１，Ｓ２，Ｓ４，Ｓ３，Ｓ６，Ｓ５）が設定される。
【０１２３】
続いて、セグメント接続を開始するにあたって、上記各セグメントの後尾の便の接続情報を処理する。この処理は、セグメントの先頭に位置していない接続（便）を除去する処理である（ステップＳ４３）。以上のようにして、有効な接続便が求まる。例えば、図７（ａ）に示すシップライン１が、セグメンテーションＳ１２で切断された場合、有効な接続便はｆ２とｆ４となる。
【０１２４】
次に、ステップＳ４３で得られた有効な接続便の全てに対して、個々に、セグメント接続確率テーブル（Segment 接続確率テーブル) を作成する（ステップＳ４４）。
【０１２５】
図１７は、上述したように、図７（ａ）にシップライン１が、セグメンテーションＳ１２で切断された場合における、有効な接続便ｆ２に関するセグメント接続確率テーブルの例を示す図である。
【０１２６】
同図に示す、ｆ２に関するセグメント接続確率テーブル７０は、ｆ３、ｆ５，ｆ９との接続確率、ｆ５→ｆ６，ｆ５→ｆ１０，ｆ９→ｆ６，及びｆ９→ｆ１０との接続確率を示している。この場合、ｆ３は、当日デッドヘッド後に当日乗務は行わない接続である（接続確率は、０．２０）。また、ｆ３及びｆ５は、翌日乗務の接続である（接続確率は、それぞれ、０．３０，０．２０）。また、さらに、ｆ５→ｆ６，ｆ５→ｆ１０，ｆ９→ｆ６，及びｆ９→ｆ１０は、翌日デッドヘッド後に翌日乗務を行う接続である（接続確率は、それぞれ、０．１０，０．０５，０．０５，及び０．１０）。尚、このステップＳ４４のセグメント接続確率テーブルの作成は、プリプロセス処理で得られたセグメント接続確率テーブル５０ｈや既に作成されている乗務パターン等を基にして行われる，セグメント接続確率テーブルの再構成処理である。
【０１２７】
以上のようにして、ＧＡ実行部２２ａのデコード処理部３によるステップＳ４１〜Ｓ４４のデコード処理が行われる。
次に、クルー・ペアリングモデル計算部２２ｂによる解の生成処理が開始される。
【０１２８】
この場合、まず、クルー・ペアリングモデル計算部２２ｂ内部に設けられたセグメント接続コントローラ（不図示）が、ステップＳ４２で得られたセグメントの割り付け順位結果に従って、先頭のセグメントを取り出し、このセグメントを先頭とする乗務パターンの作成を開始する。また、セグメント接続コントローラは、以下に示す判断基準にしたがって、ステップＳ４６〜４８の３つのステップＳのいすれかの処理を実行する。
【０１２９】
▲１▼  もし、通月（regular)のセグメントが期割れになったらステップＳ４６  で局所探索によりセグメント（Segment)を繋ぐ。
▲２▼  現在、処理対象のセグメントの遺伝子４３に、まだ、未使用で、かつ、まだ乗務パターンに組み込まれていない接続候補便情報があれば、ステップＳ４７で、その接続候補便情報に従って、セグメントを繋ぐ。
【０１３０】
▲３▼  現在、処理対象のセグメントの遺伝子４３で使用可能な接続候補便情報が無くなれば、ステップＳ４８で、ステップＳ４４で作成したセグメント接続確率テーブルを用いて、セグメントを繋ぐ。
【０１３１】
セグメント接続確率テーブルは、▲１▼〜▲３▼の順に、順に判断して、実行すべきステップを決定する。
ステップＳ４６では、局所探索手法器４−２が未接続のセグメントの中から、現時点の乗務パターンの後尾の便に接続するのに最適なセグメントを、局所探索により探索し、そのセグメントを、該乗務パターンの最後尾の便に繋げる。
【０１３２】
ステップＳ４７では、ＧＡ探索器４−３が、現在までに作成されている乗務パターンの最後尾の便の遺伝子４３の接続候補リストに従って、該最後尾の便に接続すべきセグメントを決定する。
【０１３３】
ステップＳ４８では、確率的探索器４−４がステップＳ４４で作成されたセグメント接続確率テーブルに従って、現在までに作成されている乗務パターンの最後尾の便に接続すべきセグメントを決定する。尚、このとき使用されるセグメント接続確率テーブルは、該最後尾の便のセグメント接続確率テーブルである。
【０１３４】
上記ステップＳ４６〜Ｓ４８のいずれかのステップの処理によって、セグメントの新たな接続が行われると、制約違反判定器４−５によって、そのセグメントの接続が制約違反器かどうかが判断される（ステップＳ４９）。
【０１３５】
そして、制約違反であれば、制約違反処理器４−６がステップＳ４６、Ｓ４７，またはＳ４８で繋いだセグメントを、現在の乗務パターンから取り除き（ステップＳ５０）、ステップＳ４５に戻る。
【０１３６】
一方、ステップＳ４９で制約違反でないと判断されれば、乗務パターン（Crew Pattern) が完成したか判断する（ステップＳ５１）。
乗務パターンの完成条件とは、例えば、以下のようなものである。
【０１３７】
▲１▼  ステップＳ４７の遺伝子４３のデコードで“−１”（強制終了）がデコードされたとき。
▲２▼  乗務パターンの終端の便で、当日に、基地空港に帰還可能である確率が９５％である。
【０１３８】
ステップＳ５１で、乗務パターンが完成していないと判断した場合は、ステップＳ４５に戻り、次のセグメントの接続処理に進む。
一方、ステップＳ５１で、乗務パターンが完成したと判断すれば、該乗務パターンを解の一部として登録する等の終端処理を行い、次の乗務パターンの作成処理に移行するために、ステップＳ４５に戻る。
【０１３９】
以上のようにして、ステップＳ４５〜Ｓ５２のループ処理が繰り返されることにより、次々に複数の乗務パターンが作成され、解が作成されていく。そして、ステップＳ４５で、セグメント接続コントローラは、処理の終了を判断すると、それまでに得られた解を解・適応度算出器４−７に出力し、処理の実行権を解・適応度算出器４−７に委譲する。
【０１４０】
解・適応度算出器４−７は、セグメント接続確率テーブルから受け取った解の適応度を算出し（ステップＳ５１）、今回の処理で使用した染色体２−１（染色体４０）の解２−２と適応度２−３を染色体集団２に出力し（ステップＳ５２）、処理を終了する。
【０１４１】
図１８〜図２２は、図１３のフローチャートの処理の実行による乗務パターン作成（解２−２の作成）の手順を具体的に説明する図である。
以下の説明では、図１８に示すシップライン(Ship line) １〜３について乗務パターンを作成する例について説明する。尚、図１８は、上述した図６に示すシップライン１〜３と同一なので、ここでは、各シップラインの構成などの詳しい説明は省略する。
【０１４２】
まず、全てのシップライン１〜３が、染色体４０の遺伝子４２のデコードにより、それぞれに対応する図７（ａ）〜（ｃ）に示すセグメンテーション確率テーブル３０ａ〜３０ｃを参照して、図１９に示すようにセグメント分割されたとする。すなわち、シップライン１は、便ｆ１と便ｆ２を接続するセグメントＳ１と、便ｆ３と便ｆ４を接続するセグメントＳ２に分割されたとする。同様にして、図１９に示すように、シップライン２は、便ｆ５と便ｆ６を接続するセグメントＳ３と、便ｆ７と便ｆ８を接続するセグメントＳ４に分割され、シップライン３は、便ｆ９と便ｆ１０を接続するセグメントＳ５と、便ｆ１１と便ｆ１２を接続するセグメントＳ６に分割されたとする。
【０１４３】
次に、遺伝子４１のデコードの結果により、セグメント接続コントローラにより、セグメントＳ１を先頭とする乗務パターンの作成が開始される（図１６参照）。図９では図示していないが、セグメントＳ１の後尾の便ｆ２の遺伝子４３（４３−２）に最初の接続候補便として、セグメントＳ５の先頭の便ｆ９が指定されていたとする。これにより、セグメントＳ１とセグメントＳ５を図２１の実線の矢印１のように接続する（ステップＳ４７）。このセグメント接続が制約違反でないとすると、セグメントＳ５は基準空港（ＨＮＤ）に到着する便ｆ１０が終端の便となっているので、まず、第１の乗務パターン（Ｓ１→Ｓ５）の作成が終了する。この結果、セグメントＳ５は奇数日の期割れ（０１０１０１０１０１）なので、セグメントＳ１の残りの運航は偶数日の期割れとなる。
【０１４４】
次に、上記期割れにより、局所探索手法器４−２により局所探索が開始され、セグメントＳ１の接続先として、偶数日の期割れとなっているセグメントＳ３が見つけ出されたとする（ステップＳ４６）。これにより、セグメントＳ１とセグメントＳ３を図２１の破線の矢印２のように接続する。このセグメント接続が制約違反でないとすると、セグメントＳ３は基準空港（ＨＮＤ）に到着する便ｆ６が終端の便となっているので、図２０の破線の矢印２に示すような第２の乗務パターン（Ｓ１→Ｓ３）が作成される。
【０１４５】
以上の処理により、セグメントＳ１の運航日は全て、上記第１及び第２の乗務パターンに組み込まれたので、セグメントＳ１を先頭とする乗務パターンの作成処理は、終了する。
【０１４６】
次に、セグメント接続コントローラは、図１６に示すセグメント割り付け順に従って、セグメントＳ２を先頭とする乗務パターンの作成を開始させる。
すると、セグメントＳ２は基地空港（この場合、基地空港には、ＨＮＤ（羽田）だけが指定されているとする）からのデッドヘッドがないため、先頭とはなれず、次の先頭となるセグメントの検索処理に進む。
【０１４７】
この結果、図１６に示す割り付け順に従って、次の先頭セグメントはセグメントＳ４となる。この時点で、セグメントＳ４に接続可能な残りのセグメントはセグメントＳ２なので、図２１の実線の矢印３に示すように，セグメントＳ４とセグメントＳ２を図２１の実線の矢印３のように接続する（ステップＳ４６）。このセグメント接続が制約違反でないとすると、セグメントＳ２は基準空港（ＨＮＤ）に到着する便ｆ４が終端の便となっているので、図２１の実線の矢印３に示すような第３の乗務パターン（Ｓ４→Ｓ２）が作成される。
【０１４８】
この第３の乗務パターンの作成により、セグメントＳ２の残りの運航は偶数日に運航する期割れとなるので、セグメント接続コントローラにより、局所探索手法器４−２が起動され、局所探索により、期割れとなったセグメントＳ２を補完するセグメントが探索される。これにより、セグメントＳ２に接続するセグメントとして、セグメントＳ２と同様なパターンの偶数日に運航する期割れとなっているセグメント６が探索され、図２１の実線の矢印３に示すように，セグメントＳ２とセグメントＳ６を図２１の破線の矢印３のように接続する（ステップＳ４６）。このセグメント接続が制約違反でないとすると、セグメントＳ６は基準空港（ＨＮＤ）に到着する便ｆ１２が終端の便となっているので、図２１の破線の矢印４で示される第４の乗務パターン（Ｓ６→Ｓ２）が作成される。
【０１４９】
以上の処理により、セグメントＳ２の運航日は全て、上記第３及び第４の乗務パターンに組み込まれたので、セグメントＳ２を先頭とする乗務パターンの作成処理は、終了する。
【０１５０】
この結果、全てのセグメントＳ１〜Ｓ６の全ての運航日が、第１〜第４の乗務パターンに組み込まれたので、乗務パターン生成のプロセスは全て終了する。
尚、図１９〜図２０に示す例では、確率的探索器４−４が利用されていないが、局所探索手法器４−２及びＧＡ探索器４−３のいずれでも、適切なセグメントを探索できない場合には、セグメント接続コントローラにより確率的探索器４−４が起動され、確率的探索器４−４によりセグメント接続が実行される。
【０１５１】
尚、上記実施形態は、本発明を乗務パターン作成装置に適用した例であるが、本発明は、これに限定されることなく、制約充足最適化問題等を解く最適化装置全てに適用可能である。
【０１５２】
図２２は、本発明の実施形態を実現するコンピュータのハードウェア構成を示す図である。
同図において、ＣＰＵ１０１は、バス１０９を介して、ＲＯＭ１０２、ＲＡＭ１０３、外部記憶装置１０４、記録媒体駆動装置１０５、入出力装置１０７，及び通信インターフェース１０８と接続されている。
【０１５３】
ＣＰＵ１０１は、ＲＯＭ１０２に記憶されたプログラム及びＲＡＭ１０３にロードされたプログラムを実行することにより、上述した本実施形態の最適化装置の機能を実現する。外部記憶装置１０４は、ＲＡＭ１０３にロードされる上記プログラム、上記ファイル１３、１４等を記憶する。
【０１５４】
外部記憶装置１０４は、例えば、磁気ディスク装置、光磁気ディスク装置等である。記録媒体駆動装置１０５は、上記プログラムが記録された可搬記憶媒体１０６が装着される。可搬記憶媒体１０６に格納されているプログラムは、記録媒体駆動装置１０５により読み取られ、ＲＡＭ１０３上にロードされ、ＣＰＵ１０１により実行される。この実行により、上述した本実施形態の最適化装置の機能が実現される。
【０１５５】
通信インターフェース１０８は、ネットワーク２００を介して情報提供業者３００が保有する上記プログラムを、外部記憶装置１０４にダウンロードする。このようにしてダウンロードされたプログラムは、外部記憶装置１０４から読みだされてＲＡＭ１０３に展開されて、ＣＰＵ１０１により実行される。この実行により、上述した本実施形態の最適化装置の機能が実現される。
【０１５６】
また、上記プログラムを、情報提供業者３００が保有するコンピュータで遠隔実行させて、上述した本実施形態の最適化装置の機能を該コンピュータで実現されることも可能である。このような形態の場合、解は、通信インターフェース１０８を介して、コンピュータ１００に受信され、入出力装置１０７を介して出力されることになる。
【０１５７】
入出力装置１０７は、ユーザに、ＧＵＩ等を介して、外部記憶装置１０４等に格納されている制約条件エディタ１１、クルー・ペアリング・エディタ１２をＣＰＵ１０１に実行させる環境を提供する。そして、ユーザに、これらのエディタ１１、１２を利用して、ファイル１３、１４を作成・編集させる。また、入出力装置１０７は、上記プログラムの実行により得られた解等を出力（表示・印字等）する。
【０１５８】
可搬記憶媒体１０６は、磁気ディスク、光ディスク、光磁気ディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disc) ，ＰＣカード等である。
ネットワーク２００は、インターネット、イントラネット、エクストラネット、ＶＰＮ（Virtual Private Network)、公衆回線、専用回線、衛星回線、ＣＡＴＶ(CAble TeleVision)回線、ＬＡＮ，ＭＡＮ，ＷＡＮ等である。
【０１５９】
【発明の効果】
以上、説明したように、本発明によれば、以下のような効果が得られる。
１）  従来技術では全く扱うことができなかった、不定期な業務を含む長期間に渡るモデル（Fully Dated Model)での計画を処理することが可能になる。
２）  個々の処理に必要な前処理、後処理を、解生成の段階で問題モデルが自動的に付与するため、航空機の乗務パターンの作成に適用した場合、デッドヘッド（dead head ）等の取扱が一元的に可能になる。
３）  広範囲な探索空間を持つ問題を、効率的に探索可能になり、探索時間を大幅に減少させることが可能になる。また、ヒューリスティクス、確率的探索、ルールに基づく探索がバランス良く実現でき、制約条件が多い組み合わせ問題についても、質の良い解を短時間に導出できるようになる。。
４）  航空の乗務スケジュールの作成に適用した場合、従来、数年間の実務経験を積んだ専門家が、人手で一週間程度かけていたスケジュール作成を、半日程度で自動的に作成できるようになった。
【図面の簡単な説明】
【図１】本発明の原理構成図である。
【図２】本発明の原理を説明するフローチャートである。
【図３】本発明の実施形態の全体システム構成を示すブロック図である。
【図４】シップライン設定セットアップ処理を説明する図である。
【図５】本実施形態で使用する制約条件の事例を示す図である。
【図６】シップラインの具体例を示す図である。
【図７】図６の各シップラインのセグメンテーション確率テーブルの作成方法を説明する図である。
【図８】」図６のシップライン１の８種類のセグメンテーションを表現するデータ構造を示す図である。
【図９】本実施形態で使用する染色体のデータ構造の一例を示す図である。
【図１０】本実施形態の全体動作を説明するフローチャートである。
【図１１】プリプロセス処理で作成する接続テーブルのデータ構造を示す図である。
【図１２】図１２のセグメント接続確率テーブル以外のレコードのデータ構造を示す図である。
【図１３】本実施形態による、染色体を用いた解の生成処理を説明するフローチャートである。
【図１４】シップライン１〜３の一例を示す図である。
【図１５】図１５のシップライン１〜３について、図９の染色体をデコードすることにより得られるセグメントの先頭便のソート結果を示す図である。
【図１６】図１６のソート結果を基にして得られる、セグメントの割り付け順位を示す図である。
【図１７】図１３のフローチャートの染色体のデコード処理で生成される、有効な接続の便のセグメント接続確率テーブルのデータ構造の一例を示す図である。
【図１８】シップライン１〜３の具体例を示す図である。
【図１９】図９の染色体を、図７のセグメンテーション確率テーブルを利用してデコードした結果、得られる図１８のシップライン１〜３のセグメント分割結果を示す図である。
【図２０】図１９のセグメント分割結果に対して、図９の染色体のデコード結果と局所探索手法を適用して、第１及び第２の乗務パターンを作成する手順を説明する図である。
【図２１】図２０に示された処理の後に、図９の染色体のデコード結果と局所探索手法を適用して、第３及び第４の乗務パターンを作成する手順を説明する図である。
【図２２】本実施形態を実現するコンピュータのハードウェア構成の一例を示す図である。
【符号の説明】
１    ＧＡ処理部
１−１  適応度計算器
１−２  選択操作器
１−３  交叉操作器
１−４  突然変異操作器
２    染色体集団
２−１  染色体
２−２  解
２−３  適応度
３  デコード処理部
３−１  問題のパラメータ
４  問題モデル計算部
４−１  コントローラ
４−２  局所探索手法器
４−３  ＧＡ探索器
４−４  確率的探索器
４−５  制約違反判定器
４−６  制約違反処理器
４−７  解・適応度算出器
１０  ＧＵＩ（グラフィカル・ユーザ・インタフェース）装置
１１  制約条件エディタ
１２  クルー・ペアリング・エディタ
１３  制約条件等を格納するファイル
１４  便データを格納するファイル
２０  ＧＡクルー・ペアリング・最適化装置
２１  プリプロセッサ
２２  最適化部
２２ａ  ＧＡ実行部
２２ｂ  クルー・ペアリングモデル計算部
３０ａ  シップライン１用のセグメンテーション確率テーブル
３０ｂ  シップライン２用のセグメンテーション確率テーブル
３０ｃ  シップライン３用のセグメンテーション確率テーブル
４０  染色体
４１  各便１〜便１２の割り付け順序情報を格納する遺伝子
４２  セグメンテーション１〜３のセグメンテーション情報を格納している遺伝子
４３  便１〜便１２の接続候補リストを格納している遺伝子
５０  プリプロセス処理で作成される接続テーブルのデータ構造
５０ａ  対象の便情報
５０ｂ  同一機材の次接続便情報
５０ｃ  当日乗換便情報
５０ｄ  当日デッドヘッド情報
５０ｅ  翌日の乗務便情報
５０ｆ  翌日の乗換便情報
５０ｇ  翌日デッドヘッド情報
５０ｈ  セグメント接続確率テーブル
５０ｉ  基地空港からの出発情報
５０ｊ  基地空港への到着情報
６０  ５０ａ〜５０ｇ及び５０ｉ，５０ｊのデータ構造
７０  セグメント接続確率テーブル
１００  コンピュータ
１０１  ＣＰＵ
１０２  ＲＯＭ
１０３  ＲＡＭ
１０４  外部記憶装置
１０５  記録媒体駆動装置
１０６  可搬記録媒体
１０７  入出力装置
１０８  通信インターフェース
２００  ネットワーク
３００  情報提供業者
【図１】
0003862899.tif 000002
【図２】
0003862899.tif 000003
【図３】
0003862899.tif 000004
【図４】
0003862899.tif 000005
【図５】
0003862899.tif 000006
【図６】
0003862899.tif 000007
【図７】
0003862899.tif 000008
【図８】
0003862899.tif 000009
【図９】
0003862899.tif 000010
【図１０】
0003862899.tif 000011
【図１１】
0003862899.tif 000012
【図１２】
0003862899.tif 000013
【図１３】
0003862899.tif 000014
【図１４】
0003862899.tif 000015
【図１５】
0003862899.tif 000016
【図１６】
0003862899.tif 000017
【図１７】
0003862899.tif 000018
【図１８】
0003862899.tif 000019
【図１９】
0003862899.tif 000020
【図２０】
0003862899.tif 000021
【図２１】
0003862899.tif 000022
【図２２】
0003862899.tif 000023