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

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

URL: http://arxiv.org/abs/2606.18730v1
Date: Wed, 17 Jun 2026 06:17:12 GMT
Title: Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles
Abstract summary: 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.
Score: 20.81107528768337
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The Moving-Target Traveling Salesman Problem (MT-TSP) seeks a minimum cost trajectory for an agent that departs from a static depot, visits a set of moving targets, each within one of their assigned time windows, and returns to the depot. In this article, we study the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO), a generalization of the MT-TSP where the agent trajectory must avoid moving obstacles. 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 that computes high-quality feasible solutions for the problem. We evaluate our approaches against an existing baseline algorithm on a broad range of problem instances with up to 40 targets and 40 obstacles. The results demonstrate that both the proposed methods significantly outperform the baseline with respect to success rates, solution costs, and computation time.

Related papers

NaviFormer: A Deep Reinforcement Learning Transformer-like Model to Holistically Solve the Navigation Problem [53.70554593151033]
NaviFormer is a deep reinforcement learning model that solves the global navigation problem by predicting both high-level routes and low-level trajectories.<n>Results show competitive accuracy from NaviFormer since it can understand the constraints and difficulties of each subproblem.<n>Its superior computation speed proves its suitability for real-time missions.
arXiv Detail & Related papers (2026-04-18T11:32:34Z)
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)
LDC-MTL: Balancing Multi-Task Learning through Scalable Loss Discrepancy Control [48.98651927356094]
Multi-task learning (MTL) has been widely adopted for its ability to simultaneously learn multiple tasks.<n>We propose LDC-MTL, a simple and scalable loss discrepancy control approach for MTL, formulated from a bilevel optimization perspective.<n>Our method incorporates two key components: (i) a bilevel formulation for fine-grained loss discrepancy control, and (ii) a scalable first-order bilevel algorithm that requires only $mathcalO(1)$ time and memory.
arXiv Detail & Related papers (2025-02-12T17:18:14Z)
A Meta-Engine Framework for Interleaved Task and Motion Planning using Topological Refinements [51.54559117314768]
Task And Motion Planning (TAMP) is the problem of finding a solution to an automated planning problem. We propose a general and open-source framework for modeling and benchmarking TAMP problems. We introduce an innovative meta-technique to solve TAMP problems involving moving agents and multiple task-state-dependent obstacles.
arXiv Detail & Related papers (2024-08-11T14:57:57Z)
A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
We develop a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints. We demonstrate its effectiveness on two well-known real-world applications.
arXiv Detail & Related papers (2024-06-14T15:59:36Z)
iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning [8.747306544853961]
The paper considers a Min-Max Multiple Traveling Salesman Problem (MTSP) The goal is to find a set of tours, one for each agent, to collectively visit all the cities while minimizing the length of the longest tour. We introduce a new self-supervised, bilevel, end-to-end learning framework, which we refer to as imperative MTSP (iMTSP)
arXiv Detail & Related papers (2024-05-01T02:26:13Z)
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)
Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
arXiv Detail & Related papers (2023-07-25T12:33:53Z)
DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in Complex Environments [55.204450019073036]
We present a novel reinforcement learning based task allocation and decentralized navigation algorithm for mobile robots in warehouse environments. We consider the problem of joint decentralized task allocation and navigation and present a two level approach to solve it. We observe improvement up to 14% in terms of task completion time and up-to 40% improvement in terms of computing collision-free trajectories for the robots.
arXiv Detail & Related papers (2022-09-07T00:35:27Z)
An Effective Iterated Two-stage Heuristic Algorithm for the Multiple Traveling Salesmen Problem [2.5374893654938324]
Multiple Traveling Salesmen Problem mTSP is a general extension of the famous NP-hard Traveling Salesmen Problem (TSP) In this paper, we address the mTSP with both of the minsum objective and the minmax objective, which aims at minimizing the total length of the m tours. We propose an iterated two-stage algorithm, denoted as ITSHA.
arXiv Detail & Related papers (2022-01-24T02:43:08Z)
Pruning Self-attentions into Convolutional Layers in Single Path [89.55361659622305]
Vision Transformers (ViTs) have achieved impressive performance over various computer vision tasks. We propose Single-Path Vision Transformer pruning (SPViT) to efficiently and automatically compress the pre-trained ViTs. Our SPViT can trim 52.0% FLOPs for DeiT-B and get an impressive 0.6% top-1 accuracy gain simultaneously.
arXiv Detail & Related papers (2021-11-23T11:35:54Z)
Location-routing Optimisation for Urban Logistics Using Mobile Parcel Locker Based on Hybrid Q-Learning Algorithm [0.0]
Parcel lockers (MPLs) have been introduced by urban logistics operators as a means to reduce traffic congestion and operational cost. This paper proposes an integer programming model to solve the Location Routing Problem for MPLs.
arXiv Detail & Related papers (2021-10-29T01:27:12Z)

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