A Hybrid Algorithm for Traveling Salesman Problem in Road Network
Yu Li · Acta Geodaetica et Cartographica Sinica · 2014
Traveling salesman problem is a classic problem of network analysis.However,single heuristic algorithms have some drawbacks,such as high computational complexity,rigorous parameters,strong dependence on the initial value,which are difficult to quickly achieve global optimization.This paper designed and implemented a genetic tabu search algorithm combined with global optimization capability of genetic algorithm and the memory function of tabu search.In particularly,genetic mutation operator exploited the new search space and enhanced the probability of obtaining the global optimal solution.Tabu search avoided circuitous detection and reflected the strong ability of mountain climbing.Moreover,this paper evaluated the algorithm from accuracy,stability and efficiency using different scale of transportation network data.The results show that genetic-tabu search algorithm has higher accuracy which improves 9%than tabu search algorithm when the accuracy error is less than1%,and it can reduce the time consumption over 50% compared with genetic algorithm.