互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

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


□ 王海龙 周辉仁 郑丕谔 唐万生

  (天津大学 系统工程研究所 天津 300072)
  
  摘 要:针对所有旅行商路径总和最小为优化标准的多旅行商一类问题,用遗传算法优化,并提出了矩阵解码方法。对距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较。结果表明,该算法是有效的,适用于距离对称和非对称的多旅行商问题求解。
  关键词:遗传算法; 多旅行商问题; 优化; 解码方法
  中图分类号:TP301.6; TP18文献标志码:A
  文章编号:1001-3695(2009)05-1726-03
  
  Study on multiple traveling salesman problem based on genetic algorithm
  WANG Hailong ZHOU Huiren ZHENG Pie TANG Wansheng
  (Institute of Systems Engineering Tianjin University Tianjin 300072 China)
  Abstract:In order to solve MTSP(multiple traveling salesman problem) that employed totalpathshortest as the evaluating rule this paper used genetic algorithmto optimize it and proposed decoding method with matrix. Simulated asymmetric multiple traveling salesman problems using the different crossover operators. The results suggest that this method is efficient. It is fit for solving symmetric and asymmetric multiple traveling salesman problems.
  Key words:genetic algorithm; multiple traveling salesman problem; optimization; decoding method
  
  0 引言
  
  旅行商问题(traveling salesman problem TSP)是一个典型的组合优化难题,它在许多领域都有着广泛的应用,已被证明属于NP问题[1]。TSP是指:有N个城市,要求旅行商到达每个城市各一次且仅一次,并回到起点,且要求旅行路线最短。而多旅行商问题(MTSP)是指M个旅行商从同一个城市(或不同城市)出发,分别走一条旅行路线,使得每个城市有且仅有一个旅行商经过(出发城市除外)且总路程最短。有关TSP的研究在现实问题中有很大的使用价值,交通运输、管道敷设、路线的选择、计算机网络的拓扑设计、邮递员送信等均可抽象成TSP或MTSP[2~5]。 ......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017