Title :
TSP problem based on dynamic environment
Author :
Yan, Xue-song ; Zhou, Ai-min ; Kang, Li-shan ; Chen, Yu-ping
Author_Institution :
State Key Lab. of Software Eng., Wuhan Univ., China
Abstract :
Many real world optimization problems are related with time and some of them can be modeled by the Dynamic TSP(DTSP). A DTSP is harder than a general TSP, which is a NP-hard problem, because the city number of the DTSP is time varying. We have first given a mathematical model for DTSP. Then we have discussed the GT algorithm which is a algorithm solve static TSP problem. Based on GT algorithm, we have proposed an evolutionary algorithm, which can solve DTSP problem, given its details, analyzed its character and have given a graph of CHN144+1 problem. In the end, we have given the research area in future.
Keywords :
computational complexity; evolutionary computation; graph theory; travelling salesman problems; GaoTao algorithm; NP-hard problem; dynamic TSP; evolutionary algorithm; genetic algorithm; graph theory; mathematical model; optimization problems; Algorithm design and analysis; Cities and towns; Computer science; Evolutionary computation; Geology; Heuristic algorithms; Laboratories; Mathematical model; NP-hard problem; Software engineering;
Conference_Titel :
Intelligent Control and Automation, 2004. WCICA 2004. Fifth World Congress on
Print_ISBN :
0-7803-8273-0
DOI :
10.1109/WCICA.2004.1341994
