混合算法求解着色瓶颈旅行商问题

作     者：董学士 董文永 蔡永乐 Dong Xueshi;Dong Wenyong;Cai Yongle

作者机构：武汉大学计算机学院武汉430072 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2018年第55卷第11期

页      面：2372-2385页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 0839[工学-网络空间安全] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金项目(61672024 61170305)~~ 

主　　题：混合算法 遗传算法 着色瓶颈旅行商问题 着色旅行商问题 瓶颈旅行商问题 

摘      要：基于着色旅行商问题(colored traveling salesman problem,CTSP),给出了一种适用性更加宽泛的组合优化问题模型:着色瓶颈旅行商问题(colored bottleneck traveling salesman problem,CBTSP).CBTSP可建模含有部分重合工作区域的规划问题,譬如有合作任务和单独任务的人员与车辆的路线规划,此类问题由于目标函数与旅行商问题不一样,因此不能够用CTSP模型来建模.由于CBTSP属于NP难问题,对于规模大的此类问题,自然启发式算法是个合适的选择.基于此,提出了一种自然启发式算法求解CBTSP,该算法是基于伊藤过程的粒子群算法(particle swarm optimization,PSO)、模拟退火算法(simulated annealing,SA)和遗传算法(genetic algorithm,GA)的混合算法(PSGA).PSGA首先用二重染色体编码来构建问题的解,然后运用遗传算法的交叉操作进行更新,其中交叉长度由伊藤过程的活动强度来控制,而活动强度由粒子半径和环境温度来决定.为了充分验证算法的有效性,使用小尺度到大尺度不同规模的数据进行实验,通过广泛的实验与分析表明:PSGA求解CBTSP问题的求解质量要优于对比算法.