一种多染色体遗传算法解决多旅行商问题  

Multi-chromosome Genetic Algorithm for Multiple Traveling Salesman Problem

作　　者：叶多福 刘刚 何兵 Ye Duofu;Liu Gang;He Bing(Rocket Force University of Engineering,Xi'an 710025,China)

机构地区：[1]火箭军工程大学

出　　处：《系统仿真学报》2019年第1期36-42,共7页Journal of System Simulation

基　　金：国家自然科学基金(61403399)

摘　　要：建立带时间窗口的多旅行商问题模型,设计旅行商数量和旅行时间总和主次两个目标函数,设计一种多染色体编码的编码方式,开发复杂突变算子树进化操作,克服了传统遗传算法搜索空间大的问题。仿真比较了算法的性能,仿真结果表明带复杂突变树的多染色体遗传算法均衡了旅行商数量与旅行时间总和两个目标函数,提高了算法的运行速度,减少旅行时间总和15.8%。A multi-traveling salesman model with time window is established,and two objective functions for the number of traveling salesmen and the sum of travel time are designed.A multi-chromosome coding method is designed to develop complex mutation operator tree,which overcomes the problem of large searching space of traditional genetic algorithms.The performances of algorithms are compared by simulation,and the simulation results show that the genetic algorithm with complex multi-chromosome mutation tree can balance the two objective functions of the number of TSP and total travel time well,improve the algorithm of travel speed,and reduce the total travel time by 15.8%.

关 键 词：多旅行商问题 时间窗口 编码 多染色体遗传算法 突变算子树 

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