論文の概要: 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（参考訳）: 遅延分岐と価格による障害物を含む移動目標車両経路問題の最適解法
- 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倍の速度で動作可能であることがわかった。
関連論文リスト
- Drive, Pack, Fly: The Travelling Thief Problem with Drone [0.0]
収集作業では、積荷の蓄積が徐々に車両を減速させ、ルーティング効率に累積的なペナルティを与える。
搭載ドローンは、外装品を回収し、メイスパンを短くし、運用利益を増大させることで、このペナルティを相殺することができる。
本稿では,TTP-D(Travelling Thief Problem with Drone)を提案する。
論文 参考訳（メタデータ） (2026-08-17T11:34:15Z) - CR^2: Cost-Aware Risk-Controlled Routing for Wireless Device-Edge LLM Inference [52.849509991178884]
大規模言語モデル(LLM)は集中型クラウドからモバイルエッジ環境に移行する。
軽量オンデバイスモデルとより強力なエッジモデルの間のクエリレベルのルーティングは、このトレードオフをナビゲートするための柔軟なメカニズムを提供する。
既存のルータは、集中クラウド設定とトークンレベルのコストの最適化のために設計されており、無線エッジデプロイメントにおける動的レイテンシとエネルギーオーバーヘッドをキャプチャできない。
論文 参考訳（メタデータ） (2026-05-12T11:50:15Z) - Navigating the Clutter: Waypoint-Based Bi-Level Planning for Multi-Robot Systems [54.887871365121775]
乱雑な環境におけるマルチロボット制御は、複雑な物理的制約を伴う難しい問題である。
タスクとモーションプランニングを協調的に最適化するハイブリッドマルチロボット制御フレームワークを提案する。
我々のアプローチは、動作に依存しないベースラインとVLAベースのベースラインよりもタスクの成功を継続的に改善する。
論文 参考訳（メタデータ） (2026-04-22T22:58:47Z) - 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) - Optimal Cost Design for Model Predictive Control [30.86835688868485]
多くのロボティクスドメインは、計画に非モデル制御(MPC)を使用し、時間的地平線を減らし、最適化を行い、各ステップで再計画を行う。
本研究では, MPC を用いて最適化するコストは, タスクの真理コスト(端末コスト)と同等である,という一般的な仮定に挑戦する。
連続型MDPにおけるMPC計画ロボットの最適コストを設計できるゼロ階トラジェクトリに基づくアプローチを提案する。
論文 参考訳（メタデータ） (2021-04-23T00:00:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。