基于离散海鸥算法求解循环取货车辆路径问题

吉林大学学报(信息科学版) ›› 2023, Vol. 41 ›› Issue (3): 493-502.

基于离散海鸥算法求解循环取货车辆路径问题

张强¹, 韩利婷¹, 姜慧清¹, 朱必磊¹, 魏永和²

1. 东北石油大学计算机与信息技术学院, 黑龙江大庆 163318; 2. 国家电网冀北电力有限公司管理培训中心, 北京 100000

收稿日期:2022-06-02 出版日期:2023-06-08 发布日期:2023-06-14
作者简介:张强(1982— ), 男, 黑龙江大庆人, 东北石油大学教授, 博士, 主要从事智能进化算法和神经网络研究, ( Tel) 86-13796989561(E-mail)dqpi_zq@ 163. com。
基金资助:
国家自然科学基金资助项目(61702093); 黑龙江省自然科学基金资助项目( F2018003); 黑龙江省博士后专项经费资助项目(LBH-Q20077)

Solving Vehicle Routing Problem of Milk-Run Based on Discrete Seagull Algorithm

ZHANG Qiang¹, HAN Liting¹, JIANG Huiqing¹, ZHU Bilei¹, WEI Yonghe²

1. School of Computer and Information Technology, Northeast Petroleum University, Daqing 163318, China; 2. Management Training Center, Chinses Grid Hebei Electric Power Company Limited, Beijing 100000, China

Received:2022-06-02 Online:2023-06-08 Published:2023-06-14

摘要/Abstract

摘要： 针对如何降低循环取货车辆路径问题(VRP: Vehicle Routing Problem)中的运输成本, 提出一种离散海鸥算法。首先, 在海鸥迁移过程中, 采用 insert、 reverse 操作更新海鸥位置加快算法寻优速度; 其次, 在海鸥攻击过程中, 采用 swap、 3-opt操作更新海鸥位置提升算法局部搜索能力; 最后, 结合模拟退火算法避免算法在运行过程中陷入局部最优, 重新定义了在离散的车辆路径问题下的更新策略。以总成本最低为目标函数, 构建相应的数学模型。实验结果表明, 该算法具有高效解决循环取货车辆路径问题的能力, 寻优效果及求解质量均高于标准海鸥优化算法、粒子群算法、模拟退火算法、灰狼优化算法、鲸鱼算法和飞蛾扑火算法。

关键词: 离散海鸥算法; , 循环取货; , 车辆路径问题; , 优化算法

Abstract: To reduce the transportation cost in the VRP (Vehicle Routing Problem) of milk-run, a discrete seagull algorithm is proposed. Firstly, in the process of seagull migration, insert and reverse operations are used to update the seagull position to improve the algorithm's search speed. Secondly, swap and 3-opt operations are used to update the seagull position to improve the algorithm's local search capability. Finally, combined with simulated annealing algorithm, the phenomenon of landing on local optimum is prevented during the operation of the algorithm, the update strategy is redefined under the discrete vehicle routing problem. With the lowest total cost as the objective function, the corresponding mathematical model is constructed. Experiment results show that the algorithm is able to efficaciously deal with the vehicle routing problem of milk-run, the finding effect and solution quality are better than the standard seagull optimization algorithm, particle swarm algorithm, simulated annealing, gray wolf optimization, whale optimization algorithm, and moth-flame optimization.

Key words: discrete seagull algorithm; , milk-run; , vehicle routing problem; , optimization algorithm

中图分类号:

TP18

张强, 韩利婷, 姜慧清, 朱必磊, 魏永和. 基于离散海鸥算法求解循环取货车辆路径问题[J]. 吉林大学学报(信息科学版), 2023, 41(3): 493-502.

ZHANG Qiang, HAN Liting, JIANG Huiqing, ZHU Bilei, WEI Yonghe. Solving Vehicle Routing Problem of Milk-Run Based on Discrete Seagull Algorithm[J]. Journal of Jilin University (Information Science Edition), 2023, 41(3): 493-502.

[1]	张勇, 韦焱文, 王明吉 , 路敬祎 , 邢鹏飞 , 周兴达. 基于 CEEMDAN-LZC 和 SOA-ELM 的管道信号识别[J]. 吉林大学学报(信息科学版), 2023, 41(2): 193-201.
[2]	杨华民 , 于志 , 底晓强 , 梁钟予 , 张兴旭 . 基于学生行为数据的学生心理健康状态预测[J]. 吉林大学学报(信息科学版), 2022, 40(5): 819-828.
[3]	蔡娣 , 路阳 , 林立媛 , 杜娇娇 , 管闯. 基于稀疏自编码和 SPSO-SVM 的稻瘟病早期病害识别[J]. 吉林大学学报(信息科学版), 2022, 40(3): 416-423.
[4]	曹广华, 陈前, 齐少栓, 闫丽梅. 基于 EEMD-SSA 组合模型的短期电力负荷预测[J]. 吉林大学学报(信息科学版), 2022, 40(3): 362-370.
[5]	张铁晟, 张凤武, 张明毅. 基于 LGWO 和扰动观察复合算法的 MPPT 研究[J]. 吉林大学学报(信息科学版), 2022, 40(3): 379-386.
[6]	洪涛, 张富强. 基于端对端最优功率的成套连采系统设计[J]. 吉林大学学报(信息科学版), 2021, 39(6): 675-681.
[7]	李占山, 杨鑫凯, 胡彪, 张博. 差分进化樽海鞘群特征选择算法[J]. 吉林大学学报(信息科学版), 2021, 39(1): 1-7.
[8]	张超, 侯男, 路敬祎, 王闯. 改进的 PSO-VMD 算法及其在管道泄漏检测中的应用[J]. 吉林大学学报(信息科学版), 2021, 39(1): 28-36.
[9]	石彤, 李盼池. 量子教学优化算法及在函数优化中的应用[J]. 吉林大学学报(信息科学版), 2020, 38(5): 578-587.
[10]	李学贵, 郭远涛, 李盼池, 王艾. 基于改进涡流搜索算法的支持向量机分类模型[J]. 吉林大学学报(信息科学版), 2020, 38(3): 312-319.
[11]	赵航, 岳晓峰, 方博, 袁晓磊, 马国元, 郭宋吾铭. 基于PSO-GA-BP神经网络的视觉伺服控制系统[J]. 吉林大学学报(信息科学版), 2020, 38(2): 172-178.
[12]	刘苗 , 姚荣 , 钟晓曦 , 孙振兴 . 基于禁忌搜索的认知无线电性能优化算法[J]. 吉林大学学报(信息科学版), 2020, 38(2): 142-147.
[13]	任伟建, 高梦宇, 高铭泽, 张鹏, 刘丹. 基于混合算法的点云配准方法研究[J]. 吉林大学学报(信息科学版), 2019, 37(4): 408-416.
[14]	康朝海, 王思琪, 任伟建, 王博宇. 基于高斯学习多峰延迟粒子群优化算法[J]. 吉林大学学报(信息科学版), 2019, 37(4): 399-407.
[15]	王雪,王秋爽 . 基于混合优化算法的医学图像配准技术[J]. 吉林大学学报(信息科学版), 2016, 34(5): 703-708.