arxiv: 2603.21880 · v3 · submitted 2026-03-23 · 💻 cs.RO

Recognition: no theorem link

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

Anoop Bhat , Geordan Gutow , Surya Singh , Zhongqiang Ren , Sivakumar Rathinam , Howie Choset

Authors on Pith no claims yet

Pith reviewed 2026-05-15 01:03 UTC · model grok-4.3

classification 💻 cs.RO

keywords moving target vehicle routingbranch and pricelazy evaluationgraph of convex setsmotion planningobstaclestime windowsoptimal routing

0 comments

The pith

Lazy Branch-and-Price with Relaxed Continuity finds optimal routes for agents to intercept moving targets while avoiding obstacles.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces Lazy BPRC to solve the Moving Target Vehicle Routing Problem with Obstacles to optimality. It adapts the branch-and-price framework by using lower bounds on tour costs from motion planning with relaxed continuity constraints, deferring full expensive calculations until necessary. True costs are then computed lazily by finding shortest paths on a Graph of Convex Sets. This produces exact solutions for multi-agent routing with time windows, speed limits, capacity, and static obstacles. A reader would care because exact methods for such dynamic routing problems have been too slow for practical use.

Core claim

Lazy BPRC finds optimal solutions for the MT-VRP-O by alternating between a restricted master problem that selects tours using lower-bound costs from relaxed continuity constraints and a pricing problem that generates new tours, lazily evaluating true shortest-path costs on a Graph of Convex Sets only when the bounds indicate a tour is promising.

What carries the argument

Lazy Branch-and-Price with Relaxed Continuity (Lazy BPRC), which defers true cost computations in the branch-and-price framework via lower bounds from motion planning with relaxed continuity constraints solved on a Graph of Convex Sets.

If this is right

Optimal solutions can be found for MT-VRP-O instances that include multiple agents, moving targets with time windows, static obstacles, and constraints on speed and capacity.
The method runs up to an order of magnitude faster than two ablations that lack the lazy evaluation or the continuity relaxation.
Tours are represented as sequences of target-time window pairings and their costs are obtained from shortest paths on a Graph of Convex Sets.
The restricted master problem selects from a growing set of tours while the pricing problem adds new ones based on the current lower-bound solution.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same lazy bounding approach could reduce computation in other vehicle routing settings where evaluating each candidate route requires solving a continuous motion planning subproblem.
Tighter or adaptive relaxations of the continuity constraints might further improve the balance between bound quality and computation time.
The framework could support online replanning by reusing previously generated tours and bounds when targets change trajectory.
Integrating this method with sampling-based planners might extend its applicability to higher-dimensional configuration spaces.

Load-bearing premise

The lower bounds obtained from motion planning with relaxed continuity constraints are sufficiently tight that the branch-and-price procedure still finds the true optimum without prematurely discarding optimal tours.

What would settle it

A small MT-VRP-O instance with a known optimal tour where the lower bound from the relaxed continuity method exceeds the true cost of that tour, causing the algorithm to prune it and return a suboptimal solution.

Figures

Figures reproduced from arXiv: 2603.21880 by Anoop Bhat, Geordan Gutow, Howie Choset, Sivakumar Rathinam, Surya Singh, Zhongqiang Ren.

