論文の概要: Machine Learning in Airline Crew Pairing to Construct Initial Clusters
for Dynamic Constraint Aggregation
- arxiv url: http://arxiv.org/abs/2010.00134v1
- Date: Wed, 30 Sep 2020 22:38:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-13 00:12:47.047436
- Title: Machine Learning in Airline Crew Pairing to Construct Initial Clusters
for Dynamic Constraint Aggregation
- Title（参考訳）: 動的拘束アグリゲーションのための初期クラスタ構築のためのエアラインクルーペアの機械学習
- Authors: Yassine Yaakoubi, Fran\c{c}ois Soumis, Simon Lacoste-Julien
- Abstract要約: クルーペアリング問題(Crew pairing problem, CPP)は、一般的に、飛行をペアリングで分割する必要があるセット問題としてモデル化される。
機械学習(ML)を用いて、同じ乗組員によって連続的に実行される確率の高い飛行群を生成する。
最大50万回のフライトを持つ月毎のCPPにおいて、MLベースのクラスタが生成するCommercial-GENCOL-DCAは、初期クラスタが供給するBaselineを上回っていることを示す。
- 参考スコア（独自算出の注目度）: 23.980050729253612
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The crew pairing problem (CPP) is generally modelled as a set partitioning
problem where the flights have to be partitioned in pairings. A pairing is a
sequence of flight legs separated by connection time and rest periods that
starts and ends at the same base. Because of the extensive list of complex
rules and regulations, determining whether a sequence of flights constitutes a
feasible pairing can be quite difficult by itself, making CPP one of the
hardest of the airline planning problems. In this paper, we first propose to
improve the prototype Baseline solver of Desaulniers et al. (2020) by adding
dynamic control strategies to obtain an efficient solver for large-scale CPPs:
Commercial-GENCOL-DCA. These solvers are designed to aggregate the flights
covering constraints to reduce the size of the problem. Then, we use machine
learning (ML) to produce clusters of flights having a high probability of being
performed consecutively by the same crew. The solver combines several advanced
Operations Research techniques to assemble and modify these clusters, when
necessary, to produce a good solution. We show, on monthly CPPs with up to 50
000 flights, that Commercial-GENCOL-DCA with clusters produced by ML-based
heuristics outperforms Baseline fed by initial clusters that are pairings of a
solution obtained by rolling horizon with GENCOL. The reduction of solution
cost averages between 6.8% and 8.52%, which is mainly due to the reduction in
the cost of global constraints between 69.79% and 78.11%.
- Abstract（参考訳）: 乗組員ペアリング問題(CPP)は一般的に、飛行をペアリングで分割する必要がある設定分割問題としてモデル化される。
ペアリング(英: pairing)とは、接続時間と休息期間によって切り離された飛行脚の連続であり、同じ基地で始まり、終了する。
複雑な規則と規則の広範なリストのため、一連の飛行が単独で実現可能なペアリングを構成するかどうかを決定することは極めて困難であり、cppは航空会社計画の最も難しい問題の一つとなっている。
本稿では,まず,大規模cppsの効率的な解法を実現するために動的制御戦略を追加することで,desaulniers et al. (2020) のプロトタイプベースラインソルバの改良を提案する。
これらの解法は、制約をカバーする飛行を集約して問題のサイズを減らすように設計されている。
次に、機械学習(ML)を用いて、同じ乗組員によって連続的に実行される確率の高い飛行群を生成する。
このソルバはいくつかの高度なOperations Research技術を組み合わせて、これらのクラスタを組み立て、必要に応じて修正し、優れたソリューションを生成する。
最大50万便の月次CPPにおいて、MLベースのヒューリスティックスによって生成されたクラスタによるCommercial-GENCOL-DCAは、GenCOLと水平方向に転がったソリューションのペアである初期クラスタによって供給されるベースラインよりも優れていることを示す。
ソリューションコストの平均は6.8%から8.52%であり、これは主に69.79%から78.11%のグローバル制約のコストの削減によるものである。
関連論文リスト
- Capacity-Aware Planning and Scheduling in Budget-Constrained Monotonic MDPs: A Meta-RL Approach [7.385321178884467]
多くの実世界のシーケンシャル修復問題は、単調マルコフ決定プロセス(MDP)を用いて効果的にモデル化できる。
本研究は,多成分単調MDPを予算とキャパシティの制約で解く問題に対処する。
論文 参考訳（メタデータ） (2024-10-28T17:48:45Z) - Joint Demonstration and Preference Learning Improves Policy Alignment with Human Feedback [58.049113055986375]
我々は、報酬モデルとポリシーをトレーニングするために、AIHF(Alignment with Integrated Human Feedback)と呼ばれる単一ステージアプローチを開発する。
提案した手法は、一般的なアライメントアルゴリズムに容易に還元し、活用できる、効率的なアルゴリズムの集合を認めている。
本研究では,LLMにおけるアライメント問題と,MuJoCoにおけるロボット制御問題を含む広範な実験により,提案手法の有効性を実証する。
論文 参考訳（メタデータ） (2024-06-11T01:20:53Z) - Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering [1.3927943269211591]
実用的なランタイムにおける車両ルーティングの効率的な解決は、デリバリ管理企業にとって重要な課題である。
本稿では,CVRPとCCBC(Constrainedid-Based Clustering)の理論的および実験的関係について検討する。
提案するフレームワークは,3つの段階から構成される。第1段階では,制約付きセントロイドベースのクラスタリングアルゴリズムが,ユーザの実現可能なクラスタを生成する。
論文 参考訳（メタデータ） (2024-03-20T22:24:36Z) - Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。
汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。
我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
論文 参考訳（メタデータ） (2023-10-10T01:39:04Z) - Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
本稿では,ロボット推論と計画における連続的制約満足度問題(CCSP)の解法について紹介する。
対照的に、構成拡散連続制約解法(Diffusion-CCSP)は、CCSPに対する大域的な解を導出する。
論文 参考訳（メタデータ） (2023-09-02T15:20:36Z) - Flight-connection Prediction for Airline Crew Scheduling to Construct
Initial Clusters for OR Optimizer [23.980050729253612]
本稿では、機械学習の分類アルゴリズムを用いて大規模商用解法(GENCOL)を初期化するケーススタディを提案する。
1%未満の少額の貯蓄は、大型航空会社の年間収入を数十万ドル増額することを意味している。
論文 参考訳（メタデータ） (2020-09-26T01:32:07Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Competitive Mirror Descent [67.31015611281225]
制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。
本稿では, 競合ミラー降下法(CMD)を提案する。
特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-06-17T22:11:35Z) - Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。
ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
論文 参考訳（メタデータ） (2020-06-05T13:48:26Z) - 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) - Real-World Airline Crew Pairing Optimization: Customized Genetic
Algorithm versus Column Generation Method [0.0]
航空機乗組員ペアリング最適化問題(CPOP)は、航空会社の高度に制約された飛行スケジュールにおいて、最小限のコストで全フライトをカバーする一連のフライトシーケンスを見つけることを目的としている。
CPOPはNPハードであり、それに取り組むのは非常に難しい。
本稿ではドメイン知識駆動型カスタマイズGAを提案する。
論文 参考訳（メタデータ） (2020-03-08T15:04:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。