基于GA的最小旅行时间的多旅行商问题研究  

Study on minimum completion time multiple traveling salesman problem based on genetic algorithm

作　　者：周辉仁[1] 唐万生[1] 魏颖辉[2] 

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

出　　处：《计算机应用研究》2009年第7期2526-2529,共4页Application Research of Computers

基　　金：辽宁省教育厅科研课题资助项目(20060439)

摘　　要：以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准,而对最小完成时间的多旅行商一类问题研究得相对较少。针对所有旅行商最小完成时间的多旅行商一类问题,用遗传算法进行优化,且提出了矩阵解码方法。以距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较,适于距离对称和非对称的多旅行商问题求解。Previous research on multiple traveling salesman problems is 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-time-shortest as the evaluating rule. In order to solve this problem, used genetic algorithm to optimize it and proposed decoding method with matrix. This paper simulated symmetric and asymmetric multiple traveling salesman problems and compared different crossover operators. It is fit for solving symmetric and asymmetric multiple traveling salesman problems.

关 键 词：遗传算法 多旅行商问题 最小完成时间 解码方法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]