JP6959320B2 - 情報を出力するための方法および装置 - Google Patents

Description

本開示の実施形態は、コンピューター技術の分野に関し、特に、情報を出力するための方法および装置に関する。

空港駐機スポットのスケジューリングアルゴリズムは、空港のフライトスケジュールに基づいてフライトに駐機スポットを割り当てるためのアルゴリズムである。従来の方法については、（１）中国の主要な空港は、主に経験に基づいてフライトに駐機スポットを割り当て、多くの手間とタイムがかかる。（２）一部の空港では貪欲アルゴリズムを採用して問題を解決しようとしているが、効果が満足できるようなものではなく、空港によって徐々に放棄されている。業界の主流の研究は主に整数計画法や発見的アルゴリズムに焦点を当てており、短期間で最適解または優良解を取得することを目指している。ただし、空港駐機スポットのスケジューリングは通常、複雑なビジネス上の問題を伴う多目的最適化の問題であるため、大規模な空港における複雑なシステムにおいては実装できた解決手段がない。

現在、空港はフライト混雑とフライト遅延など一連の運用安全と運用効率の問題に直面しているが、空港遅延の根本的な原因は、駐機スポット、滑走路、誘導路などのかなめとなる地上リソースが不十分であるか、有効に活用されていないことにある。したがって、空港における既存のかなめとなる地上リソースに対する科学的な利用と合理的な配分により、民間航空産業の急速な発展と空港施設リソースの不足の間の矛盾を軽減することができる。

実務で乗客の正確な歩行距離や搭乗/乗換に必要な時間などを取得することの困難さなど、既存の駐機スポット割り当て戦略で使用されるいくつかの変数では、誤ったモデル解を引き起こす可能性がある。フライトエリアの地上運用部分はほとんど考慮せずに割り当てた結果、滑走路の競合、誘導路の競合、およびフライトの遅延を引き起こし、地上運用効率を低下させる可能性がある。現在、こうした競合の解決策は主に手動介入に依存している。民間航空業界が急速に発展し、航空ビジネスが繁忙を極め、駐機スポットが相対的に不足している現状では、かかる競合が頻繁に発生しており、手動介入のみに頼るだけでは十分とはいえない。

本開示の実施形態は、情報を出力する方法および装置を提案する。

第１の態様では、本開示の実施例は、フライト情報、駐機スポット情報、誘導路情報、および滑走経路を取得するステップと、フライト情報、駐機スポット情報、誘導路情報、および滑走経路に基づいて、目標、決定変数、および制約条件を含む整数計画モデルを構築するステップと、制約条件に基づいて整数計画モデルを最適化するステップと、最適化された整数計画モデルを解き、フライトと駐機スポットの対応関係表を取得して出力するステップと、を含む情報を出力するための方法を提供する。

いくつかの実施例において、該方法は、ターゲットフライトの調整要求の受信に対応して、一部の駐機スポットをランダムに選択して再配置リストに追加するステップと、フライトと駐機スポットの対応関係表におけるランダムに選択された一部の駐機スポットと競合する駐機スポットを再配置リストに追加するステップと、再配置リストにかかわる駐機スポット情報と関連するフライト情報、誘導路情報と滑走経路に基づいて、ローカル整数計画モデルを構築するステップと、ローカル整数計画モデルを解き、ローカル範囲最適解を取得し、フライトと駐機スポットの対応関係表を更新するステップと、をさらに含む

いくつかの実施例において、該方法は、駐機スポットを割り当てられていないフライトには、貪欲アルゴリズムによって駐機スポットを割り当てるステップをさらに含む。

いくつかの実施例において、該方法は、フライトと駐機スポットの対応関係表の効果を評価するステップをさらに含む。

いくつかの実施例において、決定変数は、フライト占用駐機スポット識別子、フライトプッシュアウト競合識別子、航空会社の搭乗橋使用率目標の達成率、誘導路占用識別子、フライトの属性、駐機スポットの属性、フライトの到着時刻、フライトの出発時刻、フライトの搭乗開始時刻、フライトの搭乗終了時刻、フライトの降機開始時刻、フライトの降機終了時刻、近い駐機スポット識別子、フライトの乗客数、搭乗・降機客競合識別子、駐機スポットと滑走路間の距離、仮駐機スポット識別子、航空会社の搭乗橋使用率目標識別子、競合駐機スポット識別子のうちの少なくとも１つを含む。

いくつかの実施例において、制約条件は、属性の制約、ＶＩＰフライトの制約、スペースの制約、タイムの制約、競合駐機スポットの制約、搭乗・降機客競合の制約、プッシュアウト競合の制約のうちの少なくとも１つを含む。

いくつかの実施例において、目標は、フライトの搭乗橋使用率、旅客の搭乗橋使用率、航空会社の搭乗橋使用率目標の達成率、プッシュアウトの競合率、滑走距離率、近い駐機スポットの時間使用率、仮駐機スポットの使用率のうちの少なくとも１つの加重和である。

いくつかの実施例において、制約条件に基づいて整数計画モデルを最適化するステップは、駐機スポット競合制約の最適化、プッシュアウト競合制約の最適化、競合駐機スポット制約の最適化、航空会社の搭乗橋使用率の区分的線形変換のうちの少なくとも１つを含む。

いくつかの実施例において、最適化された整数計画モデルを解くステップは、分枝限定法を使用して最適化された整数計画モデルを解くことを含む。

第２の態様では、本開示の実施例は、フライト情報、駐機スポット情報、誘導路情報、および滑走経路を取得するように構成された取得ユニットと、フライト情報、駐機スポット情報、誘導路情報、および滑走経路に基づいて、目標、決定変数、および制約条件を含む整数計画モデルを構築するように構成された構築ユニットと、制約条件に基づいて整数計画モデルを最適化するように構成された最適化ユニットと、最適化された整数計画モデルを解き、フライトと駐機スポットの対応関係表を取得して出力するように構成された解決ユニットと、を含む情報を出力するための装置を提供する。

いくつかの実施例において、該装置は調整ユニットをさらに含み、調整ユニットは、ターゲットフライトの調整要求の受信に対応して、一部の駐機スポットをランダムに選択して再配置リストに追加し、フライトと駐機スポットの対応関係表におけるランダムに選択された一部の駐機スポットと競合する駐機スポットを再配置リストに追加し、再配置リストにかかわる駐機スポット情報と関連するフライト情報、誘導路情報と滑走経路に基づいて、ローカル整数計画モデルを構築し、ローカル整数計画モデルを解き、ローカル範囲最適解を取得し、フライトと駐機スポットの対応関係表を更新するように構成されている。

いくつかの実施例において、調整ユニットはさらに、駐機スポットを割り当てられていないフライトには、貪欲アルゴリズムによって駐機スポットを割り当てるように構成されている。

いくつかの実施例において、該装置は、前記フライトと駐機スポットの対応関係表の効果を評価するように構成された評価ユニットをさらに含む。

いくつかの実施例において、決定変数は、フライト占用駐機スポット識別子、フライトプッシュアウト競合識別子、航空会社の搭乗橋使用率目標の達成率、誘導路占用識別子、フライトの属性、駐機スポットの属性、フライトの到着時刻、フライトの出発時刻、フライトの搭乗開始時刻、フライトの搭乗終了時刻、フライトの降機開始時刻、フライトの降機終了時刻、近い駐機スポット識別子、フライトの乗客数、搭乗・降機客競合識別子、駐機スポットと滑走路間の距離、仮駐機スポット識別子、航空会社の搭乗橋使用率目標識別子、競合駐機スポット識別子のうちの少なくとも１つを含む。

