TY - JOUR
AU - Bertagnon, Alessandro
AU - Gavanelli, Marco
PY - 2020/04/03
Y2 - 2024/07/19
TI - Improved Filtering for the Euclidean Traveling Salesperson Problem in CLP(FD)
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 34
IS - 02
SE - AAAI Technical Track: Constraint Satisfaction and Optimization
DO - 10.1609/aaai.v34i02.5498
UR - https://ojs.aaai.org/index.php/AAAI/article/view/5498
SP - 1412-1419
AB - <p>The Traveling Salesperson Problem (TSP) is one of the best-known problems in computer science. The Euclidean TSP is a special case in which each node is identified by its coordinates on the plane and the Euclidean distance is used as cost function.</p><p>Many works in the Constraint Programming (CP) literature addressed the TSP, and use as benchmark Euclidean instances; however the usual approach is to build a distance matrix from the points coordinates, and then address the problem as a TSP, disregarding the information carried by the points coordinates for constraint propagation.</p><p>In this work, we propose to use geometric information, present in Euclidean TSP instances, to improve the filtering power. In order to have a declarative approach, we implemented the filtering algorithms in Constraint Logic Programming on Finite Domains (CLP(FD)).</p>
ER -