一种改进的求解TSP问题的近似算法

摘要

旅行商问题(TSP)是典型的具有NPC复杂性的组合优化问题.在现有求解TSP问题的2-近似算法closest-point算法基础上,通过对插入点的插入位置进行改进,提出了一种有效的近似算法最近点前后插入法(CPBOA),并采用TSPLIB中的一些典型实例对该算法进行了测试,同时与典型的常数近似比算法MST-PRIM算法和closest-point算法进行了比较.实验结果表明,该算法在求解质量上与closest-point和MST-PRIM算法相比都有很大的改进,而且速度也很快.