非完全图TSP问题研究

摘要：

指出了TSP问题是一种具有代表性的组合优化问题,在现实生活中有着广泛的应用.不同于完全图,非完全图TSP问题中存在着某些节点之间没有路径直接相连,使得处于该节点位置时,其路径选择受到一定限制.受运筹学中大M法思想的启发,提出了通过引入一个非常大的正数(即大M)来表示此类节点间的距离,从而将非完全图TSP问题转化成完全图TSP问题,降低了问题求解的难度,并且验证了该方法的有效性.

关键词：TSP问题、非完全图、大M法、仿真

分类号：F57(城市交通运输经济)

资助基金：重庆工程职业技术学院院级课题编号 :RWB201504;重庆市高等教育学会高等教育科学研究课题编号 :CQGJ15387C;重庆市教育评估研究会立项课题编号 :PJY2015 -50

在线出版日期：2016-05-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：182-184