GHOST employs a two-level hierarchical search strategy to solve GCS-TSP.
High-Level Tour Search (Algorithm 2)
The high-level search generalizes the Lawler-Murty procedure. It performs a best-first search on an OPEN list of nodes, prioritized by their lower-bound tour cost (n.c). Each node n corresponds to solving a Restricted-TSP (RTSP) instance on a complete graph induced by the GCS, with specified inclusion (Ê⁺) and exclusion (Ê⁻) edge sets. The root node r is initialized with an unrestricted TSP. The search iteratively pops the node n with the smallest n.c. If n.c is no smaller than the cost of the current best trajectory c(n*.τ), the search terminates, returning n*.τ as optimal. Otherwise, it calls EvalNode to unfold n.π and compute c(n.τ). If c(n.τ) improves upon c(n*.τ), n* is updated. For each edge e_i in n.π, a child node nc_i is created by adding e_i to nc.Ê⁻ and all edges with indices less than i to nc.Ê⁺. If a feasible RTSP tour exists for (nc.Ê⁺, nc.Ê⁻), nc_i is inserted into OPEN.
Low-Level Path Unfolding and Trajectory Optimization (EvalNode function)
The EvalNode function calls the abstract-path-unfolding algorithm (Algorithm 1) to generate paths π unfolded from an abstract tour π̂. These paths are considered in non-decreasing order of their lower-bound cost L(π). Pruning occurs if L(π) exceeds the current best trajectory cost c(n.τ). For each unfolded path π, the function computes the optimal trajectory τ conditioned on π via convex optimization. If a lower cost is found, n.τ is updated. This convex optimization follows the "GCS convex restriction" but extends it to allow π to revisit vertices and edges multiple times by introducing separate variables for each occurrence.
Lower-Bound Graph (LBG) Construction
A directed hypergraph H = (P, F) is constructed. A triplet p = (u, v, w) in P represents a passage through vertex v with predecessor u and successor w. A hyperedge (p, p') in F connects p = (·, u, v) to p' = (u, v, ·). Each triplet p is labeled with a lower-bound cost lbp, computed as the optimal trajectory cost conditioned on p via a convex program. This lbp never overestimates the cost portion c(x_u, x_v) + c(x_v, x_w).
Abstract-Path-Unfolding Algorithm (Algorithm 1)
This algorithm uses a multi-label A*-like best-first search to enumerate all paths unfolded from a given abstract path π̂ = (v_1, ..., v_k) on G in non-decreasing order of their lower-bound costs. Each search state n consists of a triplet p, a label l (progress towards v_l+1), current cost n.g, and estimated final cost n.f = n.g + h_π̂(p, n.l). The search maintains an OPEN list prioritized by n.f. Nodes are initialized for every triplet p matching the prefix of π̂. When n.π ends at v_k and n.l = k, n.π is yielded as the next-best unfolded path. Child nodes nc are created by appending consistent triplets, incrementing nc.l if w = v_n.l+1, updating nc.g by adding lbp, and setting nc.f with an admissible heuristic h_π̂. Nodes with nc.f > c are pruned.
Restricted-TSP over Abstract Triplets
The RTSP is solved on the induced complete graph Ĝ = (V, Ê). It uses binary variables y_p for triplets p ∈ P, minimizing the lower-bound tour cost:
min ∑_p∈P b(p)y_p
subject to:
∑_p=(·,v,·)∈P y_p = 1, ∀v ∈ V
∑_z≠v y_zuv = ∑_w≠u y_uvw, ∀(u, v) ∈ Ê
∑_p∈P_e=(u,v) y_p = 2, ∀e = (u, v) ∈ Ê⁺
y_p = 0, ∀p∈P_ind, e∈Ê⁻
Subtour elimination constraints are added iteratively: ∑_p∈C y_p ≤ |C| - 1 for any new subtour C. The cost b(p) for a triplet p is defined as L(π_u,v) + b_mid(p) + L(π_v,w), where b_mid(p) is the minimum lbp over relevant triplets depending on whether (u,v) and (v,w) are in E.