💻 computer science

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

This paper proposes new filtering algorithms within Constraint Logic Programming that leverage geometric information from Euclidean coordinates to achieve stronger constraint propagation and improved computational performance for the Euclidean Traveling Salesperson Problem and its variants, such as the Generalized TSP.

Original authors: Alessandro Bertagnon, Marco Gavanelli

Published 2026-08-12

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Alessandro Bertagnon, Marco Gavanelli

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a delivery driver with a map full of stops to make. You want to visit every stop exactly once and return home, but you also want to burn the least amount of gas possible. This is the classic "Traveling Salesperson Problem," a puzzle that has stumped mathematicians and computer scientists for decades. It's not just about delivery trucks; it's about everything from routing smart vehicles to organizing data on a computer chip. The tricky part is that as you add more stops, the number of possible routes explodes so fast that even the world's fastest computers can get lost in the maze.

To solve this, computers often use a method called "Constraint Programming." Think of this like a super-smart detective who doesn't just guess routes randomly. Instead, the detective sets up a series of rules (constraints) to eliminate impossible or silly options immediately. For example, "You can't visit the same city twice" or "You can't drive in a circle that skips the rest of the trip." Usually, when the problem involves distances on a flat map (what scientists call the "Euclidean" case), the computer just treats the map like a generic list of numbers, ignoring the fact that the stops are actually drawn on a piece of paper with straight lines and angles. It's like trying to navigate a city by only looking at a list of street names, without ever looking at the map itself.

This paper asks a simple but powerful question: What if we stopped ignoring the map? The authors, Alessandro Bertagnon and Marco Gavanelli, decided to build a new set of "rules" for their computer detective that actually understand geometry. They created special algorithms that know that in a perfect, shortest path, roads shouldn't cross each other like an "X" in the sky, and that the outer edge of a group of points should be visited in a neat, circular order. By teaching the computer to "see" the shape of the problem, they found a way to cut out millions of bad guesses much faster than before. They also showed that these geometric tricks work even when the problem gets more complicated, like when you have to visit a group of cities but only need to stop at one of them.

The Paper's Core Discovery

The main finding of this work is that by using the specific geometric properties of the Traveling Salesperson Problem (TSP)—specifically the fact that the shortest path on a flat plane never crosses itself and follows the outer edge of a shape in a specific order—computers can solve these routing puzzles significantly faster. The authors implemented these new rules in a programming language called Constraint Logic Programming (CLP).

They tested their new "geometric filtering" against the best existing methods. The results were striking: for random maps with up to 100 points, their new approach reduced the time it took to find the best solution by about 70% on average. In terms of the computer's "thinking steps" (search nodes), they cut the work down by roughly 59% to 75%, depending on the specific strategy used. This means the computer didn't just think faster per step; it had to think about far fewer steps to find the answer.

What They Ruled Out and How They Did It

The paper explicitly argues against the standard approach of treating Euclidean TSPs (where distances are straight lines on a plane) exactly the same as general TSPs. The common method is to calculate the distance between every pair of points, create a giant table of numbers, and then apply generic rules. The authors show that this "blind" approach ignores valuable information that is already there: the coordinates of the points. They demonstrate that ignoring the geometry leads to a much larger search space and slower solutions.

They also clarify what their method is not. They do not claim to have solved the TSP completely or to have created a magic bullet that works for every single type of routing problem. For instance, they note that their "no-crossing" rule doesn't apply to problems where roads must cross, such as in real-world city grids with one-way streets or bridges, or in problems with strict time windows where a detour might be necessary. Their work is specifically for "complete Euclidean instances" where the points are on a flat plane and crossings are avoidable.

The "No-Crossing" and "Convex Hull" Magic

To make the computer smarter, the authors introduced two main geometric concepts:

The No-Crossing Rule: Imagine you are drawing a loop with a string connecting dots on a table. If your string crosses itself, you can always pull the string tighter to make a shorter loop that doesn't cross. The authors proved mathematically that the optimal (shortest) path will never have crossing lines. They built a special "filter" into their computer program that instantly deletes any route option that would cause a crossing. This is like a bouncer at a club who immediately kicks out anyone trying to enter through the wrong door, saving the bouncer from having to check their ID later.
The Convex Hull Order: Imagine stretching a rubber band around a group of nails on a board. The shape the rubber band makes is called the "convex hull." The authors showed that in the shortest path, the nails on the very edge of this rubber band must be visited in a specific order (clockwise or counter-clockwise). They created rules that force the computer to respect this order, preventing it from wasting time checking routes that zigzag back and forth across the edge.

Extending the Magic to Group Problems

The paper also tackles a harder version of the problem called the "Generalized Traveling Salesperson Problem" (GTSP). In this version, instead of visiting every single city, you have to visit a set of "clusters" (groups of cities), but you only need to stop at one city in each group. This is like a delivery driver who has to drop off packages in three different neighborhoods but only needs to visit one house in each neighborhood.

The authors showed that their geometric rules could be adapted for this harder problem too. They defined "neighbors" based on the geometry of the clusters and applied the same no-crossing and ordering logic. In their tests on these group problems, the new geometric approach reduced the average solving time by up to 76% for clustered maps and 67% for grid-like maps.

The Bottom Line

The authors are careful to state that while their method is a huge improvement over previous Constraint Programming techniques, it is not yet as fast as the world's most powerful specialized solvers (like Concorde) for the basic TSP. However, those super-solvers often cannot handle the more complex "Generalized" versions of the problem that the authors successfully tackled.

The paper concludes that by simply paying attention to the shape of the problem—using the fact that lines don't cross and edges follow a curve—computers can prune away bad answers much more efficiently. This doesn't just speed up the calculation; it changes the nature of the search, allowing computers to solve larger and more complex routing puzzles that were previously too difficult to crack within a reasonable time. The authors suggest that this geometric approach could inspire similar improvements in other routing problems, provided the roads don't have to cross in unavoidable ways.

Technical Summary: Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its Variants in Constraint Logic Programming

Problem Definition
The paper addresses the Euclidean Traveling Salesperson Problem (ETSP), a variant of the classic TSP where nodes are defined by coordinates in a 2D plane and distances are calculated using the Euclidean metric. While the general TSP is NP-hard, the Euclidean version admits a Polynomial Time Approximation Scheme (PTAS). In the field of Constraint Programming (CP), the standard approach to solving ETSP instances is to compute the full distance matrix and treat the problem as a general TSP, thereby ignoring the intrinsic geometric information (coordinates, angles, and spatial relationships) available in the Euclidean case. The authors argue that this approach fails to exploit geometric properties that could lead to stronger constraint propagation and more efficient search. Furthermore, the paper extends this investigation to the Euclidean Generalized Traveling Salesperson Problem (EGTSP), where nodes are partitioned into clusters, and the goal is to visit at least one node from each cluster. To the authors' knowledge, CP approaches for EGTSP had not been previously explored.

Methodology
The authors propose new filtering algorithms implemented within the Constraint Logic Programming (CLP) framework, specifically using the ECLiPSe solver. The core methodology involves translating classical geometric theorems into dedicated propagators that operate on the successor representation of the TSP (where variables $Next_i$ denote the node following node $i$ ).

The proposed geometric filtering techniques include:

No-Crossing Constraint: Based on the theorem that an optimal Euclidean tour cannot contain crossing edges (Flood, 1956), the authors introduce a nocrossing constraint. This binary constraint prevents two segments in the tour from intersecting unless they share an endpoint.
- Implementation: The propagator utilizes a "watched literals" strategy to minimize activations. It sorts potential successors by the angle they form relative to a reference line. By tracking the minimum and maximum angles in the domains of the variables, the propagator can efficiently determine if a candidate edge would cross all possible edges from another node, allowing for $O(d)$ amortized complexity per activation (where $d$ is the domain size), significantly better than the $O(d^2)$ of a straightforward implementation.
Convex Hull Reasoning: Leveraging the property that cities on the boundary of the convex hull must be visited in cyclic order (Deineko et al., 1994), the authors implement three pruning strategies:
- Restricting the successor of a convex hull vertex to only the next vertex in the hull sequence (unless the hull vertex is not visited, which is handled in the EGTSP extension).
- Enforcing a "right turn" constraint on the angle formed by incoming and outgoing edges at convex hull vertices to ensure clockwise traversal.
- A path-based propagator that prevents paths originating from a convex hull vertex from reaching other hull vertices except the immediate successor.
- Extension: The authors extend this reasoning to "internal hulls" formed by partial paths during the search, applying similar pruning logic to the convex hull of the points enclosed by the current partial path.
EGTSP Adaptation: For the Generalized variant, the authors adapt the convex hull reasoning. They define "neighbours" of a hull vertex as points within the same cluster that do not intersect the convex hull of all other clusters. They prove that if the convex hull of the neighbours of two adjacent hull vertices is disjoint from the convex hull of all other clusters, specific successor relationships can be forbidden. This allows the geometric pruning to be applied even when not all hull vertices are visited.

Key Contributions

Geometric Propagators: The translation of the "no-crossing" and "convex hull ordering" properties into efficient CLP propagators that provide stronger pruning than standard general TSP models.
EGTSP Modeling: The proposal of the first constraint model for the Euclidean Generalized TSP within the CP literature, including a novel adaptation of geometric filtering for cluster-based routing.
Algorithmic Efficiency: The development of optimized propagators (e.g., using angle sorting and linked lists) that reduce the computational cost of filtering from quadratic to linear amortized time relative to domain size.
Comprehensive Evaluation: An extensive experimental campaign comparing the proposed geometric models (GEO) against state-of-the-art CP models using Held-Karp bounds and reduced costs (HK-RMC) on both structured (TSPLIB) and random (uniform and clustered) instances.

Experimental Results
The experiments were conducted on instances ranging from 20 to 100 nodes using two search strategies: MAX-REGRET and LC FIRST MAX COST.

Structured Instances: On TSPLIB and geographical instances, the geometric model (GEO) combined with HK-RMC consistently solved instances faster and with fewer search nodes than HK-RMC alone. The geometric filtering was particularly effective during the proof of optimality.
Random Instances (Uniform): The GEO+HK-RMC model achieved an average reduction of 70% in solving time and 59% in search nodes compared to HK-RMC alone. The improvement was more pronounced for larger instances (80+ nodes).
Random Instances (Clustered): Similar improvements were observed, with an average 70% reduction in solving time. The number of clusters did not significantly degrade the performance of the geometric filtering.
EGTSP Results: On Euclidean GTSP instances, the geometric model (GEO) outperformed the baseline (ECLP).
- For clustered instances, solving time was reduced by 76% and search nodes by 77%.
- For grid-based instances, solving time was reduced by 67%.
- For uniform instances, reductions were lower (19% time, 17% nodes) due to the difficulty of forming significant neighbour sets, but the approach remained beneficial.

Significance and Claims
The authors claim that their work demonstrates that exploiting geometric information intrinsic to Euclidean instances can significantly enhance constraint propagation in CP/CLP.

Pruning Power: The primary benefit is a reduction in the search space (fewer nodes explored) rather than just a lower constant cost per node.
Generality: The methodology is shown to be extensible beyond the basic TSP to the EGTSP, a variant relevant to logistics and routing where multiple providers exist for each resource.
Modesty: The authors explicitly state that their results are not yet comparable to state-of-the-art specialized solvers like Concorde (which uses ILP and branch-and-cut). However, they emphasize that Concorde cannot solve GTSP instances. The goal of the research was to demonstrate the power of declarative geometric reasoning in CP, not to propose a faster imperative algorithm. They suggest that these techniques could be ported to imperative solvers to achieve similar gains.
Limitations: The approach assumes the optimal solution does not contain crossings, which limits its direct applicability to variants like TSP with Time Windows where crossings might be necessary. Future work is proposed to investigate extensions to other routing models where geometric assumptions hold.

The Paper's Core Discovery

What They Ruled Out and How They Did It

The "No-Crossing" and "Convex Hull" Magic

Extending the Magic to Group Problems

The Bottom Line

More like this