高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于离散鲸鱼群算法的物资应急调度研究

蒋华伟 郭陶 杨震 赵丽科

蒋华伟, 郭陶, 杨震, 赵丽科. 基于离散鲸鱼群算法的物资应急调度研究[J]. 电子与信息学报, 2022, 44(4): 1484-1494. doi: 10.11999/JEIT210173
引用本文: 蒋华伟, 郭陶, 杨震, 赵丽科. 基于离散鲸鱼群算法的物资应急调度研究[J]. 电子与信息学报, 2022, 44(4): 1484-1494. doi: 10.11999/JEIT210173
JIANG Huawei, GUO Tao, YANG Zhen, ZHAO Like. Research on Material Emergency Scheduling Based on Discrete Whale Swarm Algorithm[J]. Journal of Electronics & Information Technology, 2022, 44(4): 1484-1494. doi: 10.11999/JEIT210173
Citation: JIANG Huawei, GUO Tao, YANG Zhen, ZHAO Like. Research on Material Emergency Scheduling Based on Discrete Whale Swarm Algorithm[J]. Journal of Electronics & Information Technology, 2022, 44(4): 1484-1494. doi: 10.11999/JEIT210173

基于离散鲸鱼群算法的物资应急调度研究

doi: 10.11999/JEIT210173
基金项目: 国家自然科学基金(51677055),河南省自然科学基金(162300410055),河南省科技攻关项目(212102210499),河南省高等学校重点科研项目(22A520003)
详细信息
    作者简介:

    蒋华伟:男,1970年生,教授,博士生导师,研究方向为优化计算、机器学习等

    郭陶:女,1996年生,硕士生,研究方向为车辆路径优化

    杨震:男,1990年生,讲师,博士,研究方向为图像处理与信息分析等

    赵丽科:女,1990年生,讲师,博士,研究方向为智能遥感影像处理

    通讯作者:

    郭陶 2237247390@qq.com

  • 中图分类号: TN911.7; P399

Research on Material Emergency Scheduling Based on Discrete Whale Swarm Algorithm