いくつかの実施例において、制約条件は、属性の制約、ＶＩＰフライトの制約、スペースの制約、タイムの制約、競合駐機スポットの制約、搭乗・降機客競合の制約、プッシュアウト競合の制約のうちの少なくとも１つを含む。

いくつかの実施例において、目標は、フライトの搭乗橋使用率、旅客の搭乗橋使用率、航空会社の搭乗橋使用率目標の達成率、プッシュアウトの競合率、滑走距離率、近い駐機スポットの時間使用率、仮駐機スポットの使用率のうちの少なくとも１つの加重和である。

いくつかの実施例において、制約条件に基づいて前記整数計画モデルを最適化するステップは、駐機スポット競合制約の最適化、プッシュアウト競合制約の最適化、競合駐機スポット制約の最適化、航空会社の搭乗橋使用率の区分的線形変換のうちの少なくとも１つを含む。

いくつかの実施例において、解決ユニットはさらに、分枝限定法を使用して最適化された整数計画モデルを解くように構成されている。

第３の態様では、本開示の実施例は、１つまたは複数のプロセッサと、１つまたは複数のプログラムが格納されている記憶装置と、を含み、１つまたは複数のプログラムが１つまたは複数のプロセッサによって実行されると、１つまたは複数のプロセッサに第１の態様のいずれかに記載の方法を実施させる電子機器を提供する。

第４の態様では、本開示の実施例は、コンピュータープログラムが格納されているコンピューター可読媒体であって、プログラムがプロセッサによって実行されると、第１の態様のいずれかに記載の方法を実施するコンピューター可読媒体を提供する。

本開示の実施形態は、情報を出力する方法および装置を提供し、駐機スポット割り当て問題を整数０〜１計画問題に変換することにより数学的モデリングを行う。アルゴリズムレベルで駐機スポットのスケジューリングを解決することにより、空港の運用効率と乗客の満足度を向上させることができる。数理計画法は、発見的アルゴリズムと比較して、最適解を取得することができる。

本開示の他の特徴、目的、および利点は、添付の図面を参照しながら行った非限定的な実施形態に関する詳細な説明から、より明らかになるであろう。
本開示の実施形態が適用され得る例示的なシステムアーキテクチャ図である。 本開示にかかわる情報を出力するための方法の一実施形態のフローチャートである。 本開示にかかわる情報を出力するための方法における駐機スポット競合の制約の最適化の概略図である。 本開示にかかわる情報を出力するための方法における駐機スポット競合の制約の最適化の概略図である。 本開示にかかわる情報を出力するための方法の別の実施形態のフローチャートである。 本開示にかかわる情報を出力するための方法の効果図である。 本開示にかかわる情報を出力するための装置の一実施形態の概略構造図である。 本開示の実施形態の実施に適する電子機器のコンピューターシステムの概略構造図である。

以下、添付の図面と実施形態を参照しながら、本開示についてさらに詳細に説明する。本明細書に記載される特定の実施形態は、本発明ではなく本発明の単なる例示であることを理解されたい。また、説明の便宜上、関連する発明に関連する部分しか図面に示されていないことにも留意されたい。

本開示の実施形態と実施形態の特徴は、矛盾しない前提では、互いに組み合わせることができることに留意されたい。以下、図面と実施形態を参照して、本開示を詳細に説明する。

図１は、本開示情報を出力する方法、または情報を出力するための装置が適用され得る実施形態の例示的なシステムアーキテクチャ１００を示している。

図１に示されるように、システムアーキテクチャ１００は、航空機１０１、１０２、１０３と、サーバー１０４と、を含み得る。航空機１０１、１０２、１０３とサーバー１０４の間には、通信リンクを提供するための無線ネットワークがある。

航空機１０１、１０２、１０３は、ネットワークを介してサーバー１０４と対話して、メッセージなどを受信または送信する。

サーバー１０４は、航空機の離着陸を制御するために、空港の塔に設置されることができる。サーバーは事前に、各フライトに駐機スポットを割り当ててから、フライトに通知することができる。遅延またはキャンセルのためにフライトが時間どおりに空港に到着できない場合、航空機はサーバーに推定到着時刻を送信し、サーバーは駐機スポット割り当てを再調整することができる。サーバーは、フライトの実際の発着時刻に基づいて定期的に駐機スポットを再割り当てすることもできる。サーバーによって割り当てられる駐機スポットは、遠い駐機スポットと近い駐機スポットに分けられる。遠い駐機スポットとは、搭乗橋を介して直接搭乗できない駐機スポットを指す。通常は、シャトルバスを介して航空機まで移動し、そしてタラップ車を介して航空機に搭乗する。近い駐機スポットの場合は、航空機が直接ターミナルビルの前に駐機され、搭乗橋とドッキングされた後、ターミナルと航空機とが連通される。搭乗橋には階段がない。搭乗橋とは、搭乗時に航空機の搭乗口につながる部分を指す。航空機が遠い駐機スポットに駐機されている場合、空港ターミナルと遠い駐機スポットにある航空機との間を往復するシャトルバスが必要となる。

サーバーはハードウェアであってもよく、ソフトウェアであってもよいことに留意されたい。サーバーはハードウェアである場合、複数のサーバーからなる分散サーバークラスターとして実施してもよく、単一のサーバーとして実施してもよい。サーバーはソフトウェアである場合、複数のソフトウェアまたはソフトウェアモジュール（例えば、分散サービスを提供するための複数のソフトウェアまたはソフトウェアモジュール）として実施してもよく、単一のソフトウェアまたはソフトウェアモジュールとして実施してもよい。これは特に限定されない。

本開示の実施形態によって提供される情報を出力する方法は一般的にサーバー１０４によって実行されることに留意されたい。したがって、情報を出力するための装置は一般的にサーバー１０４に配置される。

図１の航空機、ネットワーク、およびサーバーの数は単なる例示にすぎないことを理解されたい。実施のニーズに応じて、任意の数の航空機、ネットワーク、およびサーバーが存在し得る。

さらに図２を参照すると、本開示にかかわる情報を出力するための方法の一実施形態のフロー２００が示されている。該情報を出力するための方法には、次のステップ（ステップ２０１〜２０３）が含まれている。

ステップ２０１：フライト情報、駐機スポット情報、誘導路情報、および滑走経路を取得する。

本実施形態では、情報を出力するための方法の実行主体（例えば、図１に示されるサーバー）は、予め記憶されたフライト情報、駐機スポット情報、誘導路情報、および滑走経路を取得することができる。該フライト情報は、航空会社（以下、「航空社」という）、フライトの種類（国際線または国内線）、航空機のモデル、タスク（乗客または貨物）、フライトの到着時刻、フライトの出発時刻、フライトの搭乗開始時刻、フライトの搭乗終了時刻、フライトの降機開始時刻、フライトの降機終了時刻の内の少なくとも１つを含み得る。航空会社、フライトの種類、航空機のモデル、タスクはいずれもフライトの属性である。駐機スポット情報は、駐機スポットの位置（遠い駐機スポットまたは近い駐機スポット）、駐機スポットの種類（国際線または国内線）、駐機可能な航空機のモデル、用途（公務または民間航空）の内の少なくとも１つを含み得る。駐機スポット情報は、駐機スポット属性とも呼ばれる。誘導路情報は、駐機スポットと誘導路の対応関係を表す。複数の駐機スポットは１つの誘導路を共用することができる。誘導路は、駐機スポットに滑り込むことにも、駐機スポットから滑り出すことにも使用できる。誘導路情報はプッシュアウトの競合の判断に使用できる。滑走経路とは、駐機スポットから滑走路までの滑走距離を指す。

