求解车辆路径问题的量子差分进化算法

发布时间：2021-06-29 19:43

　　基于量子差分进化算法在解决组合优化问题时表现出的计算效率及优化性能方面的优势,提出应用量子差分进化算法求解车辆路径问题,将量子比特解码为表示顾客顺序的实数量子染色体,设计了基于量子比特概率幅的差分交叉和变异算子以保持种群多样性,构建了动态量子旋转门进行变领域搜索,提出应用贪婪准则进行量子更新选择,将设计的算法应用于典型车辆路径问题,求解结果表明算法具有较好的鲁棒性,与标准CVRP算例的对比结果表明笔者算法是求解中、小型规模算例的一个有效算法。 

【文章来源】：浙江工业大学学报. 2020,48(01)北大核心

【文章页数】：6 页

【部分图文】：

2-Opt操作过程示意图

图3是P-n20-k2求解迭代过程与量子进化算法及差分进化算法的比较,图中实线为量子差分进化算法,虚线为量子进化算法,点线为差分进化算法。由图3可知:进化前期,3 种算法均能实现快速优化,相对而言,差分进化算法在进化前期的进化速度最快,但随着进化代数的增加,差分进化算法的搜索性能下降,最终的收敛解最差;量子进化算法的前期搜索效果较好,随着迭代次数的增加,其进化速度变慢;而量子差分进化算法结合其他两种算法的优点,在搜索后期持续优化,搜索到更好的解。因此,相对量子进化算法及差分进化算法,笔者算法在求解VRP问题时具有更强的全局搜索能力。4 结 论

若l满足式(4)载重要求,则将其放入该车中,将l移出待配送顾客集,否则计算其他未配送顾客与i的距离,按式(9)依次选择,若没有顾客能放入该车辆,则建立一个新的车辆群重复前面的过程,直到所有顾客都分配车辆,图1为某一解码后的结果,图1表示15 个顾客的配送方案。由图1可知:该方案需要两辆车,第一辆车的配送顺序为“配送中心0-6-2-9-4-11-13-配送中心”,第二辆车为“配送中心-5-1-3-7-8-10-12-14-15-配送中心”。2.2 量子变异

【参考文献】：
期刊论文
[1]考虑碳排放的选址-路径问题研究[J]. 赵燕伟,钱振宇,张景玲,张春苗.  浙江工业大学学报. 2018(05)
[2]基于化学反应优化算法的车辆路径问题[J]. 蒋海青,赵燕伟,冷龙龙.  计算机集成制造系统. 2018(08)
[3]求解CVRP问题的改进和声算法[J]. 颜腾威,王丽侠,周杰,王基一.  计算机技术与发展. 2016(09)
[4]基于分解的多目标量子差分进化算法[J]. 常新功,刘文娟,吕亚丽.  计算机应用与软件. 2016(08)
[5]多车型同时取送货问题的低碳路径研究[J]. 赵燕伟,李文,张景玲,任设东.  浙江工业大学学报. 2015(01)
[6]量子差分进化算法及在函数极值优化中的应用研究[J]. 张晓雷.  自动化技术与应用. 2014(08)
[7]求解车辆路径问题的人工蜂群算法[J]. 王志刚,夏慧明.  计算机工程与科学. 2014(06)
[8]一种实数编码的量子差分进化算法[J]. 陈晓峰,杨广明,黄明.  小型微型计算机系统. 2013(05)
[9]基于车辆共享的软时间窗动态需求车辆路径问题[J]. 王万良,黄海鹏,赵燕伟,张景玲.  计算机集成制造系统. 2011(05)
[10]基于混合禁忌搜索算法的动态车辆路径研究[J]. 陈晓眯,孟志青,徐杰.  浙江工业大学学报. 2009(05)

硕士论文
[1]基于混合量子进化算法的随机车辆路径问题的研究[D]. 李川.浙江工业大学 2012



本文编号：3257045