Title :
Exact Heuristic Algorithm for Traveling Salesman Problem
Author :
Lin, Dongmei ; Wu, Xiangbin ; Wang, Dong
Author_Institution :
Center of Inf. & Educ. Technol., Foshan Univ., Foshan
Abstract :
Natural properties of stochastic searching strategies and operations in metaheuristic algorithms have important influence on convergence performance of various metaheuristic algorithms. Through similarity analysis to two kinds of metaheuristic algorithms, exact heuristic algorithm based on branch-and-cut is put forward according to change trend of similarity between two arbitrary high-quality solutions. In the meanwhile, two conditions were given in this paper because efficiency of branch-and-cut algorithm is closely allied to complexity of solved object. New heuristic algorithm can help metaheuristic algorithms finding superior solutions than other heuristic algorithms, and accelerate metaheuristic algorithms convergence. Simulation experiments show that new heuristic algorithm is efficacious.
Keywords :
combinatorial mathematics; optimisation; stochastic processes; tree searching; branch-and-cut algorithm; metaheuristic algorithm; similarity analysis; stochastic search strategy; traveling salesman problem; Acceleration; Algorithm design and analysis; Computational modeling; Computer science education; Educational institutions; Educational technology; Heuristic algorithms; Iterative algorithms; Stochastic processes; Traveling salesman problems; branch-and-cut; exact algorithm; heuristic algorithm; local search algorithm; traveling salesman problem;
Conference_Titel :
Young Computer Scientists, 2008. ICYCS 2008. The 9th International Conference for
Conference_Location :
Hunan
Print_ISBN :
978-0-7695-3398-8
Electronic_ISBN :
978-0-7695-3398-8
DOI :
10.1109/ICYCS.2008.43