任意選択で、滑走路の運用モード（例えば、東から離陸、西から着陸）を取得することもできる。滑走路の運用モードの切り替えに対応して滑走経路などの情報を調整する。

ステップ２０２：フライト情報、駐機スポット情報、誘導路情報、および滑走経路に基づいて、整数計画モデルを構築する。

本実施形態では、整数計画とは、計画中の変数（全部または一部）が整数に制限されることを意味する。整数計画モデルは、目標、決定変数、および制約条件を含む。０−１計画は整数計画の特殊なケースであり、その変数が０または１に限定される。以下、例をあげて整数０−１計画問題を構築する。

１．決定変数
Ｎを航空機の総数（到着フライトの番号と出発フライトの番号とからなる）とし、Ｍを駐機スポットの総数とし、Ｒを誘導路の総数とし、Ｌを航空社の総数とする。以下、ｉ∈[０，Ｎ]、ｊ∈[０，Ｍ]、ｋ∈[０，Ｒ]、ｌ∈[０，Ｌ]。（１）、（２）、（３）は最終必須変数である。（４）における変数は事前に取得できる不変定数である。

（１）フライトｉが駐機スポットｊを占用している場合は、次のように表される。
Ｘ_ｉ，ｊはフライト占用駐機スポットの識別子を表す。該値が１である場合、占用を意味し、該値が０である場合、不占用を意味する。

２）フライトiがその他のフライトのプッシュアウトと競合するかどうかは、次のように表される。
Ｚ_iはフライトプッシュアウト競合の識別子を表す。該値が１である場合、競合を意味し、該値が０である場合、不競合を意味する。プッシュアウト競合とは、１つのフライトが別の１つのフライトのプッシュアウトを妨げるか、別の１つのフライトのプッシュアウトにより該フライトが遅延になることを意味する。

（３）Ｂ_ｌは航空社ｌの搭乗橋使用率目標の達成率を表す。
航空社の搭乗橋使用率が搭乗橋使用率目標の上限と下限の間にある場合、Ｂ_ｌの値が１である。航空社の搭乗橋使用率が搭乗橋使用率目標の上限を上回るか、下限を下回る場合、Ｂ_ｌの値が１未満の実数である。フライトの搭乗橋使用率とは、フライトがターミナルビルの搭乗橋の近傍に駐機されており、旅客がシャトルバスに乗ることなく直接搭乗ゲートから搭乗する確率を指す。

（４）ＹＩＮ_ｊ，ｋは、駐機スポットｊが滑り込み誘導路ｋを占用しているかどうかを表す。ＹＯＵＴ_ｊ，ｋは、駐機スポットｊが滑り出し誘導路ｋを占用しているかどうかを表す。Ｐ_ｉは、フライトｉの属性を表す。Ｐ_ｊは、駐機スポットが要求する属性を表す。ｔｉｎ_ｉは、フライトｉの到着時刻を表す。ｔｏｕｔ_ｉは、フライトｉの出発時刻を表す。ｔ_ｐ_ｉｎ_ｓ_ｉは、搭乗開始時刻を表す。ｔ_ｐ_ｉｎ_ｅ_ｉは、搭乗終了時刻を表す。ｔ_ｐ_ｏｕｔ_ｓ_ｉは、降機開始時刻を表す。ｔ_ｐ_ｏｕｔ_ｅ_ｉは、降機終了時刻を表す。ｂ_ｊは駐機スポットjが近い駐機スポットであるかどうかを表す。ｐ_ｉは、フライトｉの旅客数を表す。ＢＣ_{ｉ１，ｉ２，ｉ３}は、フライトｉ_１、ｉ_２が同時に搭乗するときに、ｉ_３が同時に降機できないかどうかを表す。ｄ_ｊ は、駐機スポットｊから滑走路までの距離を表す。ｔ_ｊは、駐機スポットｊが仮の駐機スポットであるかどうかを表す。Ｔ_ｌは、航空社ｌが航空社の搭乗橋使用率目標を設定しているかどうかを表す。Ｃ_{ｊ１,ｊ２}は、ｊ_１とｊ_２は競合駐機スポット（例えば、親子駐機スポット）であるかどうかを表す。

２．制約条件
（１）属性の制約：国際線／国内線の属性の制約（フライトの国際線／国内線の属性に対する駐機スポットの要件）、タスクの制約（フライトのタスクに対する駐機スポットの要件）、航空社の制約（フライトの航空社に対する駐機スポットの要件）、航空機のモデルの制約（航空機のサイズに対する駐機スポットの要件）

フライトの属性と駐機スポットの属性とが一致しない。例えば、国内線フライトは国際線の駐機スポットに駐機できない。

（２）ＶＩＰフライトの制約

ここで、ｉはＶＩＰフライトである。

ＶＩＰとは、重要な旅客を指す。

（３）１つのフライトは１つの駐機スポットにしか配置できない（スペースの制約）

（４）同一の時点で同一の駐機スポットに１つのフライトしか駐機できない（タイムの制約）。次の式は同時に成立できない。

（５）競合駐機スポットを同時に使用できない。次の式は同時に成立できない。

競合駐機スポットの典型的な例は、親子駐機スポットである。１つの親駐機スポットは、２つ以上の子駐機スポットから構成される。子駐機スポットにフライトが割り当てられている場合、親駐機スポットと競合するため、親駐機スポットにフライトを割り当てることはできない。同様に、親駐機スポットにフライトが割り当てられている場合、子駐機スポットにフライトを割り当てることはできない。ただし、子駐機スポットと子駐機スポットとは競合しない。

（６）搭乗・降機客競合の制約。次の式は同時に成立できない。

（７）誘導路プッシュアウト競合の制約。Ｚ_ｉ１、Ｚ_ｉ２は、プッシュアウト競合のフライトｉ１とｉ２のペアを表す。
フライトｉ１の滑り込みとフライトｉ２の滑り出しの間の競合：

フライトｉ１の滑り出しとフライトｉ２の滑り込みの間の競合：

フライトｉ１の滑り出しとフライトｉ２の滑り出しの間の競合：

はフライトｉ１の滑り込み時刻とフライトｉ２の滑り出し時刻の間の競合を表す。

はフライトｉ１の滑り出し時刻とフライトｉ２の滑り込み時刻の間の競合を表す。

はフライトｉ１の滑り出し時刻とフライトｉ２の滑り出し時刻の間の競合を表す。

３．目標
（１）フライトの搭乗橋使用率

（２）旅客の搭乗橋使用率

（３）航空会社の搭乗橋使用率目標の達成率

（４）プッシュアウト競合率

（５）滑走距離率

ここで、Ｃｏｎｓｔａｎｔ１は、予め設定された最長距離の長さである。

