pith. sign in

arxiv: 2606.18730 · v1 · pith:3Z7BUTAFnew · submitted 2026-06-17 · 💻 cs.RO · cs.AI· math.CO· math.OC

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

Allen George Philip , Anoop Bhat , Sivakumar Rathinam , Howie Choset This is my paper

Pith reviewed 2026-06-26 20:49 UTC · model grok-4.3

classification 💻 cs.RO cs.AImath.COmath.OC
keywords moving target traveling salesmanmoving obstaclesbilevel searchmixed integer conic programmingpath planningtime windowscollision avoidance
0
0 comments X

The pith

A mixed-integer conic program and two-phase bilevel search solve the moving-target TSP with moving obstacles more effectively than prior approaches.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops solution methods for planning a trajectory that visits moving targets within time windows while dodging moving obstacles. It offers both an exact MICP model solvable by standard tools and a heuristic TPBS that scales to dozens of targets and obstacles. If correct, these methods make such planning feasible for real-world robot navigation tasks where everything is dynamic. Readers care because classic TSP ignores motion, but here motion is central.

Core claim

The MICP formulation and TPBS algorithm compute trajectories for the MT-TSP-MO that achieve higher success rates, lower costs, and shorter run times than a baseline method across instances with as many as 40 targets and 40 obstacles.

What carries the argument

The two-phase bilevel search that first sequences the targets then optimizes the timed trajectory while avoiding obstacles.

If this is right

  • The approaches enable planning for larger numbers of dynamic targets and obstacles than before.
  • High-quality feasible solutions become available quickly even when exact optimality is hard.
  • Direct use of off-the-shelf solvers for the MICP makes implementation straightforward for practitioners.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • These techniques could be adapted for online replanning when motion predictions update.
  • Similar bilevel decompositions might apply to other vehicle routing problems with time-dependent constraints.
  • Testing on physical robots would reveal how model mismatch affects performance.

Load-bearing premise

All target and obstacle trajectories are known perfectly ahead of time and can be encoded into the optimization constraints.

What would settle it

Running the methods on a collection of instances where target or obstacle paths contain uncertainty or are revealed only during execution would test if the reported advantages hold.

Figures

Figures reproduced from arXiv: 2606.18730 by Allen George Philip, Anoop Bhat, Howie Choset, Sivakumar Rathinam.

