Improved Filtering for the Euclidean Traveling Salesperson Problem in CLP(FD)

Alessandro Bertagnon, Marco GavanelliAAAI 2020 · DOI

Abstract

This paper introduces novel geometric filtering techniques for the Euclidean Traveling Salesperson Problem (ETSP) within Constraint Logic Programming (CLP). By leveraging coordinate data to prevent edge crossings and enforce convex hull properties, the authors significantly prune the search space, roughly halving the runtime compared to standard constraint programming approaches.

Introduction

The Traveling Salesperson Problem (TSP) is a cornerstone of combinatorial optimization. While specialized solvers like Concorde are highly efficient for pure TSP instances, they lack the flexibility of Constraint Programming (CP), which allows for the easy integration of side constraints such as time windows or specific visit orders. However, CP solvers typically underperform on Euclidean TSP instances because they discard geometric information, reducing coordinates to a simple distance matrix. This research addresses this gap by proposing new constraints that utilize 2D geometry to filter impossible paths early in the search process.

Geometric Filtering Methods

The authors implement their approach in CLP(FD) using the ECLiPSe language, introducing two primary geometric constraints: nocrossing and Convex Hull reasoning.

Avoiding Crossings

A known property of an optimal Euclidean TSP is that the path never crosses itself. The nocrossing constraint identifies and removes edges that would force such a crossing. To maintain efficiency, the authors developed an angle-based propagator that runs in $O(d)$ amortized time, where $d$ is the domain size.

Illustration of an edge crossing at point Q, which the nocrossing constraint aims to eliminate.

Convex Hull Reasoning

In an optimal ETSP, vertices on the convex hull must be visited in their cyclic order. Using Andrew’s monotone chain algorithm, the solver identifies the hull and applies pruning rules to ensure successors follow the hull's orientation or move to internal points. This logic is further extended to "internal hulls" for points nested within partial paths.

Experimental Evaluation

The algorithms were evaluated using TSPLIB instances, real-world city coordinates, and random point distributions. The results demonstrate that geometric filtering is a powerful tool for pruning the search space, particularly during the "proof of optimality" phase.

Performance comparison showing the number of solved instances over time for various filtering models.

As shown in the performance graph, the "Geometric" and "Geom.

  • BvHRRR" models solve significantly more instances within the 1800-second timeout than standard models. The addition of geometric filtering roughly halved the runtime compared to basic CP models and those using advanced Held-Karp pruning.

Conclusion

Geometric filtering provides a significant performance boost for ETSP in CLP by exploiting the physical structure defined by coordinates. While specialized solvers like Concorde remain faster for pure TSP, these geometric constraints offer a robust way to improve CP solvers, especially when side constraints are present. Future work includes extending these techniques to non-convex polygons and Vehicle Routing Problems (VRP).

Summary updated

BibTeX
@inproceedings{bertagnon2020improved,
  author = {Alessandro Bertagnon and Marco Gavanelli},
  title = {{Improved Filtering for the Euclidean Traveling Salesperson Problem in CLP(FD)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5498},
}
Figure