Discrete Grey Wolf Optimization Algorithm for VRPSPDTW Problem
CSTR:
Author:
  • Article
  • | |
  • Metrics
  • |
  • Reference [22]
  • | | | |
  • Comments
    Abstract:

    In this study, a mathematical model aiming at minimizing the total distribution distance is established for the vehicle routing problem of simultaneous delivery and pickup with time window constraints. According to the characteristics of the model, a discrete grey wolf optimization (DGWO) algorithm is proposed to solve the problem on the basis of preserving the search mechanism of the grey wolf optimization (GWO) algorithm. Multiple strategies are adopted to construct the initial solution of the population, and the unfeasible solution is allowed to expand the search area of the population; the neighborhood search strategy with scoring strategy is introduced to adjust the probability of each operator so that the algorithm can select the operator with better optimization effect; the deletion-insertion mechanism is used to explore the high-quality solution region and accelerate the convergence of the population. The standard data set is tested in the simulation experiment, and the experimental results are compared with the p-SA algorithm, DCS algorithm, VNS-BSTS algorithm, and SA-ALNS algorithm. The experiment shows that the DGWO algorithm can effectively solve the vehicle routing problem of simultaneous delivery and pickup with time window constraints.

    Reference
    [1] Zhang SQ, Mu D, Wang C. A solution for the full-load collection vehicle routing problem with multiple trips and demands: An application in Beijing. IEEE Access, 2020, 8: 89381-89394.
    [2] Pureza V, Morabito R, Reimann M. Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW. European Journal of Operational Research, 2012, 218(3): 636-647. [doi: 10.1016/j.ejor.2011.12.005
    [3] Alyasiry AM, Forbes M, Bulmer M. An exact algorithm for the pickup and delivery problem with time windows and last-in-first-out loading. Transportation Science, 2019, 53(6): 1695-1705. [doi: 10.1287/trsc.2019.0905
    [4] Angelelli E, Mansini R. The vehicle routing problem with time windows and simultaneous pick-up and delivery. In: Klose A, Speranza MG, Wassenhove LN, eds. Quantitative Approaches to Distribution Logistics and Supply Chain Management. Berlin Heidelberg: Springer , 2002. 249-267.
    [5] Bettinelli A, Cacchiani V, Crainic TG, et al. A branch-and-cut-and-price algorithm for the multi-trip separate pickup and delivery problem with time windows at customers and facilities. European Journal of Operational Research, 2019, 279(3): 824-839. [doi: 10.1016/j.ejor.2019.06.032
    [6] Sitek P, Wikarek J, Rutczyńska-Wdowiak K, et al. Optimization of capacitated vehicle routing problem with alternative delivery, pick-up and time windows: A modified hybrid approach. Neurocomputing, 2021, 423: 670-678. [doi: 10.1016/j.neucom.2020.02.126
    [7] 张九龙, 王晓峰, 芦磊, 等. 若干新型智能优化算法对比分析研究. 计算机科学与探索, 2022, 16(1): 88-105
    [8] 钟倩漪, 钱谦, 伏云发, 等. 粒子群优化算法在关联规则挖掘中的研究综述. 计算机科学与探索, 2021, 15(5): 777-793
    [9] 李丹. 改进群智能优化算法的海上物流配送路径优化方法. 舰船科学技术, 2020, 42(16): 184-186
    [10] Wang HF, Chen YY. A genetic algorithm for the simultaneous delivery and pickup problems with time window. Computers & Industrial Engineering, 2012, 62(1): 84-95
    [11] 黄务兰, 张涛. 基于改进全局人工鱼群算法的VRPSPDTW研究. 计算机工程与应用, 2016, 52(21): 21-29
    [12] 王超, 刘超, 穆东, 等. 基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题. 计算机集成制造系统, 2018, 24(3): 570-582
    [13] Belgin O, Karaoglan I, Altiparmak F. Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Computers & Industrial Engineering, 2018, 115: 1-16
    [14] Lagos C, Guerrero G, Cabrera E, et al. An improved particle swarm optimization algorithm for the VRP with simultaneous pickup and delivery and time windows. IEEE Latin America Transactions, 2018, 16(6): 1732-1740. [doi: 10.1109/TLA.2018.8444393
    [15] Wang Y, Li Q, Guan XY, et al. Collaborative multi-depot pickup and delivery vehicle routing problem with split loads and time windows. Knowledge-based Systems, 2021, 231: 107412. [doi: 10.1016/j.knosys.2021.107412
    [16] Mirjalili S, Mirjalili SM, Lewis A. Grey wolf optimizer. Advances in Engineering Software, 2014, 69: 46-61. [doi: 10.1016/j.advengsoft.2013.12.007
    [17] 黄戈文, 蔡延光, 戚远航, 等. 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题. 电子学报, 2019, 47(12): 2602-2610
    [18] 姜天华. 混合灰狼优化算法求解柔性作业车间调度问题. 控制与决策, 2018, 33(3): 503-508
    [19] 顾九春, 姜天华, 朱惠琦. 多目标离散灰狼优化算法求解作业车间节能调度问题. 计算机集成制造系统, 2021, 27(8): 2295-2306
    [20] Della Croce F, Tadei R, Volta G. A genetic algorithm for the job shop problem. Computers & Operations Research, 1995, 22(1): 15-24
    [21] Ma YF, Li ZM, Yan F, et al. A hybrid priority-based genetic algorithm for simultaneous pickup and delivery problems in reverse logistics with time windows and multiple decision-makers. Soft Computing, 2019, 23(15): 6697-6714. [doi: 10.1007/s00500-019-03754-5
    [22] Shi Y, Zhou YJ, Boudouh T, et al. A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup-delivery and time window. Engineering Applications of Artificial Intelligence, 2020, 95: 103901. [doi: 10.1016/j.engappai.2020.103901
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

陈凯,邓志良,龚毅光.离散灰狼优化算法求解VRPSPDTW问题.计算机系统应用,2023,32(11):83-94

Copy
Share
Article Metrics
  • Abstract:529
  • PDF: 1712
  • HTML: 1035
  • Cited by: 0
History
  • Received:May 09,2023
  • Revised:June 06,2023
  • Online: September 19,2023
Article QR Code
You are the first990394Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063