（６）近い駐機スポットの時間使用率

Ｃｏｎｓｔａｎｔ２は、予め設定された時間帯の長さ（例えば、２４時間）である。

（７）仮の駐機スポットの使用率

以上をまとめると、目的関数が次のように設定される。

最後の目標は、ｍａｘ（ｈ（ｘ））時のフライトと駐機スポットとの間の対応関係を解くことである。

ステップ２０３：制約条件に基づいて、整数計画モデルを最適化する。

本実施形態では、整数計画法を解くときに採用しているのは、ほとんど分枝限定法である。ここで、主に２つの角度からモデルを最適化する。

（１）制約を減らす。複数の制約を１つの制約にマージできる場合、線形計画法を解くときの速度が向上するほか、メモリの消費も削減できる。

（２）境界をより厳しくする。制約ａと制約ｂが整数計画モデルでは同等であるが、線形計画モデルではａがｂを導出できるのに対して、ｂがａを導出できない場合、ａはｂよりも厳しい。例えば、「ａ＋ｂ≦１、ａ＋ｃ≦１、ｂ＋ｃ≦１」であれば、ａ、ｂ、ｃとも０〜１の整数である場合、「ａ＋ｂ＋ｃ≦１」という結論を出せる。上記の２つの観点からこの最適化を検討する。第１の観点からすると、制約が３から１に変更された場合、線形計画法の解決に有益である。第２の観点からすると、ａ、ｂ、ｃとも実数である場合、前の３つの制約は後の１つの制約を導出できない。このとき、「ａ＋ｂ＋ｃ≦１」でこの問題を説明すると、線形計画法の解と整数計画法の解との間の距離が前の解決手段のそれよりも小さく、整数計画法の解決に有益である。したがって、この最適化により、線形計画法の速度が向上するだけでなく、整数解を見つける難易度も下がる。

具体的な最適化のステップは、次のとおりである。
（１）駐機スポット競合の制約の最適化：
駐機スポット競合の制約を例にとると、同一の時点で同一の駐機スポットに１つのフライトしか駐機できないため、時間的にダブっている２つのフライト同士は同一の駐機スポットに駐機不可である。これらの競合するフライトは、実際には、フライト１とフライト２の時刻の競合、フライト１とフライト３の時刻の競合、フライト１とフライト４の時刻の競合、フライト２とフライト３の時刻の競合、フライト２とフライト４の時刻の競合、フライト３とフライト４の時刻の競合など、いくつかのループを形成している。つまり、１つの完全グラフ（図３ａ参照）を形成している。エッジは競合を表す。

したがって、上記の制約条件は、「フライト１、フライト２、フライト３、フライト４のうちのいずれか１つしか特定の駐機スポットに駐機できないこと」に変換できる。数は６から１に削減される。如何にして図から各フライトの最大完全サブグラフを見つけるかは、またＮＰＣ（Ｎｏｎ-ｄｅｔｅｒｍｉｎｉｓｔｉｃ Ｐｏｌｙｎｏｍｉａｌ ｃｏｍｐｌｅｔｅ、非決定性多項式完全）問題となる。そのため、引き続き最適化をし、時間を次元として考察する。特定の時点で複数のフライトの時刻が競合する場合、これらのフライトの内のいずれか１つしか特定の駐機スポットに駐機できない。時間軸で絶え間なく進むにつれて、不断に新しい競合のグループを取得しつつ、前の小さな競合のグループを削除する。例えば、フライト１とフライト２の競合が最初に見つかった場合、それらを競合グループに追加する。その後、フライト１、フライト２、およびフライト３が同時に競合する場合、前者の競合は後者のサブセットになる。この場合、フライト１とフライト２の競合グループを削除し、現在の最大の競合グループのみを残し、このように繰り返す。

図３ｂに示されるように、時間軸で分割する。分割されたフライトは１つの競合グループを形成し、例えば、分割線１がフライト１、フライト２、フライト３及びフライト４からなる競合グループを形成可能である。また、１つの分割線が競合グループを生成できる場合、必然的に競合グループ内の特定のフライトの開始時刻を通過する１本の分割線が同じ競合グループを取得できると導出することができる。上記のように、分割線２が１つの競合グループ（フライト１、フライト２、フライト３、フライト４）を取得できる場合、必然的に１本の分割線（本実施形態では、分割線１となる）が特定のフライト（本実施形態では、フライト４）の開始時刻を通過し、同じ競合グループを取得できる。

最適化前のフライトｉ１の駐機スポット競合の制約：
Ｘ_{ｉ１,ｊ１}＋Ｘ_{ｉ２,ｊ１}≦１;Ｘ_{ｉ１,ｊ１}＋Ｘ_{ｉ３,ｊ１}≦１;Ｘ_{ｉ１,ｊ１}＋Ｘ_{ｉ４,ｊ１}≦１;

最適化後、制約は次のように縮小される：
Ｘ_{ｉ１,ｊ１}＋(Ｘ_{ｉ２,ｊ１}＋Ｘ_{ｉ３,ｊ１}＋Ｘ_{ｉ４,ｊ１})/３≦１;

空港業務を踏まえて導出した推論に基づいて、各フライトの到着時刻を辿り分割線として競合グループを探せばよく、時間の複雑さは桁違いに減少される。

（２）プッシュアウト競合の制約の最適化：
プッシュアウト競合についても、時間の次元から考察することができる。同一の時点で同一の誘導路を占用してプッシュアウト／プッシュインされるフライトは互いにプッシュアウト競合が起こることがある。そのため、同様にこれらのプッシュアウト競合の制約をマージして制約を減らすこともできる。

例えば、フライトｉ１は駐機スポットｊ１に駐機され、フライトｉ２は駐機スポットｊ２に駐機され、フライトｉ３は駐機スポットｊ３に駐機されている。フライトｉ１、ｉ２、ｉ３はプッシュアウト／プッシュインされる時刻がダブっている。また、駐機スポットｊ１、ｊ２、ｊ３は同一の誘導路ｋを占用している。この場合、フライトｉ１の競合判定について、従来では「Ｚ_ｉ１＋１≧Ｘ_{ｉ１,ｊ１}＋Ｘ_{ｉ２,ｊ２}」、「Ｚ_ｉ１＋１≧Ｘ_{ｉ１,ｊ１}＋Ｘ_{ｉ３,ｊ３}」など複数の異なる式があるが、実際には、「Ｚ_ｉ１＋１≧Ｘ_{ｉ１,ｊ１}＋(Ｘ_{ｉ２,ｊ２} ОＲ Ｘ_{ｉ３，ｊ３} ОＲ …)」という１つの式に簡素化することができる。

つまり、Ｘ_{ｉ２,ｊ２}、Ｘ_{ｉ３,ｊ３}などの駐機スキームのいずれか１つさえ成立すれば、フライトｉ１と競合して同一の誘導路ｋを占用することになるため、フライトｉ１に誘導路競合が発生する。ここのОＲ演算は、次のように書くことができる。
Ｚ_ｉ１＋１≧Ｘ_{ｉ１,ｊ１}＋（Ｘ_{ｉ２,ｊ２}＋Ｘ_{ｉ３,ｊ３}＋…）/ｎ

