論文の概要: Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity
- arxiv url: http://arxiv.org/abs/2603.00663v2
- Date: Tue, 17 Mar 2026 12:45:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-23 08:17:41.785728
- Title: Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity
- Title（参考訳）: リラクシド連続性を有する分岐・価格による移動目標車両経路問題の最適解法
- Authors: Anoop Bhat, Geordan Gutow, Zhongqiang Ren, Sivakumar Rathinam, Howie Choset,
- Abstract要約: 移動目標車両ルーティング問題(MT-VRP)は、一連の移動目標を迎撃する複数のエージェントの軌跡を求める。
MT-VRP に対して,Relaxed Continuity (BPRC) を用いたブランチ・アンド・プライスアルゴリズムを導入する。
提案アルゴリズムは, これまでの研究結果から, ベースラインよりも桁違いに高速な最適解を求める。
- 参考スコア（独自算出の注目度）: 24.447439182269974
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Moving Target Vehicle Routing Problem (MT-VRP) seeks trajectories for several agents that intercept a set of moving targets, subject to speed, time window, and capacity constraints. We introduce an exact algorithm, Branch-and-Price with Relaxed Continuity (BPRC), for the MT-VRP. The main challenge in a branch-and-price approach for the MT-VRP is the pricing subproblem, which is complicated by moving targets and time-dependent travel costs between targets. Our key contribution is a new labeling algorithm that solves this subproblem by means of a novel dominance criterion tailored for problems with moving targets. Numerical results on instances with up to 25 targets show that our algorithm finds optimal solutions more than an order of magnitude faster than a baseline based on previous work, showing particular strength in scenarios with limited agent capacities.
- Abstract（参考訳）: 移動目標車両ルーティング問題(MT-VRP)は、速度、時間窓、容量の制約を受ける一連の移動目標を傍受するいくつかのエージェントの軌跡を求める。
MT-VRP に対して,Relaxed Continuity (BPRC) を用いたブランチ・アンド・プライスアルゴリズムを導入する。
MT-VRPのブランチ・アンド・プライスアプローチの主な課題は価格サブプロブレムである。
我々の重要な貢献は、移動目標の問題に適した新しい支配基準によって、このサブプロブレムを解決する新しいラベリングアルゴリズムである。
最大25個のターゲットを持つインスタンス上での数値的な結果から,提案アルゴリズムは従来よりも1桁以上高速な最適解を求めることができ,エージェント能力に制限のあるシナリオにおいて,特に強みを示す。
関連論文リスト
- Blockchain-Enabled Routing for Zero-Trust Low-Altitude Intelligent Networks [77.17664010626726]
低高度インテリジェントネットワーク(LAIN)における複数のUAVクラスタによるルーティングに焦点を当てる。
潜在的な脅威によるダメージを最小限に抑えるため,ソフトウェア定義の周辺技術とブロックチェーン技術を用いたゼロトラストアーキテクチャを提案する。
提案手法は,平均E2E遅延を59%削減し,TSRを29%改善することを示した。
論文 参考訳（メタデータ） (2026-02-27T04:30:35Z) - Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
車両ルーティング問題 (VRP) は進化的最適化における基本的なNPハード問題である。
本稿では、強化学習エージェントを事前のインスタンスで訓練し、初期解を迅速に生成する最適化フレームワークを提案する。
このフレームワークは、様々な時間予算において、現在の最先端のソルバよりも一貫して優れています。
論文 参考訳（メタデータ） (2025-04-08T15:21:01Z) - A Bi-Objective Approach to Last-Mile Delivery Routing Considering Driver Preferences [42.16665455951525]
MOVRP(Multi-Objective Vehicle Routing Problem)は、輸送・物流業界における複雑な最適化問題である。
本稿では,運転者の判断や操作者の嗜好を考慮した経路作成を目的としたMOVRPに対する新しいアプローチを提案する。
この目的に対処するための2つのアプローチとして,視覚的に魅力的な経路計画と,同様の経路を計画するための過去の運転行動のデータマイニングを評価した。
論文 参考訳（メタデータ） (2024-05-25T04:25:00Z) - 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) - Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。
本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。
特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
論文 参考訳（メタデータ） (2023-10-22T02:46:37Z) - 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) - Goal Kernel Planning: Linearly-Solvable Non-Markovian Policies for Logical Tasks with Goal-Conditioned Options [54.40780660868349]
我々はLinearly-Solvable Goal Kernel Dynamic Programming (LS-GKDP)と呼ばれる合成フレームワークを導入する。
LS-GKDPは、Linearly-Solvable Markov Decision Process (LMDP)形式とOptions Framework of Reinforcement Learningを組み合わせたものである。
本稿では,目標カーネルを持つLMDPが,タスク接地によって定義された低次元部分空間におけるメタポリティシの効率的な最適化を実現する方法を示す。
論文 参考訳（メタデータ） (2020-07-06T05:13:20Z) - Learning to Track Dynamic Targets in Partially Known Environments [48.49957897251128]
我々は、アクティブな目標追跡を解決するために、深層強化学習アプローチを用いる。
特に,アクティブ・トラッカー・ターゲティング・ネットワーク(ATTN)を導入し,アクティブ・ターゲティング・ターゲティングの主要なタスクを解決するための統一的なRLポリシーを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:45:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。