論文の概要: Real-World Airline Crew Pairing Optimization: Customized Genetic
Algorithm versus Column Generation Method
- arxiv url: http://arxiv.org/abs/2003.03792v2
- Date: Sat, 27 May 2023 20:59:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 05:07:32.351348
- Title: Real-World Airline Crew Pairing Optimization: Customized Genetic
Algorithm versus Column Generation Method
- Title（参考訳）: 実世界の航空機乗組員ペアリング最適化:コラム生成法に対する遺伝的アルゴリズムのカスタマイズ
- Authors: Divyam Aggarwal, Dhish Kumar Saxena, Thomas Back, and Michael Emmerich
- Abstract要約: 航空機乗組員ペアリング最適化問題(CPOP)は、航空会社の高度に制約された飛行スケジュールにおいて、最小限のコストで全フライトをカバーする一連のフライトシーケンスを見つけることを目的としている。
CPOPはNPハードであり、それに取り組むのは非常に難しい。
本稿ではドメイン知識駆動型カスタマイズGAを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Airline crew pairing optimization problem (CPOP) aims to find a set of flight
sequences (crew pairings) that cover all flights in an airline's highly
constrained flight schedule at minimum cost. Since crew cost is second only to
the fuel cost, CPOP solutioning is critically important for an airline.
However, CPOP is NP-hard, and tackling it is quite challenging. The literature
suggests, that when the CPOP's scale and complexity is reasonably limited, and
an enumeration of all crew pairings is possible, then Metaheuristics are used,
predominantly Genetic Algorithms (GAs). Else, Column Generation (CG) based
Mixed Integer Programming techniques are used. Notably, as per the literature,
a maximum of 45,000 crew pairings have been tackled by GAs. In a significant
departure, this paper considers over 800 flights of a US-based large airline
(with a monthly network of over 33,000 flights), and tests the efficacy of GAs
by enumerating all 400,000+ crew pairings, apriori. Towards it, this paper
proposes a domain-knowledge-driven customized-GA. The utility of incorporating
domain-knowledge in GA operations, particularly initialization and crossover,
is highlighted through suitable experiments. Finally, the proposed GA's
performance is compared with a CG-based approach (developed in-house by the
authors). Though the latter is found to perform better in terms of solution's
cost-quality and run time, it is hoped that this paper will help in better
understanding the strengths and limitations of domain-knowledge-driven
customizations in GAs, for solving combinatorial optimization problems,
including CPOPs.
- Abstract（参考訳）: 航空会社のクルーペアリング最適化問題(cpop)は、航空会社の高度に制約されたフライトスケジュールのすべてのフライトをカバーする一連のフライトシーケンス(crewペアリング)を最小コストで見つけることを目的としている。
乗員コストは燃料コストに次いで第2位であるため、CPOP解決は航空会社にとって極めて重要である。
しかし、CPOPはNPハードであり、それに取り組むのは非常に難しい。
文献によれば、CPOPのスケールと複雑さが合理的に制限され、全てのクルーペアの列挙が可能になった場合、メタヒューリスティックスは主に遺伝的アルゴリズム(GA)が用いられる。
その他、列生成(cg)ベースの混合整数プログラミング技術が用いられる。
特に文献によると、最大45,000人の乗員ペアがGAによって取り組まれている。
本稿では,米国発の大型航空会社の800便以上(月33,000便以上)について検討し,約400,000人以上の乗務員のペアを列挙してGAの有効性を検証した。
そこで本研究ではドメイン知識によるカスタマイズGAを提案する。
GA操作、特に初期化とクロスオーバーにドメイン知識を組み込むことの有用性は、適切な実験を通して強調される。
最後に、提案したGAの性能を、CGベースのアプローチ(著者が社内で開発した)と比較する。
後者は,ソリューションのコスト品質と実行時間の観点からは優れているが,本論文は,GAにおけるドメイン知識駆動型カスタマイズの強みと限界をよりよく理解し,CPOPを含む組合せ最適化問題の解決に役立てることが期待される。
関連論文リスト
- Communication-Efficient Federated Group Distributionally Robust Optimization [49.14751984342068]
フェデレーション学習は、異なるクライアントにおけるデータボリュームと分散の不均一性のために、課題に直面します。
グループ分散ロバスト最適化(GDRO)に基づいてこの問題に対処するための既存のアプローチは、しばしば高い通信とサンプルの複雑さをもたらす。
本研究では, 通信効率の高いFederated Group Distributionally Robust Optimizationに適したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-10-08T21:07:53Z) - Controllable Prompt Tuning For Balancing Group Distributional Robustness [53.336515056479705]
グループ間で優れたパフォーマンスを実現するための最適化スキームを導入し、それらの性能を著しく犠牲にすることなく、全員に良い解決策を見出す。
本稿では,制御可能なプロンプトチューニング(CPT)を提案する。
突発的相関ベンチマークでは, 変換器と非変換器の両アーキテクチャ, および非モーダルおよびマルチモーダルデータにまたがって, 最先端の結果が得られた。
論文 参考訳（メタデータ） (2024-03-05T06:23:55Z) - AffineGlue: Joint Matching and Robust Estimation [74.04609046690913]
AffineGlue, 連立2視点特徴マッチングとロバストな推定法を提案する。
AffineGlueは、最小限のモデルを推定するために、1対多の対応から潜在的なマッチを選択する。
ガイドマッチングはモデルと一致した一致を見つけるために使用され、1対1の一致の曖昧さに悩まされる。
論文 参考訳（メタデータ） (2023-07-28T08:05:36Z) - MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with
Known Pareto Front [71.19090689055054]
多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。
提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。
本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
論文 参考訳（メタデータ） (2023-04-28T07:09:23Z) - Learning to Solve Combinatorial Graph Partitioning Problems via
Efficient Exploration [72.15369769265398]
実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。
最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
論文 参考訳（メタデータ） (2022-05-27T17:13:10Z) - GAIA: A Transfer Learning System of Object Detection that Fits Your
Needs [136.60609274344893]
大規模データセットの事前学習によるトランスファーラーニングは,コンピュータビジョンや自然言語処理において,ますます重要な役割を担っている。
本稿では,物体検出の領域に着目し,GAIAと呼ばれる移動学習システムを提案する。
GAIAは、レイテンシ制約や指定されたデータドメインなどの下流要求に適合するモデルを選択する、強力な事前訓練されたウェイトを提供することができる。
論文 参考訳（メタデータ） (2021-06-21T18:24:20Z) - Machine Learning in Airline Crew Pairing to Construct Initial Clusters
for Dynamic Constraint Aggregation [23.980050729253612]
クルーペアリング問題(Crew pairing problem, CPP)は、一般的に、飛行をペアリングで分割する必要があるセット問題としてモデル化される。
機械学習(ML)を用いて、同じ乗組員によって連続的に実行される確率の高い飛行群を生成する。
最大50万回のフライトを持つ月毎のCPPにおいて、MLベースのクラスタが生成するCommercial-GENCOL-DCAは、初期クラスタが供給するBaselineを上回っていることを示す。
論文 参考訳（メタデータ） (2020-09-30T22:38:47Z) - Flight-connection Prediction for Airline Crew Scheduling to Construct
Initial Clusters for OR Optimizer [23.980050729253612]
本稿では、機械学習の分類アルゴリズムを用いて大規模商用解法(GENCOL)を初期化するケーススタディを提案する。
1%未満の少額の貯蓄は、大型航空会社の年間収入を数十万ドル増額することを意味している。
論文 参考訳（メタデータ） (2020-09-26T01:32:07Z) - A Novel Column Generation Heuristic for Airline Crew Pairing
Optimization with Large-scale Complex Flight Networks [0.0]
本稿では,Airline Crew Pairing(AirCROP)の社内開発を可能にする新しいCGを提案する。
CPO/AirCROPの有効性は4,200機以上の飛行、15の乗員基地、複数のハブ・アンド・スポーク・サブネットワークでテストされている。
論文 参考訳（メタデータ） (2020-05-18T12:19:02Z) - On Learning Combinatorial Patterns to Assist Large-Scale Airline Crew
Pairing Optimization [0.0]
本稿では,飛行接続データ中の可視パターンを学習するための変分グラフオートエンコーダの新たな適応法を提案する。
結果として生じる飛行接続予測は、新しいペアリングを生成するために小説を使ってオンザフライで組み合わせられる。
提案手法の実用性は、複数のハブ・アンド・スポーク・ワークスと複数のクルー・ベースを特徴とする、大規模(4200以上のフライト)、実世界、アメリカの航空会社の複雑なフライト・ネットワーク上で実証されている。
論文 参考訳（メタデータ） (2020-04-28T20:16:22Z) - On Initializing Airline Crew Pairing Optimization for Large-scale
Complex Flight Networks [0.0]
本論文は,飛行スケジュールをカバーする一連のフライトシーケンス(重対)を,いくつかの法的制約を満たしつつ,最小限のコストで生成することを目的とする。
GE Aviationが提供する現実の大規模かつ複雑な飛行ネットワーク(3200以上の飛行と15の乗員基地を含む)では、提案されたデータセットは、別の最先端アプローチよりも10倍のスピード向上を示している。
論文 参考訳（メタデータ） (2020-03-15T08:21:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。