論文の概要: A Novel Column Generation Heuristic for Airline Crew Pairing Optimization with Large-scale Complex Flight Networks

• arxiv url: http://arxiv.org/abs/2005.08636v4
• Date: Fri, 2 Jul 2021 11:48:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-02 00:23:58.777315
• Title: A Novel Column Generation Heuristic for Airline Crew Pairing Optimization with Large-scale Complex Flight Networks
• Title（参考訳）: 大規模複合飛行ネットワークを用いた飛行船ペア最適化のための新しいカラム生成ヒューリスティック
• Authors: Divyam Aggarwal, Dhish Kumar Saxena, Saaju Pualose, Thomas B\"ack, Michael Emmerich
• Abstract要約: 本稿では,Airline Crew Pairing(AirCROP)の社内開発を可能にする新しいCGを提案する。 CPO/AirCROPの有効性は4,200機以上の飛行、15の乗員基地、複数のハブ・アンド・スポーク・サブネットワークでテストされている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Crew Pairing Optimization (CPO) is critical for an airlines' business viability, given that the crew operating cost is second only to the fuel cost. CPO aims at generating a set of flight sequences (crew pairings) to cover all scheduled flights, at minimum cost, while satisfying several legality constraints. The state-of-the-art heavily relies on relaxing the underlying Integer Programming Problem into a Linear Programming Problem, which in turn is solved through the Column Generation (CG) technique. However, with the alarmingly expanding airlines' operations, CPO is marred by the curse of dimensionality, rendering the exact CG-implementations obsolete, and necessitating the heuristic-based CG-implementations. Yet, in literature, the much prevalent large-scale complex flight networks involving multiple { crew bases and/or hub-and-spoke sub-networks, largely remain uninvestigated. This paper proposes a novel CG heuristic, which has enabled the in-house development of an Airline Crew Pairing Optimizer (AirCROP). The efficacy of the heuristic/AirCROP has been tested on real-world, large-scale, complex network instances with over 4,200 flights, 15 crew bases, and multiple hub-and-spoke sub-networks (resulting in billion-plus possible pairings). Notably, this paper has a dedicated focus on the proposed CG heuristic (not the entire AirCROP framework) based on balancing random exploration of pairings; exploitation of domain knowledge (on optimal solution features); and utilization of the past computational & search effort through archiving. Though this paper has an airline context, the proposed CG heuristic may find wider applications across different domains, by serving as a template on how to utilize domain knowledge to better tackle combinatorial optimization problems.
• Abstract（参考訳）: 乗組員のペアリング最適化(cpo)は、乗組員の運用コストが燃料コストに次いで第2位であることから、航空会社のビジネスの存続に不可欠である。 cpoは、いくつかの法的制約を満たしながら、スケジュールされたすべてのフライトをカバーする一連の飛行シーケンス(クルーペアリング)を作成することを目指している。 最先端の手法は、基礎となる整数プログラミング問題を線形計画問題に緩和することに大きく依存しており、これはカラム生成(cg)技術によって解決される。 しかし、航空会社の事業拡大に伴い、CPOは次元性の呪いに悩まされ、正確なCG実装は廃止され、ヒューリスティックベースのCG実装が必要とされる。 しかし、文献では、複数の { crew bases と/またはハブアンドスポークのサブネットワークを含む、非常に一般的な大規模な複雑な飛行ネットワークは、ほとんど調査されていない。 本稿では,AirCROP(Airline Crew Pairing Optimizer)の社内開発を可能にする新しいCGヒューリスティックを提案する。 ヒューリスティック/エアCROPの有効性は、実世界の大規模で複雑なネットワークインスタンスで4,200機以上の飛行、15人の乗員基地、複数のハブ・アンド・スポーク・サブネットワーク(数十億以上のペアリング)でテストされている。 特に,本論文では,ペアリングのランダムな探索,ドメイン知識の活用(最適解の特徴に基づく),アーカイビングによる過去の計算・探索の活用を中心に,提案したCGヒューリスティック(AirCROPフレームワーク全体ではない)に焦点をあてる。 本論文は航空会社の文脈を持つが,提案したCGヒューリスティックは,ドメイン知識の活用による組合せ最適化問題への対処方法のテンプレートとして,様々な分野にまたがる幅広い応用を見出すことができる。

関連論文リスト

• The Perfect Blend: Redefining RLHF with Mixture of Judges [68.58426626501883]
  人間のフィードバックによる強化学習(RLHF)が,大規模言語モデル(LLM)の指導的アプローチとなっている。 MTLにRLHFを適用するには、現在、報酬モデルとデータの組み合わせに対する重み付けを慎重に調整する必要がある。 CGPO(Constrained Generative Policy Optimization)と呼ばれる新しいポストトレーニングパラダイムを導入する。
  論文  参考訳（メタデータ） (2024-09-30T15:06:53Z)
• A Graph-based Adversarial Imitation Learning Framework for Reliable & Realtime Fleet Scheduling in Urban Air Mobility [5.19664437943693]
  本稿では,艦隊スケジューリング問題の包括的最適化について述べる。 また、代替ソリューションのアプローチの必要性も認識している。 新しい模倣アプローチは、目に見えない最悪のシナリオにおいて、パフォーマンスと顕著な改善を実現する。
  論文  参考訳（メタデータ） (2024-07-16T18:51:24Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• Iterative Soft Shrinkage Learning for Efficient Image Super-Resolution [91.3781512926942]
  画像超解像(SR)は、CNNからトランスフォーマーアーキテクチャへの広範なニューラルネットワーク設計を目撃している。 本研究は,市販のネットワーク設計を生かし,基礎となる計算オーバーヘッドを低減するため,超高解像度イテレーションにおけるネットワークプルーニングの可能性について検討する。 本研究では, ランダムネットワークのスパース構造を最適化し, 重要でない重みを小さめに微調整することにより, 反復型軟収縮率(ISS-P)法を提案する。
  論文  参考訳（メタデータ） (2023-03-16T21:06:13Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。 我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。 我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
  論文  参考訳（メタデータ） (2023-02-02T18:27:20Z)
• ADAPT: An Open-Source sUAS Payload for Real-Time Disaster Prediction and Response with AI [55.41644538483948]
  小型無人航空機システム(sUAS)は、多くの人道支援や災害対応作戦において顕著な構成要素となっている。 我々は,SUAS上にリアルタイムAIとコンピュータビジョンをデプロイするための,オープンソースのADAPTマルチミッションペイロードを開発した。 本研究では,河川氷の状態を監視し,破滅的な洪水現象をタイムリーに予測するための,リアルタイム・飛行中の氷分断の例を示す。
  論文  参考訳（メタデータ） (2022-01-25T14:51:19Z)
• Efficient UAV Trajectory-Planning using Economic Reinforcement Learning [65.91405908268662]
  UAV間でタスクを分散するための経済取引に触発された新しい強化学習アルゴリズムであるREPlannerを紹介します。 エージェントが協力し、リソースを競うことができるマルチエージェント経済ゲームとして、パス計画問題を策定します。 UAV協力によるタスク分布の計算を行うため、Swarmサイズの変化に対して非常に耐性が高い。
  論文  参考訳（メタデータ） (2021-03-03T20:54:19Z)
• 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)
• 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)
• Real-World Airline Crew Pairing Optimization: Customized Genetic Algorithm versus Column Generation Method [0.0]
  航空機乗組員ペアリング最適化問題(CPOP)は、航空会社の高度に制約された飛行スケジュールにおいて、最小限のコストで全フライトをカバーする一連のフライトシーケンスを見つけることを目的としている。 CPOPはNPハードであり、それに取り組むのは非常に難しい。 本稿ではドメイン知識駆動型カスタマイズGAを提案する。
  論文  参考訳（メタデータ） (2020-03-08T15:04:57Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。