Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity

Anoop Bhat; Geordan Gutow; Zhongqiang Ren; Sivakumar Rathinam; Howie Choset

cs.ROFeb 28, 2026

Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity

Authors: Anoop Bhat, Geordan Gutow, Zhongqiang Ren, Sivakumar Rathinam, Howie Choset

Organizations: Robotics Institute at Carnegie Mellon University, Pittsburgh, PA 15213 · Mechanical and Aerospace Engineering at Michigan Technological University, Houghton, MI 49931 · UM-SJTU Joint Institute and Department of Automation at Shanghai Jiao Tong University, Shanghai, China · Department of Mechanical Engineering and Department of Computer Science and Engineering at Texas A&M University, College Station, TX 77843

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.

Figures & tables

Figure 1: Targets move along piecewise-linear trajectories with time windows shown in bold lines. Two agents begin at the depot and collectively intercept all targets. Trajectories of agents are shown in blue.

Figure 2: Example where existing VRP dominance checks fail for the MT-VRP. Since each target has one time window in this example, we represent a target-window using the index of the target. We treat the depot as a fictitious target 0. (a) ${\tau_{\textnormal{a}}}$ is an optimal (i.e. minimum-distance) trajectory visiting the sequence of targets $\Gamma=(0,3,1,2)$ , and ${\tau_{\textnormal{a}}}^{\prime}$ is an optimal trajectory visiting the sequence $\Gamma^{\prime}=(0,1,3,2)$ . 3 3 3 Agents in the MT-VRP can change their speed, which is why ${\tau_{\textnormal{a}}}$ and ${\tau_{\textnormal{a}}}^{\prime}$ can travel the same distance, even though ${\tau_{\textnormal{a}}}$ meets target 2 later than ${\tau_{\textnormal{a}}}^{\prime}$ : ${\tau_{\textnormal{a}}}$ can simply arrive at its interception position, then stop and wait for target 2. Conventional VRP dominance checks would conclude that $\Gamma$ dominates $\Gamma^{\prime}$ , since ${\tau_{\textnormal{a}}}$ and ${\tau_{\textnormal{a}}}^{\prime}$ have the same cost. 4 4 4 While dominance checks technically compare reduced cost , which adds bias terms to the cost, the bias terms for $\Gamma$ and $\Gamma^{\prime}$ are equal in Fig. 4 (a), and the same goes for $\bar{\Gamma}$ and $\bar{\Gamma}^{\prime}$ in Fig. 4 (b). (b) $\bar{\tau}_{\text{a}}$ optimally visits $\bar{\Gamma}=(0,3,1,2,4,0)$ obtained by appending 4 and 0 to $\Gamma$ , and $\bar{\tau}_{\text{a}}^{\prime}$ optimally visits $\bar{\Gamma}^{\prime}=(0,1,3,2,4,0)$ , obtained by appending 4 and 0 to $\Gamma^{\prime}$ . $\bar{\tau}_{\text{a}}$ travels more distance than $\bar{\tau}_{\text{a}}^{\prime}$ , so $\bar{\Gamma}$ is worse than $\bar{\Gamma}^{\prime}$ . Thus $\Gamma$ does not dominate $\Gamma^{\prime}$ .

Figure 3: (a) and (b) show two partial tours $\Gamma$ and $\Gamma^{\prime}$ ending with $\gamma_{1,2}$ . We want to check if $\Gamma$ dominates $\Gamma^{\prime}$ . (c) We check dominance by comparing an upper-bounding trajectory $\tau_{\text{a,ub}}$ for $\Gamma$ and a lower-bounding trajectory $\tau_{\text{a,lb}}^{\prime}$ for $\Gamma^{\prime}$ , as described in Section 5.2 . (d) We strengthen our dominance check by dividing $\gamma_{1,2}$ into segments and applying the check from (c) for each segment; an example is shown for the 5th segment of $\gamma_{1,2}$ , denoted as $\xi_{1,2,5}$ .

Panel of Figure 4 — Algorithm 1 SolvePricingProblem( $\lambda,\mathcal{B}$ )

Figure 4: (a) Varying the number of targets. The gap in computation time between BPRC and the baseline and ablations widens as we increase the number of targets up to 20. The gap shrinks at 25 targets because BPRC reaches the time limit in 5 instances. We do not show a computation time for BPRC-ablate-dominance for 25 targets because it reached the memory limit in every instance. (b) Varying the capacity. BPRC shows advantage for small capacities. (c) %Gap (as defined in Experiment 2) of each method’s relaxation solution. BPRC’s relaxation has a smaller %Gap, and is thus tighter, in every instance. (d) Varying the number of agents. BPRC shows advantage when the number of agents is 3 or larger. (e) Varying the time window lengths. BPRC’s performance advantage widens as we increase time window length up to 50, then shrinks because BPRC reaches the time limit in many instances. (f) Varying the number of segments in BPRC. Horizontal and vertical axes are log-scaled. MICP’s min, median, and max are shown as flat lines without scatter points because the quantity being varied is specific to BPRC. We only show MICP’s computation time to indicate that BPRC has smaller median computation time for a wide range of parameter values.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 6 — Algorithm 2 GenerateFeasibleSolution( $\mathcal{B}$ )

Vehicle Routing

Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.

See all 135 papers

Optimal Solutions for the Moving Target Vehicle Routing Problem with Obstacles via Lazy Branch-and-Price
Mar 23, 2026Anoop Bhat, Geordan Gutow, David Neiman +4Vehicle Routing Motion Planning
Robotics Institute at Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213. · Mechanical and Aerospace Engineering at Michigan Technological University, Houghton, MI 49931 · Robotics and AI Institute, Cambridge, MA 02142. +2
Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles
Jun 17, 2026Allen George Philip, Anoop Bhat, Sivakumar Rathinam +1Traveling Salesperson Problem Combinatorial Optimization
Mechanical Engineering, Texas A&M University, College Station, TX 77843-3123 · Robotics Institute, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213, USA · Mechanical Engineering, and Computer Science and Engineering, Texas A&M University, College Station, TX 77843-3123
Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints
Aug 14, 2026Andrew Soroka, German Mikhelson, Alexander Mescheryakov +1Vehicle Routing Metaheuristic Optimization
Moscow State University, Faculty of Computational Mathematics and Cybernetics, Moscow · Space Research Institute of RAS, Moscow

Mar 23, 2026J/K move · Enter open · S save

Optimal Solutions for the Moving Target Vehicle Routing Problem with Obstacles via Lazy Branch-and-Price

Anoop Bhat, Geordan Gutow, David Neiman, Surya Singh+3

Robotics Institute at Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213. · Mechanical and Aerospace Engineering at Michigan Technological University, Houghton, MI 49931 · Robotics and AI Institute, Cambridge, MA 02142.+2

Vehicle Routing Motion Planning

Open paper AskPDF arXiv

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.

Abstract

Vehicle Routing

Explore similar work

Optimal Solutions for the Moving Target Vehicle Routing Problem with Obstacles via Lazy Branch-and-Price

Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles

Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints