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

Genetic Algorithm Based Solution of Multiple Travelling Salesman Problem

作　　者：代坤[1] 鲁士文[2] 蒋祥刚[3] 

机构地区：[1]中国科学院研究生院信息学院,北京100080 [2]中国科学院计算技术研究所,北京100080 [3]华东计算技术研究所,上海200233

出　　处：《计算机工程》2004年第16期139-140,145,共3页Computer Engineering

基　　金：国防预研项目

摘　　要：旅行商问题是一个经典的NP完全问题,多人旅行商问题的求解则更具挑战性。以往对求解多人旅行商问题的研究局限于以所有成员路径总和最小为优化标准,而对以所有成员路径最大值最小为优化标准的另一类多人旅行商问题却未加注意。文章给出了这两类多人旅行商问题的形式化描述,探讨了利用遗传算法求解这两类多人旅行商问题的基本思想和具体方案,进行了仿真实验验证。仿真实验数据表明,这是一种高效而且适应性强的多入旅行商问题求解方法。Previous researches on multiple travelling salesman problem are mostly limited to the kind that employed total-path-shortest as the evaluating rule, but little notice is paid on the kind that employed longest-path-shortest as the evaluating rule. The formalized models of the two kinds of multiple travelling salesman problem are presented in this paper, and the main idea and specific way of applying genetic algorithm in solving the two kinds of travelling salesman problem arc also discussed , the simulation is made at the end. As the simulation result shows, it is an effective and robust way of solving travelling salesman problem.

关 键 词：旅行商问题 遗传算法 路径规划 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]