摘要
在数学推导和证明的基础上,给出了一个求解对称型TSP问题下界的快速算法,利用该算法求解了TSP标准问题库中部分对称型问题,给出了计算结果并与标准问题库中公布的最好解进行了比较,获得了令人满意的效果.
Based on mathematical inference and proof, we propose a quick algorithm for calculating the lower bound of symmetric Travelling Salesman Problem. By using the algorithm, series of numerical examples of TSP(traveling salesman problem) from TSBLIB are solved and the computational results are compared with the best-known solutions published, which give promising results.
出处
《系统工程理论与实践》
EI
CSCD
北大核心
2004年第12期84-88,99,共6页
Systems Engineering-Theory & Practice
基金
国家自然科学基金(70471065)
上海市教委重点学科建设资助项目
关键词
旅行商问题
下界
算法
逼近程度
TSP(traveling salesman problem)
lower bound
algorithm
approximation ratio
