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

Hybrid Algorithm for Colored Bottleneck Traveling Salesman Problem

作　　者：董学士[1] 董文永[1] 蔡永乐[1] Dong Xueshi;Dong Wenyong;Cai Yongle(Computer School,Wuhan University,Wuhan 430072)

机构地区：[1]武汉大学计算机学院,武汉430072

出　　处：《计算机研究与发展》2018年第11期2372-2385,共14页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(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问题的求解质量要优于对比算法.Based on colored traveling salesman problem(CTSP),this paper gives a more widely applicable combination optimization problem(COP)model named colored bottleneck traveling salesman problem(CBTSP),which can be used to model the planning problems with the partially overlapped workspace such as the route planning of persons and vehicles with cooperative and independent tasks.The objective function of these problems is different from the one of traveling salesman problems(TSPs),therefore it can t be modeled by CTSP.Since CBTSP is NP-hard problem,for this kind of large scale problem,nature-inspired algorithms are good choice for solving it.Based on these,the paper proposes a nature-inspired algorithm to solve CBTSP,and the new algorithm named PSGA is a hybrid algorithm of particle swarm optimization(PSO),simulated annealing(SA)and genetic algorithm(GA)based on IT process.PSGA firstly uses dual-chromosome coding to generate solution of CBTSP,and then updates the solution by using the crossover operator of GA.During this process,the length of crossover is controlled by the activity intensity,which is affected by the particle radius and environment temperature.In order to test the effectiveness of PSGA algorithm,the paper makes experiments by using small scale to large scale CBTSP data,and the extensive experiments show that PSGA can demonstrate better solution quality than the compared algorithms.

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

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