うち、Ｚ_ｉ１、Ｘ_{ｉ１,ｊ１}、Ｘ_{ｉ２,ｊ２}、Ｘ_{ｉ３,ｊ３}…はいずれも０〜１の変数である。Ｚ_ｉ１は、フライトｉ１にプッシュアウト競合が発生したことを意味する。ｎは、分子の数である。この式においては、Ｘ_{ｉ１,ｊ１}が１であり、かつ括弧内のＸ_{ｉ２,ｊ２}、Ｘ_{ｉ３,ｊ３}などの変数のいずれか１つが１である場合、Ｚ_ｉ１は１でなければならない。たとえＸ_{ｉ１,ｊ１}、Ｘ_{ｉ２,ｊ２}、Ｘ_{ｉ３,ｊ３}などの変数はいずれも１であるとしても、Ｚ_ｉ１は１でなければならない。ｎが後続の変数の数以上である限り、この式は成立する。ｎを変数の数に設定した場合、不等式の境界をより厳しくすることができる。

さらに、１つのフライトは駐機スポットに滑り込むときと駐機スポットから滑り出すときにはそれぞれ誘導路を１回占用するため、誘導路を２回占有する変数をマージして不等式におけるОＲというアイテムに配置することができる。

（３）競合駐機スポット（例えば、親子駐機スポット）の制約の最適化：
競合駐機スポットの制約は、駐機スポットフライト競合の制約に似ている。駐機スポットフライト競合の制約とは、タイム競合フライトが同じ駐機スポットに駐機されることを意味する。競合駐機スポットの制約とは、タイム競合フライトが競合駐機スポットに駐機されることを意味する。

フライトｉ１とｉ２、ｉ３、ｉ４とはタイム競合である場合、駐機スポットｊ１とｊ２、ｊ３、ｊ４とは駐機スポット競合関係にある。ｊ１は親駐機スポット、ｊ２〜ｊ４は子駐機スポットである場合、
最適化前のフライトｉ１の駐機スポット競合の制約：
Ｘ_{ｉ１,ｊ１}＋Ｘ_{ｉ２,ｊ２}≦１;Ｘ_{ｉ１,ｊ１}＋Ｘ_{ｉ３,ｊ３}≦１;Ｘ_{ｉ１,ｊ１}＋Ｘ_{ｉ４,ｊ４}≦１；
最適化後、制約は１に削減される：
Ｘ_{ｉ１,ｊ１}＋(Ｘ_{ｉ２,ｊ２}＋Ｘ_{ｉ３,ｊ３}＋Ｘ_{ｉ４,ｊ４})/３≦１

（４）航空社の搭乗橋使用率の区分的線形変換：
航空社の搭乗橋使用率は、非線形の指標である。それが設定された区間を下回る場合、指標が引き続き上がるように励まされ、設定された区間を上回る場合、指標が下がるように罰せられる。最終的に、搭乗橋使用率が設定された区間内にあるようになってはじめて、設定された目標を達成したといえる。この問題を最適化するために、非線形を区分的線形に変換して、モデルの解決プロセスを簡素化する。

ステップ２０４：最適化された整数計画モデルを解き、フライトと駐機スポットの対応関係表を取得して出力する。

本実施形態では、整数計画法を解くための一般的な方法は分枝限定法（ｂｒａｎｃｈ ａｎｄ ｂｏｕｎｄ）であるが、様々な特別な問題を解決するには、いくつかの特別な方法が採用される。例えば、割り当て問題を解決するには、ハンガリーのアルゴリズムを採用すると便利である。分枝限定法は、整数計画問題を解くために最も一般的に使用されるアルゴリズムである。この方法は、純粋な整数計画法だけでなく、混合整数計画法の問題も解決できる。分枝限定法は検索と反復の方法であり、異なる枝変数と副問題を選択して分枝操作する。

本開示の上記実施形態は、実際の空港業務における複数の目標を整数計画モデルに統合することにより、非線形指標を区分的線形に変換する方法を提供する。モデルを最適化することにより、５分以内に最適解を得られる。

さらに図４を参照すると、情報を出力するための方法の別の実施形態のフロー４００が示されている。情報を出力するための方法のフロー４００は、以下のステップ（ステップ４０１〜４０８）を含む。

ステップ４０１：フライト情報、駐機スポット情報、誘導路情報、および滑走経路を取得する。

ステップ４０２：フライト情報、駐機スポット情報、誘導路情報、および滑走経路に基づいて、整数計画モデルを構築する。

ステップ４０３：制約条件に基づいて、整数計画モデルを最適化する。

ステップ４０４：最適化された整数計画モデルを解き、フライトと駐機スポットの対応関係表を取得して出力する。

ステップ４０１〜４０４は、ステップ２０１〜２０４と実質的に同じであるため、再度説明しない。

ステップ４０５：ターゲットフライトの調整要求の受信に対応して、一部の駐機スポットをランダムに選択して再配置リストに追加する。

本実施形態では、調整要求は、調整すべきフライトリストＶと、調整すべきフライトが所在する駐機スポットリストＰすなわち再配置リストと、を含む。空港内の既存の駐機スポットから一部の駐機スポットをランダムに選択してＰに追加する。

ステップ４０６：フライトと駐機スポットの対応関係表におけるランダムに選択された一部の駐機スポットと競合する駐機スポットを、再配置リストに追加する。

本実施形態では、Ｐを通じて、Ｐの各ノードの、割り当てられたフライトと駐機スポットの対応関係表Ｐにおける親子競合駐機スポット、タイム競合駐機スポット、スペース競合駐機スポット、および搭乗・降機客競合駐機スポットなどの各競合駐機スポットを辿る。これらの競合駐機スポットがＰに含まれていない場合、Ｐに追加する。最終的に形成されたＰは、ローカルに調整すべきすべての駐機スポットのリストである。予め影響を受ける駐機スポットとランダムに選択された一部の駐機スポットに基づいて、駐機スポット関係連結グラフを構築することができる。それにより競合駐機スポットの特定が容易になる。

ステップ４０７：再配置リストにかかわる駐機スポット情報と関連するフライト情報、誘導路情報と滑走経路に基づいて、ローカル整数計画モデルを構築する。

本実施形態では、ステップ４０６で取得した再配置リストにかかわる駐機スポット情報およびこれらの駐機スポットに割り当てられたフライトのフライト情報を取得し、再び誘導路情報と滑走経路を使用してローカル整数計画モデルを構築する。具体的なプロセスはステップ２０２と同じであるため、再度説明しない。

ステップ４０８：ローカル整数計画モデルを解き、ローカル範囲の最適解を得て、フライトと駐機スポットの対応関係表を更新する。

本実施形態では、同様に分枝限定法を使用してローカル整数計画モデルを解き、ローカル範囲の最適解を得る。次いで、ステップ２０４で生成されたフライトと駐機スポットの対応関係表とを対照して、変更された内容を更新する。

本実施形態のいくつかのオプションの実施方法では、このとき、駐機スポットを割り当てられていないフライトがあり得る。最後に、駐機スポットを割り当てられていないフライトが特定の駐機スポットを割り当てられるまで貪欲アルゴリズムによって配置される。これで、リアルタイム調整が終了し、リアルタイム調整プロセス全体が５秒以内に完了することができる。貪欲アルゴリズム（「欲張りアルゴリズム」とも呼ばれる）とは、問題を解決するときに、常に現時点で最良の選択をすることを意味する。つまり、全体的な最適性を考慮しないで、得られたのはある意味でのローカル最適解である。

