帝国竞争算法求解CVRP  

Imperialist competitive algorithm for solving CVRP

作　　者：蔡延光[1] 王世豪 戚远航 王福杰 林卓胜 Cai Yanguang;Wang Shihao;Qi Yuanhang;Wang Fujie;Lin Zhuosheng(School of Automation,Guangdong University of Technology,Guangzhou 510006,China;School of Computer Science,Zhongshan Institute,University of Electronic Science&Technology of China,Zhongshan Guangdong 528402,China;School of Electrical Engineering&Intelligentization,Dongguan University of Technology,Dongguan Guangdong 523808,China;Faculty of Intelligent Manufacturing,Wuyi University,Jiangmen Guangdong 529020,China)

机构地区：[1]广东工业大学自动化学院,广州510006 [2]电子科技大学中山学院计算机学院,广东中山528402 [3]东莞理工学院电子工程与智能化学院,广东东莞523808 [4]五邑大学智能制造学部,广东江门529020

出　　处：《计算机应用研究》2021年第3期782-786,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61074147,61901304);广东省自然科学基金资助项目(S2011010005059,2019A1515010493,2016A030313018);广东省教育部产学研结合项目(2012B091000171,2011B090400460);广东省科技计划资助项目(2012B050600028,2014B010118004,2016A050502060);广州市花都区科技计划资助项目(HD14ZD001);广州市科技计划资助项目(201604016055);广州市天河区科技计划资助项目(2018CX005);广东省普通高校青年创新人才资助项目(2018KQNCX333,2018KQNCX252);中山市重大科技专项(2017A1024,2017SF0603,2016A1028);中山市科技计划重点项目(2018B1018)。

摘　　要：针对带容量约束的车辆路径问题(CVRP),提出了一种带分裂机制的帝国竞争算法进行求解。首先,结合CVRP的特性,采用基于贪婪准则的编解码策略实现算法空间到解空间的转换。其次,提出帝国分裂策略来增强算法的全局搜索能力,并结合2-Opt提高算法的局部搜索能力。最后,通过25个基准算例的仿真实验表明:所提算法能有效求解CVRP,所有算例的优化误差不超过1.0%;与已有的帝国竞争算法、粒子群算法、遗传算法、布谷鸟搜索算法相比,所提算法的求解效率更高。For the capacitated vehicle routing problem(CVRP),this paper proposed an imperialist competitive algorithm which integrated a split mechanism to solve the problem.Firstly,combined with the characteristics of CVRP,this algorithm used the encoding and decoding strategies based on greedy criteria to switch from the algorithm space to the solution space.Secondly,this algorithm presented an imperialist splitting mechanism to improve the global search ability of the algorithm,and simultaneously combined with the 2-Opt algorithm to enhance the local search ability.Finally,the results of simulation experiments with 25 benchmark examples indicate that:the proposed algorithm can effectively solve CVRP,and the optimization errors of all examples are less than 1.0%.Furthermore,the proposed algorithm is more efficiently than the existing imperialist competitive algorithms,particle swarm optimization algorithm,genetic algorithm and cuckoo search algorithm.

关 键 词：车辆路径问题 帝国竞争算法 粒子群算法 遗传算法 2-Opt 

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