基于GA的MTSP问题的研究  

Research on MTSP Based on Genetic Algorithm

作　　者：郭强[1] 迟洪钦[1] 

机构地区：[1]上海师范大学信息与机电工程学院,上海200234

出　　处：《计算机与数字工程》2010年第10期5-7,18,共4页Computer & Digital Engineering

基　　金：上海市教委项目(编号:0000004153.2)资助

摘　　要：目前对于旅行商问题的研究已经到了一个比较成熟的阶段,但是对于多旅行商问题的研究还相对较少。文章针对使所有旅行商路程尽可能平均(即所有旅行商路程的最大值最小),且所有旅行商的总路程最小的一类多旅行商问题进行研究,通过三交换启发式交叉算子,变换变异算子和矩阵解码方法来优化简单的遗传算法。最后通过仿真试验,验证了该算法的有效性和可行性。Nowadays,the research of the traveling salesman problem has reached a relatively mature stage,but the research of the multiple traveling salesman problem has little involved.It directed towards the problem of that,distance of all of the travers is averaged（in another word,all of the travers＇ longest distance is shortest）,and all of the travers＇ sum distance is shortest.In order to optimize the genetic algorithm,used three-exchange coressover heuristic operators,exchange mutation operators and decoding method with matrix.At the end,the experimental results simulated show that this algorithm is effective and feasible to solve MTSP.

关 键 词：遗传算法 多旅行商问题 变换变异算子 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]