図４から分かるように、本実施形態にかかわる情報を出力するための方法のフロー４００は、図２に対応する実施形態と比較して、リアルタイムで駐機スポットを調整するステップを具現化している。したがって、本実施形態で説明された解決手段は、貪欲と計画の統合という構想を通じて、リアルタイム調整戦略の設計を実行している。駐機スポット関係連結グラフを使用してローカルに調整された駐機スポットリストを構築することにより、リアルタイム調整全体が５秒以内に完了することができる。

本実施形態のいくつかのオプションの実施方法では、該方法は、前記フライトと駐機スポットの対応関係表の効果を評価するステップをさらに含む。Ｔ日の夜間フライトで初期化してＴ＋１日のフライトをスケジュールし、特定の大規模な空港の実際の月間ディスパッチデータと比較してみると、次のようになる。

近い駐機スポットのフライト間隔分布の統計的比較は、図５に示している。

近い駐機スポットのフライト間隔分布から分かるように、手動割り当てによるフライト間隔の２極（最大と最小）の分布は、自動割り当てによるフライト間隔のそれよりもはるかに深刻である。近い駐機スポットの浪費が目立つ。自動割り当てに切り替えられたあと、一部の近い駐機スポットにおける長すぎたフライト間隔が明らかに短縮され、近い駐機スポットリソースがより効果的に活用されるようになった。

数か月間にわたるデータを通じて二者の効果を比較した結果、手動による割り当てよりも、主要な指標が大幅に改善され、搭乗橋使用率が１０％上がり、旅客の搭乗橋使用率が１０％上がり、各競合率の指標が大幅に下がったことが分かった。

さらに図６を参照すると、上記の各図に示された方法の実施として、本開示は、図２に示された方法の実施形態に対応する情報を出力するための装置の実施形態を提供する。該装置は、具体的に様々な電子機器に適用することができる。

図６に示されるように、本実施形態にかかわる情報を出力するための装置６００は、取得ユニット６０１と、構築ユニット６０２と、最適化ユニット６０３と、解決ユニット６０４と、を含む。該取得ユニット６０１は、フライト情報、駐機スポット情報、誘導路情報、および滑走経路を取得するように構成されている。該構築ユニット６０２は、フライト情報、駐機スポット情報、誘導路情報、および滑走経路に基づいて、目標、決定変数、および制約条件を含む整数計画モデルを構築するように構成されている。該最適化ユニット６０３は、制約条件に基づいて整数計画モデルを最適化するように構成されている。該解決ユニット６０４は、最適化された整数計画モデルを解き、フライトと駐機スポットの対応関係表を取得して出力するように構成されている。

本実施形態では、情報を出力するための装置６００における取得ユニット６０１、構築ユニット６０２、最適化ユニット６０３、および解決ユニット６０４の具体的な処理は、図２に対応する実施形態のステップ２０１、ステップ２０２、ステップ２０３、およびステップ２０４を参照することができる。

本実施形態のいくつかのオプションの実施方法では、装置６００は、調整ユニット（図示せず）をさらに含む。該調整ユニットは、ターゲットフライトの調整要求の受信に対応して、一部の駐機スポットをランダムに選択して再配置リストに追加し、フライトと駐機スポットの対応関係表におけるランダムに選択された一部の駐機スポットと競合する駐機スポットを再配置リストに追加し、再配置リストにかかわる駐機スポット情報と関連するフライト情報、誘導路情報と滑走経路に基づいて、ローカル整数計画モデルを構築し、ローカル整数計画モデルを解き、ローカル範囲の最適解を取得し、フライトと駐機スポットの対応関係表を更新するように構成されている。

本実施形態のいくつかのオプションの実施方法では、調整ユニットはさらに、駐機スポットを割り当てられていないフライトに対して、貪欲アルゴリズムによって駐機スポットを割り当てるように構成されている。

本実施形態のいくつかのオプションの実施方法では、装置６００は、フライトと駐機スポットの対応関係表の効果を評価するように構成された評価ユニット（図示せず）をさらに含む。

本実施形態のいくつかのオプションの実施方法では、決定変数は、フライト占用駐機スポット識別子、フライトプッシュアウト競合識別子、航空社の搭乗橋使用率目標の達成率、誘導路占用識別子、フライトの属性、駐機スポットの属性、フライトの到着時刻、フライトの出発時刻、フライトの搭乗開始時刻、フライトの搭乗終了時刻、フライトの降機開始時刻、フライトの降機終了時刻、近い駐機スポット識別子、フライトの乗客数、搭乗・降機客競合識別子、駐機スポットと滑走路間の距離、仮駐機スポット識別子、航空社の搭乗橋使用率目標識別子、競合駐機スポット識別子のうちの少なくとも１つを含む。

本実施形態のいくつかのオプションの実施方法では、制約条件は、属性の制約、ＶＩＰフライトの制約、スペースの制約、タイムの制約、競合駐機スポットの制約、搭乗・降機客競合の制約、プッシュアウト競合の制約のうちの少なくとも１つを含む。

本実施形態のいくつかのオプションの実施方法では、目標は、フライトの搭乗橋使用率、旅客の搭乗橋使用率、航空社の搭乗橋使用率目標の達成率、プッシュアウトの競合率、滑走距離率、近い駐機スポットの時間使用率、仮駐機スポットの使用率のうちの少なくとも１つの加重和である。

本実施形態のいくつかのオプションの実施方法では、制約条件に基づいて整数計画モデルを最適化することは、駐機スポット競合の制約の最適化、プッシュアウト競合の制約の最適化、競合駐機スポットの制約の最適化、航空社の搭乗橋使用率の区分的線形変換のうちの少なくとも１つを含む。

本実施形態のいくつかのオプションの実施方法では、解決ユニットはさらに、分枝限定法を使用して最適化された整数計画モデルを解くように構成されている。

さらに図７を参照すると、本開示の実施形態の実施に適する電子機器（例えば、図１のサーバー）７００のブロック図が示されている。図７に示されるサーバーは単なる例であり、本開示の実施形態の機能および使用範囲に如何なる制限も課すべきではない。

図７に示されるように、電子機器７００は、読み取り専用メモリ（ＲＯＭ）７０２に記憶されたプログラムまたは記憶装置７０８からランダムアクセスメモリ（ＲＡＭ）７０３にロードされたプログラムにより、様々な適切な動作および処理を実行できる処理装置（例えば、中央処理装置、グラフィックスプロセッサなど）７０１を含み得る。ＲＡＭ７０３には、電子機器７００の動作に必要な各種プログラムやデータも記憶されている。処理装置７０１、ＲＯＭ７０２、およびＲＡＭ７０３は、バス７０４を介して相互に接続されている。入出力（Ｉ/Ｏ）インターフェース７０５もバス７０４に接続されている。

一般的に、Ｉ/Ｏインターフェース７０５に接続できる装置は、タッチスクリーン、タッチパッド、キーボード、マウス、カメラ、マイク、加速度計、ジャイロスコープなどの入力装置７０６と、液晶ディスプレイ（ＬＣＤ）、スピーカー、バイブレーターなどの出力装置７０７と、ハードディスクなどの記憶装置７０８と、通信装置７０９と、を含む。通信装置７０９は、電子機器７００が他の装置と無線または有線で通信してデータを交換することを可能にする。図７は様々な装置を有する電子機器７００を示しているが、図示された装置のすべてを実施または有する必要はないことを理解されたい。代替的により多いまたはより少ない装置が実施されてもよい。図７に示される各ブロックは、１つの装置を表すことも、必要に応じて複数の装置を表すこともできる。

