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 can be visited, and the agents must avoid static obstacles and satisfy speed and capacity constraints. Previously studied VRPs are often addressed using a framework called branch-and-price. This framework requires computing the cost for a single agent to visit a given sequence of target-time window pairings, for several candidate sequences. These sequences are called tours. Computing tour costs is more expensive in the MT-VRP-O than in previously studied VRPs due to the presence of both moving targets and static obstacles. Thus, we introduce a new exact algorithm, Lazy Branch-and-Price with Relaxed Continuity (Lazy BPRC), for the MT-VRP-O. The key idea in Lazy BPRC is to use cheap-to-compute lower bounds on tour costs where costs are traditionally used, and lazily update lower bounds to true costs. When computing a tour's true cost is needed, we do so by searching for a shortest path on a graph of convex sets, and we introduce a new heuristic to accelerate the search. We demonstrate that Lazy BPRC runs up to an order of magnitude faster than two ablations.
From: Anoop Bhat [view email]
[v1]
Mon, 23 Mar 2026 12:10:12 UTC (621 KB)
[v2]
Sat, 28 Mar 2026 14:24:26 UTC (619 KB)
[v3]
Fri, 17 Apr 2026 00:13:18 UTC (619 KB)
[v4]
Fri, 22 May 2026 16:48:09 UTC (619 KB)
[v5]
Fri, 11 Sep 2026 12:56:20 UTC (641 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。