Funds: The National Natural Science Foundation of China (51677055), The Natural Science Foundation of Henan Province (162300410055), The Science and Technology Research Project of Henan Province (212102210499), The Key Scientific Research Projects of Colleges and Universities in Henan Province (22A520003)
  • 摘要: 针对鲸鱼群算法求解多配送中心带时间窗的物资应急调度问题时存在的易陷入局部极值等缺点,该文提出一种改进离散鲸鱼群算法(IDWSA)。首先采用混合初始化策略提高初始种群的质量;然后构建以相似配送顺序和相同配送中心为比较项的两种移动规则,并设计自适应柯西变异算子和路径选择策略对个体进行移动;最后构造全局评价函数用于选择个体以维持种群多样性。在Solomon标准测试集上,IDWSA所求最好解的距离与MAPSO, GA, HACO, ABC相比分别减少了2.25%, 13.4%, 6%, 1.46%,有效缩短了车辆的行驶距离。
  • 图  1  MESPMDCTW问题的有向图表示

    图  2  3层编码示例

    图  3  混合初始化策略

    图  4  个体移动规则

    图  5  基于相似配送顺序的个体移动示例

    图  6  不同种群规模和不同迭代次数下所求最好解

    图  7  不同迭代次数和不同种群规模下的求解时间

    图  8  不同迭代次数下种群多样性

    图  9  5种算法实验结果对比

    表  1  路径选择策略

     输入:路径权值矩阵W,未被访问受灾点集合S
     输出:可行路径L
     (1) p=0,L=[0]
     (2) while len(S)!=0
     (3)   max=W[p][0], max_index=0
     (4)   for i=1 to len(S) do
     (5)     if max<W[p][i] then
     (6)       max=W[p][i], max_index=i
     (7)     end if
     (8)   end for
     (9) L.append(max_index)
     (10) S.remove(max_index)
     (11) end while
    下载: 导出CSV

    表  2  数据集配送中心信息

    位置配送中心
    123
    x153553
    y306028
    下载: 导出CSV

    表  3  评价指标及含义

    评价指标含义
    最好解/车辆数不同求解次数中求得的车辆行驶路径的最短总距离/当前解的所用总车辆数
    最差解/车辆数不同求解次数中求得的车辆行驶路径的最长总距离/当前解的所用总车辆数
    种群平均解/车辆数当前种群中所有个体表示的车辆行驶距离的平均值/当前种群所有解的平均总车辆数
    平均最好解所有实验中最好解的平均值
    平均最差解所有实验中最差解的平均值
    平均解所有实验中所求平均解的平均值
    平均偏差(平均解–最好解)/最好解
    最大偏差(最差解–最好解)/最好解
    运算时间每一次实验所耗费的时间
    平均运算时间所有实验次数下算法的平均运行时间
    下载: 导出CSV

    表  4  不同参数下算法所求解的质量

    种群大小迭代次数平均最好解(km)平均最差解(km)平均解(km)
    20101966.82231.42011.35
    151902.62092.21944.6
    2018542051.21907.68
    25162720221890.43
    30152018781692.96
    35157919271743.6
    301018812051.21907.68
    151752.712239.71869.97
    201621.318551655.52
    251501.62001.951713.41
    301496.21956.171709.3
    3514992016.51756.9
    4010189520891965.34
    151723.12003.61867.6
    20168919291735.55
    251534.22009.61796.5
    301571.62011.21801.26
    351509.321967.511839.3
    下载: 导出CSV

    表  5  3种种群初始化方式结果对比

    混合初始化策略DFC随机生成
    初始种群种群多样性0.1050.090.12
    平均最好解(km)21722333.552959.36
    平均最差解(km)3703.132685.353643.74
    平均解(km)3069.482526.383407.23
    最终解种群多样性0.03190.026430.02943
    平均最好解(km)15201794.952171.68
    平均最差解(km)18781911.772461.23
    平均解(km)1692.961809.342296.54
    下载: 导出CSV

    表  6  两种函数求得可行解

    全局评价函数适应度函数
    最好解/车辆数1477/91576/9
    最差解/车辆数1868/101927/11
    种群平均解/车辆1672.96/101743.6/10
    最大偏差0.260.22
    平均偏差0.130.10
    平均运算时间46.1646.31
    下载: 导出CSV
  • [1] ZHOU Lei, WU Xianhua, XU Zeshui, et al. Emergency decision making for natural disasters: An overview[J]. International Journal of Disaster Risk Reduction, 2018, 27: 567–576. doi: 10.1016/j.ijdrr.2017.09.037
    [2] DANTZIG G B and RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80–91. doi: 10.1287/mnsc.6.1.80
    [3] DORLING K, HEINRICHS J, MESSIER G G, et al. Vehicle routing problems for drone delivery[J]. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2017, 47(1): 70–85. doi: 10.1109/TSMC.2016.2582745
    [4] PARADISO R, ROBERTI R, LAGANÁ D, et al. An exact solution framework for multitrip vehicle-routing problems with time windows[J]. Operations Research, 2020, 68(1): 180–198. doi: 10.1287/opre.2019.1874
    [5] MUNARI P, MORENO A, DE LA VEGA J, et al. The robust vehicle routing problem with time windows: Compact formulation and branch-price-and-cut method[J]. Transportation Science, 2019, 53(4): 1043–1066. doi: 10.1287/trsc.2018.0886
    [6] 刘长石, 申立智, 盛虎宜, 等. 考虑交通拥堵规避的低碳时变车辆路径问题研究[J]. 控制与决策, 2020, 35(10): 2486–2496. doi: 10.13195/j.kzyjc.2019.0257

    LIU Changshi, SHEN Lizhi, SHENG Huyi, et al. Research on low-carbon time-dependent vehicle routing problem with traffic congestion avoidance approaches[J]. Control and Decision, 2020, 35(10): 2486–2496. doi: 10.13195/j.kzyjc.2019.0257
    [7] 张景玲, 刘金龙, 赵燕伟, 等. 时间依赖型同时取送货VRP及超启发式算法[J]. 计算机集成制造系统, 2020, 26(7): 1905–1917. doi: 10.13196/j.cims.2020.07.019

    ZHANG Jingling, LIU Jinlong, ZHAO Yanwei, et al. Time dependent simultaneous delivery VRP and super heuristic algorithm[J]. Computer Integrated Manufacturing Systems, 2020, 26(7): 1905–1917. doi: 10.13196/j.cims.2020.07.019
    [8] MARINAKIS Y, MARINAKI M, and MIGDALAS A. A multi- adaptive particle swarm optimization for the vehicle routing problem with time windows[J]. Information Sciences, 2019, 481: 311–329. doi: 10.1016/j.ins.2018.12.086
    [9] RAMACHANDRANPILLAI R and AROCK M. Spiking neural firefly optimization scheme for the capacitated dynamic vehicle routing problem with time windows[J]. Neural Computing and Applications, 2021, 33(1): 409–432. doi: 10.1007/s00521-020-04983-8
    [10] LAHYANI R, GOUGUENHEIM A L, and COELHO L C. A hybrid adaptive large neighbourhood search for multi-depot open vehicle routing problems[J]. International Journal of Production Research, 2019, 57(22): 6963–6976. doi: 10.1080/00207543.2019.1572929
    [11] 胡蓉, 李洋, 钱斌, 等. 结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题[J/OL]. 自动化学报. http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190872, 2020.

    HU Rong, LI Yang, QIAN bin, et al. Enhanced ant colony algorithm combined with clustering decomposition for solving complex green vehicle routing problem[J/OL]. Acta Automatica Sinica. http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190872, 2020.
    [12] ZHANG Zizhen, QIN Hu, and LI Yanzhi. Multi-objective optimization for the vehicle routing problem with outsourcing and profit balancing[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 21(5): 1987–2001. doi: 10.1109/TITS.2019.2910274
    [13] LONG Jianyu, SUN Zhenzhong, PARDALOS P M, et al. A hybrid multi-objective genetic local search algorithm for the prize-collecting vehicle routing problem[J]. Information Sciences, 2019, 478: 40–61. doi: 10.1016/j.ins.2018.11.006
    [14] 骆剑平, 李霞, 陈泯融. 基于改进混合蛙跳算法的CVRP求解[J]. 电子与信息学报, 2011, 33(2): 429–434. doi: 10.3724/SP.J.1146.2010.00328

    LUO Jianping, LI Xia, and CHEN Minrong. Improved shuffled frog leaping algorithm for solving CVRP[J]. Journal of Electronics &Information Technology, 2011, 33(2): 429–434. doi: 10.3724/SP.J.1146.2010.00328
    [15] 李国明, 李军华. 基于混合禁忌搜索算法的随机车辆路径问题[J]. 控制与决策, 2021, 36(9): 2161–2169. doi: 10.13195/j.kzyjc.2020.0107

    LI Guoming and LI Junhua. Stochastic vehicle routing problem based on hybrid tabu search algorithm[J]. Control and Decision, 2021, 36(9): 2161–2169. doi: 10.13195/j.kzyjc.2020.0107
    [16] XIANG Xiaoshu, TIAN Ye, ZHANG Xingyi, et al. A pairwise proximity learning-based ant colony algorithm for dynamic vehicle routing problems[J]. IEEE Transactions on Intelligent Transportation Systems, To be published. doi: 10.1109/TITS.2021.3052834.
    [17] SOLOMON M M. VRPTW benchmark problems[EB/OL]. http://w.cba.neu.edu/~msolomon/problems.htm, 2003.
    [18] ZENG Bing, GAO Liang, and LI Xinyu. Whale swarm algorithm for function optimization[C]. Proceedings of the 13th International Conference on Intelligent Computing Theories and Application, Liverpool, United Kingdom, 2017: 624–639. doi: 10.1007/978-3-319-63309-1_55.
    [19] PEZZELLA F, MORGANTI G, and CIASCHETTI G. A genetic algorithm for the flexible job-shop scheduling problem[J]. Computers & Operations Research, 2008, 35(10): 3202–3212. doi: 10.1016/j.cor.2007.02.014
    [20] GAO Kaizhou, SUGANTHAN P N, PAN Quanke, et al. An improved artificial bee colony algorithm for flexible job-shop scheduling problem with fuzzy processing time[J]. Expert Systems with Applications, 2016, 65: 52–67. doi: 10.1016/j.eswa.2016.07.046
    [21] 张国辉, 高亮, 李培根, 等. 改进遗传算法求解柔性作业车间调度问题[J]. 机械工程学报, 2009, 45(7): 145–151. doi: 10.3901/JME.2009.07.145

    ZHANG Guohui, GAO Liang, LI Peigen, et al. Improved genetic algorithm for the flexible job-shop scheduling problem[J]. Journal of Mechanical Engineering, 2009, 45(7): 145–151. doi: 10.3901/JME.2009.07.145
    [22] WANG Kangzhou, LAN Shulin, and ZHAO Yingxue. A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service[J]. Journal of the Operational Research Society, 2017, 68(11): 1409–1421. doi: 10.1057/s41274-016-0170-7
    [23] ZHANG Huizhen, ZHANG Qinwan, MA Liang, et al. A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows[J]. Information Sciences, 2019, 490: 166–190. doi: 10.1016/j.ins.2019.03.070
    [24] GU Zhaoquan, ZHU Yan, WANG Yuexuan, et al. Applying artificial bee colony algorithm to the multidepot vehicle routing problem[J]. Software: Practice and Experience, 2020. doi: 10.1002/spe.2838.
  • 加载中
图(9) / 表(6)
计量
  • 文章访问数:  741
  • HTML全文浏览量:  262
  • PDF下载量:  70
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-02-25
  • 修回日期:  2021-11-01
  • 录用日期:  2021-11-05
  • 网络出版日期:  2021-11-13
  • 刊出日期:  2022-04-18

目录

    /

    返回文章
    返回