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

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

URL: http://arxiv.org/abs/2603.21880v2
Date: Sat, 28 Mar 2026 14:24:26 GMT
Title: Optimal Solutions for the Moving Target Vehicle Routing Problem with Obstacles via Lazy Branch and Price
Abstract summary: We introduce Lazy Branch-and-Price with Relaxed Continuity (Lazy BPRC), which finds optimal solutions for the MT-VRP-O.<n>Lazy BPRC applies the branch-and-price framework for VRPs, which alternates between a restricted master problem (RMP) and a pricing problem.<n>We demonstrate that Lazy BPRC runs up to an order of magnitude faster than two ablations.
Score: 23.0719839118772
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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.

Related papers

Drive, Pack, Fly: The Travelling Thief Problem with Drone [0.0]
In collection operations, accumulating payload progressively slows the vehicle, imposing a cumulative penalty on routing efficiency.<n>An onboard drone can offset this penalty by retrieving outlying items, thereby shortening the makespan and increasing operational profit.<n>This paper introduces the Travelling Thief Problem with Drone (TTP-D), which maximises the collected profit, net of a time-based rental cost.
arXiv Detail & Related papers (2026-08-17T11:34:15Z)
CR^2: Cost-Aware Risk-Controlled Routing for Wireless Device-Edge LLM Inference [52.849509991178884]
Large language models (LLMs) move from centralized clouds to mobile edge environments.<n> query-level routing between lightweight on-device models and stronger edge models provides a flexible mechanism to navigate this trade-off.<n>Existing routers are designed for centralized cloud settings and optimize token-level costs, failing to capture the dynamic latency and energy overheads in wireless edge deployments.
arXiv Detail & Related papers (2026-05-12T11:50:15Z)
Navigating the Clutter: Waypoint-Based Bi-Level Planning for Multi-Robot Systems [54.887871365121775]
Multi-robot control in cluttered environments is a challenging problem that involves complex physical constraints.<n>We propose a hybrid multi-robot control framework that jointly optimize task and motion planning.<n>Our approach consistently improves task success over motion-agnostic and VLA-based baselines.
arXiv Detail & Related papers (2026-04-22T22:58:47Z)
Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity [24.447439182269974]
The Moving Target Vehicle Routing Problem (MT-VRP) seeks trajectories for several agents that intercept a set of moving targets.<n>We introduce an exact algorithm, Branch-and-Price with Relaxed Continuity (BPRC), for the MT-VRP.<n>We show that our algorithm finds optimal solutions more than an order of magnitude faster than a baseline based on previous work.
arXiv Detail & Related papers (2026-02-28T14:09:54Z)
Budget-Aware Agentic Routing via Boundary-Guided Training [24.0709108941881]
Budget-Aware Agentic Routing selects between a cheap and an expensive model at each step to optimize the cost-success frontier.<n> Boundary-Guided Training builds a difficulty taxonomy to anchor learning under sparse rewards.<n>Experiment results show that our method improves the efficiency frontier, matching strong routing baselines at substantially lower cost.
arXiv Detail & Related papers (2026-02-04T07:39:27Z)
SCoTT: Strategic Chain-of-Thought Tasking for Wireless-Aware Robot Navigation in Digital Twins [78.53885607559958]
We propose SCoTT, a wireless-aware path planning framework.<n>We show that SCoTT achieves path gains within 2% of DP-WA* while consistently generating shorter trajectories.<n>We also show the practical viability of our approach by deploying SCoTT as a ROS node within Gazebo simulations.
arXiv Detail & Related papers (2024-11-27T10:45:49Z)
A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets [27.63278352602436]
This paper introduces a new formulation that finds the optimum for the Moving-Target Traveling Salesman Problem (MT-TSP)<n>The problem seeks to find a shortest path for an agent, that starts at a depot, visits a set of moving targets exactly once within their assigned time-windows, and returns to the depot.<n>We compare our formulation with the current state-of-the-art Mixed Conic Program (MICP) solver for the MT-TSP.
arXiv Detail & Related papers (2024-03-07T22:03:36Z)
Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
This paper presents a novel form of the PSO methodology that uses the Roulette Wheel Method (RWPSO) Experiments using the Solomon VRPTW benchmark datasets on the RWPSO demonstrate that RWPSO is competitive with other state-of-the-art algorithms from the literature.
arXiv Detail & Related papers (2023-06-04T09:18:02Z)
Simultaneous Contact-Rich Grasping and Locomotion via Distributed Optimization Enabling Free-Climbing for Multi-Limbed Robots [60.06216976204385]
We present an efficient motion planning framework for simultaneously solving locomotion, grasping, and contact problems. We demonstrate our proposed framework in the hardware experiments, showing that the multi-limbed robot is able to realize various motions including free-climbing at a slope angle 45deg with a much shorter planning time.
arXiv Detail & Related papers (2022-07-04T13:52:10Z)
Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs [65.23158435596518]
Solving the multi-vehicle routing problem as a team Markov game with partially observable costs. Our multi-agent reinforcement learning approach, the so-called multi-agent Neural Rewriter, builds on the single-agent Neural Rewriter to solve the problem by iteratively rewriting solutions.
arXiv Detail & Related papers (2022-06-13T09:17:40Z)
Optimal Cost Design for Model Predictive Control [30.86835688868485]
Many robotics domains use non model control (MPC) for planning, which sets a reduced time horizon, performs optimization, and replans at every step. In this work, we challenge the common assumption that the cost we optimize using MPC should be the same as the ground truth cost for the task (plus a terminal cost) We propose a zeroth-order trajectory-based approach that enables us to design optimal costs for an MPC planning robot in continuous MDPs.
arXiv Detail & Related papers (2021-04-23T00:00:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.