論文の概要: The Iterative Chainlet Partitioning Algorithm for the Traveling Salesman Problem with Drone and Neural Acceleration

• arxiv url: http://arxiv.org/abs/2504.15147v1
• Date: Mon, 21 Apr 2025 14:51:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-29 16:11:02.352763
• Title: The Iterative Chainlet Partitioning Algorithm for the Traveling Salesman Problem with Drone and Neural Acceleration
• Title（参考訳）: ドローンとニューラルアクセラレーションを用いたトラベリングセールスマン問題の反復連鎖分割アルゴリズム
• Authors: Jae Hyeok Lee, Minjun Kim, Jinkyoo Park, Changhyun Kwon,
• Abstract要約: ドローンによるトラベリングセールスマン問題(TSP-D)解決のための反復連鎖分割(ICP)アルゴリズムとそのニューラルネットワーク ICPは、ソリューションの品質と計算時間の両方で、既存のアルゴリズムより優れています。
• 参考スコア（独自算出の注目度）: 19.41080715658528
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This study introduces the Iterative Chainlet Partitioning (ICP) algorithm and its neural acceleration for solving the Traveling Salesman Problem with Drone (TSP-D). The proposed ICP algorithm decomposes a TSP-D solution into smaller segments called chainlets, each optimized individually by a dynamic programming subroutine. The chainlet with the highest improvement is updated and the procedure is repeated until no further improvement is possible. The number of subroutine calls is bounded linearly in problem size for the first iteration and remains constant in subsequent iterations, ensuring algorithmic scalability. Empirical results show that ICP outperforms existing algorithms in both solution quality and computational time. Tested over 1,059 benchmark instances, ICP yields an average improvement of 2.75% in solution quality over the previous state-of-the-art algorithm while reducing computational time by 79.8%. The procedure is deterministic, ensuring reliability without requiring multiple runs. The subroutine is the computational bottleneck in the already efficient ICP algorithm. To reduce the necessity of subroutine calls, we integrate a graph neural network (GNN) to predict incremental improvements. We demonstrate that the resulting Neuro ICP (NICP) achieves substantial acceleration while maintaining solution quality. Compared to ICP, NICP reduces the total computational time by 49.7%, while the objective function value increase is limited to 0.12%. The framework's adaptability to various operational constraints makes it a valuable foundation for developing efficient algorithms for truck-drone synchronized routing problems.
• Abstract（参考訳）: 本研究では、反復連鎖分割(ICP)アルゴリズムと、そのニューラルアクセラレーションを用いて、ドローンによるトラベリングセールスマン問題(TSP-D)を解決する。 提案したICPアルゴリズムはTSP-Dの解をチェーンレットと呼ばれる小さなセグメントに分解し,動的プログラミングサブルーチンによって個別に最適化する。 改善率の高いチェーンレットを更新し、さらなる改善が不可能になるまで手順を繰り返す。 サブルーチン呼び出しの数は、最初のイテレーションでは問題のサイズが線形に制限され、その後のイテレーションでは一定であり、アルゴリズムのスケーラビリティが保証される。 実験の結果、ICPは解の質と計算時間の両方で既存のアルゴリズムよりも優れていた。 1,059のベンチマークインスタンスでテストした結果、ICPは従来の最先端アルゴリズムよりも平均2.75%のソリューション品質向上を実現し、計算時間を79.8%削減した。 手順は決定論的であり、複数の実行を必要とせずに信頼性を確保する。 サブルーチンは、既に効率的なICPアルゴリズムにおける計算ボトルネックである。 サブルーチン呼び出しの必要性を低減するため、グラフニューラルネットワーク(GNN)を統合して、漸進的な改善を予測する。 結果, NICP (Neuro ICP) は, 溶液品質を維持しながら, 相当な加速を達成できることを実証した。 ICPと比較して、NICPは計算時間を49.7%削減し、目的関数値の増大は0.12%に制限される。 このフレームワークの様々な運用上の制約への適応性は、トラックドロンの同期ルーティング問題に対する効率的なアルゴリズムを開発するための貴重な基盤となる。

関連論文リスト

• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。 USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
  論文  参考訳（メタデータ） (2023-12-19T02:27:22Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。 我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
  論文  参考訳（メタデータ） (2022-10-21T15:56:13Z)
• Optimization-Based GenQSGD for Federated Edge Learning [12.371264770814097]
  我々は、連合学習(FL)のための一般化された並列最小バッチ収束降下(SGD)アルゴリズムを提案する。 我々は,時間収束誤差の下でのエネルギーコストを最小限に抑えるために,アルゴリズムパラメータを最適化する。 その結果,既存のFLアルゴリズムよりも有意な利得が得られた。
  論文  参考訳（メタデータ） (2021-10-25T14:25:11Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• An Efficient Algorithm for Cooperative Semi-Bandits [0.0]
  本稿では,有名なFollow The Perturbed Leaderアルゴリズムの協調バージョンであるCoop-FTPLを紹介する。 T 時間ステップ後のアルゴリズムの期待された後悔は QT log(k)(k$alpha$ 1 /Q + m) であり、Q は総アクティベーション確率質量である。
  論文  参考訳（メタデータ） (2020-10-05T07:08:26Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Fast and Robust Iterative Closest Point [32.42799285301607]
  イテレーティブ・クローズト・ポイント(ICP)は、2つの点集合間の剛性登録のための基本技術である。 Sparse ICPのような最近の研究は、計算速度を犠牲にしてスパース性最適化によって堅牢性を達成する。 本稿では,古典的な点対点ICPを最大化最小化(MM)アルゴリズムとして扱えることを示す。
  論文  参考訳（メタデータ） (2020-07-15T11:32:53Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。 本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
  論文  参考訳（メタデータ） (2020-06-21T11:23:20Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)
• Channel Assignment in Uplink Wireless Communication using Machine Learning Approach [54.012791474906514]
  本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。 我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。 計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
  論文  参考訳（メタデータ） (2020-01-12T15:54:20Z)

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

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