面向多起点均衡多旅行商问题的进化算法  

Improved evolutionary algorithm for balanced multiple traveling salesmen problem with multiple starting points

作　　者：孙冰 王川[2] 杨强 刘晓芳 毛文涛[1] SUN Bing;WANG Chuan;YANG Qiang;LIU Xiao-fang;MAO Wen-tao(College of Computer and Information Engineering,Henan Normal University,Xinxiang 453007,China;College of Software,Henan Normal University,Xinxiang 453007,China;College of Artificial Intelligence,Nanjing University of Information Science and Technology,Nanjing 210044,China;College of Artificial Intelligence,Nankai University,Tianjin 300071,China)

机构地区：[1]河南师范大学计算机与信息工程学院,河南新乡453007 [2]河南师范大学软件学院,河南新乡453007 [3]南京信息工程大学人工智能学院,江苏南京210044 [4]南开大学人工智能学院,天津300071

出　　处：《计算机工程与设计》2023年第7期2030-2038,共9页Computer Engineering and Design

基　　金：国家自然科学基金青年基金项目(62006124);江苏省自然科学基金青年基金项目(BK20200811);江苏省高等学校自然科学研究面向基金项目(20KJB520006)。

摘　　要：为解决多起点均衡多旅行商问题,分析问题的特点,从优化旅行商的起点、最小化所有旅行商总路程和维持各旅行商路径均衡的角度出发,提出一种基于改进交叉、变异操作的遗传算法。根据均衡多旅行商问题的优化目标,构建新型评价函数,设计双染色体编码方式。在此基础上,引入改进的三交换启发式交叉操作并设计双变异策略。在经典旅行商问题的测试集TSPLIB上,与其它求解多旅行商问题的进化算法进行对比,验证算法的有效性。To solve the balanced multiple traveling salesmen problem with multiple starting points,the particularities of the problem were analyzed in terms of optimizing the starting point of salesmen,minimizing the total distance and maintaining the routes balance.A genetic algorithm based on improved crossover and mutation operations was proposed.According to the optimization objectives,a novel evaluation function was constructed and a two-chromosome encoding approach was designed.An evaluation function was constructed according to the optimization objective of the equilibrium multi-traveler problem,and a two-chromosome encoding scheme was designed.An improved three-swap heuristic crossover operation was introduced and a dual variation strategy was designed.The effectiveness of the algorithm was verified by comparison with other evolutionary algorithms on the TSPLIB test set.

关 键 词：遗传算法 均衡多旅行商问题 旅行商问题 进化算法 多目标 优化 变异策略 

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