Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming

The paper Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming by Alessandro Bertagnon and Marco Gavanelli addresses the Euclidean Traveling Salesperson Problem (ETSP) and its variants within the framework of Constraint Logic Programming (CLP). The authors note that in the Constraint Programming literature, the Euclidean TSP is typically addressed by computing the full distance matrix and treating it as a general case, which ignores the geometric information carried by the points’ coordinates. The paper proposes new filtering algorithms that exploit this geometric information to achieve stronger constraint propagation than existing approaches, and extends the methodology to the Euclidean Generalized Traveling Salesperson Problem (EGTSP).

The paper's contributions are twofold. First, it provides a more precise description of algorithms introduced in a prior conference publication and extends the experimental campaign to a large dataset of TSP instances. Second, it demonstrates that the enhanced pruning based on geometric properties can be applied beyond the TSP, specifically to the EGTSP, which is relevant in practical routing and logistics applications.

The core geometric properties exploited are the no-crossing property and convex-hull ordering. The paper states, "The underlying no-crossing and convex-hull ordering properties are classical geometric results; our contribution lies in translating them into dedicated CP/CLP constraints and propagators, and in extending this approach to the EGTSP."

The paper introduces a nocrossing constraint, based on Theorem 4.1 (Flood, 1956), which states that an optimal tour of a metric TSP cannot include two edges that cross each other. The constraint is defined as: nocrossingi,j (Next i, Next j) = (ni, nj) ∈ Dom(Next i) × Dom(Next j) Pi Pni ∩ Pj Pnj ⊂ Pi, Pj . The implementation uses a propagator with two phases. The first phase uses a watched-literal-like strategy to suspend until all elements in the domain of Next j lie in the same half-plane with respect to the line Pi Pj. The second phase uses pre-computed angles to efficiently check for crossings, reducing complexity from O(d2) to O(d) per activation, with an amortized complexity of O(d2) over a branch of the search tree.

The paper also exploits convex hull reasoning, based on Corollary 4.6 (Deineko et al., 1994): Assuming that not all cities lie on one line, an optimal tour has the property that the cities on the boundary of the convex hull of the cities are visited in their cyclic order. Three ways to exploit this are presented: (1) a unary constraint that the successor of a convex hull vertex cannot be another hull vertex except the one immediately following it; (2) a clockwise angle propagator that removes values based on the angle between incoming and outgoing edges at hull vertices; (3) a hull path propagator that removes values from variables along a path originating from a hull vertex, preventing the path from reaching any other hull vertex except the designated successor. The convex hull reasoning is further extended to internal hulls via Theorem 4.7, which states that for a partial path forming a simple polygon, the vertices of the convex hull of the points inside that polygon must be visited in a specific order.

For the EGTSP, the paper proposes a constraint model using the successor representation with a modified circuit constraint that accepts sub-tours of length 1 (for unvisited nodes). The geometric reasoning is adapted through the concept of neighbours (Definition 5.1): a point Pj in cluster C(Hi) is a neighbour of a hull vertex Hi if the segment Hi Pj does not intersect the convex hull of all points not in C(Hi). Theorem 5.2 provides a condition under which no point in the neighbour set of one hull vertex can have a point in the neighbour set of the adjacent hull vertex as its successor in an optimal EGTSP. This leads to the hull set propagator (Algorithm 4), which removes values from domains based on this condition.

The experimental evaluation was conducted in ECLiPSe v. 7.0, with a time limit of 1800 seconds on Intel Xeon E5-2630 v3 CPUs. For the ETSP, experiments were run on both structured instances (from TSPLIB, the Concorde website, and the CITIES dataset) and random instances (uniform and clustered). The models compared were GEO+HK-RMC (which includes the proposed geometric filtering plus the Held-Karp bound with Reduced and Marginal Costs) and HK-RMC alone, using two search strategies: LC FIRST MAX COST and MAX-REGRET. Results on structured instances show that the constraint models that contain geometric filtering are the ones that optimally solve the instances in the shortest time. On random uniform instances, the GEO+HK-RMC model reduced solving time by an average of 70% and search nodes by 59% (with LC FIRST MAX COST) and reduced solving time by 70% and nodes by 71% (with MAX-REGRET). On clustered instances, the reduction in solving time was also 70%, with node reductions of 43% (LC FIRST MAX COST) and 75% (MAX-REGRET). The number of timeouts was also reduced, particularly for larger instances.

