提出新算法，高效求解移动目标车辆路径问题。
Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity
- 设计新型标签算法与支配准则，解决动态目标下的路径优化难题。
- 在25个目标实例上，求解速度比基线快10倍以上。
- 特别适合代理容量受限的实际场景，如巡检与救援任务。
移动目标车辆路径问题（MT-VRP）旨在为多个智能体规划路径，以在满足速度、时间窗和容量约束的前提下拦截一组移动目标。本文提出一种精确算法——带松弛连续性的分支定价法（BPRC）。该算法的核心挑战在于定价子问题，其复杂性源于移动目标与随时间变化的路径成本。本文关键贡献是设计了一种新型标签算法，结合专为移动目标问题定制的支配准则，有效求解定价子问题。在包含最多25个目标的实例上，该算法求得最优解的速度比基于先前工作的基线方法快一个数量级以上，尤其在代理容量受限的情况下表现突出。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。