考虑同时取送和时间窗的车辆路径及求解算法

doi:10.3778/j.issn.1002-8331.2205-0405

摘要/Abstract

摘要： 针对带时间窗的同时取送货车辆路径问题（vehicle routing problem with simultaneous pickup-delivery and time windows，VRPSPDTW），构建了以车辆使用成本、车辆行驶距离成本总支出最小化的路径优化数学模型，提出自适应头脑风暴算法（adaptive brain storm optimization，ABSO）进行求解。全局搜索阶段，采用多项惩罚方式扩大搜索区域，并使用聚类及三种路径搜索策略进行全局搜索；局部搜索阶段，将六种破坏-修复算子作为备选集合，进而设计自适应动态选择邻域搜索机制，增强局部搜索效能。选取测试数据集和实际案例对算法性能进行测试，实验结果表明针对小规模标准算例，所提算法全部取得了当前已知最优解；对于大规模标准算例，通过与遗传算法、并行模拟退火算法、离散布谷鸟算法对比，所提算法实验计算结果有7.52%~12.03%的提升；对于实际案例，所提算法在收敛速度和寻优能力方面均展示出优越性，充分验证了所提算法对解决VRPSPDTW问题的有效性。

关键词: 车辆路径问题, 同时取送货, 时间窗, 头脑风暴算法, 自适应大邻域搜索

Abstract: This paper proposes an adaptive brain storm optimization（ABSO） for the vehicle routing problem with simultaneous pickup-delivery and time windows（VRPSPDTW）, a path optimization mathematical model is constructed to minimize the total expenditure of vehicle use cost and vehicle travel distance cost. In the global search stage, expand the search area with multiple penalties, as well as use clustering and three path search strategies for global search. In the local search stage, ues six kinds of damage-repair operators as candidate sets, and then design an adaptive dynamic selection neighborhood search mechanism to enhance local search efficiency. Based on the standard test data set and practical cases, the experimental results show the ABSO algorithm can obtain all the currently known optimal solution for the small-scale standard test example. For the large-scale standard test example, compared with the genetic algorithm, parallel-simulated annealing algorithm, and discrete cuckoo search, the experimental calculation results of the algorithm in this paper have an improvement of 7.52%-12.03%. For practical cases, the proposed algorithm shows its superiority in terms of convergence speed and optimization ability. The experimental calculation results verify the effectiveness of the proposed ABSO algorithm to solve the VRPSPDTW.

Key words: vehicle routing problem, simultaneous pickup-delivery, time windows, brain storm optimization, adaptive large neighborhood search

刘建胜, 蔡祥, 黄纪绘, 熊君星. 考虑同时取送和时间窗的车辆路径及求解算法[J]. 计算机工程与应用, 2023, 59(16): 295-304.

LIU Jiansheng, CAI Xiang, HUANG Jihui, XIONG Junxing. Solution Algorithm for Vehicle Routing Problem Considering Simultaneous Pickup-Delivery and Time Windows[J]. Computer Engineering and Applications, 2023, 59(16): 295-304.

参考文献

