一个求解旅行商问题的松弛算法

• 作者: 董传波
• 来源期刊: 山东科学
• 学科: 数学
• 关键词: 旅行商问题 子回路消除约束 松弛方法 线性整数规划
• 年，卷（期）: 2019,（4）
• 所属期刊栏目: 交通运输
• 页码范围: 74-79
• 页数: 6页
• 分类号: O221.4
• 字数: 3117字
• 语种: 中文
• DOI: 10.3976/j.issn.1002-4026.2019.04.010

摘要

在旅行商问题(TSP)的传统模型中,子回路消除约束的数量随着问题规模的增大具有指数增长的特性,极大地限制了TSP的求解效率.基于TSP的松弛问题,本文提出一种有效生成子回路消除约束的方法.该方法通过求解一系列线性整数规划,来实现TSP的精确快速求解.数值结果表明,本方法相比于采用Cplex直接求解,能够更快地找到TSP的最优解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	董传波		1	0	0.0	0.0