特に、本開示の実施形態によると、フローチャートを参照して説明されたプロセスは、コンピューターソフトウェアプログラムとして実施され得る。例えば、本開示の実施形態には、コンピューター可読媒体に記憶されたコンピュータープログラムを含むコンピュータープログラム製品が含まれる。該コンピュータープログラムは、フローチャートに示される方法を実行するためのプログラムコードを含む。そのような実施形態では、該コンピュータープログラムは、通信装置７０９を介してネットワークからダウンロードしてインストールするか、記憶装置７０８からインストールするか、またはＲＯＭ７０２からインストールすることができる。該コンピュータープログラムが処理装置７０１によって実行されると、本開示の実施形態の方法において定義された上述の機能を実行する。本開示の実施形態で説明されたコンピューター可読媒体は、コンピューター可読信号媒体、コンピューター可読記憶媒体、またはこの２つの任意の組み合わせであり得ることに留意されたい。コンピューター可読記憶媒体は、例えば、電子、磁気、光学、電磁気、赤外線、または半導体のシステム、装置もしくは装置、または上記の任意の組み合わせであり得るが、これらに限定されない。コンピューター可読記憶媒体のより具体的な例は、１つまたは複数のワイヤを有する電気接続、ポータブルコンピューターディスク、ハードディスク、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能なプログラム可能な読み取り専用メモリ（ＥＰＲＯＭまたはフラッシュメモリ）、光ファイバー、ポータブルコンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、光学記憶装置、磁気記憶装置、または上記の任意の適切な組み合わせを含むが、これらに限定されない。本開示の実施形態では、コンピューター可読記憶媒体は、プログラムを含むまたは記憶する任意の有形の媒体であり得る。該プログラムは、命令実行システム、装置または部材によって、またはそれらに関連して使用されることができる。本開示の実施形態では、コンピューター可読信号媒体はベースバンドで、またはキャリアの一部として伝播されるデータ信号を含み得る。コンピューター可読信号媒体には、コンピューターで読み取り可能なプログラムコードが記憶されている。そのような伝播されるデータ信号は、電磁信号、光信号、または上記の任意の適切な組み合わせを含むがこれらに限定されない様々な形態をとることができる。コンピューター可読信号媒体はさらに、命令実行システム、装置、または部材によってまたはそれらに関連して使用されるプログラムを送信、伝播、または伝送できる、コンピューター可読記憶媒体以外の任意のコンピューター可読媒体であり得る。コンピューター可読媒体に記憶されているプログラムコードは、ワイヤ、光ファイバーケーブル、ＲＦ（無線周波数）など、または上記の任意の適切な組み合わせを含むがこれらに限定されない任意の適切な媒体によって送信され得る。

上記のコンピューター可読媒体は、上記の電子機器に含まれていてもよく、別個に存在し、該電子機器に組み込まれていなくてもよい。上記のコンピューター可読媒体には、１つまたは複数のプログラムが記憶されており、上記の１つまたは複数のプログラムが電子機器によって実行されると、該電子機器は、フライト情報、駐機スポット情報、誘導路情報、および滑走経路を取得し、フライト情報、駐機スポット情報、誘導路情報、および滑走経路に基づいて、目標、決定変数、および制約条件を含む整数計画モデルを構築し、制約条件に基づいて整数計画モデルを最適化し、最適化された整数計画モデルを解き、フライトと駐機スポットの対応関係表を取得して出力する。

本開示の実施形態の動作を実行するためのコンピュータープログラムコードは、１つまたは複数のプログラミング言語、またはそれらの組み合わせで書くことができる。プログラミング言語は、Ｊａｖａ、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋などのオブジェクト指向プログラミング言語や、「Ｃ」言語または類似するプログラミング言語などの従来の手続き型プログラミング言語を含む。 プログラムコードは、完全にユーザーのコンピューター上で実行されることも、部分的にユーザーのコンピューター上で実行されることも、スタンドアロンソフトウェアパッケージとして実行されることも、部分的にユーザーのコンピューター上で実行されながら部分的にリモートコンピューター上で実行されることも、または完全にリモートコンピューターまたはサーバー上で実行されることもできる。リモートコンピューターの場合、リモートコンピューターは、ローカルエリアネットワーク（ＬＡＮ）またはワイドエリアネットワーク（ＷＡＮ）を含む任意の種類のネットワークを介してユーザーのコンピューターに接続されることができる。または、外部のコンピューターに接続されることができる（例えば、インターネットサービスプロバイダーによるインターネット経由で接続される）。

図に示されるフローチャートおよびブロック図は、本出願の様々な実施形態にかかわるシステム、方法、およびコンピュータープログラム製品の実施可能なアーキテクチャ、機能、および動作を示している。ここで、フローチャートまたはブロック図における各ブロックは、モジュール、プログラムセグメント、またはコードの一部を表すことができる。該モジュール、プログラムセグメント、またはコードの一部は、指定されたロジック関数を実施するための１つまたは複数の実行可能な命令を含む。また、いくつかの代替的な実施形態では、ブロックに記載されている機能は、図面に示されているものとは異なる順序で発生する場合があることにも留意されたい。例えば、連続して表されている２つのブロックは、実際にほぼ並行して実行されてもよく、時には逆の順序で実行されてもよい。これは関連する機能によって決まる。 また、ブロック図および/またはフローチャートにおける各ブロック、およびブロック図および/またはフローチャートにおけるブロックの組み合わせは、指定された機能または動作を実行する専用のハードウェアベースのシステムで実施できることや、専用のハードウェアとコンピューターの命令の組み合わせてで実施できることにも留意されたい。

本出願の実施形態において説明されたユニットは、ソフトウェアまたはハードウェアによって実施され得る。説明されたユニットはプロセッサに内蔵されてもよい。例えば、「取得ユニットと、構築ユニットと、最適化ユニットと、解決ユニットと、を含むプロセッサ」と説明されることができる。ここで、これらのユニットの名前は、ユニット自体に対する制限を構成しない場合がある。例えば、取得ユニットは、「フライト情報、駐機スポット情報、誘導路情報、および滑走経路を取得するユニット」と説明されることができる。

上記の説明は、あくまでも本出願の好ましい実施形態および応用技術原理の説明にすぎない。本出願にかかわる発明の範囲は、上記の技術的特徴の特定の組み合わせによって形成された技術的解決手段に限定されず、上記の発明の構想から逸脱しない範囲で上記の技術的特徴またはその同等の技術的特徴の任意の組み合わせによって形成されたその他の技術的解決手段、例えば、上記の特徴と本出願に開示された同様の機能を有する技術的特徴（それだけに限定されない）とが相互に代替することによって形成された技術的解決手段もカバーしていることを当業者は理解すべきである。

Claims (15)

