基于遗传算法的一类多旅行商问题研究  

Study on multiple traveling salesman problem based on genetic algorithm

作　　者：王海龙[1] 周辉仁[1] 魏颖辉[2] 

机构地区：[1]天津大学系统工程研究所,天津300072 [2]辽宁科技学院管理系,辽宁本溪117022

出　　处：《计算机应用》2009年第1期119-122,共4页journal of Computer Applications

摘　　要：旅行商问题是一个经典的NP完全问题,对多人旅行商问题的求解则更具有意义。以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准,而对所有旅行商路径最大值最小的多旅行商一类问题研究的相对较少。针对所有旅行商路径最大值最小的多旅行商一类问题,用遗传算法优化,并且提出了矩阵解码方法。该方法适于距离对称和非对称的多旅行商问题求解。以距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较。Traveling salesman problem is a classical complete nondeterministic polynomial problem. It is significant to solve Multiple Traveling Salesman Problems （MTSP）. Previous researches on multiple traveling salesman problem are mostly limited to the kind that employed total-path-shortest as the evaluating rule, but little notice is made on the kind that employed longest-path-shortest as the evaluating rule. In order to solve this problem, genetic algorithm was used to optimize it and decoding method with matrix was proposed. It is fit for solving symmetric and asymmetric MTSP. Symmetric and asymmetric multiple traveling salesman problems were simulated and different crossover operators were compared.

关 键 词：遗传算法 多旅行商问题 优化 解码方法 

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