(57)【要約】  航空会社の業務などの輸送業務をスケジュールするための方法である。本方法は望ましくは、出発地と目的地と到着又は出発の時刻とを指定する輸送に関する要求（１００）を選択し、航空機（５０８）、乗務員及び出発ゲートなどの利用可能な資源のデータベースから資源を選択する。この資源選択は望ましくは、要求に指定された特定の業務からの営業利益への寄与又は他の財務結果などの結果関数を最適化するように実行される。スケジュール断片（１０８）を開発すると、指定された資源が約束され、利用可能な資源のデータベースは関連時刻にこれらの資源がもはや利用可能でないことを示すように修正される（１１０）。それからシステムは、もう１つの要求を処理し、全スケジュールを開発するように本プロセスを繰り返す。本システムは、複雑な輸送業務に関しても短時間で、典型的には数分以内に実施可能なスケジュールを開発できる。スケジュールは、代替の戦略と仮定とを使用して開発され、互いに対してテストされることが可能である。【選択図】  図１
2009527857.tif 000002
【特許請求の範囲】
【請求項１】
輸送業務に関するスケジュールを生成する、コンピュータ実現の方法であって；
（ａ）  各要求が出発地と目的地と出発時刻又は到着時刻とに関連する、複数の出発地と複数の目的地との間の輸送に関する複数の要求の順序付けられたリストを提供するステップと、
（ｂ）  スケジュール断片を設定するステップが利用可能な資源の１つ以上のリストから資源を割り当てることを含む、前記順序付けリストにおける要求の１つを満足させるためのスケジュール断片を設定すること、
（ｃ）  ステップ（ｂ）における資源の使用に基づいて修正された状態を示すために利用可能な資源の前記１つ以上のリストを修正すること、及び
（ｄ）  ステップ（ｂ）及び（ｃ）が前記リスト内の前記要求の前記順序にしたがって前記複数の要求に関して実行されるように、かつ、各要求に関するステップ（ｂ）が次の前の要求に関するステップ（ｃ）の結果から得られる状態を使用して実行されるように、ステップ（ｂ）及び（ｃ）を繰り返すこと、
のためにコンピュータを使用するステップと、
を含む方法。
【請求項２】
１つの要求に関して１つのスケジュール断片を設定する前記ステップは、前記要求内の出発時刻に近接した時刻の範囲内で出発時刻を調整することを含む、請求項１に記載の方法。
【請求項３】
１つのスケジュール断片を設定する前記ステップは、出発時刻を前記要求に関する荷重に関係付ける情報に基づいて少なくとも１つの結果を決定することを含む、請求項２に記載の方法。
【請求項４】
前記時刻の範囲は、他の要求に関して前に決定されたスケジュール断片に少なくともある程度基づいて選択される、請求項２に記載の方法。
【請求項５】
スケジュール断片を設定する前記ステップは、前記スケジュール断片に関する結果関数が１つ以上の基準を満足させるように実行される、請求項１に記載の方法。
【請求項６】
前記１つ以上の基準は、前記スケジュール断片に関する前記結果関数の最大化又は最小化を含む、請求項５に記載の方法。
【請求項７】
前記結果関数は、前記スケジュール断片に関する１つ以上の財務値を含む、請求項５に記載の方法。
【請求項８】
前記スケジュールに関する総計財務値を導き出すために前記スケジュール断片に関する前記財務値を総計するステップを更に含む、請求項７に記載の方法。
【請求項９】
各要求は予測された負荷を含み、前記方法は市場行動の１つ以上の推定値に少なくともある程度基づいて前記要求に関する前記予測負荷を導き出すステップを更に含む、請求項７に記載の方法。
【請求項１０】
市場行動の前記１つ以上の推定値を調整し、市場行動の前記調整された推定値を使用する前述のステップを繰り返すステップを更に含む、請求項９に記載の方法。
【請求項１１】
市場行動の前記１つ以上の推定値を調整するステップは、輸送に関して課金される価格とこのような輸送において提供される価値とのうちの少なくとも１つの態様を調整するステップと、前記価格及び価値の前記少なくとも１つの態様と輸送に関する要求との間の推定された関係を適用するステップとを含む、請求項１０に記載の方法。
【請求項１２】
価格及び価値の前記少なくとも１つの態様は、輸送に関して顧客によって支払われるべき金額を含む、請求項１１に記載の方法。
【請求項１３】
価格及び価値の前記少なくとも１つの態様は、輸送の購入と引き換えに顧客に提供される付随サービスのレベルを含む、請求項１１に記載の方法。
【請求項１４】
資源を修正し、前記修正された資源を使用して前記要求の少なくとも一部に関して前述のステップを繰り返すステップを更に含む、請求項８に記載の方法。
【請求項１５】
資源の種々の集合によって達成された総計財務値を比較するステップを更に含む、請求項１４に記載の方法。
【請求項１６】
１つの要求に関して１つのスケジュール断片を設定するステップは、前記要求に関して結果関数を評価するステップと、前記結果関数が１つ以上の引き下げ基準を満たす場合に前記要求に関するサービスをスケジュールしないステップとを含む、請求項１に記載の方法。
【請求項１７】
前記１つ以上の引き下げ基準は、１つ以上の保持基準の欠如を含む、請求項１６に記載の方法。
【請求項１８】
順序付けされたリストを提供する前記ステップは、複数のソートキーを確立することと、前記複数のソートキーにしたがって前記要求を順序付けることとを含む、請求項１に記載の方法。
【請求項１９】
前記ソートキーは、ある特定の要求が単一の輸送機材によって首尾よくサービス提供されるべき一連の要求の１つであるかどうかを表す連続値を含む、請求項１８に記載の方法。
【請求項２０】
前記ソートキーは、前記要求に関する少なくとも１つの財務値を含む、請求項１８に記載の方法。
【請求項２１】
前記ソートキーは、出発時刻と到着時刻のうちの少なくとも１つを含む、請求項１８に記載の方法。
【請求項２２】
順序付けリストを提供する前記ステップは、要求間の１つ以上の連続関係に基づいて前記複数のソートキーにしたがって順序付けられた前記リストを修正するステップを更に含む、請求項１８に記載の方法。
【請求項２３】
前記要求又は前記ソートキーのうちの少なくとも一方を修正し、前述のステップを繰り返すステップを更に含む、請求項１８に記載の方法。
【請求項２４】
資源の前記リストは、特定の場所と時間において利用可能な資源のデータベースを含み、ある特定の要求に関するスケジュール断片を設定する前記ステップは、前記出発地において利用可能な前記資源から資源を差し引くステップを含む、請求項１に記載の方法。
【請求項２５】
ある特定の要求に関して１つのスケジュール断片を設定する前記ステップは、前記要求に関連する業務の期待される完了時刻に続く時間の間、前記要求に関連する目的地において利用可能な資源の前記データベースに移動資源を追加するステップを更に含む、請求項２４に記載の方法。
【請求項２６】
前記要求に関連する所望の出発時刻に関して前記要求に関連する出発地において利用可能な資源が前記要求に関連する業務を可能にするために不十分であるかどうかを決定し、そのようであれば移動資源がもう１つの場所に存在して前記所望の出発時刻での業務のために時間内に出発地に再配置され得るかどうかを前記データベースから決定するステップを更に含む、請求項２４に記載の方法。
【請求項２７】
移動資源が前記所望の出発時刻による業務のために前記出発地に時間内に再配置され得ない場合に、すべての資源が利用可能にされ得るときに、前記所望の出発時刻後の実行可能な最も早い出発時刻を決定して、出発時刻を前記実行可能な最も早い出発時刻に設定するステップを更に含む、請求項２６に記載の方法。
【請求項２８】
実行可能な出発時刻の範囲内の実行可能な最も速い出発時刻が発見され得ない場合に、ある特定の資源の利用不可能性が、ある特定の要求に関するスケジュール断片を設定することを除外することを示すエラーメッセージを返すステップを更に含む、請求項２７に記載の方法。
【請求項２９】
どの資源が前記輸送システムの業務を制約しているかを示す複数の前記エラーメッセージから情報を蓄積するステップを更に含む、請求項２８に記載の方法。
【請求項３０】
前記蓄積された情報に応じて前記資源を調整し、前記要求の少なくとも一部に関して前記調整された資源を使用して前述のステップを繰り返すステップを更に含む、請求項２９に記載の方法。
【請求項３１】
前記移動資源は、輸送機材を含む、請求項２５に記載の方法。
【請求項３２】
前記移動資源は、乗務員を含む、請求項２８に記載の方法。
【請求項３３】
１つのスケジュールを形成するために前記スケジュール断片をコンパイルするステップと、前記スケジュールにしたがって前記輸送システムを運用するステップとを更に含む、請求項１に記載の方法。
【請求項３４】
前記輸送システムは、航空会社である、請求項３３に記載の方法。
【請求項３５】
輸送業務に関するスケジュールを生成する、コンピュータ実現の方法であって、
（ａ）  各要求が出発地と目的地と出発時刻及び到着時刻のうちの少なくとも１つとに関連する、複数の出発地と複数の目的地との間の輸送に関する複数の要求のリストと、複数の輸送機材と各輸送機材の場所対時間を指定する情報とを含む資源のリストとを提供するステップと、
（ｂ）  前記資源のリストにおいて識別される前記複数の輸送機材から１つの輸送機材を選択すること；
（ｃ）  前記要求の前記リストから前記要求の１つを選択し、前記選択された輸送機材を前記選択された要求に割り当てることによって前記選択された要求を満足させるためのスケジュール断片を設定すること、
（ｄ）  ステップ（ｃ）における輸送機材の使用及び要求に基づいて修正された状態を示すために前記資源のリストと要求のリストとを修正すること、及び
（ｅ）  ステップ（ｂ）〜（ｄ）が前記複数の要求に関して実行されるように、また各繰り返しのためのステップ（ｃ）が次の前の繰り返しに関するステップ（ｄ）の結果から生じる状態を使用して実行されるように、ステップ（ｂ）〜（ｄ）を繰り返すこと、
のためにコンピュータを使用するステップと、
を含む方法。
【請求項３６】
前記要求の１つを選択するステップは、この要求を満足させるために前記選択された輸送機材の使用に基づいて１セットの要求のうちの各要求に関して結果関数を評価することを含む、請求項３５に記載の方法。
【請求項３７】
前記１セットの要求のうちの各要求に関して結果関数を評価するステップは、前記選択された輸送機材の利用可能な時間に少なくともある程度基づいて前記要求内の出発時刻に近接する時刻の範囲内で出発時刻を調整することを含み、かつ、結果関数を評価するステップは、前記要求に関してロードすべき出発時刻に関する情報に少なくともある程度基づいている、請求項３６に記載の方法。
【請求項３８】
要求を選択するステップは、最善の結果関数をもたらす集合から前記要求を選択するステップを含む、請求項３６に記載の方法。
【請求項３９】
前記結果関数は、１つ以上の財務値を含む、請求項３６に記載の方法。
【請求項４０】
前記スケジュールに関する総計財務値を導き出すために前記スケジュールに関して前記財務値を総計するステップを更に含む、請求項３９に記載の方法。
【請求項４１】
各要求は、予測された負荷を含み、前記方法は、市場行動の１つ以上の推定値に少なくともある程度基づいて前記要求に関する前記予測負荷を導き出すステップを更に含む、請求項３９に記載の方法。
【請求項４２】
市場行動の前記１つ以上の推定値を調整し、市場行動の前記調整された推定値を使用して前述のステップを繰り返すステップを更に含む、請求項４１に記載の方法。
【請求項４３】
市場行動の前記１つ以上の推定値を調整するステップは、輸送に関して課金される価格とこのような輸送において提供される価値とのうちの少なくとも１つの態様を調整するステップと、前記価格及び価値のうちの前記少なくとも１つの態様と輸送に関する要求との間の推定された関係を適用するステップとを含む、請求項４２に記載の方法。
【請求項４４】
（ａ）  輸送業務において提供されるサービスを少なくともある程度定義する入力情報を受信するように動作可能な少なくとも１つの入力ノードと、
（ｂ）  前記入力ノードによって受信された入力情報がコンピュータに供給されるように前記少なくとも１つの入力ノードに接続されたコンピュータであって、
（１）  各要求が、ある特定の出発地とある特定の目的地と前記特定の出発地からの出発時刻及び前記特定の目的地への到着時刻のうちの少なくとも１つとを指定する、複数の出発地と複数の目的地との間の輸送に関する複数の要求の順序付けられたリストを保守することと、
（２）  スケジュール断片を設定するステップが利用可能な資源の１つ以上のリストから資源を割り当てることを含み、スケジュール断片を設定する前記ステップが、前記スケジュール断片に関する結果関数が１つ以上の基準を満たすように実行される、前記順序付けリスト内の前記要求の１つを満たすためのスケジュール断片を設定することと、
（３）  ステップ（２）における資源の使用に基づいて修正された状態を示すように利用可能な資源の前記１つ以上のリストを修正することと、
（４）  ステップ（２）及び（３）が前記リスト内の前記要求の順序にしたがって前記複数の要求に関して実行されるように、また各要求に関するステップ（２）が次の前の要求に関してステップ（３）の結果から生じる状態を使用して実行されるように、ステップ（２）及び（３）を繰り返すことと、
のために前記入力情報に応答して動作可能であるコンピュータと、
（ｃ）  スケジュール断片に割り当てられた前記資源の少なくとも一部を表す出力情報が少なくとも１つの出力ノードに供給されるように前記コンピュータに接続された少なくとも１つの出力ノードと、
を備える輸送業務のためのスケジューリングシステム。
【請求項４５】
前記コンピュータは電子通信ネットワークを介して少なくとも１つの出力ノードと前記少なくとも１つの入力ノードとに接続される、請求項４４に記載のシステム。
【請求項４６】
ａ）輸送業務において提供されるサービスを少なくともある程度定義する入力情報を受信するように動作可能な少なくとも１つの入力ノードと；
ｂ）前記入力ノードによって受信された入力情報がコンピュータに供給されるように前記少なくとも１つの入力ノードに接続されたコンピュータであって、
（１）各要求が出発地と目的地と出発時刻又は到着時刻とに関連する複数の出発地と複数の目的地との間の輸送に関する複数の要求のリストと、複数の輸送機材を含む資源及び各輸送機材の場所対時間を指定する情報の１つ以上のリストとを維持することと；
（２）前記輸送機材リスト内で識別される前記１つ以上の輸送機材から１つの輸送機材を選択することと；
（３）前記要求の前記リストから前記要求の１つを選択して、前記選択された輸送機材を前記選択された要求に割り当てることによって前記選択された要求を満足させるためのスケジュール断片を設定することと；
（４）ステップ（３）における輸送機材の使用と要求とに基づいて修正された状態を示すように輸送機材の前記１つ以上のリストと要求のリストとを修正することと；
（５）ステップ（２）〜（４）が前記複数の要求に関して実行されるように、また各繰り返しに関するステップ（３）が前の繰り返しに関してステップ（４）の結果から生じる状態を使用して実行されるように、ステップ（２）〜（４）を繰り返すこととのために前記入力情報に応答して動作可能であるコンピュータと
を備える輸送業務のためのスケジューリングシステム。
【請求項４７】
前記コンピュータは電子通信ネットワークを介して少なくとも１つの出力ノードと前記少なくとも１つの入力ノードとに接続される、請求項４４に記載のシステム。
【請求項４８】
ａ）複数の輸送機材と；
ｂ）複数のターミナル場所と；
ｃ）輸送業務において提供されるサービスを少なくともある程度定義する入力情報を受信するように動作可能な少なくとも１つの入力ノードと；
ｄ）前記入力ノードによって受信された入力情報が請求項１又は請求項３６に記載のプロセスを実行するために前記入力情報に応じて動作可能であるコンピュータに供給されるように、前記少なくとも１つの入力ノードに接続されたコンピュータと；
ｅ）前記プロセスによってスケジュール断片に割り当てられた資源を表す出力情報が少なくとも１つの出力ノードに供給されるように、前記ターミナル場所の１つ以上に配置され、前記コンピュータに接続された少なくとも１つの出力ノードと
を備える輸送システム。
【請求項４９】
前記輸送機材は飛行機を含み、前記ターミナル場所は空港を含む、請求項４６に記載の輸送システム。
【請求項５０】
請求項１又は請求項３６に記載の方法をコンピュータに実行させるように動作するプログラムを記憶しているコンピュータ可読媒体を備えるコンピュータのためのプログラミング要素。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願への相互参照］
本出願は、これらの開示が参照により本明細書に組み込まれる、２００６年２月２１日に出願された米国仮特許出願第６０／７７４，６２３号と、２００６年３月３日に出願された第６０／７９７，４１３号と、２００７年１月１１日に出願された第６０／８７９，８３１号との出願日の恩典を主張する。
【０００２】
［発明の分野］
本出願は、輸送業務をスケジュールするための方法及びシステムに関する。
【背景技術】
【０００３】
航空会社のような輸送会社は、スケジュールを設定する際に困難な問題に直面する。どの輸送機材（vehicle）と乗務員が特定の時間に特定の航行を行うべきかを指定するスケジュールは、業務で使用される輸送機材の利用可能性と輸送機材を運用する乗務員ならびに空港ゲートなどの固定された資源の利用可能性を考慮しなくてはならない。これらの資源の各々は典型的には、航空機の保守のための時間を取っておく必要性、異なるパイロットの異なる資格要件、及び政府規制又は労働組合協定によって設定された乗務員の勤務時間制限などの要因を考慮した規則の複雑な集合によって統制される。
【０００４】
スケジューリングシステムは、特定の空港間で特定の時間に飛行すべきフライトのリストなどの運用業務のリストから開始して、すべての業務に利用可能な適当な航空機を有するスケジュールを見出そうと試み、それから必要な乗務員をスケジュールしようと試みるなどを行い得る。実際のスケジュールを設定するプロセスは、一般に、どの時間にどのルートを飛行すべきかを決定するプロセスから切り離される。これは典型的には、資源の最適でない使用をもたらす。例えば典型的には、あるフライトの出発時刻の僅かな変更は航空会社が飛行機を別のフライトに使用することを可能にするかもしれないことを航空会社に認識させる可能性のあるフィードバックは存在しないので、飛行機は１時間当たり何千ドルというコストで時間を無駄にしている。
【０００５】
各フライトからの期待される収益などの財務変数と、利用可能な航空機などの資源によって賦課される制約との両方を考慮して航空会社又は他の輸送業者のための最適化されたスケジュールを導き出すことは望ましい。第１の考慮事項において、スケジュールにおける変数のすべてを処理して、最大の正味財務収益を与えるスケジュールを見出すために、従来のリニアプログラミング技法を適用することによって最適スケジュールを導き出すことができるように見えるかもしれない。しかしながら従来の数学的技法によって任意の規模の航空会社又は他の輸送会社のための最適スケジュールを決定することは不可能である。１日に２００フライトを提供する１００機の飛行機を有する航空会社に関して、フライト時間が固定されていると仮定して、異なる可能な乗務員配置を無視しても、第１日目に特定のフライトで特定の航空機を飛行させることに関して２０，０００の可能性が存在する。初日のフライトが異なる空港に航空機を配置換えするので、初日に関する各可能性は第２日目に関する２０，０００の可能性の異なる集合を生み出し、それによって２日間のスケジュールは（２０，０００）２あるいは４００，０００，０００の可能性を含み、３日間のスケジュールは（２０，０００）３あるいは８，０００，０００，０００，０００の可能性を含み、以下同様となる。１ヶ月間又は２ヶ月間の最適スケジュールを選択することは、本質的に無限数の可能性の分析を必要とし、最も強力なコンピュータの能力をも超えている。別の言い方をすれば、最適スケジュールを導き出すという問題は、計算負荷がスケジュールによって明確にされるべき航空機数、乗務員数及び他の要素の数と共に指数関数的に増加するような、「ＮＰ困難な（NP-hard）」と呼ばれる数学的問題のクラスに属する。
【０００６】
航空会社及び他の輸送会社のためのスケジューリングの問題に捧げられた大きな努力にもかかわらず、今までのところ、真に満足できるシステムは開発されていない。特に航空会社は最善の現在の技法を使用しても劣悪なスケジューリングの結果から生じる非効率による会社の収益のほぼ パーセントを浪費していることが推定される。したがって、本発明より前に、スケジューリングの改善に関する実質的に満たされていないニーズが存在してきた。
【発明の開示】
【０００７】
本発明の一態様は、輸送業務に関するスケジュールを生成するコンピュータ実現の方法を提供する。本発明の本態様による方法は望ましくは、各要求が出発地と目的地と出発時刻又は到着時刻とに関連する、複数の出発地と複数の目的地との間の輸送に関する複数の要求の順序付けられたリストを使用する。本方法は、望ましくは、この順序付けリストの中の要求の１つを満足させるようにスケジュール断片（スケジュールフラグメント；schedule fragment）を設定するためにコンピュータを使用する。スケジュール断片を設定するステップは、利用可能な資源の１つ以上のリストから資源を割り当てることを含む。例えば航空会社の場合、スケジュール断片を設定するステップは、最も一般的に、特定の航空機と乗務員と空港ゲートとを割り当てることを含む。本発明の本態様による方法は、望ましくは、スケジュール設定ステップにおいて資源の使用に基づいて修正された状態を示すために利用可能な資源の１つ以上のリストを修正することを含む。本方法は、また、最も好ましくは、スケジュール断片を設定するステップと利用可能な資源のリストを修正するステップとがリスト内の要求の順序にしたがって複数の要求に関して実行されるように、また各要求に関してスケジュール断片を設定するステップが次に前の要求に関する上記修正ステップの結果から生じる状態を使用して実行されるように、スケジュール断片を設定するステップと利用可能な資源のリストを修正するステップとを繰り返すステップを含む。
【０００８】
本発明のもう１つの態様は、輸送業務に関するスケジュールを生成する更なる方法を提供する。本発明の本態様による方法は、望ましくは、各要求が出発地と目的地と出発時刻又は到着時刻とに関連する、複数の出発地と複数の目的地との間の輸送に関する複数の要求のリストを使用し、また複数の輸送機材の識別情報と各輸送機材の場所対時間を指定する情報とを含む輸送機材の１つ以上のリストを使用する。本発明の本態様による方法は、望ましくは、輸送機材のリスト内で識別される１つ以上の輸送機材から１つの輸送機材を選択し、要求のリストから要求の１つを選択し、そして選択された要求に選択された輸送機材を割り当てることによって選択された要求を満足させるようにスケジュール断片を設定するためにコンピュータを使用する。ここで再び本方法は、望ましくは、スケジュール断片を設定するステップにおいて輸送機材の使用と要求とに基づいて修正された状態を示すために輸送機材の１つ以上のリストと要求のリストとを修正することを含む。本発明の本態様による方法は、望ましくは、選択ステップとスケジュール断片設定ステップとが複数の要求に関して実行されるように、またこれらのステップが次に前の繰り返しの修正ステップの結果から生じる状態を使用して各繰り返しに関して実行されるように、これらのステップを繰り返すことを含む。
【０００９】
更に以下に論じられるように、本発明のこれらの態様による方法の好ましい実施形態は、大きな航空会社などの複雑な輸送業務のためにでも現実的で有効なスケジュールを迅速に作り出すことができる。
【００１０】
本発明の更なる態様は、前に論じられたようなスケジューリング方法を実現するためのコンピュータシステムとコンピュータプログラミング要素とを提供し、またこのようなスケジューリング方法を使用する輸送システムを提供する。
【発明を実施するための最良の形態】
【００１１】
本発明の一実施形態によるプロセスは、図１に一般的な形で示されている。本プロセスは、１セットの要求ノード、すなわち将来の特定の日時に関連する輸送業務に関する１セットの要求を定式化することによって開始する。本明細書で論じられる例では、要求ノードは、乗客航空会社フライトに関する要求を表すが、他の輸送業務も同様に処理され得る。日付、出発時刻、出発地、目的地、及び各クラスにおいて期待される乗客数に加えて、各要求を定義するデータは、最も望ましくは、例えば、要求において指定された正確な時間に最善の可能性のある航空機を使用して要求を満足させる運用からの航空会社の営業利益への理想的寄与（「ＣＴＭ」）又は他の財務的結果；サービスの各クラスにおける１乗客当たりの期待収益；要求ノードによって示された業務がシステムにおいて他の業務にトラフィックルート指定するローカル線として機能するかどうかに関する指示；及び以下に論じられる他の要因などの要求を満足させることによって達成されるべき結果に関連する更なるデータを含む。このシステムは、任意の妥当な方式にしたがって定式化された要求ノードによって有用な結果を与えることができる。しかしながら以下において更に論じられる要求ノード定式化プロセスなどのプロセスにしたがって要求を定式化することは極めて望ましい。
【００１２】
プロセスの次のステージ１０２において、要求は本明細書では「トポロジー的」順序と呼ばれる順序に配置される。この順序は、要求がスケジューリング作業においてシステムによって処理される順序を定義する。順序付けステップは、主として、各ソートキーが要求ノードに関連するデータの１つ以上の要素に基づいている１つ以上のソートキーにしたがって要求をソートすることによって実行される。例えば、要求ノードは、ＣＴＭへの期待される寄与などの他の要因と共に、又は他の要因なしに出発日時別にソートされ得る。代替として、要求ノードの出発地及び目的地は、特定の都市間のフライトがこの順序においてより高く配置されるようにソートキーとして使用され得る。
【００１３】
一度要求がステップ１０２でこの順序に配置されると、本システムは想定された初期システム状態から開始する。このシステム状態は、輸送業務を実行するために必要とされる資源の利用可能性を定義するデータを含む。これらの資源は、輸送業務において使用される航空機又は他の輸送機材などの移動資源；及び乗務員ならびに例えば空港ゲートのような出発地点又は目的地点に関連する可能性のある固定された資源を含む。それからシステムは、ステップ１０２で割り当てられたトポロジー的順序付けにしたがって要求を順番に処理する。このようにしてステップ１０６でシステムは、順序付けリストの最上部の第１の要求を単に選択し、この特定の要求に関するスケジュール断片を計算するためにステップ１０８でこの要求を処理する。スケジュール断片を計算するプロセスは、実行可能な結果を、望ましくはシステムの状態を与えられた最善の達成可能な結果を作り出すなどの方法で要求を満足させることに対して加えられるべき資源の選択を含む。例えば、本システムは、特定のセグメントに関して最善のＣＴＭなどの最善の業務結果を生み出す特定の航空機と乗務員とを選択することを追求し得る。特定の業務に関するスケジュール断片の最適化は比較的単純な問題であり；所与の要求ノードに関する可能性の数がシステムにおいて利用可能な資源の数によって限定され、要求ノードの数と共に増大しないことは認められるべきである。スケジュール断片を計算するプロセスは、適応を含み得る。以下に論じられるように、本明細書で使用されるような用語「適応」は、選択又は最適化プロセスにおいて適用される初期の仮定の調整を指す。例えば、ある要求は乗客１５０名の容量で午後６時にクリーブランドを出発するフライトを指定し得るが、スケジュール断片を設定するプロセスは、僅かに遅い時刻に出発することによって、又はより小型の航空機によって、あるいはこれら両方によって達成され得る結果を分析することを含む。
【００１４】
一旦、システムが考慮中の特定の要求に適用されるべき資源の実現可能な、そして最も好ましくは最適の集合を選択したとき、資源は処理されている特定の要求に約束される。これは、ステップ１１０で新しいシステム状態を設定するという結果をもたらす。このようにしてどの時間にどの航空機が利用可能であるかのリストはステップ１０８で処理された要求に割り当てられた航空機がステップ１０８で考慮された日時にもはや利用可能であり得ないことを示すように修正される。同様にステップ１０８で処理された特定の要求に割り当てられた乗務員はもはや利用可能でなく、以下同様である。それからシステムはステップ１０６にサイクルバックし、そこでシステムは現在、リストの最上部にある次の要求を処理する。このようにして各サイクルでシステムは１つの要求を考慮し、この要求に関する資源の実現可能な集合、最も望ましくは資源の最適な集合を見出そうと試みる。本プロセスは、要求ノードのすべてがステップ１１２で処理されるまで続けられる。
【００１５】
上記のように、各要求に関するスケジュール断片の計算のときに、システムは、結果関数を、最も頻繁には要求ノードを満足させるために割り当てられた資源の集合に関連するＣＴＭなどの財務結果を評価する。本システムは、また、この結果をスケジュール断片に関して期待された結果として記録し、全体としてのスケジュールに関する総計ＣＴＭなどの総計した期待結果を与えるために前に計算された他のすべてのスケジュール断片に関連する結果と共にこの結果を総計する。輸送業務のこのステージにおけるＣＴＭなどの期待結果は、元の要求ノードの理想的ＣＴＭより正確である。スケジュール断片の計算後の期待結果は、利用可能な資源によって達成され得る結果を反映する。あるいくつかの場合には、本システムは、資源の実現可能な集合を見出すことができない可能性があり、その場合には要求が満たされないことを示す結果を返し得る。本システムは、また、これらの事例の経過を追う（把握する）こともできる。
【００１６】
システムがステップ１１２で最後の要求を処理したとき、本システムは、これらの要求のすべて、又は少なくとも利用可能な資源によって提供されることが可能であって、以下に論じられる他の基準によって除外されないサブセットを定義する全スケジュールを開発したことになる。完全なスケジュールを作り出すためにステップ１０６〜１１２を通した完全なサイクルにおいて実行されるべき計算の数は、限定され、スケジュールされるべき業務のサイズに伴って指数関数的に増加することはない。全体スケジュールを完成させるために必要とされる計算のすべては、本明細書で論じられる輸送業務を実行するようにプログラムされた従来のパソコン上で数分以内に実行され得る。スケジューリング作業は迅速に実行され得るので、スケジュールを開発する際に使用される仮定は変更されることが可能であって、スケジューリングプロセスは繰り返され得る。ステップ１１４で示されるように、コンピュータシステム又は手作業のオペレータは、例えば総計ＣＴＭ、満たされない要求の数などを評価することによってスケジューリング作業からの総計結果を観測して、スケジューリングプロセスを繰り返す決定を行うことができる。この決定は、スケジューリング作業のために利用可能とされた資源のレベル、例えば航空機又は乗務員の数を調整し、またステップ１０４で開始して全体の更なるスケジュールが完成されるまで続くスケジューリング作業を繰り返すためのステップ１１６における決定を含み得る。
【００１７】
スケジュールを迅速に計算することは実現可能であるので、このサイクルは、最も高いＣＴＭ又は最も少ない満たされない要求などの最善の結果を返す最適レベルの資源が見出されるまで何回でも繰り返されることが可能である。代替として、又は更に、システム又は手作業オペレータは、ステップ１００で要求を定式化する際に使用される仮定、又はトポロジー的順序付けステップ１０２において適用されたソーティング順序のいずれかを変更するようにシステムに命令できる。例えば、スケジューリングシステムは、種々の料金レベル、レベル又は付随サービス（例えばあるフライトに関連する手荷物制限又は食事サービス）又は競合企業に関する他の要因対既知情報をテストするためにゲーム理論を応用する収益予測モジュールと連携して使用され得る。ゲーム理論において適用される種々の仮定は、マーケットシェアの種々の推定値、したがって要求ノードにおける種々の期待乗客数と種々の１乗客当たり期待収益を生み出す。変更戦略ステップ１１８においてゲーム理論システム（図示せず）は、スケジューリングシステムを使用する航空会社によって課金される料金又は提供されるサービスとこれらの料金に対する競合企業の反応とに関して異なる仮定を試みるように命令され可能性があり、これは乗客荷重の異なる予測、したがってステップ１００における異なる要求という結果をもたらす。例えば異なる競合企業によってサービス提供されるルートに沿った異なるマーケットシェアなどの要求計算の種々の部分に、マーケットシェアの異なる推定値が適用され得る。トポロジー的順序付けステップ１０２において適用されるソートキーとソーティング順序もまた変えられ得る。したがって、航空会社によって使用される戦略のいかなる要素も本質的に変更され得る。ここで再び、スケジューリングシステムは輸送業務の数ヶ月間の完全なスケジュールを数分間で生成できるので、多数の戦略的仮定に関してスケジュールを計算することは実現可能であり、したがって最善の戦略的仮定を見出すことは実現可能である。
【００１８】
要求を定式化するためのプロセス（図１のステップ１００）は、図２〜９に更に詳細に示されている。本プロセスは、航空会社によってサービス提供されるべき都市にサービス提供するすべての輸送業者による航空券の販売を記述する前歴データをロードすることによって始まる。この乗客データは典型的には、その各々が個々の乗客による旅行を反映する乗客名記録又は「ＰＮＲ」の形で与えられる。各ＰＮＲは、典型的には、乗客の出発地と目的地；出発地と目的地との間の輸送のために支払われた価格；乗客を搬送した輸送業者によって定義されたサービスのクラスを反映する。ＰＮＲデータは、航空産業内で商業的に利用可能である。望ましくは前歴データの少なくとも１年分が使用される。
【００１９】
プロセスの次のステージ１５２で本システムは、出発地と目的地の都市の各ペアに関する前歴データをコンパイルする。本システムは、処理される期間中の日の異なる集合に関して別々のコンパイルを行い得る。例えば、本システムは、すべての平日に関して各出発地と目的地とに関する１セットのデータ；あるいは代替として問題の前歴期間中のすべての月曜日に関する１セットのデータ、同じ期間中のすべての火曜日に関する別の１セットのデータなどをコンパイルし得る。各前歴期間は、望ましくは、異なる月などの異なる期間に関してコンパイルされたデータの集合が季節的変化のパターンを検出するために互いに比較され得るように、例えば１ヶ月というように丸１年より短い。また異なる前歴期間に関してコンパイルされたデータの集合は、特定の出発地都市と目的地都市との間の旅行における成長傾向を検出するために互いに比較され得る。例えば１年より長い期間のデータ量が利用可能であれば、最近年の２月の平日に特定の出発地都市と目的地都市との間で搬送された乗客の数は年間成長の推定値を導き出すために前年の２月中の比較し得る数と比較され得る。前歴期間中の日にちの各集合に関するコンパイルは、問題の前歴期間中の各都市にサービス提供する種々の輸送業者によって提供されるサービスの各クラスにおいて各特定の出発時刻に出発する乗客の数に関するデータを含み、また各このようなサービスクラスのために乗客によって支払われた平均料金に関するデータも含む。
【００２０】
出発時刻データは、問題の前歴期間中の出発地と目的地とにサービス提供する航空会社によって提供されるスケジュールによる乗客行動を反映する。このデータは、図３にグラフで描かれている。例えばバー１５４は午前８時３０分に出発する航空会社Ａのフライトに乗ってエコノミークラスで旅行する乗客の数を表すが、バー１５６は航空会社Ａの同じフライトのファーストクラスで搬送される乗客の平均数を表し、これに対してバー１５８は午前８時４５分に出発する航空会社Ｂのシングルクラスフライトで搬送される乗客の平均数を表す。
【００２１】
本プロセスの更なるステップ１６０において、前歴情報は、本明細書でウィンドウと呼ばれる定義された時間間隔中に、例えば１日のうちの特定の１時間又は２時間ウィンドウ中に、出発する乗客を一まとめにすることによって要約され、また種々の航空会社によって提供されるサービスのクラスはスケジュールされた航空会社によって提供されるべきサービスの最も近く比較し得るクラスに写像される。このようにしてシステムは、各ウィンドウに関してスケジュールされた航空会社の各クラスに関する前歴都市ペア人口統計を形成する。例えば図４にグラフで示されるように、バー１６２は、平均的平日に特定の目的地に向かって特定の出発地を出発し、スケジュールされた輸送業者のエコノミークラスにほぼ対応するすべての輸送業者のサービスのクラスのチケットを購入した乗客の平均数を表す。同様に、バー１６４は、平均的平日に同じウィンドウ中のファーストクラスの乗客の平均数を表す。説明の明確さのためにコンパイルプロセス１５２と要約プロセス１６０は別々のプロセスとして示されているが、これらのプロセスはオーバーラップしてもよい。例えば、各ＰＮＲ記録が分析されながら、サービスのクラスは実際に使用された輸送業者のサービスのクラスからスケジュールされた輸送業者のサービスの平均的クラスに変換され得る。
【００２２】
実際に各ウィンドウは、１日のうちの他のウィンドウによって表されるマーケットとはある程度異なる潜在的乗客のマーケットを表す。これらのウィンドウのサイズは、都市ペアにサービス提供するフライトの数などの要因に依存して手動又は自動選択によって異なる都市ペアに関して変化し得る。例えば、２つの都市が１日当たり単に２便のフライトだけで結ばれている場合には、ウィンドウサイズは１２時間であり得る；都市が１日当たり数十便のフライトによって結ばれている場合（例えばニューヨーク・シカゴ間）、ウィンドウサイズは１時間より短い可能性がある。
【００２３】
本システムは、要約プロセスで使用されるウィンドウ内の任意の出発時刻を、例えばウィンドウの中心を割り当てることができる。より好ましくは、システムは、人口統計に組み込まれた前歴出発時刻に基づいて人口統計に含まれた乗客の平均出発時刻を計算し、この平均時刻を都市ペア人口統計の出発時刻として割り当てる。本システムは、また、人口統計における時刻分散の大きさ、すなわちウィンドウ内の時刻と乗客数との間の関係の程度を取得することもできる。
【００２４】
本システムは、また、スケジュールされた輸送業者によって提供されるべきサービスのクラスに関して平均的前歴料金を計算する。このようにして、各乗客名記録に関する旅行のクラスはスケジュールされた輸送業者の比較可能なクラスに一致するので、問題の乗客によって支払われた前歴料金は、同じ乗客がスケジュールされた輸送業者の比較し得るクラスでの旅行のために支払った料金と見なされる。これらの料金は、クラスとウィンドウとに関連する平均的前歴料金を与えるために人口統計に含まれる乗客のすべてについて平均される。
【００２５】
このようにして、コンパイル及び要約プロセスの終わりでシステムは、出発地都市と目的地都市の各ペアに関する１セットの前歴都市ペア人口統計を有する。このような各前歴都市ペア人口統計は、スケジュールされた輸送業者のサービスの各クラスに関する出発時刻、乗客数及び平均料金を含み、また出発時刻の分散の大きさなどの更なるデータを含み得る。
【００２６】
それからこれらの前歴都市ペア人口統計は、本プロセスの更なるステップ１６８で予測都市ペア人口統計に変換される。前に論じられたように各都市ペアに関する前歴人口統計は、すべての輸送業者によって搬送された乗客を表す。各前歴都市ペア人口統計における乗客数は、この人口統計によって表される特定のマーケットにおいてスケジュールされた航空会社に関する予測マーケットシェアと乗算される。例えば、６００名のエコノミークラス乗客と１００名のファーストクラス乗客とが平均的平日に午後６時と午後８時との間にシアトルからニューヨークに向かって出発することと、スケジュールされた輸送業者によって達成された予測マーケットシェアが２０％であることとを前歴都市ペア人口統計が示すならば、この予測された都市ペア人口統計は、この航空会社が１２０名のエコノミークラス乗客と２０名のファーストクラス乗客とを期待し得ることを示す。同様に出発地都市と目的地都市との間の交通量の年々の増加（又は減少）を考慮するために成長係数が適用され得る。更に、航空会社が実現するサービスの各クラスに関する予測平均料金は、各予測都市ペア人口統計に含まれる。平均料金の関数としてのマーケットシェアの予測は、直感的に行われ得るが、好ましくはマーケットにおける競合企業の行動を明らかにするゲーム理論などの技法を応用することによって行われる。代替としてマーケットにサービス提供する航空会社のどれもその価格戦略を変更しないという仮定に基づいて、前歴マーケットシェア及び前歴料金データが使用され得る。
【００２７】
ステップ１６８の結果から得られる予測都市ペア人口統計は、要求ノードに、すなわち図５に概要が示されているプロセスによってスケジュールされた航空会社によってサービス提供されるルートに沿った出発地と目的地との間の輸送に関する個別の要求に変換される。本プロセスの第１のステップ１８０で各都市ペア人口統計は、図６に更に詳細に示されたステップによってルート人口統計に変換される。図６のプロセスは、どの都市ペアが都市間の直接ノンストップフライトによってサービス提供されるかを航空会社が決定していることを、したがって航空会社が直接結ばれる都市のリストを有することを仮定している。直接結ばれる都市の各ペアは、本明細書では「ルート」と呼ばれる。本システムは都市ペア人口統計を取得し、それから各都市ペア人口統計を順番に処理する。ステップ１８５でシステムは、都市ペア人口統計の出発地都市を目的地都市に接続する利用可能なルートのすべてを通して最短経路を選択する。例えば本システムは、都市ペア人口統計の出発地都市にルートの出発地を有するルートのすべてを分析して、これらのルートのうちのいずれかがこの都市ペア人口統計の目的地都市にルートの目的地を有するかどうかを決定し得る。そのようであれば、このルートは直接的ノンストップルートであり、したがって最短である。そのようでなければ、本システムは都市ペア人口統計の出発地都市にルートの出発地を有する各ルートの目的地都市を分析して、これらのルートの目的地都市を構成する１セットの都市を選択し得る。それからシステムは、今度はこのような各目的地を考慮して、このような目的地都市にルートの出発地を有し、都市ペア人口統計の目的地にルートの目的地を有するルートが存在するかどうかを調べる。そのようであればシステムは、２つのルートの総計距離組合せを記録し、２つのルートのすべてのこのような組合せが見出されるまでこのような分析を続ける。それからシステムは、２つのルートの利用可能な組合せを考慮して、最も短い全体距離を有する組合せを選択する。２ルート組合せが見出されなければ、本システムはまったく同様な方法で３ルート組合せを探索し得る。
【００２８】
このアプローチの変形形態ではシステムは、直接的単一ルート経路が存在しなければシステムがハブ都市を通過するフライトを使用して２ルート及び３ルート経路を構築することを求めるように、あるいくつかの都市をハブ都市として処理し得る。これは２ルート及び３ルート経路の形成において考慮されるべき可能性の数を大幅に削減する。
【００２９】
更なる変形形態ではシステムは、出発地都市又はハブ都市から間違った方向に走るルートを、すなわちルートの目的地都市がルートの出発地都市よりも都市ペア人口統計の目的地都市から遠いルートを除外し得る。これは更に、２ルート及び３ルート経路を発見する際に考慮されるべきルートの数を制限する。本プロセスで考慮される各ルートの距離はこれらの都市間の実際の地理的マイレージであり得るか、地理的マイレージと特定の空港における着陸料又は混雑などの他の要因とに基づいたスコアであり得る。
【００３０】
一度システムが特定の都市ペア人口統計に関して最短ルート経路を発見すると、本システムはステップ１８７でこの最短経路における各ルートに関してルート人口統計を作り出す。最短ルートが偶然に単一ルート経路すなわち直接ノンストップルートであったとすれば、このルート人口統計は元の都市ペア人口統計と同じである。しかしながらこの経路がマルチルート経路であれば、本システムは、第１のルートの目的地として目的地を有し、都市ペア人口統計の出発時刻として出発時刻を有する都市ペア人口統計の出発地都市にルートの出発地を有する第１のルート人口統計を構築する。第１のルート人口統計に関する１乗客あたりの期待収益は、１乗客あたりの期待収益の一部分である。期待収益の配分はルート長に基づいて行われ得る、すなわち第１のルートに関する期待収益は経路内のすべてのルートの全長で除算されて、第１のルート自身の長さを乗算された都市ペア人口統計に関する期待収益であり得る。本システムは、また、経路内の第２のルートに関するルート人口統計を作り出す。このルート人口統計は、第１のルートの目的地都市としてルートの出発地都市を有し、第２のルートの目的地都市としてルートの目的地都市を有し、都市ペア人口統計の出発時刻に等しいルートの出発時刻プラス第１のルートに沿った期待飛行時間及び移動時間の許容量を有する。ここで再び第２のルートに関する期待収益は、全体として都市ペア人口統計に関する１乗客当たりの期待収益の一部分であり、第１のルートに関して前に論じられたように長さによって計算される。マルチルート経路の場合には、経路内の各ルートに関するルート人口統計は、ルートがローカル線ルート（経路内に後に続くルートが存在する）又は受け手ルート（経路内に前のルートが存在する）のいずれであるか、あるいは両方であることを示すように注釈付けられ得る。
【００３１】
一度ルート人口統計が経路内のルートのすべてに関して設定されると、本システムはステップ１８１に戻り、すべての都市ペア人口統計が処理されてルート人口統計に変換されるまで、次の都市ペアに関してステップ１８５、１８７のプロセスを繰り返す。各ルート人口統計は、都市ペア人口統計と同じ方法で適用可能なその日にちを識別する。例えば２月の月曜日だけに適用可能な都市ペア人口統計から導き出されたルート人口統計は同様に２月の月曜日だけに適用可能である。
【００３２】
ルート人口統計が形成された後に、これらは要求ノードの初期リストを作り出すために図５に示されたプロセスの次のステップ１９０で使用される。各ルートは順番に取られる。各ルートに関して問題のルートに対応する出発地と目的地とを有するルート人口統計のリストは、ステップ１８０で形成されたルート人口統計からコンパイルされる。各ルートに関するルート人口統計のリストは、問題のルート人口統計の適用可能な各日にちに関する１セットの要求ノードに変換される。例えば２月の月曜日に適用可能なルート人口統計は、２月の第１月曜日に対応する日にちに関する要求ノードに変換され、２月の第２月曜日に対応する日にちに関するもう１つの要求ノードに変換され、以下同様となる。本システムは、また、運用者に利用可能な先見的又は直感的な知識を考慮することもできる。例えば前歴データが平日フライトに関してコンパイルされ、特定の日にちが出発地又は目的地における宗教的休日であることを運用者が知っていれば、本システムはこの特定の日に関する期待乗客数を減らすことができる。ある特定のルートに対応するすべてのルート人口統計が処理された後に、本システムは次のルートを取り上げて同じ日のこのルートに関するルート人口統計を処理する。本プロセスは、これらのルートすべてに関するルート人口統計のすべてが処理されるまで続く。この時点で各ルートに関する要求ノードの初期リストが存在する。各このような要求ノードは、出発地、目的地、出発日時、各クラスに関する１乗客あたりの期待収益、及び各クラスにおける期待乗客数などのルート人口統計の特徴のすべてを含む。
【００３３】
プロセスの次のステージ２００でシステムは、図７に更に詳細に示されている初期リスト内の要求ノードを分析する。この分析は、ステップ２０２においてルートのリストで始まり、ステップ２０４で各ルートを順番に取得する。各ルートに関してシステムは、ステップ２０６でルートに関する要求ノードのリストを取得する。このリストは、いかなる特定の順序になっていることも必要としない。一度ある特定のルートに関する要求ノードのリストが検索されると、本システムはこのリスト内の第１の要求ノードから開始する。本システムは、ステップ２０８でこのリスト内の第１の要求ノードを取り、この要求ノードを満たすフライトでの、すなわち期待乗客数を有する出発地から目的地へのフライトでの使用のために最善の航空機を選択するように第１の要求ノードを処理する。本システムは、スケジュールされた航空会社によって使用される航空機タイプのすべてを分析して、この要求ノードに指定された乗客数をもって出発地から目的地へ飛行すれば販売利益への最大の寄与を生み出す航空機のタイプを選択する。プロセスのこのステージで「最善の」航空機タイプの選択は、このタイプの航空機が要求ノードによって指定された日時に実際に利用可能であるかどうかの考慮なしに、また例えば遠い場所から航空機を輸送してこのような日時に航空機を利用可能にする際にこのような可能性のある費用の考慮なしに、行われる。したがってプロセスのこのステージで特徴付けられる営業利益への寄与は、要求ノードを満たすことから期待される利益の上限を示す。
【００３４】
本プロセスの次のステージ２１２においてシステムは、要求ノードにおいて指定された乗客数をステップ２１０で選択された最善の航空機によって搬送され得る乗客数と比較する。要求ノードに指定された乗客数が、選択された最善の航空機の容量より少ないか等しければ、本システムは要求ノードを処理されたようにマークし、要求ノードに営業利益への期待寄与を注釈付けして、次の要求ノードを処理するためにステップ２０８に戻る。しかしながら要求ノードに指定された乗客数が、選択された最善の航空機の搬送容量より大きければ、本システムはリストから元の要求ノードを消去してステップ２１４でこの要求ノードを２つの小さな要求ノードに分割し、これら小さな要求ノードをこのルートに関する要求ノードのリストに追加して、本システムは次の未処理の要求ノードを取得するために再びステップ２０８に戻る。これらの新しい小さな要求ノードの１つは処理されるべき次の要求ノードを構成し得る。大きな要求ノードから作り出された複数の小さな要求ノードは元の要求ノードと同じであるが、これらの小さな要求ノードの各々は元の要求ノードに指定された乗客数の半分を有する。更なる要求ノードは、元の要求ノードと同じ出発時刻を有する。これらの更なる要求ノードは、リスト内のその他の要求ノードと同じ方法で処理される。このようにして極めて大きな要求ノードは第１の通過ステップ２１２で２つの要求ノードに分割され得る。これらの小さな要求ノードの各々が処理されるとき、１つ以上は更に小さな要求ノードに再び分割され得る。またこのような分割された小さな要求ノードがステップ２１０で処理されるとき、この要求ノードのために選択された最善の航空機は元の大きな要求ノードのために選択された最善の航空機とは異なる可能性がある。
【００３５】
本プロセスは、このルートに関する要求ノード（ステップ２１４における分割の結果得られたいかなる小さな要求ノードも含む）のすべてが処理されるまでこのように続き、そこでシステムはステップ２０４で次のルートとこの新しいルートに関連する要求ノードのリストとを取得して、同じプロセスを繰り返す。これはこれらのルートのすべてが同じ方法で処理されるまで続く。
【００３６】
結果として得られた要求ノードの出力リストは更なるステップ２２０に渡される（図５及び図８）。このステップでシステムは、各ルートに関して要求ノードのリストを分析し、要求ノードを互いに組み合わせることによってより良好な期待ＣＴＭが発見され得るかどうかを決定する。このステップは、ルートのリストからある特定のルートを選択し、ステップ２００（図５）からの要求ノードのすべてを出発時刻別にソートする。ステップ２２０のステップ２２４（図８）でシステムは、ソートされたリスト内の３個の最も早い要求ノードの１セットを選択する。それからシステムは、ステップ２２６で、これら３個の選択されたモードのうちの最初の２つから組合せノードを作り出そうと試みる。
【００３７】
本プロセスは、これら２つの要求ノードの各々に関してある範囲の時間を計算する。各要求ノードに関するこの時間範囲は、フライトが要求ノードに指定された時刻から時間的に偏移する場合に乗客荷重が時間と共に変化する方法の推定値に基づいている。図９にグラフで表されているように、要求ノード２５０に関する出発時刻による乗客荷重の分散は、斜交平行線模様のバーによって示されたステップ関数によって表され得る。このステップ関数は、要求ノードの元の出発時刻Ｔ２５０における要求ノードの乗客数に等しくて、より早い出発時刻とより遅い出発時刻とに関して徐々に低くなる値を有するその最大値Ｎ２５０を有する。この要求ノードに関する有意範囲は、ステップ関数が、ある任意の乗客数より大きな値を有する最も早い時刻と最も遅い時刻と見なされ得る。このステップ関数は、全体としてシステムに関する全体的仮定に基づく可能性があり、あるいは代替として特定のルートに関連する先見的知識に基づいて選択される可能性もある。例えばニューヨーク市又はワシントンＤＣなどの公知のビジネス目的地にサービス提供する要求ノードは、商用旅行者（出張者）が一般にきつく制約されたスケジュール上にいるという仮定を反映するために狭い急傾斜のステップ関数を割り当てられ得るのに対して、フロリダ州のオーランドなどの行楽地に目的地又は出発地を有する要求ノードは、休暇旅行者がスケジュールに比較的鈍感であるという仮定に基づいてかなり広い分散を割り当てられ得る。
【００３８】
更に別の実施形態では、出発時刻による乗客荷重の分散の推定値は、前歴乗客データと都市ペア人口統計とを生成するために使用される前歴データから取得され得る。例えば、前歴乗客データが要約プロセス（ステップ１５０）で使用されたウィンドウの中心点付近に広く間隔をあけた多くの異なる時刻に出発する乗客の実質的に等しい数を示すならば、都市ペア人口統計は大きな分散を割り当てられ、この分散はステップ１８０でこのような都市ペア人口統計から導き出された各ルート人口統計に割り当てられて、ルート人口統計から作り出された各要求ノードに進められ得る。更にある特定の要求ノードに関する分散は、要求ノードの出発時刻に関して片面的又は非対称であり得る。例えば、ある特定の要求ノードがマルチパスルート内の第２の、又は後に続くルート人口統計を表すルート人口統計から導き出されるという表示によってこの特定の要求ノードが注釈付けされるならば（ステップ１８０）、分散又はステップ関数は、この要求ノードの元の出発時刻の後の出発時刻に関して徐々に傾斜するように整えられ得るが、接続便フライトが早く出発する場合にこの経路のこの早いフライトからの乗客は利用可能でないという現実を反映して、要求ノードの元の出発時刻より前のすべての出発時刻に関しては乗客数ゼロに急落する可能性がある。
【００３９】
乗客数を各要求ノードに関する時刻に関連付けるこの関数は、要求ノードによって表されたいかなるかなりの数の乗客も喜んでこのルートに沿って旅行する最も早い時刻と最も遅い時刻とによって限定された有意範囲を有する。例えば、要求ノード２５０に関するステップ関数は、時刻Ｔ２５０Ｅから時刻Ｔ２５０Ｌまでの有意範囲を有する。出発時刻Ｔ２５０を有するもう１つの要求ノード２５２は、時刻Ｔ２５０Ｅから時刻Ｔ２５０Ｌの有意範囲を有する図９の影付けなしのバーによって表される分散関数を有する。本システムは、これら２つの要求ノードの有意範囲を分析してこれらの有意範囲がオーバーラップするかどうかを決定する。これらがオーバーラップしなければ、これら２つの要求ノードを組み合わせる試みは放棄されて、ステップ２２６は完了する。しかしながら、これらの有意範囲がオーバーラップすれば、本システムは組み合わされた要求ノードに関する１セットの可能な出発時刻を選択する。最も早い可能な出発時刻は、どちらが遅いにせよ、オーバーラップする有意範囲によって包含された時刻範囲内の最も早い時刻か、最も早い要求ノードの元の出発時刻のいずれかである。最も遅い可能な出発時刻は、どちらが早いにせよ、これら２つの要求ノードのオーバーラップする有意範囲によって包含された最も遅い時刻、又は、より遅い要求ノードの出発時刻である。例えば要求ノード２５０、２５２の有意範囲は、時刻Ｔ２５２Ｅから時刻Ｔ２５０Ｌでオーバーラップする。したがって組合せノードに関する最も早い可能な出発時刻はＴ２５２Ｅであって、最も遅い可能な出発時刻はＴ２５２Ｌである。実際に同じルート及び同じ日における２つの要求ノードに関するオーバーラップする有意範囲は、このオーバーラップ範囲中に出発するこのルートに沿ったフライトがより早い要求ノードに関連する幾らかの乗客と、より遅い要求ノードに関連する幾らかの乗客とを引き付けることを示している。本システムはまた、最も早い可能な出発時刻と最も遅い可能な出発時刻との間の１つ以上の中間の可能な出発時刻を計算する。例えば本システムは、最も早い可能な出発時刻と最も遅い可能な出発時刻との間の中間点として１つのこのような中間の出発時刻を計算する。
【００４０】
各可能な出発時刻に関して本システムは、このような出発時刻に関して期待される乗客数を決定する。本システムは、可能な出発時刻における各要求ノードに関するステップ関数を評価し、この可能な出発時刻に動作する組合せノードに関して期待される乗客数を与えるようにこの特定の出発時刻に関して両要求ノードに関するステップ関数の値を追加する。例えば時刻Ｔ２５２Ｅに出発するフライトに関する期待乗客数は、ＮＡとＮＢの合計である（図９）。
【００４１】
それからシステムは、各可能な出発時刻における要求ノードに関する最善の航空機を計算して、この可能な出発時刻に関するＣＴＭを計算する。結合ステップにおいて、期待乗客数が最善の航空機の容量を超えていれば、この期待乗客数はこの航空機の容量に等しく設定される。本システムは、可能な出発時刻に関するＣＴＭを比較して、最初の２つの要求ノードを結合した結果として最善のもの（可能な出発時刻）を選択し、ここでステップ２２６は終了する。それからシステムは、正確に同じ方法でステップ２４０において第２の２つの要求ノードを結合しようと試み、ステップ２４２で選択された要求ノードの３個すべてを結合しようと試みる。３個の要求ノードを結合するプロセスは、これらの要求ノードが２つの異なる出発時刻を有する２つの要求ノードに結合されるべきであることを仮定している可能性があり、また最も早い又は第１の要求ノードの出発時刻から最も遅い又は第３の要求ノードの出発時刻までの範囲内の複数の可能な出発時刻を使用し、３個の選択された要求のステップ関数に基づいて各可能な出発時刻における結合乗客荷重を計算して、もう一度、最善の航空機を選択し、各可能な出発時刻に関する最善の航空機に関するＣＴＭを計算する。これら２つの要求ノードに関する最善の総計ＣＴＭは、ステップ２４２の結果として出力される。
【００４２】
ステップ２４４でシステムは、ステップ２２６、２４０の２ノード結合とステップ２４２の３ノード結合との結果から得られるＣＴＭを比較して、これらのＣＴＭのうちの最善のものを選択し、可能な出発時刻と結合ノードに関する期待ＣＴＭと結合ノードを与えるために結合するノードのアイデンティティとを、すなわち最初の２つ、２番目の２つ、又は考慮されているこれらのノードの３個すべてを与えるために結合するノードのアイデンティティとを、含む結果を出力する。ステップ２４６でシステムは、ステップ２４４によって出力される結合ノードに関するＣＴＭをこの結合ノードを形成するために使用された個々のノードに関するＣＴＭの合計と比較する。結合ノードが個々のノードに関するＣＴＭの合計より高いＣＴＭを生み出すならば、本システムはステップ２４８に分岐して、結合出力ノードを形成するために使用された個々のノードを結合ノードで置き換え、それからステップ２２４に戻る。そのようでなければ、本システムは個々のノードを置き換えることなく直ちにステップ２４４に戻る。ステップ２２４でシステムは、前に処理されたセット内の最新の要求ノードとこれに続く２つの要求ノードとを含むもう１つのセットの３個の要求ノードを取得する。それからシステムは、同じ方法でこの新しいセットの要求ノードを処理する。これは、処理されるべき要求ノードがこれ以上存在しなくなるまで続き、そのときシステムは戻ってステップ２２１に分岐し、同じ方法で処理される次のルートを選択する。これはこれらのルートのすべてが処理されるまで続く。
【００４３】
この結合プロセスでシステムは、残りの要求プロセス２００のサブステップ２１４（図７）で行われる分割の一部を逆にできる。例えば極めて大きな要求ノードが２つの要求ノードに分割されたならば、これら２つの要求ノードは、ステップ２２６又はステップ２４０で大きな要求ノードに再び結合されることが可能である。
【００４４】
本プロセスのこの時点で、要求を定式化するステップ（図１のステップ１００）は完了する。それからシステムは、要求ノードを本明細書ではトポロジー的順序と呼ばれる順序に配置する。これは、１つ以上のソートキーにしたがって要求をソートすることによって行われる。ソートキーは、これらの要求のいかなる特徴も含み得る。１つの単純なソートキーは、要求が日付順に配置されるように、要求に指定された日付と出発時刻からなる。しかしながら他のソートキーは、例えば最も収益の高いフライトがトポロジー的順序の最初になるように期待ＣＴＭ別にソートすることによって、あるいは長距離輸送要求が最初にスケジュールされるように、又は短距離輸送要求が最初にスケジュールされるようにルートの距離別にソートすることによって、使用され得る。また航空会社は、出発地都市及び目的地都市としてハブ都市を有する要求ノードが最初に処理されるように、指定されたハブ都市間のフライトに優先順位を与えたいと思う可能性がある。前述のようにマルチルート経路のローカル線ルート要求としてルート要求がマーク付けされる可能性があり、またこのローカル線ルート要求の結果から得られる要求ノードは同様にマーク付けされる。このマーカーは、ローカル線要求ノードが最初に処理されるように、ソートキーとして使用され得る。更なる変形形態では要求ノードのこれら及び他の特徴は、重み付け係数を割り当てられ、このような係数によって重み付けされた各要求ノードの複数の特徴に基づいて複合ソートキーが計算され得る。ソートキーの選択は、スケジューリングの際に達成される結果に、ある程度影響を及ぼす。しかしながら実際には、単に出発日時別にソートすることが、より複雑なスキーム（構成）と同様に、あるいはほぼ同様に働くことが分かっている。
【００４５】
本システムは、スケジュールされるべき業務を実行するために必要とされる資源のデータベースを維持する。航空会社に関してこれらの資源は、両方とも移動体である飛行機と乗務員ならびに特定の空港における乗客搭乗ゲートを含む。このデータベースは、各資源の特徴に関する情報を含み、また生成されたスケジュールの継続時間中の将来の各時刻における各資源の状態に関する情報も含む。飛行機に関してはこれらの特徴は、典型的には、飛行機のタイプと；その各サービスクラスの座席容量と；その最大航続距離（最大ブロックタイムと言われ得る）と；典型的には１飛行時間あたりのコストと言われる飛行機を使用するコストとを含む。スケジュールにおける各時間の飛行機に関する状態情報は、場所、例えば特定の空港で、又は途中で駐機する場所；保守のために飛行機が運休中であるかどうかに関する表示；及び直近のスケジュールされた保守検査以来及び直近の主要オーバーホール以来の動作時間数及び暦日数などの飛行機の動作前歴に関する情報を含む。乗務員に関して特徴は、特定のタイプの航空機及び基地で勤務する資格を含む。各時間に関する状態情報は、乗務員が当番又は非番であるかどうかなどの情報と；乗務員の基地又はある他の空港又は途中における乗務員の場所と；乗務員が当番になって以来の時間数又はフライト数、各年月において累積された勤務時間の時間数、及び関連する政府規制、労働組合契約又は航空会社職員規定の下でのフライトのための乗務員の利用可能性の計算に関する任意の他のデータとを含む。ゲートの特徴は、このゲートが位置する空港の識別情報を含み、また特定のゲートに対応し得る航空機のタイプも含み得る。ゲートはまた、飛行機の遅れた出発に賦課され得るような占有費用をこれに関連付けている可能性もある。ゲートの状態は典型的には単に、ゲートがこのスケジュール中に各間隔で占有されているか占有されていないかどうかの表示である。
【００４６】
データベースは、スケジュールの初めに種々の資源の期待される状態を表す初期状態に設定される。
【００４７】
本システムは、トポロジー順序付けステップによって設定された順序で要求ノードを取り上げて、各要求ノードに関するスケジュール断片を計算しようとする。各スケジュール断片は、要求ノードの出発地及び目的地と、この要求ノードを満足させるフライト業務に関して指定された条件とを含む。これらの条件は、特定の航空機と特定の乗務員と特定のゲートとを含む。指定された条件は、これらの条件が実現可能であるように、すなわち航空機が存在していて占用されていないように；スロット又はゲートが利用可能であるように；また乗務員が有資格であって利用可能であるように；選択される。本システムはまた、これらの条件にしたがってそのフライトを飛ばすことに関して期待される結果を表す結果関数が基準を満たすように、スケジュール断片に関する条件を指定しようとする。最も一般的な結果関数は、この業務から期待される営業利益への寄与であって、本システムはこの業務から期待される営業利益への寄与を最大にしようとする。
【００４８】
スケジュール断片に指定されるべき条件を選択する問題は、図１０の参照によって理解され得る。航空機と指定された条件との間の距離Ｄ１は、要求に指定された出発地から要求に指定された目的地に航空機を飛ばすことに関連する営業利益へのマイナスの寄与又は費用を表し、また適用可能であれば、必要な場合に航空機を別の空港から再配置するための費用も含む。距離Ｄ２は、１時間あたりの直接費用と乗務員の再配置、乗務員に支払われる超過勤務手当などの臨時費用との両方を含む乗務員に与える費用を表す。指定された条件と要求ノードに組み込まれた人口統計との間の距離Ｄ３は、例えば指定された航空機が要求ノードに指定された時刻に出発ゲートで利用可能でない場合に、要求ノードに指定された出発時刻とは異なる出発時刻を指定する結果から生じる収益へのマイナス効果を表す。距離Ｄ３は、また、期待された乗客荷重を収容するためには小さすぎる航空機を指定する結果から生じるいかなる収益の損失も含む。距離Ｄ４は、出発地空港と目的地空港で使用されるスロット又はゲートに関連する費用を表す。本システムは、Ｄ１〜Ｄ４の合計が最小でも、資源のデータベースの現在状態によって賦課される制約すなわちデータベースに表示されたような資源の利用可能性を与えられるような条件を選択しようとする。最小化又は最大化は、厳密な数学的最小化又は最大化である必要はない。別の言い方をすればシステムは、すべての可能な代替手段を考慮する必要はないが、実際には局所的最小又は最大に到達するように利用可能な資源に一致するいくつかの代替手段だけを考慮し得る。しかしながら大抵の又はすべての利用可能な資源を考慮することは一般に実現可能である。
【００４９】
スケジュール断片に関する条件を選択するために使用されるプロセスの一実現形態が概略的に図１１に示されている。本プロセスは、ステップ３００で前に論じられたトポロジー順序付けステップの結果から得られる要求ノードの順序付けリストを入力することによって開始する。ステップ３０２でシステムは、要求ノードのすべてが処理されたかどうかを確かめる。未処理の要求ノードが存在すると仮定してシステムは、ステップ３０４で順序付けリスト内の第１の未処置要求ノードを選択する。ステップ３０６、３０８でシステムは、要求ノードの出発地、目的地及び出発時刻によって指定されたフライトを飛ばすために利用可能である飛行機の中から最善の飛行機を選択しようと試みる。これらのステップでシステムは、資源データベースの現在状態が与えられたとして、フライトが出発することになっている空港で利用可能と表示されている飛行機、又は出発地空港に飛ばされることが可能であってこのフライトのために利用可能にされ得る飛行機を見つけようとする。これらの航空機の中からシステムは、ＣＴＭに最も少ないマイナスの影響を有するある特定の航空機を探索する。出発地空港に既に駐機している航空機を使用することはほとんど常に良好であるので、本システムはステップ３０６で出発時刻に出発地空港にある飛行機を最初に分析する。満足な飛行機が見つかれば、本システムはステップ３０８をスキップし、したがってこの輸送業務の時間にほかの場所に位置する飛行機を使用する可能性を分析しない。
【００５０】
ステップ３０６で使用可能な選択プロセスは、図１２に概略的に示されている。ステップ３０９でプロセスは、全航空機から１機の航空機を選択する。この航空機が要求ノードに示された出発地空港で、要求ノードに示された出発時刻に、あるいはこの出発時刻の１時間後などの予め決められたウィンドウ内でドック入りすることを資源データベースが示すならば、本システムは次のステップ３１２に進む。そうでなければシステムは、この航空機を放棄して、航空機選択ステップ３０９に戻る。ステップ３１２でシステムは、航空機が別のフライトに約束されているか、又は要求ノードに指定されたフライトに必要とされる時間に保守に約束されているかどうかを決定するために資源データベースをチェックする。この航空機が利用可能でなければ、再びシステムはこの航空機を放棄して、ステップ３０９に戻る。この航空機が利用可能であれば、本システムはまたこの航空機が要求ノードに指定されたフライトでの使用のために使用可能な航空機であるかどうかをチェックする。例えば本システムは、出発地空港と目的地空港との間のフライトの距離に対して航空機タイプの航続距離をチェックする。この航空機が十分な航続距離を有さなければ、これはそのフライトに実行可能な航空機ではない。実行可能性を決定する際に他の要因も考慮され得る。例えば目的地空港が特定のタイプの航空機に対応するために十分な滑走路長を有さなければ、このタイプのいかなる航空機も除外され得る。航空機が除外されないと仮定してステップ３１６でシステムは、資源データベースにしたがって航空機がゲートで利用可能になる時刻対要求ノードに指定された出発時刻の間の差又は「デルタ」を決定する。航空機が要求された出発時刻に利用可能であることをデータベースが示すならば、デルタは０であることは無論である。
【００５１】
更なるステップ３１８でシステムは、要求ノードにおける選択された航空機の使用のための得点係数（スコアリングファクター）を計算する。１つの得点係数は、ステップ３１６で計算された利用可能時間デルタに基づいている。この得点係数は、航空会社によって設定された１分あたりの任意値に基づくこともあり得る。代替としてこの得点係数は、図９を参照しながら前に論じられた、乗客数を出発時刻に関係付けるステップ関数などの要求ノードにおける分散の大きさに基づいて計算され得る。したがって要求ノードが図９のステップ関数などの乗客数を出発時刻に関係付ける関数を含むならば、本システムは航空機が利用可能である時刻に一致するように出発時刻を変更する効果を反映するためにこの関数に基づいて期待乗客数を計算し得る。要求ノード内の乗客数と時間による分散を評価する結果から得られる乗客数との差は、遅延した利用可能性に関連する得点（スコア）又は費用を取得するために１乗客当たりの期待収益と乗算されることが可能である。
【００５２】
更にシステムは、現在選択された飛行機を飛ばす１時間あたりの費用に基づいて得点又は費用を計算する。本システムは、また、座席デルタすなわち期待される乗客数が航空機の座席数を超えた量を計算する。この費用は単に、座席数と乗客数との差に特定のクラスの１乗客当たり期待収益を乗算した積である。本システムはこれら種々の得点を加算して全得点を計算する。この全得点は、特定の航空機を飛ばすことのＣＴＭへのマイナス効果を表し、またしたがって図１０のＤ１を表し、そしてまた特定の航空機の選択によって引き起こされたフライト時間の何らかの遅延の、又は何らかの容量不足のＣＴＭに対するマイナス効果を表し、したがって図１０のＤ３を表す。本システムは、この航空機を実行可能な航空機のリストに追加する。リスト内の航空機の位置はこの得点に基づいている。したがってこのリストは、種々の航空機の得点にしたがってトポロジー的に順序付けられている。本システムは、次の航空機を処理するためにステップ３０９に戻る。処理されるべき航空機がこれ以上存在しなければ、本システムはステップ３２２に分岐してリスト内で最低の得点を有する航空機を選択し、図１１の乗務員選択ステップ３２４に分岐する。リスト内で航空機が見つからなければ、これは要求ノードに指定された出発地空港において利用可能な実行可能航空機が存在しないことを示し、本システムはステップ３０８に分岐する。
【００５３】
ステップ３０８は、ステップ３０８が出発地空港でドック入りと表示されなかった航空機だけを考慮し、また航空機が出発時刻を満足させるために時間内に、又は出発時刻の１時間後などの指定されたウィンドウ内に出発地空港に飛ばされ得るかどうかを資源データベースの情報に基づいて決定するための更なるサブステップを含むということを除いて、実質的にステップ３０６と同じである。またステップ３０８で各航空機に関する得点は、飛行機が関連時刻に位置している空港から出発地空港へのフライトに関する費用を含む。ステップ３０８で飛行機が見つからなければ、これは要求ノードがデータベースによって示された状態の資源によって満たされ得ないことを示す。したがってこの要求ノードに関してスケジュール断片は生成されない。その代わり、要求ノードは単に、実行可能な飛行機を有さないという結果としてこの特定の要求ノードがスキップされたことを示すためにステップ３２６でマーク付けされる。
【００５４】
飛行機がステップ３０６又は３０８で選択されると、この要求ノードにサービス提供するフライト業務の出発時刻は、このような時刻が要求ノードに指定された時刻と異なるならば、航空機が利用可能である時刻に調整される。別の言い方をすればシステムは、利用可能な航空機資源に適合するようにスケジュール断片を適応させる。
【００５５】
飛行機がステップ３０６又は３０８で選択されれば、本システムは乗務員選択ステップ３２４に進む。乗務員選択ステップは、飛行機選択ステップ３０６、３０８に類似した方法で実行される。このようにしてシステムは、利用可能な乗務員を分析して実務可能である乗務員を選択し、最低費用の実務可能な乗務員を見つけ出す。本システムはまた望ましくは、乗務員が月間又は年間の最大勤務時間を超えないように、乗務員勤務時間のバランスを考慮する。例えば、考慮されている月における乗務員に関して前にスケジュールされた勤務時間数に直接関連して、いかなる乗務員にも追加費用が割り当てられ得る。乗務員選択ステップは、飛行機選択ステップに見られる出発時刻と航空機タイプとを使用する。したがって実務可能であるためには乗務員は、ステップ３０６又は３０８で選択された飛行機のタイプに搭乗する資格がなければならず、またステップ３０６又は３０８で確定された出発時刻に出発地空港で利用可能でなければならない。また乗務員は、乗務員がフライトを完了することを可能にするために出発時刻において残っている十分な勤務時間を有さなければならない。乗務員選択ステップは、資源データベースにしたがって、出発地空港に配置されている乗務員を最初に取り扱うことができ、それから出発地空港に再配置され得る乗務員を取り扱うことができる。また乗務員選択ステップは、航空機タイプに関して全乗務員を処理し、それから全乗務員が見つからなければ、乗務員選択ステップは全乗務員を形成するために個別の乗務員を見つけ出そうとする可能性がある。代替として又は更に、乗務員選択ステップは、勤務前歴を有さない乗務員を最初に処理し、それから直ぐ前日の非番以来の勤務前歴を有する乗務員を処理し得る。これは、ある特定の乗務員が勤務時間についての制約のすべてが与えられた十分の残り勤務時間を有するかどうかを決定するために必要とされる計算が多大な時間を必要とする可能性があるので、有益であり得る。
【００５６】
乗務員を見つけることができなければ、本システムはスケジュール断片を形成しないで、代わりにステップ３２８に分岐して乗務員が利用できなかったのでスキップされたとノードにマーク付けする。一変形形態では、乗務員を見つけることの不成功が、ある特定の資格を有する乗務員の欠如によって引き起こされたのであれば、例えばボーイング７４７の乗務資格のあるパイロットを見つけ出すことの不成功であれば、本システムはこの特定の表示でこのノードにマーク付けすることができる。
【００５７】
乗務員が見つけられたと仮定してシステムは、乗務員の費用を反映する得点、例えば乗務員の基本給と、乗務員に関連する超過勤務手当、待合わせ費用、乗務員配置換えフライトなどの何らかの割増し支払いとの両方を反映する得点を計算する。この得点は図１０のＤ２を表す。乗務員が見つかれば、本システムはステップ３３０に分岐して、出発地と目的地における利用可能なゲートを探索する。ここで再び、ゲートが見つからなければ、本システムはスケジュール断片を形成せず、代わりに特定の空港におけるゲートの利用不可能によりスキップされたとノードにマーク付けする。
【００５８】
ゲートが見つかったと仮定してシステムは、スケジュール断片を形成し、前のステップで見つけられた飛行機と乗務員とゲートとを約束するために資源データベースにマーク付けすることによってこのスケジュール断片を実現する。このようにしてこれらの資源は、フライトを完了するために必要とされる時間中、占用されると表示される。またシステムは、飛行機と乗務員とを含む移動資源がフライトの終了時に対応する時刻に目的地空港に位置することを示すようにデータベースにマーク付けする。本システムは、また、直近の保守以来の更なる飛行時間を示すように航空機の状態を更新し、また乗務員がこのフライトに充てた更なる勤務時間を示すように乗務員の状態を更新する。
【００５９】
この時点で、個別のスケジュール断片は完了する。本システムは、また、ステップ３３６でこのスケジュール断片にしたがって飛んだ場合のフライトの期待営業利益寄与を記録し得る。
【００６０】
一変形形態ではシステムは、ステップ３３４で資源を約束する前に、１つ以上の下落基準に対して提案されたスケジュール断片をテストし得る。例えば提案されたスケジュール断片が営業収益へのマイナス寄与という結果を招くならば、本システムは資源を約束しないで、代わりにマイナスＣＴＭのためにスキップしたと要求ノードにマーク付けして、ステップ３０２に戻る可能性がある。更にもう１つの変形形態ではシステムは、１つ以上の保持基準が満たされれば、下落基準を打ち消し得る。例えば、本システムは、要求ノードがもう１つの要求に関するローカル線としてマーク付けされれば、スケジュール断片を保持するように整えられ得る。更なる変形形態ではこれらの保持基準は、航空会社にとって特に重要な特定の都市へのサービスを含み得る。更に別の変形形態ではシステムは、資源のあるいくつかの前の割当てを再分析することがあり得る。例えば航空機選択ステップ３０６及び３０８の結果が、要求を満足させるための航空機は利用可能でないことを、あるいは要求を満足させるために利用可能な唯一つの航空機は期待乗客数より遥かに小さいか、遥かに大きいので劣悪な結果与えることを、示すならば、本システムは処理された要求の出発時刻の数時間後以内に出発地空港に到着するフライトに前に割り当てられた航空機を分析し、航空機がより早く到着するようにこれらのフライトを再スケジュールすることが実行可能であるかどうかを決定し、そのようであればＣＴＭ又は他の結果への影響がどんなものかを決定し得る。本システムは、また、選択された航空機が考慮されている要求における出発時刻の後に利用可能になることと、このような遅延が考慮されている要求からのＣＴＭを低下させることとを第１のパスが示すならば、前にスケジュールされたフライトを再スケジュールしようとする可能性もある。更なる変形形態ではシステムは、このステージで要求を分割又は結合する効果をテストすることができる。例えば、第１の出発時刻と１００名の期待乗客とを有する第１の要求が存在し、最善の利用可能な航空機が２００座席を有するならば、本システムはもう１つの出発時刻を有する要求を探して、これら２つの要求を結合することがより高い収益を上げるかどうかを決定することができる。このステージは図７及び図８を参照しながら前に説明されたプロセスと同様のプロセスを使用し得る。しかしながらこの場合、可能な結合と分割の分析は、最善の可能な航空機に基づくよりもむしろ問題の結合又は分割された要求の出発時刻に実際に利用可能である航空機に基づいて実行される。
【００６１】
ある要求ノードに関して１つのスケジュール断片が完了した後、あるいはこの要求ノードがスキップされた後に、本システムはステップ３０２で処理されるべき要求ノードがこれ以上存在するかどうかをチェックする。存在すれば、本システムはステップ３０４で次の要求ノードを選択して上記のステップを繰り返す。更なる要求ノードが存在しなければ、スケジュールは完了する。本システムは、個別のスケジュール断片に関連するＣＴＭのすべてを加算する結果から生じる全期待ＣＴＭを出力し得る。
【００６２】
図１を参照しながら前に示されたように、本システムは資源を調整して、スケジューリングプロセス全体又はスケジューリングプロセスの一部分のいずれかを繰り返し得る。資源に対する調整は、ステップ３２４、３２８、３３２で要求がマーク付けされるときに取得されるスキップされた要求の原因に関する情報に基づくことができる。例えば、多数の要求がエンブレール（Ｅｍｂｒａｅｒ）飛行機に搭乗資格のある客室乗務員の不足によってスキップされていることと、これらのスキップが主として３月３１日以降発生することとをこれらのマーク付けが示すならば、本システムはそういう資格のある更なる客室乗務員が存在することを示すように資源のデータベースを調整して、このような更なる客室乗務員が雇用されて３月３１日現在利用可能になるように訓練されるべきであるという表示を発行し得る。本システムは、ある一定数の更なる客室乗務員が３月３１日以降に利用可能になるという過程に基づいてスケジュール全体を再計算し得る。代替として要求が出発日時にしたがって順序付けされていれば、本システムは３月３１以降のスケジュールのこの部分だけを再計算して、複合スケジュールを形成するために３月３１日より前の早期に計算されたスケジュールに再計算スケジュールを連結することができる。再計算スケジュールに関する全ＣＴＭは、提案された資源変更が経済的に望ましいかどうかを決定するために元のスケジュールに関するＣＴＭと比較され得る。同様にある特定のタイプの更なる飛行機が利用可能にされるべきであることをスキップされたノードの表示が提案しているならば、本システムはこのような更なる飛行機が利用可能であることを示すように資源のデータベースを変更し、このような表示を有するスケジュール又はスケジュールの一部分を再計算して、より多くの飛行機を取得又はリースすることによって取得可能な利益を決定するために再計算スケジュールのＣＴＭを元のスケジュールのＣＴＭと比較することができる。
【００６３】
図１３に概略的に図示された本発明のもう１つの実施形態によるプロセスは、前述の要求に類似の要求を利用する。これらの要求は、図２〜９を参照しながら前に論じられたプロセスと本質的に同じプロセスによってステップ４００で定式化され得る。ここで再び各要求は、出発地と目的地と所望の出発時刻又は到着時刻とを含むことが可能であって、望ましくは旅客航空会社の場合、各料金クラスにおける乗客荷重などの推定荷重を指定する情報も含む。ここで再び各要求は、荷重（乗客荷重又は各料金クラスにおける乗客荷重などの）を出発時刻又は到着時刻に関係付ける情報を含み得る。ここで再びシステムは、少なくとも輸送機材のリストを含む、また望ましくは例えばスケジュールによって包含されるべきである将来の間隔における各時間中に空港などのある特定のターミナルに、又は途中に配置された各輸送機材の状態などの上記に論じられたような情報を有する輸送機材のリストを含む資源のデータベースを維持する。データベースは、また、望ましくは、他の資源、例えばターミナルゲートと乗務員とを含み、また望ましくは前述と同じ情報を含む。ここで再びスケジューリング手順の初めに、データベースは初期状態にある。
【００６４】
本システムは、ステップ４０４でデータベースから特定の輸送機材を選択する。この選択は、タイプ別の、あるいは輸送機材アイデンティティ別の輸送機材の順序付けに基づくことができる。例えば航空会社は特定の飛行機を最もよく利用するために最も高価な飛行機を最初にスケジュールするように選択でき、その場合、最も高価な飛行機は輸送機材の順序の最初にあり、これによってこれら最も高価な飛行機の１つが最初に選択される。
【００６５】
ある特定の輸送機材を選択してシステムはステップ４０６で、輸送機材の状態を評価し、この輸送機材が利用可能である次の時間を見つけ出し、選択された輸送機材の使用によっておそらく満たされ得る１セットの実現可能な要求を選択する。例えば選択された輸送機材が特定の日時を通して保守において、あるいは前にスケジュールされた業務において占用されるものとしてデータベースにリスト化されるならば、本システムは、その輸送機材が利用可能になる特定の日時より長時間前の出発時刻を有するこれらの要求を除外することによって１セットの実現可能な要求を選択し得る。また、このステージでシステムは、特定の輸送機材に関して実現不可能である要求を、例えば問題の航空機によって必要とされる照明より小さな滑走路照明を有する、あるいは問題の航空機の航続距離より長い飛行距離を有する目的地空港を必要とするこれらの要求を除外し得る。本システムはまた、技術的には実現可能であり得るが、この特定の輸送機材によってサービス提供された場合に収益の高い結果をもたらす可能性が極めて低い要求を、例えばデータベースによって示された輸送機材の場所からある一定の距離より遠くに位置する出発地を有する要求を除外し得る。このステップを省略してデータベース内の要求のすべてをこの１セットの要求として使用することは可能であり；実現不可能な要求は後のステージで除外され得る。しかしながら１セットの実現可能な要求を選択することは、計算の数を削減する。
【００６６】
ステップ４０８でシステムは、ステップ４０６からのセット内の要求の１つを選択し、それからステップ４１０でシステムはステップ４０４で選択された特定の輸送機材がこの要求を達成するために使用されるという仮定に基づいて、要求に関するスケジュール断片を計算する。スケジュール断片を計算するステップは、スケジュール断片を完了させるために、また必要であれば航空機の利用可能時間の、又は利用可能時間後の出発時刻に出発時刻を調整するために、乗務員及びゲートなどの最善の資源を選択するように前述のステップと同様のステップを使用して実行され得る。ここで再びシステムは、ステップ４１０の結果から得られる可能なスケジュール断片に関してステップ４１２で結果関数を計算する。前に論じられたように、結果関数は可能なスケジュール断片に関するＣＴＭなどの財務結果を含み得る。結果関数は任意選択的に、航空機の利用可能時刻から出発時刻までに航空機によって費やされる遊休時間に対するペナルティ（罰則）を含み得る。ステップ４１４でシステムは、ステップ４０６からの１セットの要求内の要求のすべてが処理されたかどうかを決定する。処理されていなければ、本システムはステップ４０８に戻り、このセットからもう１つの要求を選択し、可能なスケジュール断片と次の要求に関する関連結果関数とを与えるようにこの要求に関してステップ４１０、４１２を繰り返す。本プロセスは、実現可能な要求のすべてが可能なスケジュール断片と関連結果関数とを生み出すために処理されるまで続く。それからシステムはステップ４１６に分岐し、そこでシステムは最善の結果関数を生み出した、例えばステップ４０６からのセット内のすべての要求のうちの最も高いＣＴＭを生み出した特定の要求を選択する。これに関してステップ４０６が省略されたか、このセットが実現不可能な要求を含むようにステップ４０６が極めて広い基準を使用したのであれば、本システムは可能なスケジュール断片を計算するステップ（ステップ４１０）のときに実現可能性を決定して、ステップ４１６における選択から実現負不能という結果を生じたいかなる要求も除外する。
【００６７】
一度最善の結果が選択されると、スケジュール断片は、最善の結果に関連する可能なスケジュール断片に指定された条件を採用して、選択された輸送機材と他の資源とを含む資源をこのスケジュール断片に約束することによって設定される。このようにしてデータベースは、選択された輸送機材とこのセットのスケジュール断片に使用される任意の他の資源とが約束されていることを示す新しい状態にステップ４１８で更新される。一度新たしい状態が設定されると、本システムは再びステップ４０６に戻り、この新しい状態に基づいて選択された航空機に関する新しい１セットの実現可能な要求を選択する。例えば、直ぐ前の通過ステップ４０６〜４１６が目的地としてのサンフランシスコまで輸送機材を利用し、特定の日の午後３時に更なる使用のためにこの輸送機材を利用可能にするスケジュール断片を設定するという結果をもたらしたならば、次の通過ステップ４０６〜４１６は、サンフランシスコにおける航空機の位置とこの日の午後３時の利用可能時刻とに基づいて航空機を最もよく利用する要求の選択という結果をもたらす。本プロセスはステップ４２０で、輸送機材が生成されたスケジュールによってカバーされるべき時間の間隔を通して完全にスケジュールされることをシステムが決定するまで、続く。輸送機材が完全にスケジュールされたのであれば、本システムはステップ４２４でこれがスケジュールされるべき最後の輸送機材であるかどうかを決定するためにチェックする。そのようでなければ、本システムは戻ってステップ４０４に分岐し、次の輸送機材を選択し、同じ方法で次の輸送機材に関する全スケジュールを開発するようにこの輸送機材に対してステップ４０６〜４２０を繰り返す；そして本プロセスは、すべての輸送機材がスケジュールされ、そこでスケジュールが完了するまで繰り返す。
【００６８】
本方法でスケジュールすることは、図１０を参照しながら論じられたと同じ一般的アプローチを使用する、すなわち、ある特定のフライト業務に関して費用を最小にする、又は他のある結果を最大にする条件を選択することを使用する。しかしながらこの実施形態では要求は、特定の航空機に関して実現可能になる順序で取り組まれる。別の言い方をすれば、この実施形態は、スケジュールを通して航空機にしたがい、この航空機が必要な時間間隔の間に完全にスケジュールされるまでプロセスを繰り返してスケジュール中の任意の時刻にこの航空機の最善の使用を見つけ出す。本プロセスの一変形形態ではシステムは、次の輸送機材を選択する前に各輸送機材に関する全スケジュールを計算しない可能性がある。例えば、ある特定の輸送機材に関してスケジュール断片を記録する新しい状態を設定した後にシステムは、戻ってステップ４０４に分岐して、もう１つの輸送機材を選択し得る。輸送機材を選択するステップは、この実施形態では、前に最も少ない回数、選択された輸送機材が選択されるように、その輸送機材が選択された回数に基づいて特定のタイプの輸送機材のすべての中から１つの輸送機材を選択するように構成され得る。この方法でシステムは、本質的に、初期状態から始まる第１の業務において各輸送機材に関する最善の使用法を見出す。それから各輸送機材が第１の業務に関してスケジュールされたことをシステムの状態が示すとき、本システムは第２の業務に関してもう一度、各輸送機材の最善の使用法を捜し求める。本プロセスは、輸送機材のすべてがスケジュールによってカバーされるべき全時間間隔を通してスケジュールされるまで続く。
【００６９】
これらの実施形態の各々において１つの全体スケジュールが定式化された後に、人間のオペレータ又はシステムは、ステップ４２８で概略的に示されたように資源を調整すること、又はステップ４３０で概略的に示されたように要求が定式化される戦略を変更することを決定して、もう１つのスケジュールを生成するためにプロセスを繰り返し得る。ここで再び、種々のセットの資源と種々の戦略とによって開発されたスケジュールは迅速に生成されて互いに比較され得る。
【００７０】
更にもう１つの変形形態では、システムは、スケジュールの一部分を設定するために図１３を参照しながら前に論じられた輸送機材順序付けスケジューリングアプローチを使用でき、またスケジュールの他の部分を設定するために図１１を参照しながら論じられた要求順序付けアプローチを使用できる。前に論じられた実施形態においてスケジューリングプロセスは、輸送機材以外の資源を、すなわち乗務員と空港ゲートとを含む。より限定された変形形態では本明細書で論じられるスケジューリングプロセスは、単に輸送機材をスケジュールするために使用可能であり、他の資源をスケジュールするためには外部のプロセスが使用され得る。このより限定された変形形態では、データベースは輸送機材に関する情報だけを含み得る。
【００７１】
上記に論じられたシステムは、望ましくは、輸送機材の保守のための時間を提供する。例えば、航空機は、典型的には、各フライトの終了時に整備（点検修理）されなくてはならない。このタイプの保守は、典型的には、一定の間隔を必要とし、またいかなる場所においても実行され得る。したがってシステムは望ましくは単に、各フライトの終了時の保守のための間隔を加える。一般に「Ｃ」及び「Ｄ」保守と呼ばれる他の保守は、航空会社によってサービス提供されるターミナルに存在する、又は存在しない可能性のある指定された保守センターで実行されなくてはならない。このタイプの保守は、例えば指定された飛行時間数、離陸又は着陸の回数、又は暦日の日数、あるいはこれらのある組合せを含み得る規則によって設定された間隔で実行されなくてはならない。前述のようにシステムによって維持される資源データベースは、これらの要因を含む各航空機に関する状態情報を有する。本システムは、航空機が１つのスケジュール断片に組み込まれる度に、データベースを、あるいはある特定の航空機に関するデータベースの部分を精査する。新しいスケジュール断片の終了時における航空機の状態が保守を必要とするような状態であれば、本システムは単に、必要とされる特定の保守に関して直感的に航空機をスケジュールし、この航空機が必要とされる間隔の間（典型的には数日間又は数週間）運休することを示すようにデータベースにマーク付けし、航空機が保守のために利用可能にされるときと必要とされる保守のタイプとを示す信号を保守管理システム又は人間のオペレータに渡すことができる。更なる変形形態では、保守期限が近づいていることを特定の航空機に関する状態情報が示すならば、本システムは適当な保守基地のある目的地、又は保守基地の近くの目的地に航空機が飛行するための人為的に低い費用を設定でき、このようにして次のスケジュールされた要求が保守基地まで、又は保守基地近くまで航空機を利用する確率を増加させることができる。保守システムと対話し、必要な保守を十分に認識して現実的に航空機をスケジュールする能力は、大きな利益をもたらす。
【００７２】
前述のシステムの各々は、航空機とその他の資源の初期状態に基づいてスケジューリングプロセスを開始し、スケジュール断片を生成することによって航空機が将来の時間にあると期待される将来状態のデータベースを構築する。最も典型的には初期状態は、スケジューリング作業が実行された後のある時刻における予測された状態である。例えば航空会社は、７月１日現在の航空機の仮定された初期状態に基づいているスケジュールであって７月及び８月中の業務に関するスケジュールを生成するために１月中このシステムを使用し得る。しかしながらスケジューリングプロセスは極めて迅速であるので、これはスケジューリングの日に観測された状態である初期状態でリアルタイムスケジューリングツールとして使用され得る。このようにしてスケジューリングプロセスは、この日以降に飛行するための最も効率的なスケジュールを選択することによって航空会社が天候途絶などの実際のイベントに反応することを可能にできる。
【００７３】
上記の論議において結果関数は、ＣＴＭなどの財務結果の観点から記述されてきた。しかしながら非財務的結果も評価され得る。例えばある特定の要求に関する結果関数は、ローカル線フライトから乗り換える乗客の待ち時間を含み得る。待ち時間は、独立に評価されることができ、あるいは長時間の待ち合わせ時間によって不便を感じる乗客はより忠実でない顧客になるという航空会社の予想を反映する財務費用に変換され得る。このような費用は、最終的結果関数を生み出すためにＣＴＭから差し引かれ得る。
【００７４】
上記に論じられた計算は、プロセッサなどのコンピュータ及び資源データベースとスケジュール断片とを保持するためのメモリという通常の要素を含む通常の汎用コンピュータ５００（図１４）を使用して実行され得る。このコンピュータは、また、コンピュータ可読媒体５０１と、このような媒体に記憶されたプログラムであって上記に論じられたステップをコンピュータに実行させるように動作するプログラムとを含むプログラミング要素を含む。媒体５０１は、資源データベースとスケジュール断片とを記憶するために使用されるメモリとは別であり得る、又はそれと一体化され得る。例えばこの媒体５０１はディスク、テープ又はコンピュータに組み込まれた固体メモリであり得る。図１４に象徴的に示されているように、これらの計算を実行するための１つのシステムは、前に論じられた業務を実行するようにプログラムされたコンピュータ５００を含み；またスケジュールされるべき輸送業務において提供されるサービスを少なくともある程度定義する入力情報を供給するための１つ以上の入力ノード５０２も含む。図示の実施形態では入力ノード５０２は入力端末として示され、これらのノードは前述のような方法で処理される情報の要素のいずれをも供給するために使用され得る。本システムは更にコンピュータ５００からスケジュール断片に割り当てられる資源の少なくとも一部を表す情報を受信するように整えられた少なくとも１つの出力ノード５０６を含む。望ましくは、各出力ノード５０６は人間可読形式で、たとえばスクリーン表示装置上に又はプリントアウトでこの情報を表示又は出力するように整えられる。入力ノード５０２と出力ノード５０６は別々に示されているが、これらのノードは互いに結合されることも可能である。入力及び出力ノードは、これらのノードがコンピュータと同じ場所にある場合にはコンピュータ５００に直接接続され得る。ノード５０２、５０６は、コンピュータ５００から離れた場所に配置される可能性もあり、また任意の適当な通信手段によって、例えば図１４に概略的に図示されたインターネット５０４などのネットワークを介してローカル接続によって、コンピュータに接続され得る。コンピュータ５００は図１４において単一要素として示されているが、コンピュータ５００の要素は任意の適当な通信手段によって互いに接続される種々の場所に分散配置される可能性もある。また、入力及び出力ノードは望ましくはネットワーク又は即時通信の他の形によってコンピュータ５００に接続されるが、これは本質的ではない；入力及び出力ノードは、入力情報を供給して、出力情報をハードコピーで、又はこれらのノードとコンピュータとの間で物理的に搬送され得る適当な電子媒体上で受信するように整えられ得る。
【００７５】
コンピュータ入力ノード及び出力ノードは、航空機５０８などの輸送機材と空港などのターミナル５１０とを含む大きな輸送システムの一部を形成する。前述のようにスケジュールは物理的ルート５１２に対応するターミナル５１０の間のルートを定義する。入力及び出力ノードは、ターミナル５１０の１つ以上に、あるいは別の場所に配置され得る。
【００７６】
本発明は本明細書では特定の実施形態を参照しながら説明されてきたが、これらの実施形態が単に本発明の原理と応用を例示していることは理解されるべきである。したがって例示的実施形態に多くの修正が行われ得ること、及び他の配置構成が添付の特許請求の範囲によって定義されたような本発明の精神と範囲から逸脱せずに考案され得ることは理解されるべきである。
【図面の簡単な説明】
【００７７】
【図１】本発明の一実施形態による方法におけるあるいくつかの要素を概略的に描く流れ図である。
【図２】図１の方法における他の要素を概略的に描く部分的流れ図である。
【図３】前歴乗客荷重データのグラフ表示である。
【図４】図３のデータから要約されたある予測乗客荷重データの図式表示である。
【図５】図１及び２に示された方法の更なるステップを描く部分的流れ図である。
【図６】図５のステップの１つをより詳細に描くもう１つの部分的流れ図である。
【図７】図５に示された別のステップをより詳細に描く更なる部分的流れ図である。
【図８】図５に示された更なるステップをより詳細に描くなお別の部分的流れ図である。
【図９】期待乗客荷重対出発時刻の概略グラフである。
【図１０】図１〜９の方法で使用されるプロセスの概略図である。
【図１１】図１〜１０の方法で使用されるあるいくつかのステップを描く更なる部分的流れ図である。
【図１２】図１１に示されたステップの１つを描くなお別の部分的流れ図である。
【図１３】本発明の更なる実施形態によるプロセスを描く概略流れ図である。
【図１４】本発明の一実施形態で使用されるコンピュータシステムと輸送システムの概略表示である。
【図１】
2009527857.tif 000003
【図２】
2009527857.tif 000004
【図３】
2009527857.tif 000005
【図４】
2009527857.tif 000006
【図５】
2009527857.tif 000007
【図６】
2009527857.tif 000008
【図７】
2009527857.tif 000009
【図８】
2009527857.tif 000010
【図９】
2009527857.tif 000011
【図１０】
2009527857.tif 000012
【図１１】
2009527857.tif 000013
【図１２】
2009527857.tif 000014
【図１３】
2009527857.tif 000015
【図１４】
2009527857.tif 000016
【手続補正書】
【提出日】平成20年10月22日(2008.10.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
輸送業務に関するスケジュールを生成する、コンピュータ実現の方法であって；
（ａ）  各要求が出発地と目的地と出発時刻又は到着時刻とに関連する、複数の出発地と複数の目的地との間の輸送に関する複数の要求の順序付けられたリストを提供するステップと、
（ｂ）  スケジュール断片を設定するステップが利用可能な資源の１つ以上のリストから資源を割り当てることを含む、前記順序付けリストにおける要求の１つを満足させるためのスケジュール断片を設定すること、
（ｃ）  ステップ（ｂ）における資源の使用に基づいて修正された状態を示すために利用可能な資源の前記１つ以上のリストを修正すること、及び
（ｄ）  ステップ（ｂ）及び（ｃ）が前記リスト内の前記要求の前記順序にしたがって前記複数の要求に関して実行されるように、かつ、各要求に関するステップ（ｂ）が次の前の要求に関するステップ（ｃ）の結果から得られる状態を使用して実行されるように、ステップ（ｂ）及び（ｃ）を繰り返すこと、
のためにコンピュータを使用するステップと、
を含む方法。
【請求項２】
１つの要求に関して１つのスケジュール断片を設定する前記ステップは、前記要求内の出発時刻に近接した時刻の範囲内で出発時刻を調整することを含む、請求項１に記載の方法。
【請求項３】
１つのスケジュール断片を設定する前記ステップは、出発時刻を前記要求に関する荷重に関係付ける情報に基づいて少なくとも１つの結果を決定することを含む、請求項２に記載の方法。
【請求項４】
前記時刻の範囲は、他の要求に関して前に決定されたスケジュール断片に少なくともある程度基づいて選択される、請求項２に記載の方法。
【請求項５】
スケジュール断片を設定する前記ステップは、前記スケジュール断片に関する結果関数が１つ以上の基準を満足させるように実行される、請求項１又は請求項２に記載の方法。
【請求項６】
順序付けされたリストを提供する前記ステップは、複数のソートキーを確定するステップと、（ｉ）ある特定の要求が単一の輸送機材によって首尾よくサービス提供される一連の要求の１つであるかどうかを示す連続値、（ｉｉ）前記要求に関する財務値、及び（ｉｉｉ）前記要求に関する出発時刻又は到着時刻のうちの少なくとも１つを含む前記複数のソートキーにしたがって前記要求を順序付けすることとを含む、請求項１に記載の方法。
【請求項７】
輸送業務に関するスケジュールを生成する、コンピュータ実現の方法であって、
（ａ）  各要求が出発地と目的地と出発時刻及び到着時刻のうちの少なくとも１つとに関連する、複数の出発地と複数の目的地との間の輸送に関する複数の要求のリストと、複数の輸送機材と各輸送機材の場所対時間を指定する情報とを含む資源のリストとを提供するステップと、
（ｂ）  前記資源のリストにおいて識別される前記複数の輸送機材から１つの輸送機材を選択すること、
（ｃ）  前記要求の１つを選択するステップが前記要求を満足させるために前記選択された輸送機材を使用することに基づいて１セットの要求のうちの各要求に関する結果関数を評価するステップを含み、結果関数を評価するステップが前記選択された輸送機材の利用可能な時刻に少なくともある程度基づいて前記要求に関連する出発時刻に近接ずる時刻の範囲内で出発時刻を調整するステップを含む、前記要求の前記リストから前記要求の１つを選択すること、
（ｄ）  前記選択された輸送機材を前記選択された要求に割り当てることによって前記選択された要求を満足させるためのスケジュール断片を設定すること、
（ｅ）  ステップ（ｃ）における輸送機材の使用及び要求に基づいて修正された状態を示すために前記資源のリストと要求のリストとを修正すること、及び
（ｆ）  ステップ（ｂ）〜（ｅ）が前記複数の要求に関して実行されるように、かつ、各繰り返しに関するステップ（ｃ）が次の前の繰り返しに関するステップ（ｅ）の結果から生じる状態を使用して実行されるように、ステップ（ｂ）〜（ｅ）を繰り返すこと、
のためにコンピュータを使用するステップと
を含む方法。
【請求項８】
結果関数を評価する前記ステップは、出発時刻を前記要求に関する荷重に関係付ける情報に少なくともある程度基づいている、請求項７に記載の方法。
【請求項９】
要求を選択する前記ステップは、最善の結果関数を生み出すセットから前記要求を選択するステップを含む、請求項８に記載の方法。
【請求項１０】
前記結果関数は、前記スケジュール断片に関する１つ以上の財務値を含み、また前記方法は、前記スケジュールに関する総計財務値を導き出すために前記スケジュール断片に関する前記財務値を総計するステップを更に含む、請求項５又は請求項７又は請求項８又は請求項９に記載の方法。
【請求項１１】
各要求は、予測された荷重を含み、前記方法は、市場行動の１つ以上の推定値に少なくともある程度基づいて前記要求に関する前記予測荷重を導き出すステップを更に含み、前記方法は、市場行動の前記１つ以上の推定値を調整して、市場行動の前記調整された推定値を使用して前述のステップを繰り返すステップを更に含む、請求項１０に記載の方法。
【請求項１２】
市場行動の前記１つ以上の推定値を調整するステップは、輸送に関して課金される価格とこのような輸送において提供される価値とのうちの少なくとも１つの態様を調整するステップと、前記価格及び価値のうちの前記少なくとも１つの態様と輸送に関する要求との間の推定された関係を適用するステップとを含む、請求項１１に記載の方法。
【請求項１３】
価格と価値のうちの前記少なくとも１つの態様は、（ｉ）輸送に関して顧客によって支払われる金額と、（ｉｉ）輸送の購入と引き換えに顧客に提供される付随的サービスのレベルと、からなるグループから選択された価格と価値とのうちの少なくとも１つの態様を含む、請求項１２に記載の方法。
【請求項１４】
資源を修正するステップと、前記修正された資源を使用して前述のステップを繰り返すステップと、種々のセットの資源によって達成された前記総計財務値を比較するステップとを更に含む、請求項１０乃至１３のいずれか１項に記載の方法。
【請求項１５】
前記資源のリストは、特定の場所と時間において利用可能な資源のデータベースを含み、かつ、ある特定の要求に関するスケジュール断片を設定するステップは、（ｉ）前記特定の要求に関連する出発地において利用可能な前記資源から資源を差し引くステップと、（ｉｉ）前記要求に関連する業務の期待される完了時刻に続くある時刻に関する前記要求に関連する目的地において利用可能な資源のデータベースに移動資源を追加するステップとを含む、請求項１〜１４のいずれか１項に記載の方法。
【請求項１６】
前記要求に関連する所望の出発時刻に関して前記要求に関連する出発地において利用可能な資源が前記要求に関連する業務を可能にするために不十分であるかどうかを決定し、不十分であれば、移動資源がもう１つの場所に存在して前記所望の出発時刻での業務のために時間内に出発地に再配置され得るかどうかを前記データベースから決定するステップを更に含む、請求項１５に記載の方法。
【請求項１７】
移動資源が前記所望の出発時刻での業務のために前記出発地に時間内に再配置され得ない場合に、すべての資源が利用可能にされ得る前記所望の出発時刻より後の最も早い実行可能な出発時刻を決定して、出発時刻を前記最も早い実行可能な出発時刻に設定するステップを更に含む、請求項１６に記載の方法。
【請求項１８】
実行可能な出発時刻の範囲内の最も速い実行可能な出発時刻が見つけられない場合に、ある特定の資源の利用不可能性が、ある特定の要求に関するスケジュール断片を設定することを除外することを示すエラーメッセージを返すステップと、どの資源が前記輸送システムの業務を制約しているかを示す複数の前記エラーメッセージから情報を蓄積するステップと、前記蓄積された情報に応じて前記資源を調整するステップと、前記要求の少なくとも一部に関して前記調整された資源を使用して前述のステップを繰り返すこととを更に含む、請求項１７に記載の方法。
【請求項１９】
１つのスケジュールを形成するために前記スケジュール断片をコンパイルするステップと、前記スケジュールにしたがって前記輸送システムを運用するステップとを更に含む、請求項１乃至１４のいずれか１項に記載の方法。
【請求項２０】
（ａ）  輸送業務において提供されるサービスを少なくともある程度定義する入力情報を受信するように動作可能な少なくとも１つの入力ノードと、
（ｂ）  前記入力ノードによって受信された入力情報がコンピュータに供給されるように前記少なくとも１つの入力ノードに接続されたコンピュータであって、請求項１〜１８のいずれか１項に記載の方法を実行するために前記入力情報に応じて動作可能であるコンピュータと、
（ｃ）  スケジュール断片に割り当てられた前記資源の少なくとも一部を表す出力情報が少なくとも１つの出力ノードに供給されるように前記コンピュータに接続された少なくとも１つの出力ノードと、
を備える輸送業務のためのスケジューリングシステム。
【請求項２１】
（ａ）  複数の飛行機と、
（ｂ）  複数の空港と、
（ｃ）  請求項２０に記載のスケジューリングシステムと、
を備える輸送システムであって、
少なくとも１つの出力ノードは、前記空港の１つ以上に配置される、輸送システム。
【請求項２２】
請求項１乃至１８のいずれか１項に記載の方法をコンピュータに実行させるように動作するプログラムを記憶しているコンピュータ可読媒体を備えるコンピュータのためのプログラミング要素。
【国際調査報告】
2009527857.tif 000017
2009527857.tif 000018