基于遗传算法的多人旅行商问题求解

作者：代坤; 鲁士文; 蒋祥刚

来源：计算机工程, 2004, (16): 139-140+145.

• 旅行商问题
• 遗传算法
• 路径规划 Travelling salesman problem
• Genetic algorithm
• Path planning

旅行商问题是一个经典的NP完全问题,多人旅行商问题的求解则更具挑战性。以往对求解多人旅行商问题的研究局限于以所有成员路径总和最小为优化标准,而对以所有成员路径最大值最小为优化标准的另一类多人旅行商问题却未加注意。文章给出了这两类多人旅行商问题的形式化描述,探讨了利用遗传算法求解这两类多人旅行商问题的基本思想和具体方案,进行了仿真实验验证。仿真实验数据表明,这是一种高效而且适应性强的多入旅行商问题求解方法。

• 单位
  中国科学院计算技术研究所; 中国科学院研究生院