Solving travelling salesman problems with an intelligent search approach

This paper presents a solution approach for addressing travelling salesman problems by applying an admissible heuristic search algorithm called Search and Learning A* algorithm. The heuristic evaluation function of this algorithm considers both local distance information and global estimated distance. The heuristic learning mechanism allows the algorithm to update the heuristic estimates of visited states and hence modify the tour configuration along the search process. The search engine of the algorithm incorporates Delaunay triangulation of computation geometry as part of the search strategy. The Delaunay triangulation identifies only the promising cities for a given state, it helps improve the search efficiency by reducing the search space.