求解多旅行商问题的新混合遗传算法:以应急物资配送为例  

New Hybrid Genetic Algorithm for Solving the Multiple Traveling Salesman Problem:An Example of Distribution of Emergence Materials

作　　者：刘明[1] 张培勇[1] 

机构地区：[1]南京理工大学经济管理学院,南京210094

出　　处：《系统管理学报》2014年第2期247-254,共8页Journal of Systems & Management

基　　金：教育部人文社科项目(11YJCZH109);南京理工大学自主科研专项计划项目(2011YBXM96);(2011XQTR10);南京理工大学经管青年教师研究基金资助项目(AE88072;JGQN1102)

摘　　要：为优化生物反恐条件下的应急物资配送过程,将该环境下的应急物资配送问题构造为一多旅行商问题(MTSP),并从理论上分析了该旅行商回路为最短Hamilton路径。以此问题为背景,针对应用传统遗传算法求解多旅行商问题时存在收敛速度缓慢等问题,提出并设计了一类新的混合遗传算法。该类新遗传算法与传统遗传算法的最主要区别在于,针对多旅行商问题专门设计了一种新的染色体编码规则、排序算子和交叉算子。仿真结果表明,该算法能够快速收敛到问题的近似最优解,并能很好地维持种群的多样性。To optimize emergence materials distribution in anti-bioterrorism system, we formulate the problem as a multiple traveling salesman problem （MTSP）. We then analyze such traveling route and prove that it is the optimal Hamilton route theoretically. We propose and design a new hybrid genetic algorithm to overcome the shortcoming of slow convergence when traditional GA is applied for MTSP. The main contribution for the new method is a special rule of coding, new order function and new crossover function. Numerical simulation shows that this algorithm can rapidly converge to the optimal solution and can maintain diversity of population.

关 键 词：多旅行商问题 混合遗传算法 应急配送 生物反恐 

分 类 号：N945.15[自然科学总论—系统科学]