論文の概要: Optimal Solutions for the Moving Target Vehicle Routing Problem with Obstacles via Lazy Branch and Price

• arxiv url: http://arxiv.org/abs/2603.21880v2
• Date: Sat, 28 Mar 2026 14:24:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-31 13:48:18.780454
• Title: Optimal Solutions for the Moving Target Vehicle Routing Problem with Obstacles via Lazy Branch and Price
• Title（参考訳）: 遅延分岐と価格による障害物を含む移動目標車両経路問題の最適解法
• Authors: Anoop Bhat, Geordan Gutow, Surya Singh, Zhongqiang Ren, Sivakumar Rathinam, Howie Choset,
• Abstract要約: MT-VRP-Oの最適解を求める遅延連続性(Lazy BPRC)を用いた遅延ブランチ・アンド・プライス(Lazy Branch-and-Price)を提案する。 Lazy BPRCは、制限されたマスター問題(RMP)と価格問題とを交互に扱うVRPのブランチ・アンド・プライス・フレームワークを適用している。 以上の結果から,Lazy BPRCは2倍の速度で動作可能であることがわかった。
• 参考スコア（独自算出の注目度）: 23.0719839118772
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Moving Target Vehicle Routing Problem with Obstacles (MT-VRP-O) seeks trajectories for several agents that collectively intercept a set of moving targets. Each target has one or more time windows where it must be visited, and the agents must avoid static obstacles and satisfy speed and capacity constraints. We introduce Lazy Branch-and-Price with Relaxed Continuity (Lazy BPRC), which finds optimal solutions for the MT-VRP-O. Lazy BPRC applies the branch-and-price framework for VRPs, which alternates between a restricted master problem (RMP) and a pricing problem. The RMP aims to select a sequence of target-time window pairings (called a tour) for each agent to follow, from a limited subset of tours. The pricing problem adds tours to the limited subset. Conventionally, solving the RMP requires computing the cost for an agent to follow each tour in the limited subset. Computing these costs in the MT-VRP-O is computationally intensive, since it requires collision-free motion planning between moving targets. Lazy BPRC defers cost computations by solving the RMP using lower bounds on the costs of each tour, computed via motion planning with relaxed continuity constraints. We lazily evaluate the true costs of tours as-needed. We compute a tour's cost by searching for a shortest path on a Graph of Convex Sets (GCS), and we accelerate this search using our continuity relaxation method. We demonstrate that Lazy BPRC runs up to an order of magnitude faster than two ablations.
• Abstract（参考訳）: MT-VRP-O(Moving Target Vehicle Routing Problem with Obstacles)は、一連の移動目標を総括して迎撃する複数のエージェントの軌跡を求める。 各ターゲットには1つ以上の時間窓があり、エージェントは静的な障害を避け、速度とキャパシティの制約を満たす必要がある。 MT-VRP-Oの最適解を求める遅延連続性(Lazy BPRC)を用いた遅延ブランチ・アンド・プライス(Lazy Branch-and-Price)を提案する。 Lazy BPRCは、制限されたマスター問題(RMP)と価格問題とを交互に扱うVRPのブランチ・アンド・プライス・フレームワークを適用している。 RMPは、ツアーの限られたサブセットから、各エージェントがフォローすべきターゲット時間ウィンドウペアリング(ツアーと呼ばれる)のシーケンスを選択することを目的としている。 価格問題は限られたサブセットにツアーを追加する。 従来、RMPを解くには、エージェントが限られたサブセットで各ツアーに従うためにコストを計算する必要がある。 MT-VRP-Oにおけるこれらのコストの計算は、移動目標間の衝突のない運動計画を必要とするため、計算集約的である。 遅延BPRCは、各ツアーのコストの低い境界を用いてRMPを解き、連続性制約を緩和した動き計画によって計算する。 我々は、必要なツアーの真のコストを怠慢に評価する。 コンベックス集合グラフ(GCS)上の最短経路を探索することでツアーのコストを計算し、連続緩和法を用いてこの探索を高速化する。 以上の結果から,Lazy BPRCは2倍の速度で動作可能であることがわかった。

関連論文リスト

• Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity [24.447439182269974]
  移動目標車両ルーティング問題(MT-VRP)は、一連の移動目標を迎撃する複数のエージェントの軌跡を求める。 MT-VRP に対して,Relaxed Continuity (BPRC) を用いたブランチ・アンド・プライスアルゴリズムを導入する。 提案アルゴリズムは, これまでの研究結果から, ベースラインよりも桁違いに高速な最適解を求める。
  論文  参考訳（メタデータ） (2026-02-28T14:09:54Z)
• Budget-Aware Agentic Routing via Boundary-Guided Training [24.0709108941881]
  予算対応エージェントルーティング(Budget-Aware Agentic Routing)は、各ステップで安価なモデルと高価なモデルを選択して、コスト削減フロンティアを最適化する。 境界誘導訓練(Boundary-Guided Training)は、希少な報酬の下で学習を定着させるために難しい分類法を構築する。 実験結果から,提案手法は高効率フロンティアを改良し,強いルーティングベースラインを極めて低コストで整合することを示した。
  論文  参考訳（メタデータ） (2026-02-04T07:39:27Z)
• SCoTT: Strategic Chain-of-Thought Tasking for Wireless-Aware Robot Navigation in Digital Twins [78.53885607559958]
  無線対応経路計画フレームワークであるSCoTTを提案する。 SCoTT は DP-WA* の2% 以内で経路ゲインを達成し, 連続的に短い軌道を生成できることを示す。 また,ガゼボシミュレーションにおいて,SCoTTをROSノードとして配置することにより,本手法の実用性を示す。
  論文  参考訳（メタデータ） (2024-11-27T10:45:49Z)
• A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets [27.63278352602436]
  本稿では,移動目標トラベリングセールスマン問題(MT-TSP)の最適解を求める新しい定式化を提案する。 問題は、補給所から始まるエージェントの最も短い経路を見つけ、割り当てられた時間ウィンドウ内で1度だけ移動対象のセットを訪れ、補給所に戻ることである。 MT-TSPのためのMICP(Mixed Conic Program)の定式化について検討した。
  論文  参考訳（メタデータ） (2024-03-07T22:03:36Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  本稿では,Roulette Wheel Method (RWPSO) を用いた新しいPSO手法を提案する。 RWPSOのSolomon VRPTWベンチマークデータセットを用いた実験は、RWPSOが文学の他の最先端アルゴリズムと競合していることを示している。
  論文  参考訳（メタデータ） (2023-06-04T09:18:02Z)
• Simultaneous Contact-Rich Grasping and Locomotion via Distributed Optimization Enabling Free-Climbing for Multi-Limbed Robots [60.06216976204385]
  移動, 把握, 接触問題を同時に解くための効率的な運動計画フレームワークを提案する。 ハードウェア実験において提案手法を実証し, より短い計画時間で, 傾斜角45degで自由クライミングを含む様々な動作を実現できることを示す。
  論文  参考訳（メタデータ） (2022-07-04T13:52:10Z)
• Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs [65.23158435596518]
  チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。 我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
  論文  参考訳（メタデータ） (2022-06-13T09:17:40Z)

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

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