Search papers, labs, and topics across Lattice.
This study addresses the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO), extending the traditional MT-TSP by requiring agents to navigate around dynamic obstacles while visiting targets within specific time windows. The authors introduce a Mixed-Integer Conic Programming (MICP) formulation alongside a Two-Phase Bilevel Search (TPBS) algorithm, which collectively yield superior performance compared to existing baseline methods across various problem instances. Key findings reveal that both approaches significantly enhance success rates, reduce solution costs, and improve computation times, highlighting their effectiveness in complex environments.
Achieving high-quality solutions for the MT-TSP-MO, our methods outperform traditional algorithms, even in challenging scenarios with numerous moving obstacles.
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.