**Figure 2.** Figure 2: Computing bounds on the cost of an example tour [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Figure 3: (a) Varying the number of targets. Lazy BPRC shows smaller [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Lazy BPRC gives a workable way to cut down on expensive motion-planning calls inside branch-and-price for moving-target routing, but the optimality argument rests on how they correct the duals after swapping in true costs.

read the letter

The main takeaway is that this paper shows how to keep branch-and-price tractable for the MT-VRP-O by solving the restricted master with cheap lower bounds from relaxed-continuity GCS paths and only computing exact tour costs when a column is selected. That lazy step is the concrete addition over standard VRP solvers and over plain GCS shortest-path methods. It builds directly on existing column-generation machinery and on the Graph of Convex Sets formulation, so the implementation path is clear for anyone already using those tools. The claimed order-of-magnitude speedup over the two ablations is the practical payoff if the numbers hold up in the full experiments. The approach is incremental rather than foundational, but it targets a real bottleneck in multi-agent interception problems with time windows and static obstacles. The soft spot is the one the stress-test note flags: when the master problem is solved with underestimates, the dual prices passed to the pricing subproblem are not the true reduced costs. The abstract does not describe a correction step, a re-optimization pass after true-cost insertion, or a formal argument that the final solution is still optimal. If the paper only shows feasible solutions that match known optima on small instances, that is useful but weaker than the optimality claim. A reader who already works with branch-and-price or GCS will get the most from the details; someone outside that niche will mainly see another VRP variant. The work is coherent on its own terms and cites the relevant prior results, so it is worth sending to referees who can check the dual-handling implementation and the experimental controls. I would bring it to a reading group focused on motion planning or combinatorial optimization.

Referee Report

2 major / 2 minor

Summary. The paper introduces Lazy Branch-and-Price with Relaxed Continuity (Lazy BPRC) for the Moving Target Vehicle Routing Problem with Obstacles (MT-VRP-O). It extends the branch-and-price framework by solving the restricted master problem using lower bounds on tour costs obtained from Graph of Convex Sets (GCS) shortest paths under relaxed continuity constraints, lazily computing exact costs only when needed. The approach claims to yield optimal solutions while achieving up to an order of magnitude speedup over two ablation methods.

Significance. If the optimality guarantee holds, this work would represent a significant advance in exact methods for dynamic vehicle routing problems involving moving targets and obstacles. By integrating relaxed motion planning bounds into column generation, it addresses the computational bottleneck of repeated motion planning in VRP solvers, with potential applications in autonomous robotics and logistics. The lazy evaluation strategy and use of GCS for acceleration are promising contributions.

major comments (2)

[§4.2] §4.2 (RMP and Pricing): The description states that the RMP is solved with lower-bound costs from relaxed continuity GCS paths, but does not specify how dual variables are recomputed or the master re-optimized after exact costs are inserted for selected columns. This is load-bearing for the optimality claim, as incorrect reduced costs could cause the pricing loop to terminate with a suboptimal set of tours.
[§5] §5 (Experiments): The claim of 'up to an order of magnitude faster' and optimality is asserted without reported numerical tables, specific ablation descriptions, or bound-tightness metrics (e.g., gap between lower-bound and exact costs across instances). Without these, the central performance and correctness assertions cannot be verified.

minor comments (2)

[Abstract] Abstract: The two ablations are referenced but not named or briefly characterized, which reduces clarity for readers assessing the speedup claim.
[Notation] Notation: Ensure 'tour' is consistently defined as a sequence of target-time window pairings from the first use onward.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive feedback on our manuscript. We address the major comments point by point below, providing clarifications and committing to revisions where appropriate to strengthen the presentation of our Lazy BPRC method.

read point-by-point responses

Referee: [§4.2] §4.2 (RMP and Pricing): The description states that the RMP is solved with lower-bound costs from relaxed continuity GCS paths, but does not specify how dual variables are recomputed or the master re-optimized after exact costs are inserted for selected columns. This is load-bearing for the optimality claim, as incorrect reduced costs could cause the pricing loop to terminate with a suboptimal set of tours.

Authors: Thank you for highlighting this important detail. In the Lazy BPRC algorithm, when a column's exact cost is computed and inserted into the RMP, we update the corresponding objective coefficient in the master problem and immediately re-solve the RMP to obtain the new dual variables. This ensures that subsequent pricing problems use accurate reduced costs based on the exact costs. We will expand the description in Section 4.2 to explicitly outline this re-optimization step, thereby reinforcing the optimality guarantee of the approach. revision: yes
Referee: [§5] §5 (Experiments): The claim of 'up to an order of magnitude faster' and optimality is asserted without reported numerical tables, specific ablation descriptions, or bound-tightness metrics (e.g., gap between lower-bound and exact costs across instances). Without these, the central performance and correctness assertions cannot be verified.

Authors: We agree that the experimental results would benefit from more detailed reporting. While the manuscript summarizes the performance improvements, we will include full numerical tables in the revised Section 5, detailing runtimes for Lazy BPRC and the two ablations across all test instances, along with specific descriptions of the ablations and metrics on the tightness of the relaxed continuity bounds (such as average and maximum gaps between lower-bound and exact costs). This will allow readers to verify the claims of optimality and speedup. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algorithmic construction from standard primitives

full rationale

The paper presents Lazy BPRC as a direct algorithmic extension of branch-and-price that lazily substitutes lower-bound costs (from GCS paths under relaxed continuity) into the restricted master problem and evaluates exact costs only for selected columns. No equation, theorem, or performance claim reduces the asserted optimality or runtime improvement to a fitted parameter, self-definition, or self-citation chain; the method is a constructive combination of existing VRP and motion-planning techniques whose correctness rests on the standard column-generation termination criterion once exact costs are inserted. The derivation chain is therefore self-contained against external algorithmic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The method relies on established components (branch-and-price framework, Graph of Convex Sets, standard motion-planning primitives) without introducing new free parameters, axioms, or postulated entities in the abstract.

pith-pipeline@v0.9.0 · 5589 in / 1068 out tokens · 52999 ms · 2026-05-15T01:03:20.446219+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages · 1 internal anchor

[1]

The moving-target traveling salesman problem,

C. S. Helvig, G. Robins, and A. Zelikovsky, “The moving-target traveling salesman problem,”Journal of Algorithms, vol. 49, no. 1, pp. 153–174, 2003

work page 2003
[2]

C. D. Smith,Assessment of genetic algorithm based assignment strategies for unmanned systems using the multiple traveling salesman problem with moving targets. University of Missouri-Kansas City, 2021

work page 2021
[3]

Dealing with time in the multiple traveling salespersons problem with moving targets,

A. Stieber and A. F ¨ugenschuh, “Dealing with time in the multiple traveling salespersons problem with moving targets,”Central Euro- pean Journal of Operations Research, vol. 30, no. 3, pp. 991–1017, 2022

work page 2022
[4]

On-orbit servicing: a time-dependent, moving-target traveling salesman problem,

J.-M. Bourjolly, O. Gurtuna, and A. Lyngvi, “On-orbit servicing: a time-dependent, moving-target traveling salesman problem,”Interna- tional Transactions in Operational Research, vol. 13, no. 5, pp. 461– 481, 2006

work page 2006
[5]

Rendezvous planning for multiple auvs with mobile charging stations in dynamic currents,

B. Li, B. R. Page, J. Hoffman, B. Moridian, and N. Mahmoudian, “Rendezvous planning for multiple auvs with mobile charging stations in dynamic currents,”IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 1653–1660, 2019

work page 2019
[6]

Toth and D

P. Toth and D. Vigo,Vehicle routing: problems, methods, and appli- cations. SIAM, 2014

work page 2014
[7]

Beyond fifty years of vehicle routing: Insights into the history and the future,

C. Archetti, L. Coelho, M. Speranza, and P. Vansteenwegen, “Beyond fifty years of vehicle routing: Insights into the history and the future,” European Journal of Operational Research, 2025

work page 2025
[8]

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

A. Bhat, G. Gutow, Z. Ren, S. Rathinam, and H. Choset, “Optimal solutions for the moving target vehicle routing problem via branch-and-price with relaxed continuity,” 2026. [Online]. Available: https://arxiv.org/abs/2603.00663

work page internal anchor Pith review Pith/arXiv arXiv 2026
[9]

Approximation results for kinetic variants of tsp,

M. Hammar and B. J. Nilsson, “Approximation results for kinetic variants of tsp,” inAutomata, Languages and Programming: 26th International Colloquium, ICALP’99 Prague, Czech Republic, July 11–15, 1999 Proceedings 26. Springer, 1999, pp. 392–401

work page 1999
[10]

Exact branch-price-and- cut algorithms for vehicle routing,

L. Costa, C. Contardo, and G. Desaulniers, “Exact branch-price-and- cut algorithms for vehicle routing,”Transportation Science, vol. 53, no. 4, pp. 946–985, 2019

work page 2019
[11]

A tutorial on column generation and branch-and-price for vehicle routing problems,

D. Feillet, “A tutorial on column generation and branch-and-price for vehicle routing problems,”4or, vol. 8, no. 4, pp. 407–424, 2010

work page 2010
[12]

Shortest paths in graphs of convex sets,

T. Marcucci, J. Umenberger, P. Parrilo, and R. Tedrake, “Shortest paths in graphs of convex sets,”SIAM Journal on Optimization, vol. 34, no. 1, pp. 507–532, 2024

work page 2024
[13]

A complete and bounded-suboptimal algorithm for a moving target traveling salesman problem with obstacles in 3d*,

A. Bhat, G. Gutow, B. Vundurthy, Z. Ren, S. Rathinam, and H. Choset, “A complete and bounded-suboptimal algorithm for a moving target traveling salesman problem with obstacles in 3d*,” in2025 IEEE International Conference on Robotics and Automation (ICRA), 2025, pp. 6132–6138

work page 2025
[14]

A complete algorithm for a moving target traveling salesman problem with obstacles,

——, “A complete algorithm for a moving target traveling salesman problem with obstacles,” inInternational Workshop on the Algorithmic Foundations of Robotics. Springer, 2024

work page 2024
[15]

A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations,

G. Ozbaygin, O. E. Karasan, M. Savelsbergh, and H. Yaman, “A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations,”Transportation Research Part B: Method- ological, vol. 100, pp. 115–137, 2017

work page 2017
[16]

Shortest path between two simple polygons,

T. Asano, T. Asano, and H. Imai, “Shortest path between two simple polygons,”Information processing letters, vol. 24, no. 5, pp. 285–288, 1987

work page 1987
[17]

Compromise-free pathfind- ing on a navigation mesh

M. Cui, D. D. Harabor, and A. Grastien, “Compromise-free pathfind- ing on a navigation mesh.” inIJCAI, 2017, pp. 496–502

work page 2017