A Heuristic Algorithm to Eliminate Edges for TSP
Wang Yong, Geng Chang Xin, W. Wen · Frontiers in artificial intelligence and applications · 2018
A heuristic algorithm is provided to trim many edges for reducing the search space of traveling salesman problem (TSP). The heuristic algorithm is designed according to a probability model and the fuzzy numbers plays an important role to enhance the performance. The heuristic algorithm may lose a few edges in some optimal solutions if the parameter N is too small or F is too big in the algorithm. Since we are not sure whether all optimal solutions in the original graph are trimmed, the best and worst solutions in the preserved graphs are not proven. The experimental results demonstrate that the heuristic algorithm computes a residual graph with less than nlog2n edges for most of the TSP instances in the TSPLIB. Thus, the computation times of algorithms for TSP will be greatly reduced when these TSP instances on sparse graphs are resolved.