Affiliations: [a]
Department of Environmental and Prevention Sciences, University of Ferrara, Ferrara, Italy
| [b]
Department of Engineering, University of Ferrara, Ferrara, Italy
Correspondence:
[*]
Corresponding author: Alessandro Bertagnon, Department of Environmental and Prevention Sciences, University of Ferrara, C.so Ercole I D’Este, 32 Ferrara, Italy. E-mail: [email protected].
Note: [1] This article is a revised and extended version of paper [6].
Abstract: The Traveling Salesperson Problem (TSP) is one of the best-known problems in computer science. Many instances and real world applications fall into the Euclidean TSP special case, in which each node is identified by its coordinates on the plane and the Euclidean distance is used as cost function. It is worth noting that in the Euclidean TSP more information is available than in the general case; in a previous publication, the use of geometric information has been exploited to speedup TSP solving for Constraint Logic Programming (CLP) solvers. In this work, we study the applicability of geometric reasoning to the Euclidean TSP in the context of an ASP computation. We compare experimentally a classical ASP approach to the TSP and the effect of the reasoning based on geometric properties. We also compare the speedup of the additional filtering based on geometric information on an ASP solver and a CLP on Finite Domain (CLP(FD)) solver.
Keywords: Answer set programming, euclidean traveling salesperson problem, experimental comparison of ASP and CLP(FD)
