Paper deep dive
Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles
Allen George Philip, Anoop Bhat, Sivakumar Rathinam, Howie Choset
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 98%
Last extracted: 6/21/2026, 2:59:05 AM
Summary
The paper addresses the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO), a generalization of the MT-TSP where an agent must visit moving targets within specific time windows while avoiding moving obstacles. The authors propose two main approaches: a Mixed-Integer Conic Programming (MICP) formulation that provides asymptotic guarantees on optimality and completeness, and a more scalable Two-Phase Bilevel Search (TPBS) algorithm. TPBS utilizes a high-level search on a Generalized Traveling Salesman Problem (GTSP) graph and a low-level search on a time-expanded graph to ensure collision-free, time-feasible trajectories. Experimental results show that the proposed methods outperform existing baselines in success rates, solution costs, and computation time.
Entities (10)
Relation Signals (5)
Allen George Philip → affiliatedwith → Texas A&M University
confidence 100% · Allen George Philip1... Mechanical Engineering, Texas A&M University
Howie Choset → affiliatedwith → Carnegie Mellon University
confidence 100% · Howie Choset2... Robotics Institute, Carnegie Mellon University
Moving-Target Traveling Salesman Problem with Moving Obstacles → solvedby → Mixed-Integer Conic Programming
confidence 100% · We present a Mixed-Integer Conic Programming (MICP) formulation that can be solved using off-the-shelf solvers
Moving-Target Traveling Salesman Problem with Moving Obstacles → solvedby → Two-Phase Bilevel Search
confidence 100% · as well as a fast and scalable Two-Phase Bilevel Search (TPBS) algorithm that computes high-quality feasible solutions for the problem.
Two-Phase Bilevel Search → uses → Generalized Traveling Salesman Problem
confidence 100% · The high-level search solves a Generalized Traveling Salesman Problem (GTSP) defined over a target graph
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2606.18730v1
- Canonical: https://arxiv.org/abs/2606.18730v1
Trouble viewing inline? Open PDF directly →
Full Text
51,852 characters extracted from source content.
Expand or collapse full text
Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles Allen George Philip1, Anoop Bhat2, Sivakumar Rathinam3, and Howie Choset2 1Mechanical Engineering, Texas A&M University, College Station, TX 77843-3123. Email: y262u297@tamu.edu2Robotics Institute, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213, USA. Emails: agbhat, choset@andrew.cmu.edu3Mechanical Engineering, and Computer Science and Engineering, Texas A&M University, College Station, TX 77843-3123. Email: srathinam@tamu.edu 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. I INTRODUCTION Given a set of moving targets with predefined trajectories and associated time windows, the Moving-Target Traveling Salesman Problem (MT-TSP) seeks a minimum-time trajectory for an agent that begins at a specified, fixed location (depot), visits all the targets within one of their respective time windows, and returns to the depot. The MT-TSP has several practical applications including monitoring and surveillance [9, 26, 16, 17], resupply missions with mobile vehicles [14], missile defense [14, 23, 25], dynamic target tracking [10], and industrial robot planning [7]. Several algorithms exist for the MT-TSP. Recent works [25, 18, 19] provide completeness and optimality guarantees for cases where targets move along linear or piecewise-linear trajectories. The algorithms in [20] and [4] address generic target trajectories by providing tight lower bounds on the optimum and asymptotic guarantees, respectively. Other heuristic approaches include [5, 8, 9, 11, 16, 26, 10]. The Moving-Target Traveling Salesman Problem with Obstacles (MT-TSP-O) is a natural generalization of the MT-TSP where the agent must avoid static obstacles. Recently, a complete algorithm was proposed for the MT-TSP-O for 2D workspaces [2], followed by a complete and bounded-suboptimal algorithm for the 3D generalization in [3]. In this article, we consider the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO) which further generalizes the MT-TSP-O (Fig. 1). Moving-target interception amidst moving obstacles has applications such as underwater replenishment of naval ships [6] and periodic recharging of Unmanned Aerial Vehicles (UAVs) using Unmanned Surface Vehicles (USVs) [15]. Finding a feasible solution to the MT-TSP-MO is NP-complete [22] due to the presence of time windows, making completeness difficult to guarantee. Furthermore, finding an optimal solution to the MT-TSP-MO is NP-hard as it generalizes the TSP. Currently, the research on the MT-TSP-MO is very limited, with [15] providing the only known approach. Hence, this paper focuses on finding high-quality feasible solutions for the MT-TSP-MO. Figure 1: A feasible solution for an example instance of the MT-TSP-MO. Solid, colored portions of the target trajectories indicate their respective time windows. The agent begins and ends its tour at the depot while avoiding moving obstacles. Our Contributions: We first present a Mixed-Integer Conic Programming (MICP) formulation for the MT-TSP-MO. This formulation can be solved using off-the-shelf solvers, and provides asymptotic guarantees on optimality and completeness with respect to a time discretization. However, its scalability is limited for large numbers of targets and obstacles. Hence, we also develop a direct Two-Phase Bilevel Search (TPBS) algorithm that scales to larger problem instances and finds feasible solutions more reliably, at the expense of guarantees on optimality and completeness. TPBS consists of two phases. The first phase quickly generates a set of initial feasible tours, and the second phase improves them to compute lower-cost tours. In both phases, TPBS employs a bilevel search framework that interleaves a high-level search with a low-level search. The high-level search solves a Generalized Traveling Salesman Problem (GTSP) defined over a target graph consisting of trajectory points for each target sampled within their respective time windows, and the depot. It returns a time-feasible tour for the agent that visits each target within one of its assigned time windows, in the absence of obstacles. The low-level search then evaluates the feasibility of each edge in the GTSP tour by checking for a collision-free, time-feasible trajectory that connects the corresponding trajectory endpoints. This is accomplished via a fast straight-line check, followed when necessary, by a depth-first search (DFS) on a time-expanded graph that includes obstacle-free workspace locations and target trajectory points at discrete time steps, and the depot. We evaluate the proposed approaches on several problem instances with varying number of targets and obstacles, and total time window durations, and show that they significantly outperform the baseline algorithm in [15] with respect to success rates, solution costs, and computational runtimes. I PROBLEM DEFINITION All the targets, obstacles, and the agent are contained within an ℝ2R^2 workspace. Let :=1,2,⋯,||T:=\1,2,·s,|T|\ denote the set of targets. Each target i∈i moves along its trajectory πi:[0,T]→ℝ2 _i:[0,T] ^2 where T represents the planning horizon. We define the trajectory point of target i at time t as π¯i(t):=(i,πi(t),t) π_i(t):=(i, _i(t),t). Associated with target i is also a set of time windows i:=[t¯i1,t¯i1],[t¯i2,t¯i2],⋯,[t¯i|i|,t¯i|i|]W_i:=\[ t_i^1, t_i^1],[ t_i^2, t_i^2],·s,[ t_i^|W_i|, t_i^|W_i|]\ where t¯iw t_i^w and t¯iw t_i^w denote the start and end time respectively of the wwth time window for the iith target. We consider the depot s to be a static, dummy target with a single time window [0,T][0,T]. Now, let :=1,2,⋯,||O:=\1,2,·s,|O|\ denote the set of obstacles. Each obstacle o∈o is assumed to be a convex polygon whose center moves along a trajectory ξo:[0,T]→ℝ2 _o:[0,T] ^2. Let o:=p∈ℝ2|Aop≤boO_o:=\p ^2\,|\,A_op≤ b_o\ denote the region occupied by obstacle o when centered at the origin. The time-varying obstacle region is then given by o(t):=p∈ℝ2|Ao(p−ξo(t))≤boO_o(t):=\p ^2\,|\,A_o(p- _o(t))≤ b_o\. This work assumes generic non-linear trajectories for the targets and linear trajectories for the obstacles. Let τa:[0,tf]→ℝ2 _a:[0,t_f] ^2 for some tf≤Tt_f≤ T be the agent trajectory. We say τa _a is feasible if it is speed admissible, i.e. never exceeds the maximum agent speed vmaxv_max and is collision-free, i.e. never enters the interior of any obstacle. We say τa _a visits a trajectory point π¯i(t) π_i(t) if τa(t)=πi(t) _a(t)= _i(t), and that τa _a follows a sequence of trajectory points if it visits all the points in the sequence, in order. We define a tour as a sequence of trajectory points which takes the form (π¯s(0),π¯i1(ti1),π¯i2(ti2),⋯,π¯i||(ti||),π¯s(tf))( π_s(0), π_i_1(t^i_1), π_i_2(t^i_2),·s, π_i_|T|(t^i_|T|), π_s(t_f)) where (i1,i2,⋯,i||)(i_1,i_2,·s,i_|T|) denotes a permutation of T. A tour is feasible if there exists a feasible agent trajectory that follows the tour, and the associated time tiℓt^i_ for each target iℓi_ in the tour lies within one of its associated time windows in iℓW_i_ . The goal of the MT-TSP-MO is to find a feasible tour Q, a feasible agent trajectory τa _a, and a final time tft_f such that τa _a follows Q and tft_f is minimized. I MIXED-INTEGER CONIC PROGRAM (MICP) FOR MT-TSP-MO We restrict the time window of the depot s to [0,0][0,0], and define a depot copy s′s with time window [0,T][0,T], and require the agent trajectory to start at s and end at s′s . For convenience, denote the set of nodes ∪s,s′T∪\s,s \ using ′T . Let :=1,2,…,||K:=\1,2,…,|K|\ denote an index set for a set of times tkt_k that discretize the time horizon [0,T][0,T]. For each node i∈′i , we denote by iS_i the subset of steps in K whose associated times tkt_k lie within one of the time windows associated with i. Additionally, for each k∈k , we denote by kV_k the subset of nodes in ′T for which at least one time window contains tkt_k. We now define the decision variables. For each k∈k , the agent position is defined by the variable pk∈ℝ2p_k ^2. We require pkp_k to be bounded by the workspace limits [pmin,pmax][p_min,p_max]. For each i∈′i and k∈ik _i, we define binary variables yi,k∈0,1y_i,k∈\0,1\ indicating whether the agent visits node i at step k. We also introduce binary variables gk∈0,1g_k∈\0,1\ for each k∈∖1k \1\ indicating whether the agent visited the depot copy s′s at some step j<kj<k. At any step k∈k , the region occupied by obstacle o∈o is the intersection of a set of halfspaces, defined by the rows ao,mTa^T_o,m of AoA_o and corresponding entries bo,mb_o,m of bob_o, where m∈ℳo:=1,2,⋯,|ℳo|m _o:=\1,2,·s,|M_o|\ and |ℳo||M_o| is equal to the number of rows in AoA_o. The binary variables ho,m,k∈0,1h_o,m,k∈\0,1\ indicate whether the agent must lie outside the mmth halfspace. Finally, we define for each k∈∖||k \|K|\, variable lk≥0l_k≥ 0 denoting the Euclidean distance traveled by the agent between steps k and k+1k+1, and auxiliary variable lkxy∈ℝ2l^xy_k ^2 representing the agent’s displacement from step k to step k+1k+1 to help define lkl_k. Our MICP formulation for the MT-TSP-MO is as follows: min∑k∈s′tkys′,k _k _s t_k\,y_s ,k (1) subject to constraints ∑k∈iyi,k=1,∀i∈′, _k _iy_i,k=1,\;\;∀\;i , (2) ∑i∈kyi,k≤1,∀k∈, _i _ky_i,k≤ 1,\;\;∀\;k , (3) ∑k∈s′tkys′,k≥∑k∈itkyi,k,∀i∈, _k _s t_k\,y_s ,k≥ _k _it_k\,y_i,k,\;\;∀\;i , (4) pk≥∑i∈kπi(tk)yi,k+pmin(1−∑i∈kyi,k),∀k∈, p_k≥ _i _k _i(t_k)y_i,k+p_min(1- _i _ky_i,k),\;∀\;k , (5) pk≤∑i∈kπi(tk)yi,k+pmax(1−∑i∈kyi,k),∀k∈, p_k≤ _i _k _i(t_k)y_i,k+p_max(1- _i _ky_i,k),\;∀\;k , (6) gk=∑j=1k−1ys′,j,∀k∈∖1, g_k= _j=1^k-1y_s ,j,\;\;∀\;k \1\, (7) pk≥πs′(t1)gk+pmin(1−gk),∀k∈∖1, p_k≥ _s (t_1)g_k+p_min(1-g_k),\;\;∀\;k \1\, (8) pk≤πs′(t1)gk+pmax(1−gk),∀k∈∖1, p_k≤ _s (t_1)g_k+p_max(1-g_k),\;\;∀\;k \1\, (9) gk+∑m∈ℳoho,m,k=1,∀o∈,∀k∈∖1, g_k+ _m _oh_o,m,k=1,\;\;∀\;o ,\;\;∀\;k \1\, (10) ∑m∈ℳoho,m,1=1,∀o∈, _m _oh_o,m,1=1,\;\;∀\;o , (11) ao,mT(pk−ξo(tk))≥bo,m−M(1−ho,m,k), a^T_o,m(p_k- _o(t_k))≥ b_o,m-M(1-h_o,m,k), ∀o∈,∀m∈ℳo,∀k∈∖||, \;∀\;o ,\;\;∀\;m _o,\;\;∀\;k \|K|\, (12) ao,mT(pk+1−ξo(tk+1))≥bo,m−M(1−ho,m,k), a^T_o,m(p_k+1- _o(t_k+1))≥ b_o,m-M(1-h_o,m,k), ∀o∈,∀m∈ℳo,∀k∈∖||, \;∀\;o ,\;\;∀\;m _o,\;\;∀\;k \|K|\, (13) lkxy=pk+1−pk,∀k∈∖||, l_k^xy=p_k+1-p_k,\;\;∀\;k \|K|\, (14) lk2≥‖lkxy‖22,∀k∈∖||, l_k^2≥ l_k^xy _2^2,\;\;∀\;k \|K|\, (15) lk≤vmax(tk+1−tk),∀k∈∖||. l_k≤ v_max(t_k+1-t_k),\;\;∀\;k \|K|\. (16) The objective (1) minimizes the time at which the agent visits the depot copy s′s . This objective relies on constraints (2) and (4) which ensure that each node in ′T is visited exactly once, and that s′s is visited only after all other nodes, respectively. In addition, constraints (3) limit the agent to visiting at most one node at any step. The agent’s position is coupled to the node assignments through the big-M constraints (5) and (6), which enforce coincidence between the agent position and the position of node i at step k whenever yi,k=1y_i,k=1, and relax this requirement otherwise. The variables gkg_k which track whether s′s has been visited at a previous step are defined through constraints (7). Following this, big-M constraints (8) and (9) ensure that the agent remains at the depot position at step k if gk=1g_k=1, and relax this requirement otherwise. Although (8) and (9) are optional, they can be beneficial as all other constraints are trivially satisfied when they are active. Note that in (5), (6), (8), and (9), the big-M values chosen are the workspace bounds pminp_min and pmaxp_max. Now we explain the obstacle avoidance constraints (10)–(13). Constraints (10) and (11) together require that for any obstacle o and step k, at least one of the ℳoM_o hyperplane variables ho,m,kh_o,m,k must be active if s′s has not been visited yet (i.e. gk=0g_k=0). However, if gk=1g_k=1, then all ℳoM_o of these variables take value 0 and consequently, the obstacle avoidance requirement is relaxed. At each step k, the ho,m,kh_o,m,k variables for obstacle o are related to the agent position pkp_k through big-M constraints (12) and (13) similar to works [21], [1]. When ho,m,k=1h_o,m,k=1, (12) requires pkp_k to lie outside the halfspace defined by the mmth inequality for obstacle o. However, when ho,m,k=0h_o,m,k=0, this requirement is relaxed. Constraints (13) require that if the agent must lie outside the halfspace defined by the mmth inequality for obstacle o at step k, then this condition must also be satisfied at step k+1k+1; otherwise, the condition is relaxed. The purpose of adding (13) is to ensure collision avoidance between the agent and obstacles over the interval between consecutive steps. This holds since obstacles are assumed to follow linear trajectories; consequently, the linear trajectory segment connecting the agent positions at steps k and k+1k+1 cannot intersect any obstacle between these steps. Next, constraints (14) and (15) together ensure that the distance lkl_k traveled by the agent between steps k and k+1k+1 satisfies lk≥‖pk+1−pk‖2l_k≥ p_k+1-p_k _2. Finally, the time-feasibility constraints (16) ensure that this distance does not exceed the maximum distance vmax(tk+1−tk)v_max(t_k+1-t_k) that the agent can travel between consecutive steps k and k+1k+1. From a solution to the MICP, we construct the agent tour Q based on the values taken by variables yi,ky_i,k, the agent trajectory τa _a by interpolating between consecutive (pk,tk)(p_k,t_k) values, and the final time tft_f from the objective value ∑k∈s′tkys′,k _k _s t_k\,y_s ,k. IV TWO-PHASE BILEVEL SEARCH Figure 2: Top: The high-level search returns a time-feasible GTSP tour Q on HG_H that visits the depot and each target once, in the absence of obstacles. Bottom: The low-level search evaluates each tour edge by computing a collision-free, time-feasible path in LG_L if a straight-line trajectory connecting the edge endpoints is infeasible. In the figure, a straight-line connection for tour edge (π¯1(t1),π¯s′(tf))( π_1(t^1), π_s (t_f)) collides with an obstacle in between time steps, and is replaced by a feasible path in LG_L. In this section, we introduce a Two-Phase Bilevel Search (TPBS) algorithm for the MT-TSP-MO. The search consists of a construction phase that quickly generates a set of initial feasible solutions, followed by an improvement phase that refines these solutions. In both phases, TPBS interleaves a high-level and a low-level search. The high-level search solves a Generalized Traveling Salesman Problem (GTSP) on a graph HG_H to generate candidate tours, while a low-level search evaluates the feasibility of the tour edges by computing feasible paths in a low-level graph LG_L if feasibility cannot be ensured initially through a fast straight-line check. This is illustrated in Fig. 2, whose notations and further details we will now discuss. Like in the previous section, we set the time window of s to [0,0][0,0], introduce a depot copy s′s which acts as a static target with associated time window [0,T][0,T], and reuse sets ,′,i for all i∈′K,T ,S_i for all i , and k for all k∈V_k for all k . Corresponding to each set iS_i, we define a cluster i:=π¯i(tk)|k∈SiC_i:=\ π_i(t_k)\,|\,k∈ S_i\. The set of nodes of HG_H is then defined as H:=⋃i∈′iV_H:= _i C_i. The edge set ℰHE_H consists of directed edges between all pairs of nodes in HV_H. Associated with each edge e is a cost (e,H) Cost(e,G_H) which takes value +∞+∞ 111From an implementation point of view +∞+∞ is represented using a sufficiently large constant. if e is infeasible and a finite value otherwise. An edge is marked infeasible if it (a) connects two nodes belonging to the same cluster, or (b) connects any node outside of the depot copy cluster s′C_s to the single depot node π¯s(0) π_s(0) in sC_s, or (c) connects any node from s′C_s to nodes outside of sC_s. Additionally, an edge e connecting node π¯i(tp) π_i(t_p) to node π¯j(tq) π_j(t_q) is marked infeasible if ‖πj(tq)−πi(tp)‖2>vmax(tq−tp) _j(t_q)- _i(t_p) _2>v_max(t_q-t_p), indicating the agent cannot depart from i at time tpt_p and arrive at j at time tqt_q even when traveling at its maximum speed vmaxv_max while ignoring obstacles. Otherwise, (e,H) Cost(e,G_H) is set to tq−tpt_q-t_p. Finally, for all edges e connecting nodes in s′C_s to the depot node in sC_s, (e,H) Cost(e,G_H) is set to 0. We define LG_L as a time-augmented graph like in [27]. For each step k in ∖1K \1\, we define two sets of nodes, kfreeV^free_k and kfreeX^free_k. We define kfreeV^free_k as π¯i(tk) π_i(t_k) for all i∈ki _k if πi(tk) _i(t_k) is obstacle-free, and kfreeX^free_k as a set of points (p,tk)(p,t_k) in space-time with locations in the obstacle-free regions of the workspace at time tkt_k. The set of nodes of LG_L is defined as L:=π¯s(0)∪⋃k∈∖1kfree∪kfreeV_L:= π_s(0)\,∪\, _k \1\V^free_k ^free_k. Note that for step k=1k=1, we only consider the trajectory point corresponding to the depot at the start time 0 provided that its position is obstacle-free. An edge e connects nodes vkv_k and vk+1v_k+1 with associated steps k and k+1k+1 respectively, if (a) for every obstacle o∈o , there exists at least one inequality m∈ℳom _o such that the positions associated with both vkv_k and vk+1v_k+1 lie outside the halfspace defined by m at times tkt_k and tk+1t_k+1, respectively and (b) the Euclidean distance d between the positions associated with vkv_k and vk+1v_k+1 satisfies d≤vmax(tk+1−tk)d≤ v_max(t_k+1-t_k). Condition (a) ensures collision avoidance at discrete time steps and along the continuous trajectory between them, and (b) ensures time feasibility. When constructing LG_L, the edge set ℰLE_L is initially empty, with edges generated and added incrementally during the low-level search, according to conditions (a) and (b). 1L←G_L← ConstrLowLevelGraph () 2 H←G_H← ConstrHighLevelGraph () 3 ℱinit,ℱimp←∅,∅F_init,\;F_imp← ,\; 4 H[e]←0∀e∈ℰHP_H[e]← 0\;\;∀\;e _H 5 for trial in 1,2,⋯,Ntours\1,2,·s,N_tours\ do 6 while initial search time limit not reached do 7 ←Q← HighLevelDFS (H,H,ℱinit)(G_H,P_H,F_init) 8 if is NULLQ is NULL then break // end Phase 1 9 10 ℰtour←E_tour← TourEdges ()(Q) 11 for each edge e∈ℰtoure _tour do 12 EvalEdge (e,L,H)(e,G_L,G_H) 13 14 if all edges in ℰtourE_tour are feasible after eval then 15 ℱinit←ℱinit∪F_init _init∪\Q\ 16 for each e∈ℰtoure _tour do 17 ℰwin←E_win← WinEdges (e,ℰH)(e,E_H) 18 H[ew]←H[ew]+δ∀ew∈ℰwinP_H[e_w] _H[e_w]+δ\;\;∀\;e_w _win 19 break 20 21 22Sort ℱinitF_init in increasing order of tour durations tft_f 23 for tour Q in ℱinitF_init do 24 while total time limit not reached do 25 tf←(())t_f← time( last(Q)) 26 ′←Q ← ImproveTour (,H)(Q,G_H) 27 ℰtour←E_tour← TourEdges (′)(Q ) 28 for each edge e∈ℰtoure _tour do 29 EvalEdge (e,L,H)(e,G_L,G_H) 30 31 if ∑e∈ℰtour(e,H)<tf _e _tour Cost(e,G_H)<t_f then 32 ←′Q 33 if no new edges evaluated this iteration then 34 ℱimp←ℱimp∪F_imp _imp∪\Q\ 35 break 36 37 38Find best tour ∗Q^* from ℱinit∪ℱimpF_init _imp and its cost tf∗t^*_f 39 τa∗←(∗,L)τ^*_a← GenAgentTraj(Q^*,G_L) return ∗,τa∗,tf∗Q^*,τ^*_a,t^*_f Algorithm 1 Two-Phase Bilevel Search 1BEFORE = dict() 2 for v∈Hv _H do 3 BEFORE[v] ← i∈′|v∉iand ∀v′∈i,(v,v′) is marked infeasible\i \,|\,v _i\; and ∀\,v _i,\;(v,v ) is marked infeasible\ 4 5STACK ← [(∅,π¯s(0))( , π_s(0))] 6 CLOSED ← ∅ 7 while STACK is not empty do 8 u=(,v)u=(U,v) ← STACK.pop() 9 if u∈CLOSEDu∈ CLOSED then continue 10 CLOSED.insert(u) 11 if =′U=T then 12 ←(u)Q← ReconstructTour(u) 13 if does not exist in ℱinitQ does not exist in F_init then return Q 14 else continue 15 16 for v′ in (v,H,Hv in SuccessorGNodes(v,G_H,P_H) do 17 u′=(∪(v′),v′)u =(U∪\ target(v )\,v ) 18 if u′∈CLOSEDu ∈ CLOSED then continue 19 u′.bp=u . bp=u 20 STACK.push(u′) STACK.push(u ) 21 22 return NULL Algorithm 2 (H,H,ℱinit) HighLevelDFS(G_H,P_H,F_init) Now we explain the details of the Two-Phase Bilevel Search (Alg 1). Lines 1–1 construct both high and low level graphs, as well as initialize sets that store the initial and improved feasible tours, ℱinitF_init and ℱimpF_imp, respectively. In line 1, HP_H denotes a dictionary mapping each edge in ℰHE_H to an associated penalty H[e]P_H[e]. All penalties are initially set to 0 in this line. Phase 1 of the algorithm is described by lines 1–1. This phase attempts to generate up to NtoursN_tours number of initial feasible tours within a prescribed initial search time limit, terminating early if no new feasible tour can be found (line 1). To quickly obtain an initial feasible tour, the high-level search HighLevelDFS (Alg 2), is invoked to compute a candidate GTSP tour with associated edges ℰtourE_tour. Each edge e∈ℰtoure _tour is then evaluated by EvalEdge (Alg 3). If all edges are found to be feasible after evaluation, the tour is feasible, and hence added to ℱinitF_init. Additionally, to encourage diversity between the current and the next feasible tour, the time window transitions associated with the current feasible tour are penalized. For each edge e=(v,v′)∈ℰtoure=(v,v ) _tour, WinEdges returns all edges in ℰHE_H connecting nodes with the same associated time window as v to nodes with the same associated time window as v′v , denoted by ℰwinE_win. The penalty associated with each edge in ℰwinE_win is increased by an amount δ. If one or more edges in ℰtourE_tour were found to be infeasible after evaluation, HighLevelDFS is invoked again to generate a new candidate tour, and the evaluation and subsequent steps are repeated, subject to the Phase 1 termination conditions. Phase 2 of the algorithm is described by lines 1–1. The initial feasible tours obtained in Phase 1 are first sorted in the increasing order of tour duration tft_f, and are then improved sequentially over the remainder of the total algorithm time limit. To improve an initial feasible tour Q it is treated as an incumbent and passed to ImproveTour which represents a user-selected GTSP heuristic (e.g., GLNS [24], PGLNS [4], or GLKH [13]). It then returns a candidate improved GTSP tour ′Q with associated edges ℰtourE_tour. As in Phase 1, all edges in ℰtourE_tour are evaluated by EvalEdge. If after evaluation, the cost of ′Q is less than the duration tft_f of the incumbent, the incumbent Q is updated to ′Q . Note that the cost of a tour equals its duration tft_f if it is feasible and +∞+∞ otherwise. Since the incumbent is always feasible, it can only be updated by another feasible tour of lower cost. Finally, if all the edges in ℰtourE_tour were already evaluated previously (i.e., line 3 in Alg 3 is not satisfied each time EvalEdge is called in line 1 of Alg 1), the termination criteria for tour improvement is reached, and Q is added to ℱimpF_imp. Otherwise, Q is passed again to ImproveTour and the subsequent steps are repeated, subject to the Phase 2 termination conditions. After both phases are complete, Alg 1 picks the lowest cost tour ∗Q^* from ℱinit∪ℱimpF_init _imp with associated duration tf∗t^*_f, and finds an associated agent trajectory τa∗τ^*_a by calling GenAgentTraj (Alg. 4). Finally, the best feasible solution found, ∗,τa∗,tf∗Q^*,τ^*_a,t^*_f is returned. 1if e is not marked as evaluated then 2 e=(π¯i(ti),π¯j(tj))e=( π_i(t^i), π_j(t^j)) 3 if StraightLineFeasible (π¯i(ti),π¯j(tj))( π_i(t^i), π_j(t^j)) then mark e as feasible 4 else γe← _e← LowLevelDFS (L,π¯i(ti),π¯j(tj))(G_L, π_i(t^i), π_j(t^j)) 5 if γe is NULL _e is NULL then 6 Mark e as infeasible 7 H←G_H← UpdateCost (+∞,e,H)(+∞,e,G_H) 8 else Mark e as feasible 9 Mark e as evaluated 10 Algorithm 3 EvalEdge (e,L,H)(e,G_L,G_H) 1γ←()γ←() 2 ℰtour←()E_tour← TourEdges(Q) 3 for each edge e∈ℰtour each edge e _tour do 4 e=(π¯i(ti),π¯j(tj))e=( π_i(t^i), π_j(t^j)) 5 if StraightLineFeasible (π¯i(ti),π¯j(tj))( π_i(t^i), π_j(t^j)) then γe←(π¯i(ti),π¯j(tj)) _e←( π_i(t^i), π_j(t^j)) 6 else γe← _e← LowLevelDFS (L,π¯i(ti),π¯j(tj))(G_L, π_i(t^i), π_j(t^j)) 7 γ←(γ,γe)γ← Extend(γ, _e) 8 return (γ) Traj(γ) Algorithm 4 (,L) GenAgentTraj(Q,G_L) We will now briefly explain subroutines HighLevelDFS, EvalEdge, and GenAgentTraj. HighLevelDFS (Alg 2) seeks to find a GTSP tour which starts at s=π¯s(0)C_s=\ π_s(0)\, visits every cluster iC_i for i∈i exactly once, before visiting cluster s′C_s . This achieved using a DFS-style search like in [4]. The search precomputes a set BEFORE[v] for each v∈Hv _H containing all targets whose clusters cannot be feasibly visited after v, and explores search nodes denoted by a tuple u=(,v)u=(U,v) with ⊆′U and v∈Hv _H. A search node represents the set of paths in HG_H that visits all clusters corresponding to targets in U (in any order) before terminating at node v. A backpointer is maintained for each search node u, denoted as u.bp, equal to a search node previously popped from the stack. If =′U=T (independent of order), a tour Q is recontructed from u. If Q was not previously added to ℱinitF_init, the search terminates, and Q is returned. Otherwise, the search continues (lines 2–2). If ≠′U , a set of successor G-nodes v′∈Hv _H are generated (line 2) that satisfies (1) Edge e=(v,v′)e=(v,v ) is not marked infeasible, (2) v′∉iv _i for any i∈i , and (3) BEFORE[v′v ] ⊆ . Condition (1) ensures a feasible tour in HG_H, (2) ensures that each cluster is visited once, and (3) ensures that by visiting v′v , we do not prevent any unvisited clusters from being visited. For each successor G-node v′v , we generate a successor search node u′=(∪(v′),v′)u =(U∪\ target(v )\,v ) where (v′) target(v ) denotes the target (or depot) corresponding to v′v in ′T . Successor search nodes u′u are pushed to the stack in order of decreasing (e,H)+H[e] Cost(e,G_H)+P_H[e], where e=(v,v′)e=(v,v ), such that the least-cost successor gets popped from the stack next. EvalEdge (Alg. 3) lazily evaluates a previously unevaluated edge e∈ℰHe _H. It first checks whether a straight-line trajectory connecting the endpoints of e intersects any obstacle over time. If not, e is marked feasible. Otherwise, LowLevelDFS is invoked on LG_L to search for a collision-free path connecting the endpoints. If no such path exists, e is marked infeasible and its cost in HG_H is set to +∞+∞. In all cases, e is marked as evaluated. GenAgentTraj (Alg 4) constructs a continuous agent trajectory from a feasible high-level tour Q. For each edge e in the tour, it attempts to generate a local path γe _e connecting the edge endpoints as follows: If a straight-line trajectory connecting the endpoints is collision-free, we set γe=e _e=e. Otherwise, γe _e is computed by invoking LowLevelDFS on LG_L. The construction of LG_L ensures time-feasible, collision-free trajectory segments connecting consecutive points in γe _e. The local paths for all tour edges are concatenated in tour order to form a complete space–time path γ, which is finally converted into a continuous agent trajectory via interpolation. V NUMERICAL RESULTS We ran two experiments on a laptop with an Intel Core I7-7700HQ 2.80GHz CPU, and 16GB RAM. The implementation was mainly in Python 3.11.6 for all approaches, with HighLevelDFS implemented in C++, and ImproveTour using PGLNS [4] since it accepts an initial tour. We set the number of threads to 1 so it works the same as GLNS [24]. Additionally, we let PGLNS terminate early if it found an improving tour containing unevaluated edges, before reaching GLNS termination criterion. The MICP was solved using Gurobi 10.0.3 [12]. The first experiment varied the number of obstacles to be 5,10,205,10,20, and 4040 while keeping the total time window duration per target fixed at 60secs60\,secs, and the second experiment varied the total target time window duration to be 40,6040,60, and 80secs80\,secs while keeping the number of obstacles fixed at 2020. For both experiments, the number of targets were varied to be 5,10,205,10,20, and 4040, with each target assigned two time windows of equal duration. We randomly generated instances where targets follow nonlinear trajectories, and obstacle trajectories are kept linear. Target trajectories were obtained by fitting cubic B-splines through piecewise-linear trajectories with speeds drawn randomly from [0.25,0.5]units/sec[0.25,0.5]\,units/sec. Obstacle speeds were also drawn randomly from this same range, and the agent’s maximum speed was set to 4units/sec4\,units/sec. All targets and obstacles were confined within a square workspace of size 40units40\,units. The obstacles were chosen to be squares with size randomly drawn from [2,3]units[2,3]\,units, and the depot location was fixed at the top right corner of the workspace. To avoid infeasible cases, we applied a conservative feasibility screening step, retaining only instances for which a feasible tour could be identified by Phase-1 of TPBS under fully relaxed time window constraints. Based on the corresponding trajectories, time windows were then defined so as to preserve feasibility of the generated instances. We compare our approaches against a baseline method introduced in [15]. The method first attempts to solve the high-level GTSP on HG_H using a heuristic. If the straight-line trajectories corresponding to the tour edges are collision-free, the solution is returned. Otherwise, two alternative strategies are invoked. The first strategy repeatedly solves the GTSP while marking colliding tour edges as infeasible, until a feasible solution is found or a time limit is reached. The second strategy is similar but additionally attempts to bypass colliding obstacles by adding space-time points around them at the time of collision, to clusters that must now be visited by the GTSP tour. The lower-cost solution from the two strategies is then returned. We ran the baseline using GLKH [13] (like in [15]), as well as GLNS, as the GTSP heuristic. For both experiments, we generated 20 instances for each combination of the number of targets, number of obstacles, and total time-window duration. Each solver was run on all instances with a 150s150s time limit, and we report the success rates, and average runtimes, and cost ratios, where success rate denotes the fraction of instances for which a feasible solution is returned, and the cost ratio for a solver is defined as (costsolver−costTPBS)/costTPBS(cost_solver-cost_TPBS)/cost_TPBS, averaged over all instances for which both methods return feasible solutions. Additionally, we report the average best solution costs and total runtimes for Phase 1 and Phase 2. For all solvers, we used a common discretization of time at 1sec1\,sec intervals, and for the construction of LG_L in TPBS, we uniformly sampled the workspace with 1unit1\,unit spacing in both the x and y directions. We set the penalty parameter δ for TPBS to 55, parameter NtoursN_tours to 44, and allocated half of the total 150s150s time budget to Phase 1. Figure 3: Success rates and average runtimes for all approaches. (a)–(d) Experiment 1: increasing obstacle count from 55–4040 with fixed total time window duration of 60secs60\,secs. (e), (c), and (f) Experiment 2: varying total time window duration from 4040–8080 secssecs with 20 obstacles. Figure 4: Average cost ratios of MICP and both baselines with respect to TPBS for Experiments 1 and 2 (same layout as Fig. 3). Figure 5: Average of best solution costs and total runtimes for Phase 1 and Phase 2 of TPBS for Experiments 1 and 2 (same layout as Fig. 3). V-A Experiment 1: Varying Number of Obstacles In this experiment, we vary the number of obstacles to be 5,10,20,405,10,20,40 while keeping the total time window duration for each target at 60secs60\,secs. The success rates and runtimes are shown in Fig. 3 (a)–(d). The proposed approaches achieve significantly higher success rates than the baselines across all tested instances. In particular, TPBS successfully solved all tested instances, while the MICP formulation remained consistently successful only up to 2020 targets and obstacles. For 4040 targets, the success rate of MICP drops sharply for all obstacle counts, with further degradation observed as the number of targets increases at 4040 obstacles. The success rates of the baseline methods decrease as the number of targets increases, across all obstacle counts. This degradation becomes more pronounced as the number of obstacles grows. We observe that the baseline performs better when using GLNS as the GTSP heuristic compared to GLKH; however, for 2020 targets and obstacles and beyond, both variants exhibit very low success rates, with GLNS achieving only a 20%20\% success rate at 2020 targets and obstacles. We observe that TPBS consistently achieves the fastest runtime and completes well within the 150s150s limit, particularly for instances up to 2020 targets and obstacles. For 55 targets, MICP is marginally faster than TPBS in most cases, except at 1010 obstacles. However, as problem size increases, TPBS significantly outperforms MICP, typically requiring half or less of the runtime for up to 2020 targets and obstacles. At 4040 targets, TPBS is the only method that reliably produces feasible solutions within the time limit, while all others frequently exhaust the runtime budget. Among the baselines, GLNS is consistently faster than GLKH, but for 1010 obstacles and above, both typically reach the time limit for 2020 or more targets, reflecting their low success rates. For 55 and 1010 targets, the baseline methods require roughly twice the runtime of MICP, underscoring their limited scalability. The cost ratios are shown in Fig. 4 (a)–(d). For 55 and 1010 obstacles, all competing methods exhibit mainly nonnegative cost ratios across all target counts, indicating no significant improvement over TPBS. At 2020 obstacles, MICP achieves a modest ≈5%≈ 5\% improvement for 1010 targets. For 4040 obstacles, isolated improvements are observed: MICP yields close to 10%10\% lower cost for 55 targets, while GLKH and GLNS outperform TPBS for 1010 targets by approximately 10%10\% and 25%25\%, respectively. In all remaining cases, TPBS achieves comparable or lower cost. Finally, Fig. 5 (a)–(d) reports the best solution costs and total runtimes for Phase 1 and Phase 2. We observe that cost improvements from Phase 2 generally increase with the number of targets, but diminish as the number of obstacles grows. In particular, for 4040 obstacles, further improving Phase 1 solutions becomes difficult, as even finding feasible solutions is challenging. The runtimes of both phases increase with problem size, scaling with both the number of targets and obstacles. For instances with 4040 targets, Phase 1 is substantially faster than Phase 2, requiring less than half the runtime across all obstacle counts. V-B Experiment 2: Varying Total Time Window Duration In this experiment, we vary the total time window duration per target to be 40,60,80secs40,60,80\,secs, while fixing the number of obstacles constant at 2020. Like in the previous experiment, success rates and runtimes are reported in Fig. 3, cost ratios in Fig. 4, and the best solution costs and total runtimes for Phase 1 and Phase 2 in Fig. 5. Across all figures, we reuse subfigure (c) for the 60secs60\,secs case. Additionally, subfigures (e) and (f) corresponds to 4040 and 80secs80\,secs respectively. From Fig. 3, we observe that the runtimes of all approaches increase with longer time window durations, particularly for larger numbers of targets. Moreover, the success rates of the proposed methods remain largely stable, whereas those of the baseline approaches fluctuate as the time window duration increases. From Fig. 4, we observe broadly consistent trends in cost ratios across all methods, with an increase as the time-window duration increases for the MICP. Interestingly, the baseline with GLKH attains a smaller cost ratio at 80secs80\,secs, than it does for shorter durations. Finally, from Fig. 5, we observe a slight increase in runtimes and consistent cost improvements from Phase 2, with longer time window durations. VI CONCLUSION AND FUTURE WORK In this paper, we presented a Mixed-Integer Conic Programming formulation and a Two-Phase Bilevel Search algorithm for the Moving-Target Traveling Salesman Problem with Moving Obstacles. Extensive numerical experiments demonstrate that the proposed approaches significantly outperform a baseline method across a broad range of problem instances. Promising directions for future work include incorporating dynamic constraints on the agent, extending to multi-agent scenarios, and developing fast algorithms with provable guarantees on completeness and optimality. References [1] R. J. Afonso, M. R. Maximo, and R. K. Galvao (2020) 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 30 (14), p. 5464–5491. Cited by: §I. [2] A. Bhat, G. Gutow, B. Vundurthy, Z. Ren, S. Rathinam, and H. Choset (2024) A complete algorithm for a moving target traveling salesman problem with obstacles. arXiv preprint arXiv:2409.09852. Cited by: §I. [3] A. Bhat, G. Gutow, B. Vundurthy, Z. Ren, S. Rathinam, and H. Choset (2025) A complete and bounded-suboptimal algorithm for a moving target traveling salesman problem with obstacles in 3d. arXiv preprint arXiv:2504.14680. Cited by: §I. [4] A. Bhat, G. Gutow, B. Vundurthy, Z. Ren, S. Rathinam, and H. Choset (2025) Parallel, asymptotically optimal algorithms for moving target traveling salesman problems. arXiv preprint arXiv:2509.08743. Cited by: §I, §IV, §IV, §V. [5] J. Bourjolly, O. Gurtuna, and A. Lyngvi (2006) On-orbit servicing: a time-dependent, moving-target traveling salesman problem. International Transactions in Operational Research 13 (5), p. 461–481. Cited by: §I. [6] G. G. Brown, W. C. DeGrange, W. L. Price, and A. A. Rowe (2017) Scheduling combat logistics force replenishments at sea for the us navy. Naval Research Logistics (NRL) 64 (8), p. 677–693. Cited by: §I. [7] P. Chalasani and R. Motwani (1999) Approximating capacitated routing and delivery problems. SIAM Journal on Computing 28 (6), p. 2133–2149. Cited by: §I. [8] N. S. Choubey (2013) Moving target travelling salesman problem using genetic algorithm. International Journal of Computer Applications 70 (2). Cited by: §I. [9] R. S. de Moraes and E. P. de Freitas (2019) Experimental analysis of heuristic solutions for the moving target traveling salesman problem applied to a moving targets monitoring system. Expert Systems with Applications 136, p. 392–409. Cited by: §I. [10] B. Englot, T. Sahai, and I. Cohen (2013) Efficient tracking and pursuit of moving targets by heuristic solution of the traveling salesman problem. In 52nd ieee conference on decision and control, p. 3433–3438. Cited by: §I. [11] C. Groba, A. Sartal, and X. H. Vázquez (2015) Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: an application to fish aggregating devices. Computers & Operations Research 56, p. 22–32. Cited by: §I. [12] Gurobi Optimization, LLC (2023) Gurobi Optimizer Reference Manual. External Links: Link Cited by: §V. [13] K. Helsgaun (2015) Solving the equality generalized traveling salesman problem using the lin–kernighan–helsgaun algorithm. Mathematical Programming Computation 7, p. 269–287. Cited by: §IV, §V. [14] C. S. Helvig, G. Robins, and A. Zelikovsky (2003) The moving-target traveling salesman problem. Journal of Algorithms 49 (1), p. 153–174. Cited by: §I. [15] Y. Li, S. Li, Y. Zhang, W. Zhang, and H. Lu (2023) Dynamic route planning for a usv-uav multi-robot system in the rendezvous task with obstacles. Journal of Intelligent & Robotic Systems 107 (4), p. 52. Cited by: §I, §I, §V. [16] D. Marlow, P. Kilby, and G. Mercer (2007) The travelling salesman problem in maritime surveillance–techniques, algorithms and analysis. In Proceedings of the international congress on modelling and simulation, p. 684–690. Cited by: §I. [17] A. Maskooki and M. Kallio (2023) A bi-criteria moving-target travelling salesman problem under uncertainty. European Journal of Operational Research. Cited by: §I. [18] A. G. Philip, Z. Ren, S. Rathinam, and H. Choset (2024) A mixed-integer conic program for the moving-target traveling salesman problem based on a graph of convex sets. In 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 8847–8853. Cited by: §I. [19] A. G. Philip, Z. Ren, S. Rathinam, and H. Choset (2025) A mixed-integer conic program for the multi-agent moving-target traveling salesman problem. In 2025 IEEE 21st International Conference on Automation Science and Engineering (CASE), Vol. , p. 492–498. External Links: Document Cited by: §I. [20] A. G. Philip, Z. Ren, S. Rathinam, and H. Choset (2025) C∗: a new bounding approach for the moving-target traveling salesman problem. IEEE Transactions on Robotics 41 (), p. 4663–4678. External Links: Document Cited by: §I. [21] Z. Ren, A. G. Philip, S. Zhao, S. Rathinam, and H. Choset (2025) CP-milp: mixed integer linear programming for multi-agent motion planning with linear dynamics. IEEE Robotics and Automation Letters 10 (12), p. 12573–12579. External Links: Document Cited by: §I. [22] M. W. Savelsbergh (1985) Local search in routing problems with time windows. Annals of Operations research 4 (1), p. 285–305. Cited by: §I. [23] C. D. Smith (2021) Assessment of genetic algorithm based assignment strategies for unmanned systems using the multiple traveling salesman problem with moving targets. University of Missouri-Kansas City. Cited by: §I. [24] S. L. Smith and F. Imeson (2017) GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem. Computers & Operations Research 87, p. 1–19. Cited by: §IV, §V. [25] A. Stieber and A. Fügenschuh (2022) Dealing with time in the multiple traveling salespersons problem with moving targets. Central European Journal of Operations Research 30 (3), p. 991–1017. Cited by: §I. [26] Y. Wang and N. Wang (2023) Moving-target travelling salesman problem for a helicopter patrolling suspicious boats in antipiracy escort operations. Expert Systems with Applications 213, p. 118986. Cited by: §I. [27] S. Zhao, A. G. Philip, S. Rathinam, H. Choset, and Z. Ren (2025) CB-gcs: conflict-based search on the graph of convex sets for multi-agent motion planning. In 2025 IEEE 21st International Conference on Automation Science and Engineering (CASE), Vol. , p. 2208–2214. External Links: Document Cited by: §IV.