第
38
卷第
2
期
计算机应用研究
Vol. 38 No. 2
录用定稿
Application Research of Computers Accepted Paper
——————————
收稿日期：
2020-01-22
；修回日期：
2020-04-08
基金项目：国家自然科学基金项目
(61074147
，
61901304)
；广东省自然科学基金项目
(S2011010005059
，
2019A1515010493
，
2016A030313018)
；广东省教育部产学研结合项目
(2012B091000171
，
2011B090400460)
；广东省科技计划项目
(2012B050600028
，
2014B010118004
，
2016A050502060)
；广州市花都区科技计划项目
(HD14ZD001)
；广州市科技计划项目
(201604016055)
；广州市天河区科技计划项目
(2018CX005)
；广东省普通高校青年创新人才项目
(2018KQNCX333
，
2018KQNCX252)
；中山市重大科技专项
(2017A1024
，
2017SF0603
，
2016A1028)
；中
山市科技计划重点项目
(2018B1018)
作者简介：蔡延光
(1963-)
，男，湖北咸宁人，教授，博导，博士，主要研究方向为网络控制与优化、组合优化、智能优化、智能交通系统；王世豪
(1996-)
，男，湖南郴州人，硕士研究生，主要研究方向为智能优化、机器学习；戚远航
(1993-)
，男
(
通信作者
)
，广东湛江人，讲师，硕导，博士，主要研
究方向为复杂系统建模与优化、智能优化、运输调度优化、布局优化、运筹学
(qiyuanhang77@163.com)
．
帝国竞争算法求解
CVRP
*
蔡延光
1
，王世豪
1
，戚远航
2
†
，王福杰
3
，林卓胜
4
(1.
广东工业大学
自动化学院
,
广州
510006; 2.
电子科技大学中山学院
计算机学院
,
广东
中山
528402; 3.
东莞
理工学院
电子工程与智能化学院
,
广东
东莞
523808; 4.
五邑大学
智能制造学部
,
广东
江门
529020)
摘 要：针对带容量约束的车辆路径问题
(CVRP)
，提出了一种带分裂机制的帝国竞争算法进行求解。首先，结合
CVRP
的特性，采用基于贪婪准则的编解码策略实现算法空间到解空间的转换。其次，提出帝国分裂策略来增强算
法的全局搜索能力，并结合
2-Opt
提高算法的局部搜索能力。最后，通过
25
个基准算例的仿真实验表明：所提出的
算法能有效求解
CVRP
，所有算例的优化误差不超过
1.0%
；与已有的帝国竞争算法、粒子群算法、遗传算法、布谷
鸟搜索算法相比，所提出算法的求解效率更高。
关键词：车辆路径问题；帝国竞争算法；粒子群算法；遗传算法；
2-Opt
中图分类号：
TP301
doi: 10.19734/j.issn.1001-3695.2020.01.0006
Imperialist competitive algorithm for solving CVRP
Cai Yanguang
1
, Wang Shihao
1
, Qi Yuanhang
2†
, Wang Fujie
3
, Lin Zhuosheng
4
(1. School of Automation, Guangdong University of Technology, Guangzhou Guangdong 510006, China; 2. School of
Computer Science, University of Electronic Science & Technology of China, Zhongshan Institute, Zhongshan Guangdong
528402, China; 3. School of Electrical Engineering & Intelligentization, Dongguan University of Technology, Dongguan
Guangdong 523808, China; 4. Faculty of Intelligent Manufacturing, Wuyi University, Jiangmen Guangdong 529020, China)
Abstract:
For the capacitated vehicle routing problem (CVRP) , this paper proposed an imperialist competitive algorithm
which integrates 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 presents more efficiently than the
other existing imperialist competitive algorithms, particle swarm optimization algorithm, genetic algorithm and cuckoo search
algorithm.
Key words:
vehicle routing problem; imperialist competitive algorithm; particle swarm optimization; genetic algorithm;
2-Opt
0
引言
车辆路径问题
(vehicle routing problem
，
VRP)
[1]
是
1956
年
由
Dantzig
和
Ramser
[2]
首次提出，已被证明是
NP-hard
问题，
该问题一直是计算机科学与组合优化领域学者们关注和研究
的热点问题。带容量约束的车辆路径问题
(capacitated vehicle
routing problem
，
CVRP)
[3~5]
是
VRP
的基本问题，与实际生活
中资源配送和路径规划息息相关，主要解决当多配送车辆服
务多个客户点，且配送车辆具有容量限制时，如何规划配送
车辆的配送路径使得总服务成本最低的问题。因为精确求解
算法无法满足性能要求，所以学者们常常使用启发式算法等
近似求解算法进行求解。
Akhand
等人
[6]
针对
CVRP
问题比较
了多种路线优化方法，发现使用粒子群优化算法进行路线优
化，能够提供更好的解决方案。为了进一步提高求解精度，
Foysal
等人
[7]
提出基于双层局部搜索的粒子群优化算法。在
双层本地搜索中，本地搜索的一层适用于所有迭代中的整个
种群，而另一层仅应用于不同代生成的最佳粒子池。因此，
该算法能在较短优化时间内得到较优求解。
Stanley
等人
[8]
设
计了二进制编码方法的遗传算法求解
CVRP
问题，为遗传算
法求解
CVRP
问题提供了思路。为了减少优化耗时，姜昌华
等人
[9]
针对提出一种结合
2-Opt
局部优化的混合遗传算法，
增强算法的局部搜索能力和收敛速度。
Jon
等人
[10]
通过将布
谷鸟搜索算法结合
2-Opt
算法和双桥运算，为解决
CVRP
问
题提供了新的思路。
帝国竞争算法
(imperialist competitive algorithm
，
ICA)
是
2007
年由
Atashpaz-Gargari
等人
[11]
提出，具有收敛速度快和
全局搜索能力强的特点。
ICA
已被应用于求解旅行商问题
(traveling salesman problem
，
TSP)
[12, 13]
。张鑫龙等人
[14]
提出
一种新型
ICA
求解
TSP
问题，帝国同化采用替换重建方式，
革命过程结合自适应算子，得到了较好的优化效果；裴小兵
网络首发时间：2020-07-06 13:57:05
网络首发地址：https://kns.cnki.net/kcms/detail/51.1196.TP.20200706.1050.005.html
评论0