論文の概要: Logic-Constrained Shortest Paths for Flight Planning

• arxiv url: http://arxiv.org/abs/2412.13235v2
• Date: Fri, 20 Dec 2024 10:38:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-23 13:01:31.061871
• Title: Logic-Constrained Shortest Paths for Flight Planning
• Title（参考訳）: 飛行計画のための論理的制約付き短距離経路
• Authors: Ricardo Euler, Pedro Maristany de las Casas, Ralf Borndörfer,
• Abstract要約: 論理制約短経路問題(LCSP)は、1対1の短経路問題と、ルーティンググラフに課される満足度制約を組み合わせた問題である。 LCSPのための新しい分岐および境界ベースアルゴリズムを提案する。 本稿では,TLFをLCSPとしてモデル化し,分岐および有界アルゴリズムを用いてそれを解決する方法について述べる。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: The Logic-Constrained Shortest Path Problem (LCSP) combines a one-to-one shortest path problem with satisfiability constraints imposed on the routing graph. This setting arises in flight planning, where air traffic control (ATC) authorities are enforcing a set of traffic flow restrictions (TFRs) on aircraft routes in order to increase safety and throughput. We propose a new branch and bound-based algorithm for the LCSP. The resulting algorithm has three main degrees of freedom: the node selection rule, the branching rule and the conflict. While node selection and branching rules have been long studied in the MIP and SAT communities, most of them cannot be applied out of the box for the LCSP. We review the existing literature and develop tailored variants of the most prominent rules. The conflict, the set of variables to which the branching rule is applied, is unique to the LCSP. We analyze its theoretical impact on the B&B algorithm. In the second part of the paper, we show how to model the Flight Planning Problem with TFRs as an LCSP and solve it using the branch and bound algorithm. We demonstrate the algorithm's efficiency on a dataset consisting of a global flight graph and a set of around 20000 real TFRs obtained from our industry partner Lufthansa Systems GmbH. We make this dataset publicly available. Finally, we conduct an empirical in-depth analysis of node selection rules, branching rules and conflicts. Carefully choosing an appropriate combination yields an improvement of an order of magnitude compared to an uninformed choice.
• Abstract（参考訳）: 論理制約短経路問題(LCSP)は、1対1の短経路問題と、ルーティンググラフに課される満足度制約を組み合わせた問題である。 この設定は、航空交通管制当局が安全とスループットを高めるために、航空機ルート上の一連の交通流制限(TFR)を課している飛行計画において発生する。 LCSPのための新しい分岐および境界ベースアルゴリズムを提案する。 結果として得られるアルゴリズムは、ノード選択規則、分岐規則、競合の3つの主要な自由度を持つ。 ノード選択と分岐規則は、MIPとSATコミュニティで長い間研究されてきたが、そのほとんどはLCSPのボックスから適用することはできない。 我々は、既存の文献をレビューし、最も顕著な規則の調整された変種を開発する。 分岐規則を適用する変数の集合であるコンフリクトはLCSPに固有のものである。 我々はB&Bアルゴリズムに対する理論的影響を分析する。 本論文の第2部では,TFRをLCSPとしてモデル化し,分岐および有界アルゴリズムを用いてそれを解決する方法について述べる。 本研究では,グローバルフライトグラフと産業パートナーのLufthansa Systems GmbHから得られた約20000実TFRからなるデータセット上で,アルゴリズムの効率を実証する。 このデータセットを公開しています。 最後に,ノード選択ルール,分岐ルール,競合の詳細な分析を行う。 適切な組み合わせを慎重に選択すると、インフォームドされていない選択に比べて桁違いに改善される。

関連論文リスト

• Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
  線形制約が未知の多腕バンディットにおける純粋探索として問題を研究する。 まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。 第二に、ラグランジアンの下界と凸の性質を利用して、トラック・アンド・ストップとガミファイド・エクスプローラー(LATSとLAGEX)の2つの計算効率の良い拡張を提案する。
  論文  参考訳（メタデータ） (2024-10-24T15:26:14Z)
• Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
  提案手法は,最初の最適非角度マルチエージェントパスフィンディングアルゴリズムである。 我々のプランナーは、Continuous Conflict-based Search (CCBS)アルゴリズムと、Safe Interval Path Planning (TO-AA-SIPP)の最適な任意の角度変種に基づいている。 古典的MAPFから任意の角度設定、すなわち Disjoint Splitting と Multi-Constraint への2つの手法を適用する。
  論文  参考訳（メタデータ） (2024-04-25T07:41:47Z)
• A Quantum Inspired Bi-level Optimization Algorithm for the First Responder Network Design Problem [0.0]
  トルコの交通・インフラ省からの提案では、ファースト・レスポンダーズのみが使用する道路セグメントのサブセットを割り当てることになっている。 本稿では,この1次応答器ネットワーク設計問題に対する混合整数非線形プログラミングの定式化について述べる。 FRとエスキューパスのフローバランスの制約を用いて、部分的なグラバーベースを得るために、擬似非拘束バイナリ最適化(QUBO)モデルを用いる。
  論文  参考訳（メタデータ） (2024-01-23T03:22:05Z)
• CACTO: Continuous Actor-Critic with Trajectory Optimization -- Towards global optimality [5.0915256711576475]
  本稿では,Tlayy(TO)とReinforcement Learning(RL)を1つの軌道で組み合わせた,動的システムの連続制御のための新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-11-12T10:16:35Z)
• Trajectory-guided Control Prediction for End-to-end Autonomous Driving: A Simple yet Strong Baseline [96.31941517446859]
  現在のエンドツーエンドの自律運転法は、計画された軌道に基づいてコントローラを実行するか、直接制御予測を行う。 我々の統合されたアプローチには、それぞれ軌道計画と直接制御のための2つの枝があります。 CARLAシミュレータを用いて閉ループ都市運転環境の評価を行った。
  論文  参考訳（メタデータ） (2022-06-16T12:42:44Z)
• Comparative analysis of machine learning methods for active flow control [60.53767050487434]
  遺伝的プログラミング(GP)と強化学習(RL)はフロー制御において人気を集めている。 この研究は2つの比較分析を行い、地球規模の最適化手法に対して最も代表的なアルゴリズムのいくつかをベンチマークする。
  論文  参考訳（メタデータ） (2022-02-23T18:11:19Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)
• Improved Algorithms for Conservative Exploration in Bandits [113.55554483194832]
  文脈線形帯域設定における保守的学習問題について検討し、新しいアルゴリズムである保守的制約付きLinUCB(CLUCB2)を導入する。 我々は、既存の結果と一致したCLUCB2に対する後悔の限界を導き、多くの合成および実世界の問題において、最先端の保守的バンディットアルゴリズムよりも優れていることを実証的に示す。
  論文  参考訳（メタデータ） (2020-02-08T19:35:01Z)

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

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