For the EGTSP, instances were generated using three partitioning approaches: uniform, clustering, and grid. The GEO model (with geometric pruning) was compared to the basic ECLP model. The GEO model consistently solved more instances within the time limit. For clustering-type instances, the average solving time was reduced by 76% and nodes by 77%; for grid-type instances, reductions were 67% and 66%, respectively; for uniform-type instances, reductions were 19% and 17%. The paper notes that the lower improvements on uniform instances are due to the distribution of points making it difficult to have significant sets of neighbours.

The paper concludes that the use of geometric information can result in stronger pruning and that the proposed techniques are effective. It acknowledges that results are not yet comparable to state-of-the-art solvers like Concorde, but notes that Concorde cannot solve GTSP instances. The authors also mention a limitation: the techniques are not universally applicable to all TSP variants, such as TSP with Time Windows, whose optimal solutions may contain crossings. Future work includes investigating extensions to other routing models where the geometric structure preserves the required assumptions.

Improvements to AI Systems:

1. Geometric-Aware Constraint Propagation for Routing Solvers

• Integrate the nocrossing constraint and convex-hull ordering propagators into general-purpose AI planning/optimization systems (e.g., OR-Tools, CP-SAT, or hybrid ML-CP solvers) to prune search spaces for Euclidean routing problems.

• The improved system can solve TSP/GTSP instances faster by eliminating crossing edges and enforcing hull-order without computing full distance matrices, reducing time complexity from O(d2) to O(d) per propagation step.

2. Adaptive Search Strategy Selection via Geometric Features

• Use the paper’s experimental insights (e.g., 70% time reduction on uniform/clustered instances) to train a meta-learner that predicts when to activate geometric filtering based on point distribution (uniform vs. clustered vs. grid).

• The improved system can dynamically toggle geometric constraints, balancing pruning strength with overhead, leading to robust performance across diverse instance types.

3. Extended Geometric Reasoning for Generalized TSP (GTSP) in Logistics AI

• Implement the hull set propagator and neighbour-based pruning for multi-cluster routing (e.g., delivery zones, warehouse grouping).

• The improved system can solve real-world GTSP instances (e.g., vehicle routing with mandatory stops per region) with 76% fewer search nodes on clustered data, enabling faster route optimization in dynamic logistics.

4. Hybrid CP/ML Model for TSP Variants with Geometric Validity

• Combine the geometric constraints with learned heuristics (e.g., graph neural networks predicting promising edges) to guide branching.

• The improved system can prune geometrically invalid subtours early, reducing the search space for ML-guided solvers and improving solution quality for large-scale instances (e.g., >1000 cities) where pure ML fails.

5. Domain-Specific Constraint Library for Euclidean Optimization

• Package the proposed propagators (nocrossing, hull path, clockwise angle) as reusable modules in constraint programming frameworks.

• The improved system can automatically apply these constraints to any Euclidean metric problem (e.g., drone path planning, circuit board drilling), not just TSP, by detecting geometric structure in the input.

6. Timeout Reduction and Scalability for Hard Instances

• Use the paper’s finding that geometric filtering reduces timeouts on large structured instances to design a fail-safe mechanism: if a solver exceeds a time threshold, it activates geometric pruning as a fallback.

• The improved system can solve previously intractable instances (e.g., TSPLIB’s pr1002) within 1800s, extending the operational range of AI-based route optimizers.

7. Theoretical Guarantees for Non-Crossing Optimality in AI Planning

• Encode Theorem 4.1 and Corollary 4.6 as hard constraints in AI planners for Euclidean problems, ensuring solutions respect geometric optimality conditions.

• The improved system can certify that its solutions are crossing-free and hull-ordered, providing verifiable quality guarantees for safety-critical applications (e.g., autonomous vehicle routing).

The Traveling Salesperson Problem (TSP) is one of the best-known problems in computer science and arises in many engineering applications, such as smart vehicles and intelligent transportation systems. In the "Euclidean" case, each node is defined by its coordinates in the plane and distances are computed using the Euclidean metric. In the Constraint Programming (CP) literature, the Euclidean TSP is typically addressed by computing the full distance matrix and treating it as a general case; however this approach ignores the geometric information carried by the points' coordinates. In this work, we propose new filtering algorithms, implemented in Constraint Logic Programming (CLP), that exploit such geometric information to achieve stronger constraint propagation than existing approaches. Moreover, we show how this methodology can be extended to other Euclidean variants of the TSP, including the Euclidean Generalized Traveling Salesperson Problem (EGTSP), which is relevant in practical routing and logistics applications. Experimental results demonstrate the computational advantages of the proposed approach.