[1] 江海，陈峰.面向快递同城运输的车辆路径问题研究[J].工业工程，2019，22（4）：58-63.
JIANG H，CHEN F.A study of vehicle routing problem for urban transport of express[J].Industrial Engineering Journal，2019，22（4）：58-63.
[2] ASGHARI M，AL-E S M J M.Green vehicle routing problem：a state-of-the-art review[J].International Journal of Production Economics，2021，231：107899.
[3] 付朝晖，刘长石.多物流中心共同配送的车辆路径问题研究[J].计算机工程与应用，2021，57（16）：291-298.
FU C H，LIU C C.Research on multi-depot vehicle routing problem based on joint distribution mode[J].Computer Engineering and Applications，2021，57（16）：291-298.
[4] ANGELELLI E，MANSINI R.The vehicle routing problem with time windows and simultaneous pick-up and delivery[M]//Quantitative approaches to distribution logistics and supply chain management.Berlin，Heidelberg：Springer，2002：249-267.
[5] WANG H F，CHEN Y Y.A genetic algorithm for the simultaneous delivery and pickup problems with time window[J].Computers & Industrial Engineering，2012，62（1）：84-95.
[6] WANG C，MU D，ZHAO F，et al.A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows[J].Computers & Industrial Engineering，2015，83：111-122.
[7] 王超，刘超，穆东，等.基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题[J].计算机集成制造系统，2018，24（3）：570-582.
WANG C，LIU C，MU D，et al.VRPSPDTW problem solving by discrete cuckoo search[J].Computer Integrated Manufacturing Systems，2018，24（3）：570-582.
[8] 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[J].IEEE Latin America Transactions，2018，16（6）：1732-1740.
[9] MA Y，LI Z，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[J].Soft Computing，2019，23（15）：6697-6714.
[10] LI H，WANG L，HEI X，et al.A decomposition-based chemical reaction optimization for multi-objective vehicle routing problem for simultaneous delivery and pickup with time windows[J].Memetic Computing，2018，10（1）：103-120.
[11] QIU M，FU Z，EGLESE R，et al.A tabu search algorithm for the vehicle routing problem with discrete split deliveries and pickups[J].Computers & Operations Research，2018，100：102-116.
[12] CASAZZA M，CESELLI A，CALVO R W.A route decomposition approach for the single commodity split pickup and split delivery vehicle routing problem[J].European Journal of Operational Research，2021，289（3）：897-911.
[13] PAUL A，KUMAR R S，ROUT C，et al.A bi-objective two-echelon pollution routing problem with simultaneous pickup and delivery under multiple time windows constraint[J].OPSEARCH，2021，58（4）：962-993.
[14] CHAIEB M，SASSI D B.Measuring and evaluating the home health care scheduling problem with simultaneous pick-up and delivery with time window using a tabu search metaheuristic solution[J].Applied Soft Computing，2021，113：107957.
[15] WANG Y，LI Q，GUAN X，et al.Collaborative multi-depot pickup and delivery vehicle routing problem with split loads and time windows[J].Knowledge-Based Systems，2021，231：107412.
[16] SHI Y.Brain storm optimization algorithm[C]//International Conference in Swarm Intelligence.Berlin，Heidelberg：Springer，2011：303-309.
[17] LI J Q，LI J K，ZHANG L J，et al.Solving type-2 fuzzy distributed hybrid flowshop scheduling using an improved brain storm optimization algorithm[J].International Journal of Fuzzy Systems，2021，23（4）：1194-1212.
[18] KUMAR T D，VENKATESAN P.Performance estimation of multicarrier CDMA using adaptive brain storm optimization for 5G communication system in frequency selective fading channel[J].Transactions on Emerging Telecommunications Technologies，2020，31（4）：e3829.
[19] 梁晓萍，郭振军，朱昌洪.基于头脑风暴优化算法的BP神经网络模糊图像复原[J].电子与信息学报，2019，41（12）：2980-2986.
ZHANG X P，GUO Z J，ZHU C H.BP neural network fuzzy image restoration based on brain storming optimization algorithm[J].Journal of Electronics & Information Technology，2019，41（12）：2980-2986.
[20] SONG M，LI J，HAN Y，et al.Solving the vehicle routing problem with time window by using an improved brain strom optimization[C]//2019 IEEE Congress on Evolutionary Computation，2019：1306-1313.
[21] LIU M，SHEN Y，ZHAO Q，et al.A hybrid BSO-ACS algorithm for vehicle routing problem with time windows on road networks[C]//2020 IEEE Congress on Evolutionary Computation，2020：1-8.
[22] DESAULNIERS G.Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows[J].Operations Research，2010，58（1）：179-192.
[23] 周蓉，沈维蕾.装卸一体化车辆路径问题的自适应并行遗传算法[J].中国机械工程，2018，29（22）：2740-2749.
ZHOU R，SHEN W L.An adaptive parallel genetic algorithm for VRPSPD[J].China Mechanical Engineering，2018，29（22）：2740-2749.
[24] XIA Y，FU Z.Improved tabu search algorithm for the open vehicle routing problem with soft time windows and satisfaction rate[J].Cluster Computing，2019，22（4）：8725-8733.