# A Mixed-Integer Conic Program for the Multi-Agent Moving-Target Traveling Salesman Problem

arXiv: https://arxiv.org/abs/2501.06130 · HTML: https://mlsanity.com/paper/2501.06130/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2025.

## Built on by (most cited first, 1 of 1)

- [Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles](https://mlsanity.com/paper/2606.18730/) (2026)

## Abstract (arXiv)

The Moving-Target Traveling Salesman Problem (MT-TSP) seeks a shortest path for an agent that starts at a stationary depot, visits a set of moving targets exactly once, each within one of their respective time windows, and returns to the depot. In this paper, we introduce a new Mixed-Integer Conic Program (MICP) formulation for the Multi-Agent Moving-Target Traveling Salesman Problem (MA-MT-TSP), a generalization of the MT-TSP involving multiple agents. Our approach begins by restating the current state-of-the-art MICP formulation for MA-MT-TSP as a Nonconvex Mixed-Integer Nonlinear Program (MINLP), followed by a novel reformulation into a new MICP. We present computational results demonstrating that our formulation outperforms the state-of-the-art, achieving up to two orders of magnitude reduction in runtime, and over 90% improvement in optimality gap.