C$^{*}$: A New Bounding Approach for the Moving-Target Traveling Salesman Problem

We introduce a new bounding approach called Continuity* (C<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula>), which provides optimality guarantees for the Moving-Target Traveling Salesman Problem (MT-TSP). Our approach relaxes the continuity constraints on the agent's tour by partitioning the targets' trajectories into smaller segments. This allows the agent to arrive at any point within a segment and depart from any point in the same segment when visiting each target. This formulation enables us to pose the bounding problem as a Generalized Traveling Salesman Problem (GTSP) on a graph, where the cost of traveling along an edge requires solving a new problem called the Shortest Feasible Travel (SFT). We present various methods for computing bounds for the SFT problem, leading to several variants of C<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula>. We first prove that the proposed algorithms provide valid lower-bounds for the MT-TSP. Additionally, we provide computational results to validate the performance of all C<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula> variants on instances with up to 15 targets. For the special case where targets move along straight lines, we compare our C<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula> variants with a mixed-integer Second Order Conic Program (SOCP) based method, the current state-of-the-art solver for the MT-TSP. While the SOCP-based method performs well on instances with 5 and 10 targets, C<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula> outperforms it on instances with 15 targets. For the general case, on average, our approaches find feasible solutions within approximately 4.5<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\%$</tex-math></inline-formula> of the lower-bounds for the tested instances.