Solving traveling salesman problems with heuristic learning approach

This research studies the feasibility of applying heuristic learning algorithm in artificial intelligence to address the traveling salesman problem. The research focuses on tour construction and seeks to overcome the weakness of traditional tour construction heuristics, which are of greedy and myopic nature. The advantage of tour construction heuristic is its simplicity in concept. However, the greedy and myopic nature of tour construction heuristic result in a sub-optimal solution, and the tour needs to be improved with much effort after it is built. The improvement is made using tour improvement heuristics, which improves tour by changing the tour configuration until a better solution is found. Traditional tour construction heuristics were not designed to modify the configuration of the tour, which is an important feature in tour improvement heuristics, during the tour construction process. This research investigates the application of a real time admissible heuristic learning algorithm that allows the tour configuration to change as the tour is built. The heuristic evaluation function of the algorithm considers both local and global estimated distance information. The search engine of the algorithm incorporates Delaunay triangulations of computational geometry as part of the search strategy. This helps to improve the search efficiency because computational geometry provides information about the geometric properties of nodes distributed in Euclidean plane, so that only promising nodes that are likely to be in the optimal tour are considered during the search process. A state space transformation process that defines state, state transition operator and state transition cost has been developed. The heuristic estimation of a state is computed using minimal spanning tree, and the set of relevant states for consideration at each state selection is identified through the application of Delaunay triangulations. Computational results show that the geometric distribution of nodes in the Euclidean plane influences the heuristic estimation, because it influences the computation of minimal spanning tree. Problems that exhibit distinct and well-separated clusters are advantageous to this approach because it is capable of producing good quality heuristic estimate. A restrictive search approach that could further reduce the search space of the heuristic learning algorithm has also been investigated. It is based on the characteristics of optimal tour in which nodes located on the convex hull are visited in the order in which they appear on the convex hull boundary. Using this characteristic together with the proximity concept of Voronoi diagram in computational geometry, some of the nodes that are unlikely to travel in the same direction as the optimal tour can be pruned. This approach could identify promising candidate edge set using only edges from one triangle selected from Delaunay triangulations, and the triangle is selected based on the direction the tour travels. The examples used in this research show that the saving in heuristic updates can be quite significant