基于点线回路优化求解TSP的一个新算法

作者：顾大权; 刘高飞; 袁珏; 侯太平; 汪晋

来源：解放军理工大学学报(自然科学版), 2010, (04): 423-427.

• 算法
• 旅行商问题
• 回路优化 algorithm
• TSP
• loop optimizing

快速有效地解决TSP问题,有着重要的理论价值和极高的实际应用价值。提出了基于点线回路优化求解TSP的算法,首先将原基本回路切去一些点(线段、路径)变成残缺回路,然后把切去的点(线段、路径)重新插入到残缺回路的所有节点之间,生成新的基本回路,切去点(线段、路径)的数量,从一个变到基本回路节点数的一半。算法实现容易、运行速度快,生成的结果接近其最优解。算法尽量避免了陷入局部极小,使得在短时间内能够求解较大规模的TSP问题。

• 单位
  中国人民解放军陆军工程大学