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

• URL: http://arxiv.org/abs/2603.00663v2
• Date: Tue, 17 Mar 2026 12:45:02 GMT
• Title: Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity
• Abstract summary: 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.
• Score: 24.447439182269974
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Dynamical Vehicle Orienteering Problem for Multi-Rotor Unmanned Aerial Vehicles [3.5945543871230274]
  The Dynamical Vehicle Orienteering Problem (DVOP) is a generalization of the Orienteering Problem (OP)<n>We study the DVOP in the context of multi-rotor Aerial Unmanned Vehicle (UAV) flight planning.
  arXiv  Detail & Related papers  (2026-07-15T12:48:18Z)
• Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles [20.81107528768337]
  We study the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO)<n>We present a Mixed-Integer Conic Programming (MICP) formulation that can be solved using off-the-shelf solvers, as well as a fast and scalable Two-Phase Bilevel Search (TPBS) algorithm.<n>We evaluate our approaches against an existing baseline algorithm on a broad range of problem instances with up to 40 targets and 40 obstacles.
  arXiv  Detail & Related papers  (2026-06-17T06:17:12Z)
• 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 with Obstacles via Lazy Branch and Price [23.0719839118772]
  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.
  arXiv  Detail & Related papers  (2026-03-23T12:10:12Z)
• Blockchain-Enabled Routing for Zero-Trust Low-Altitude Intelligent Networks [77.17664010626726]
  We focus on the routing with multiple UAV clusters in low-altitude intelligent networks (LAINs)<n>To minimize the damage caused by potential threats, we present the zero-trust architecture with the software-defined perimeter and blockchain techniques.<n>We show that the proposed framework reduces the average E2E delay by 59% and improves the TSR by 29% on average compared to benchmarks.
  arXiv  Detail & Related papers  (2026-02-27T04:30:35Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  Vehicle Routing Problems (VRP) are a fundamental NP-hard challenge in Evolutionary optimization.<n>We introduce an optimization framework where a reinforcement learning agent is trained on prior instances and quickly generates initial solutions.<n>This framework consistently outperforms current state-of-the-art solvers across various time budgets.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• Task Delay and Energy Consumption Minimization for Low-altitude MEC via Evolutionary Multi-objective Deep Reinforcement Learning [52.64813150003228]
  The low-altitude economy (LAE), driven by unmanned aerial vehicles (UAVs) and other aircraft, has revolutionized fields such as transportation, agriculture, and environmental monitoring.<n>In the upcoming six-generation (6G) era, UAV-assisted mobile edge computing (MEC) is particularly crucial in challenging environments such as mountainous or disaster-stricken areas.<n>The task offloading problem is one of the key issues in UAV-assisted MEC, primarily addressing the trade-off between minimizing the task delay and the energy consumption of the UAV.
  arXiv  Detail & Related papers  (2025-01-11T02:32:42Z)
• A Bi-Objective Approach to Last-Mile Delivery Routing Considering Driver Preferences [42.16665455951525]
  The Multi-Objective Vehicle Routing Problem (MOVRP) is a complex optimization problem in the transportation and logistics industry. This paper proposes a novel approach to the MOVRP that aims to create routes that consider drivers' and operators' decisions and preferences. We evaluate two approaches to address this objective: visually attractive route planning and data mining of historical driver behavior to plan similar routes.
  arXiv  Detail & Related papers  (2024-05-25T04:25:00Z)
• 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)
• Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
  When vehicle routing decisions are intertwined with higher-level decisions, the resulting optimization problems pose significant challenges for computation. We propose a novel deep-learning-based approach called Genetic Algorithm with Neural Cost Predictor (GANCP) to tackle the challenge. In particular, our proposed neural network learns the objective values of the HGS-CVRP open-source package that solves capacitated vehicle routing problems.
  arXiv  Detail & Related papers  (2023-10-22T02:46:37Z)
• 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)
• Goal Kernel Planning: Linearly-Solvable Non-Markovian Policies for Logical Tasks with Goal-Conditioned Options [54.40780660868349]
  We introduce a compositional framework called Linearly-Solvable Goal Kernel Dynamic Programming (LS-GKDP)<n>LS-GKDP combines the Linearly-Solvable Markov Decision Process (LMDP) formalism with the Options Framework of Reinforcement Learning.<n>We show how an LMDP with a goal kernel enables the efficient optimization of meta-policies in a lower-dimensional subspace defined by the task grounding.
  arXiv  Detail & Related papers  (2020-07-06T05:13:20Z)
• Learning to Track Dynamic Targets in Partially Known Environments [48.49957897251128]
  We use a deep reinforcement learning approach to solve active target tracking. In particular, we introduce Active Tracking Target Network (ATTN), a unified RL policy that is capable of solving major sub-tasks of active target tracking.
  arXiv  Detail & Related papers  (2020-06-17T22:45:24Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.