| 一个求解旅行商问题的松弛算法 |
| |
| 引用本文： | 董传波. 一个求解旅行商问题的松弛算法[J]. 山东科学, 2019, 32(4): 74-79. DOI: 10.3976/j.issn.1002-4026.2019.04.010 |
| |
| 作者姓名： | 董传波 |
| |
| 作者单位： | 中国航空油料集团有限公司,北京 100088 |
| |
| 基金项目： | 中国航油科技项目基金（2017081501） |
| |
| 摘 要： | 在旅行商问题（TSP）的传统模型中,子回路消除约束的数量随着问题规模的增大具有指数增长的特性,极大地限制了TSP的求解效率。基于TSP的松弛问题,本文提出一种有效生成子回路消除约束的方法。该方法通过求解一系列线性整数规划,来实现TSP的精确快速求解。数值结果表明,本方法相比于采用Cplex直接求解,能够更快地找到TSP的最优解。
|
| 关 键 词： | 旅行商问题 子回路消除约束 松弛方法 线性整数规划 |
| 收稿时间： | 2019-03-15 |
A relaxation algorithm for solving the traveling salesman problem |
| |
| DONG Chuan-bo. A relaxation algorithm for solving the traveling salesman problem[J]. Shandong Science, 2019, 32(4): 74-79. DOI: 10.3976/j.issn.1002-4026.2019.04.010 |
| |
| Authors: | DONG Chuan-bo |
| |
| Affiliation: | China National Aviation Fuel Group Limited,Beijing 100088,China |
| |
| Abstract: | In the traditional traveling salesman problem (TSP) models,the number of sub-tour elimination constraints exponentially increases with an increase in the size of the problem,which considerably limits the efficiency of solving the TSP.Based on the TSP relaxation problems,a method has been proposed in this study to effectively generate sub-tour elimination constraints.Further,the proposed method achieves an accurate and quick solution of TSP by solving the linear integer programming series.The numerical results denote that when compared with the Cplex direct solution,the proposed method can obtain the optimal solution of TSP more rapidly. |
| |
| Keywords: | traveling salesman problem sub-tour elimination constraints relaxation method linear integer programming |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《山东科学》浏览原始摘要信息 |
|
点击此处可从《山东科学》下载全文 |
|