Figure 1
Figure 1. Figure 1: A feasible solution for an example instance of the MT-TSP-MO. [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Top: The high-level search returns a time-feasible GTSP tour [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 5
Figure 5. Figure 5: Average of best solution costs and total runtimes for Phase 1 and [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 4
Figure 4. Figure 4: Average cost ratios of MICP and both baselines with respect to [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper presents a Mixed-Integer Conic Programming (MICP) formulation and a Two-Phase Bilevel Search (TPBS) algorithm for the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO). It evaluates both methods against a baseline on generated instances with up to 40 targets and 40 obstacles, claiming higher success rates, lower solution costs, and faster computation times.

Significance. If the empirical results hold under standard statistical scrutiny, the work supplies both an exact MICP model solvable by off-the-shelf solvers and a scalable heuristic for a practically relevant extension of the MT-TSP that incorporates moving obstacles. The explicit requirement that target and obstacle trajectories are known a priori is stated clearly and aligns with the modeling assumptions.

major comments (1)
  1. [Results] Results section (and abstract): the central claim of significant outperformance in success rates, costs, and runtimes is presented without error bars, statistical significance tests, or details on instance-generation parameters and exclusion criteria, which undermines verification of the reported improvements on instances up to size 40.
minor comments (1)
  1. [Abstract] Abstract: the problem statement could explicitly note that trajectories are known in advance, as this is definitional for the feasible-set assumptions in both the MICP and TPBS.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their constructive feedback. We address the single major comment below and will revise the manuscript to strengthen the empirical presentation.

read point-by-point responses

  1. Referee: [Results] Results section (and abstract): the central claim of significant outperformance in success rates, costs, and runtimes is presented without error bars, statistical significance tests, or details on instance-generation parameters and exclusion criteria, which undermines verification of the reported improvements on instances up to size 40.

    Authors: We agree that the current presentation of results lacks the statistical rigor and experimental details needed for full verification. In the revised version we will add error bars (standard deviations across the instance sets), report the outcomes of appropriate statistical significance tests (e.g., paired Wilcoxon signed-rank tests) between our methods and the baseline, and expand the description of the instance-generation procedure, including all relevant parameters and any exclusion criteria applied. These additions will be made to both the results section and the abstract. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents an MICP formulation and a TPBS algorithm for MT-TSP-MO, then reports empirical outperformance on generated instances with known trajectories. No derivation chain exists that reduces a claimed prediction or first-principles result to its own inputs by construction; the work consists of standard modeling plus algorithmic search, with performance claims resting on direct experimental comparison rather than any self-referential fitting, ansatz smuggling, or load-bearing self-citation. The central results are falsifiable via the reported benchmarks and do not invoke uniqueness theorems or renamed empirical patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces no new physical entities or fitted constants. It rests on standard assumptions of mixed-integer conic programming and bilevel search being applicable to the modeled dynamics.

axioms (1)
  • domain assumption Off-the-shelf MICP solvers can solve the formulated problem instances to optimality or near-optimality within practical time limits.
    The abstract states that the MICP formulation can be solved using off-the-shelf solvers.

pith-pipeline@v0.9.1-grok · 5719 in / 1175 out tokens · 20877 ms · 2026-06-26T20:49:32.848062+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 3 canonical work pages

  1. [1]

    Experimental analysis of heuristic solutions for the moving target traveling salesman problem applied to a moving targets monitoring system,

    R. S. de Moraes and E. P. de Freitas, “Experimental analysis of heuristic solutions for the moving target traveling salesman problem applied to a moving targets monitoring system,”Expert Systems with Applications, vol. 136, pp. 392–409, 2019

    2019

  2. [2]

    Moving-target travelling salesman problem for a helicopter patrolling suspicious boats in antipiracy escort operations,

    Y . Wang and N. Wang, “Moving-target travelling salesman problem for a helicopter patrolling suspicious boats in antipiracy escort operations,” Expert Systems with Applications, vol. 213, p. 118986, 2023

    2023

  3. [3]

    The travelling salesman problem in maritime surveillance–techniques, algorithms and analysis,

    D. Marlow, P. Kilby, and G. Mercer, “The travelling salesman problem in maritime surveillance–techniques, algorithms and analysis,” inPro- ceedings of the international congress on modelling and simulation, 2007, pp. 684–690

    2007

  4. [4]

    A bi-criteria moving-target travelling salesman problem under uncertainty,

    A. Maskooki and M. Kallio, “A bi-criteria moving-target travelling salesman problem under uncertainty,”European Journal of Opera- tional Research, 2023

    2023

  5. [5]

    The moving-target traveling salesman problem,

    C. S. Helvig, G. Robins, and A. Zelikovsky, “The moving-target traveling salesman problem,”Journal of Algorithms, vol. 49, no. 1, pp. 153–174, 2003

    2003

  6. [6]

    C. D. Smith,Assessment of genetic algorithm based assignment strategies for unmanned systems using the multiple traveling salesman problem with moving targets. University of Missouri-Kansas City, 2021

    2021

  7. [7]

    Dealing with time in the multiple traveling salespersons problem with moving targets,

    A. Stieber and A. F ¨ugenschuh, “Dealing with time in the multiple traveling salespersons problem with moving targets,”Central Euro- pean Journal of Operations Research, vol. 30, no. 3, pp. 991–1017, 2022

    2022

  8. [8]

    Efficient tracking and pursuit of moving targets by heuristic solution of the traveling salesman problem,

    B. Englot, T. Sahai, and I. Cohen, “Efficient tracking and pursuit of moving targets by heuristic solution of the traveling salesman problem,” in52nd ieee conference on decision and control. IEEE, 2013, pp. 3433–3438

    2013

  9. [9]

    Approximating capacitated routing and delivery problems,

    P. Chalasani and R. Motwani, “Approximating capacitated routing and delivery problems,”SIAM Journal on Computing, vol. 28, no. 6, pp. 2133–2149, 1999

    1999

  10. [10]

    A mixed-integer conic program for the moving-target traveling salesman problem based on a graph of convex sets,

    A. G. Philip, Z. Ren, S. Rathinam, and H. Choset, “A mixed-integer conic program for the moving-target traveling salesman problem based on a graph of convex sets,” in2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2024, pp. 8847– 8853

    2024

  11. [11]

    A mixed-integer conic program for the multi-agent moving- target traveling salesman problem,

    ——, “A mixed-integer conic program for the multi-agent moving- target traveling salesman problem,” in2025 IEEE 21st International Conference on Automation Science and Engineering (CASE), 2025, pp. 492–498

    2025

  12. [12]

    C ∗: A new bounding approach for the moving-target traveling salesman problem,

    ——, “C ∗: A new bounding approach for the moving-target traveling salesman problem,”IEEE Transactions on Robotics, vol. 41, pp. 4663– 4678, 2025

    2025

  13. [13]

    Parallel, asymptotically optimal algorithms for moving target travel- ing salesman problems,

    A. Bhat, G. Gutow, B. Vundurthy, Z. Ren, S. Rathinam, and H. Choset, “Parallel, asymptotically optimal algorithms for moving target travel- ing salesman problems,”arXiv preprint arXiv:2509.08743, 2025

    work page arXiv 2025

  14. [14]

    On-orbit servicing: a time-dependent, moving-target traveling salesman problem,

    J.-M. Bourjolly, O. Gurtuna, and A. Lyngvi, “On-orbit servicing: a time-dependent, moving-target traveling salesman problem,”Interna- tional Transactions in Operational Research, vol. 13, no. 5, pp. 461– 481, 2006

    2006

  15. [15]

    Moving target travelling salesman problem using genetic algorithm,

    N. S. Choubey, “Moving target travelling salesman problem using genetic algorithm,”International Journal of Computer Applications, vol. 70, no. 2, 2013

    2013

  16. [16]

    Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: An application to fish aggregating devices,

    C. Groba, A. Sartal, and X. H. V ´azquez, “Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: An application to fish aggregating devices,”Computers & Operations Research, vol. 56, pp. 22–32, 2015

    2015

  17. [17]

    A complete algorithm for a moving target traveling salesman problem with obstacles,

    A. Bhat, G. Gutow, B. Vundurthy, Z. Ren, S. Rathinam, and H. Choset, “A complete algorithm for a moving target traveling salesman problem with obstacles,”arXiv preprint arXiv:2409.09852, 2024

    work page arXiv 2024

  18. [18]

    A complete and bounded-suboptimal algorithm for a moving target traveling salesman problem with obstacles in 3d,

    ——, “A complete and bounded-suboptimal algorithm for a moving target traveling salesman problem with obstacles in 3d,”arXiv preprint arXiv:2504.14680, 2025

    work page arXiv 2025

  19. [19]

    Scheduling combat logistics force replenishments at sea for the us navy,

    G. G. Brown, W. C. DeGrange, W. L. Price, and A. A. Rowe, “Scheduling combat logistics force replenishments at sea for the us navy,”Naval Research Logistics (NRL), vol. 64, no. 8, pp. 677–693, 2017

    2017

  20. [20]

    Dynamic route planning for a usv-uav multi-robot system in the rendezvous task with obstacles,

    Y . Li, S. Li, Y . Zhang, W. Zhang, and H. Lu, “Dynamic route planning for a usv-uav multi-robot system in the rendezvous task with obstacles,”Journal of Intelligent & Robotic Systems, vol. 107, no. 4, p. 52, 2023

    2023

  21. [21]

    Local search in routing problems with time windows,

    M. W. Savelsbergh, “Local search in routing problems with time windows,”Annals of Operations research, vol. 4, no. 1, pp. 285–305, 1985

    1985

  22. [22]

    Cp-milp: Mixed integer linear programming for multi-agent motion planning with linear dynamics,

    Z. Ren, A. G. Philip, S. Zhao, S. Rathinam, and H. Choset, “Cp-milp: Mixed integer linear programming for multi-agent motion planning with linear dynamics,”IEEE Robotics and Automation Letters, vol. 10, no. 12, pp. 12 573–12 579, 2025

    2025

  23. [23]

    Task allocation and trajectory planning for multiple agents in the presence of obstacle and connectivity constraints with mixed-integer linear programming,

    R. J. Afonso, M. R. Maximo, and R. K. Galvao, “Task allocation and trajectory planning for multiple agents in the presence of obstacle and connectivity constraints with mixed-integer linear programming,” International Journal of Robust and Nonlinear Control, vol. 30, no. 14, pp. 5464–5491, 2020

    2020

  24. [24]

    Cb- gcs: Conflict-based search on the graph of convex sets for multi-agent motion planning,

    S. Zhao, A. G. Philip, S. Rathinam, H. Choset, and Z. Ren, “Cb- gcs: Conflict-based search on the graph of convex sets for multi-agent motion planning,” in2025 IEEE 21st International Conference on Automation Science and Engineering (CASE). IEEE, 2025, pp. 2208– 2214

    2025

  25. [25]

    Glns: An effective large neighborhood search heuristic for the generalized traveling salesman problem,

    S. L. Smith and F. Imeson, “Glns: An effective large neighborhood search heuristic for the generalized traveling salesman problem,” Computers & Operations Research, vol. 87, pp. 1–19, 2017

    2017

  26. [26]

    Solving the equality generalized traveling salesman problem using the lin–kernighan–helsgaun algorithm,

    K. Helsgaun, “Solving the equality generalized traveling salesman problem using the lin–kernighan–helsgaun algorithm,”Mathematical Programming Computation, vol. 7, pp. 269–287, 2015

    2015

  27. [27]

    Gurobi Optimizer Reference Manual,

    Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,”

  28. [28]

    Available: https://www.gurobi.com

    [Online]. Available: https://www.gurobi.com