求解带容量约束车辆路径问题的离散布谷鸟算法.pdf

东 北 石 油 大 学 学 报 第45卷 第1期 2021年2月
JOURNAL OF NORTHEAST PETROLEUM UNIVERSITY Vol 45 No 1 Feb 2021
DOI10 3969/jissn2095—41072021 01 010
求解带容量约束车辆路径问题的离散布谷鸟算法
向明尚，张强
(东北石油大学计算机与信息技术学院，黑龙江大庆163318 )
摘 要：提出一种离散布谷鸟算法(DCA)求解带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem) °
该算法采用轮盘赌机制增强初始解选择的随机性，对基本布谷鸟算法的莱维飞行操作中，使用2—opt法和exchange法
进行位置更新；在寄生巢位置更新中，使用shitt法和reverse法增强最优解的局部幵发能力。选取augerat标准数据集测
试算法，并比较BA、ACO、SA及PSO算法结果°实验结果表明：离散布谷鸟算法能够有效解决带容量约束车辆路径问
题，有较强的寻优能力，求解质量优于其他4种对比算法°
关 键 词：离散布谷鸟算法；容量约束；车辆路径；轮盘赌机制；2—opt法
中图分类号:TP301 文献标识码:A 文章编号： 2095 - 4107(2021)01 -0095 - 07
0引言
带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem, CVRP)［1］是物流研究领域中一
个具有很高的实际应用和理论研究价值的问题。为求解有容量车辆路径问题，减少陷入局部最优的情况,
张景玲等⑵提出一种基于强化学习的超启发算法；黄戈文等旧提出一种采用灰狼空间整数编码和先路由
后分组解决方案生成策略的自适应遗传灰狼优化算法，用于求解带容量约束的车辆路径问题;何国强等⑷
采用传统遗传算法求解带容量约束的车辆路径问题,存在早熟收敛 、易陷入局部最优等问题，设计双种群
混合遗传算法进行求解；为解决带容量约束的车辆路径问题，李阳等5提出一种混合变邻域生物共栖搜索
算法进行求解。
布谷鸟算法(Cuckoo Algorithm,CA)是一种模拟布谷鸟寄生育雏行为的仿生优化算法6 °近年来，
人们把布谷鸟搜索算法应用到实际工程优化问题中。对制造型企业生