TY - GEN
T1 - Solving TSP by dismantling cross paths
AU - Pan, Yongsheng
AU - Xia, Yong
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/11/12
Y1 - 2014/11/12
N2 - Traveling salesman Problem (TSP) is a classical NP-hard problem and has been extensively studied in literature. Eliminating the cross paths, which commonly exist in approximate solutions to large scale TSP, can effectively improve the quality of the solutions. Through studying the impact of cross paths on the cost of a loop, in this paper we develop a method to detect and dismantle cross paths, and thus propose a novel greedy algorithm-based approach to the TSP. This approach has been evaluated on ten TSP data sets and compared to three classical optimization techniques, including the elastic network, ant colony algorithm and genetic algorithm. Our results show that the proposed approach can get approximate solution of high quality with far less computational cost and has an excellent performance in solving large-scale TSP.
AB - Traveling salesman Problem (TSP) is a classical NP-hard problem and has been extensively studied in literature. Eliminating the cross paths, which commonly exist in approximate solutions to large scale TSP, can effectively improve the quality of the solutions. Through studying the impact of cross paths on the cost of a loop, in this paper we develop a method to detect and dismantle cross paths, and thus propose a novel greedy algorithm-based approach to the TSP. This approach has been evaluated on ten TSP data sets and compared to three classical optimization techniques, including the elastic network, ant colony algorithm and genetic algorithm. Our results show that the proposed approach can get approximate solution of high quality with far less computational cost and has an excellent performance in solving large-scale TSP.
KW - cross paths
KW - greedy algorithm
KW - optimization
KW - Traveling salesman problem
UR - http://www.scopus.com/inward/record.url?scp=84916238840&partnerID=8YFLogxK
U2 - 10.1109/ICOT.2014.6956614
DO - 10.1109/ICOT.2014.6956614
M3 - 会议稿件
AN - SCOPUS:84916238840
T3 - IEEE International Conference on Orange Technologies, ICOT 2014
SP - 121
EP - 124
BT - IEEE International Conference on Orange Technologies, ICOT 2014
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2014 IEEE International Conference on Orange Technologies, ICOT 2014
Y2 - 20 September 2014 through 23 September 2014
ER -