1. フライト情報、駐機スポット情報、誘導路情報、および滑走経路を取得するステップであって、前記誘導路情報は、駐機スポットと誘導路の対応関係を表し、前記滑走経路は、駐機スポットから滑走路までの滑走距離を表す、ステップと、
   前記フライト情報、前記駐機スポット情報、前記誘導路情報、および前記滑走経路に基づいて、目標、決定変数、および制約条件を含む整数計画モデルを構築するステップと、
   前記制約条件に基づいて前記整数計画モデルを最適化するステップと、
   最適化された整数計画モデルを解き、フライトと駐機スポットの対応関係表を取得して出力するステップと、を含み、
   前記目標は、フライトの搭乗橋使用率、旅客の搭乗橋使用率、航空会社の搭乗橋使用率目標の達成率、プッシュアウトの競合率、滑走距離率、近い駐機スポットの時間使用率、仮駐機スポットの使用率のうちの少なくとも１つの加重合計であり、
   前記決定変数は、フライト占用駐機スポット識別子、フライトプッシュアウト競合識別子、航空会社の搭乗橋使用率目標の達成率、誘導路占用識別子、フライトの属性、駐機スポットの属性、フライトの到着時刻、フライトの出発時刻、フライトの搭乗開始時刻、フライトの搭乗終了時刻、フライトの降機開始時刻、フライトの降機終了時刻、近い駐機スポット識別子、フライトの乗客数、搭乗・降機客競合識別子、駐機スポットと滑走路間の距離、仮駐機スポット識別子、航空会社の目標搭乗橋使用率識別子、競合駐機スポット識別子のうちの少なくとも１つを含み、
   前記制約条件は、属性の制約、ＶＩＰフライトの制約、スペースの制約、タイムの制約、競合駐機スポットの制約、搭乗・降機客競合の制約、プッシュアウト競合の制約のうちの少なくとも１つを含む情報を出力するための方法。
2. 前記方法は、
   ターゲットフライトの調整要求の受信に対応して、一部の駐機スポットをランダムに選択して再配置リストに追加するステップと、
   前記フライトと駐機スポットの対応関係表におけるランダムに選択された一部の駐機スポットと競合する駐機スポットを前記再配置リストに追加するステップと、
   前記再配置リストにかかわる駐機スポット情報と関連するフライト情報、前記誘導路情報と前記滑走経路に基づいて、ローカル整数計画モデルを構築するステップと、
   前記ローカル整数計画モデルを解き、ローカル範囲最適解を取得し、前記フライトと駐機スポットの対応関係表を更新するステップと、をさらに含む請求項１に記載の方法。
3. 前記方法は、
   駐機スポットを割り当てられていないフライトには、貪欲アルゴリズムによって駐機スポットを割り当てるステップをさらに含む請求項２に記載の方法。
4. 前記方法は、
   前記フライトと駐機スポットの対応関係表の効果を評価するステップをさらに含む請求項１に記載の方法。
5. 前記制約条件に基づいて前記整数計画モデルを最適化するステップは、
   駐機スポット競合制約の最適化、プッシュアウト競合制約の最適化、競合駐機スポット制約の最適化、航空会社の搭乗橋使用率の区分的線形変換のうちの少なくとも１つを含む請求項１に記載の方法。
6. 前記最適化された整数計画モデルを解くステップは、分枝限定法を使用して最適化された整数計画モデルを解くことを含む請求項５に記載の方法。
7. フライト情報、駐機スポット情報、誘導路情報、および滑走経路を取得するように構成された取得ユニットであって、前記誘導路情報は、駐機スポットと誘導路の対応関係を表し、前記滑走経路は、駐機スポットから滑走路までの滑走距離を表す、取得ユニットと、
   前記フライト情報、前記駐機スポット情報、前記誘導路情報、および前記滑走経路に基づいて、目標、決定変数、および制約条件を含む整数計画モデルを構築するように構成された構築ユニットと、
   前記制約条件に基づいて前記整数計画モデルを最適化するように構成された最適化ユニットと、
   最適化された整数計画モデルを解き、フライトと駐機スポットの対応関係表を取得して出力するように構成された解決ユニットと、を含み、
   前記目標は、フライトの搭乗橋使用率、旅客の搭乗橋使用率、航空会社の搭乗橋使用率目標の達成率、プッシュアウトの競合率、滑走距離率、近い駐機スポットの時間使用率、仮駐機スポットの使用率のうちの少なくとも１つの加重合計であり、
   前記決定変数は、フライト占用駐機スポット識別子、フライトプッシュアウト競合識別子、航空会社の搭乗橋使用率目標の達成率、誘導路占用識別子、フライトの属性、駐機スポットの属性、フライトの到着時刻、フライトの出発時刻、フライトの搭乗開始時刻、フライトの搭乗終了時刻、フライトの降機開始時刻、フライトの降機終了時刻、近い駐機スポット識別子、フライトの乗客数、搭乗・降機客競合識別子、駐機スポットと滑走路間の距離、仮駐機スポット識別子、航空会社の目標搭乗橋使用率識別子、競合駐機スポット識別子のうちの少なくとも１つを含み、
   前記制約条件は、属性の制約、ＶＩＰフライトの制約、スペースの制約、タイムの制約、競合駐機スポットの制約、搭乗・降機客競合の制約、プッシュアウト競合の制約のうちの少なくとも１つを含む情報を出力するための装置。
8. 前記装置は調整ユニットをさらに含み、
   前記調整ユニットは、
   ターゲットフライトの調整要求の受信に対応して、一部の駐機スポットをランダムに選択して再配置リストに追加し、
   前記フライトと駐機スポットの対応関係表におけるランダムに選択された一部の駐機スポットと競合する駐機スポットを前記再配置リストに追加し、
   前記再配置リストにかかわる駐機スポット情報と関連するフライト情報、前記誘導路情報と前記滑走経路に基づいて、ローカル整数計画モデルを構築し、
   前記ローカル整数計画モデルを解き、ローカル範囲最適解を取得し、前記フライトと駐機スポットの対応関係表を更新するように構成されている請求項７に記載の装置。
9. 前記調整ユニットはさらに、駐機スポットを割り当てられていないフライトには、貪欲アルゴリズムによって駐機スポットを割り当てるように構成されている請求項８に記載の装置。
10. 前記装置は、前記フライトと駐機スポットの対応関係表の効果を評価するように構成された評価ユニットをさらに含む請求項７に記載の装置。
11. 前記制約条件に基づいて前記整数計画モデルを最適化するステップは、
    駐機スポット競合制約の最適化、プッシュアウト競合制約の最適化、競合駐機スポット制約の最適化、航空会社の搭乗橋使用率の区分的線形変換のうちの少なくとも１つを含む請求項７に記載の装置。
12. 前記解決ユニットはさらに、分枝限定法を使用して最適化された整数計画モデルを解くように構成されている請求項１１に記載の装置。
13. １つまたは複数のプロセッサと、
    １つまたは複数のプログラムが格納されている記憶装置と、を含み、
    前記１つまたは複数のプログラムが前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに請求項１〜６のいずれか１項に記載の方法を実施させる電子機器。
14. コンピュータープログラムが格納されているコンピューター可読媒体であって、前記プログラムがプロセッサによって実行されると、請求項１〜６のいずれか１項に記載の方法を実施するコンピューター可読媒体。
15. コンピュータプログラムであって、
    前記コンピュータプログラムがプロセッサにより実行されると、請求項１〜６のいずれか１項に記載の方法を実現する、コンピュータプログラム。

Images