Vehicle Routing Problem of Simultaneous Pickup-Delivery with Time Windows Based on Multi-depot Joint Distribution Mode

CAI Xiang; GAO Bo; ZHU Zhiqiang; LIU Jiansheng

doi:10.19554/j.cnki.1001-3563.2025.11.025

PDF(1852 KB)

Packaging Engineering ›› 2025, Vol. 46 ›› Issue (11) : 229-242. DOI: 10.19554/j.cnki.1001-3563.2025.11.025

Automatic and Intelligent Technology

Vehicle Routing Problem of Simultaneous Pickup-Delivery with Time Windows Based on Multi-depot Joint Distribution Mode

CAI Xiang, GAO Bo, ZHU Zhiqiang, LIU Jiansheng

Author information +

History +

Abstract

In order to cope with the pressure and challenge brought to logistics and distribution enterprises due to construction of complete supply chain in major manufacturing centers, the work aims to study the vehicle routing problem of simultaneous pickup-delivery with time windows based on multi-depot joint distribution mode. Firstly, with the minimum total cost as the optimization objective, a mathematical optimization model considering multiple costs was established, and the variable firefly algorithm was proposed to solve the problem. Secondly, to solve the problems such as uneven initial population distribution and large dependence on step parameters of firefly algorithm, Lévy flight random disturbance mechanism was introduced to intervene and expand the search space of the algorithm. The random expansion factor strategy was proposed to increase the moving step of firefly position update, avoid the phenomenon of population concentration, break the population constraint, and improve the distribution of population in the algorithm search space. Finally, three sets of experiments were conducted to verify the effectiveness of the proposed model and algorithm. The proposed algorithm was superior to the comparison algorithm in terms of both solution quality and solution speed. The differences and advantages between the multi-depot joint distribution and the traditional distribution mode were analyzed and compared, and the superiority and universality of the model and algorithm proposed in this work were further verified. The research results can provide theoretical basis and decision reference for vehicle routing problem under multi-depot joint distribution mode.

Key words

multi-depot joint distribution / simultaneous pickup and delivery / time windows / firefly algorithm / variable neighborhood search

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

CAI Xiang, GAO Bo, ZHU Zhiqiang, LIU Jiansheng. Vehicle Routing Problem of Simultaneous Pickup-Delivery with Time Windows Based on Multi-depot Joint Distribution Mode[J]. Packaging Engineering. 2025, 46(11): 229-242 https://doi.org/10.19554/j.cnki.1001-3563.2025.11.025

References

[1] LIM M K, JONES C.Resource Efficiency and Sustainability in Logistics and Supply Chain Management[J]. International Journal of Logistics Research and Applications, 2017, 20(1): 20-21.
[2] SCHMIDT C E, SILVA A C L, DARVISH M, et al. Time-Dependent Fleet Size and Mix Multi-Depot Vehicle Routing Problem[J]. International Journal of Production Economics, 2023, 255: 108653.
[3] 王祺, 肖青. 模糊需求下的多中心冷链配送车辆路径问题[J]. 计算机工程与应用, 2023, 59(23): 341-350.
WANG Q, XIAO Q.Multi-Depot Cold Chain Distribution Vehicle Route Problem under Fuzzy Demand[J]. Computer Engineering and Applications, 2023, 59(23): 341-350.
[4] DE OLIVEIRA F B, ENAYATIFAR R, SADAEI H J, et al. A Cooperative Coevolutionary Algorithm for the Multi-Depot Vehicle Routing Problem[J]. Expert Systems with Applications, 2016, 43: 117-130.
[5] 张歆悦, 靳鹏, 胡笑旋, 等. 时间依赖型多配送中心带时间窗的开放式车辆路径问题研究[J]. 中国管理科学, 2024, 32(1): 146-157.
ZHANG X Y, JIN P, HU X X, et al.Research on the Time-Dependent Multi-Depot Open Vehicle Routing Problem with Time Windows[J]. Chinese Journal of Management Science, 2024, 32(1): 146-157.
[6] AGHADAVOUDI J A, ALINAGHIAN M.Multi-Depot Vehicle Routing Problem with Roaming Delivery Locations Considering Hard Time Windows: Solved by a Hybrid ELS-LNS Algorithm[J]. Expert Systems with Applications, 2024, 255: 124608.
[7] LIU W J, QIU J, DENG J, et al.Variable Neighbourhood Search Embedded Perturbation Mechanism for Multi-Depot Vehicle Routing Problem with Simultaneous Delivery & Pickup, and Time Limit[J]. Computers & Industrial Engineering, 2024, 189: 109942.
[8] LI J Q, DAI B T, NIU Y Y, et al.Multi-Type Attention for Solving Multi-Depot Vehicle Routing Problems[J]. IEEE Transactions on Intelligent Transportation Systems, 2024, 25(11): 17831-17840.
[9] DUBEY N, TANKSALE A.A Multi-Depot Vehicle Routing Problem with Time Windows, Split Pickup and Split Delivery for Surplus Food Recovery and Redistribution[J]. Expert Systems with Applications, 2023, 232: 120807.
[10] 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.
[11] 刘建胜, 蔡祥, 黄纪绘, 等. 考虑同时取送和时间窗的车辆路径及求解算法[J]. 计算机工程与应用, 2023, 59(16): 295-304.
LIU J S, CAI X, HUANG J H, et al.Solution Algorithm for Vehicle Routing Problem Considering Simultaneous Pickup-Delivery and Time Windows[J]. Computer Engineering and Applications, 2023, 59(16): 295-304.
[12] 王超, 刘超, 穆东, 等. 基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题[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.
[13] WU H G, GAO Y L.An Ant Colony Optimization Based on Local Search for the Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Window[J]. Applied Soft Computing, 2023, 139: 110203.
[14] ZHOU G H, LI D, BIAN J S, et al.Two-Echelon Time-Dependent Vehicle Routing Problem with Simultaneous Pickup and Delivery and Satellite Synchronization[J]. Computers & Operations Research, 2024, 167: 106600.
[15] PRAXEDES R, BULHÕES T, SUBRAMANIAN A, et al. A Unified Exact Approach for a Broad Class of Vehicle Routing Problems with Simultaneous Pickup and Delivery[J]. Computers & Operations Research, 2024, 162: 106467.
[16] 何美玲, 杨梅, 韩珣, 等. 带时间窗的时间依赖型同时取送货车辆路径问题研究[J]. 交通运输系统工程与信息, 2024, 24(4): 231-242.
HE M L, YANG M, HAN X, et al.Time-Dependent Vehicle Routing Optimization Considering Simultaneous Pickup-Delivery and Time Windows[J]. Journal of Transportation Systems Engineering and Information Technology, 2024, 24(4): 231-242.
[17] 蔡祥. 带时间窗的同时取送货车辆路径问题优化模型及算法研究[D]. 南昌: 南昌大学, 2023: 38-50.CAI X. Research on Optimization Models and Algorithms for Vehicle Routing Problem of Simultaneous Pick-up and Delivery with Time Windows[D]. Nanchang: Nanchang University, 2023: 38-50.
[18] WANG Z, SHEU J B.Vehicle Routing Problem with Drones[J]. Transportation Research Part B: Methodological, 2019, 122: 350-364.
[19] KARAKATIČ S, PODGORELEC V.A Survey of Genetic Algorithms for Solving Multi Depot Vehicle Routing Problem[J]. Applied Soft Computing, 2015, 27: 519-532.
[20] YESODHA R, AMUDHA T.A Bio-Inspired Approach: Firefly Algorithm for Multi-Depot Vehicle Routing Problem with Time Windows[J]. Computer Communications, 2022, 190: 48-56.
[21] 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.
[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] YANG X S. Firefly Algorithm, Stochastic Test Functions and Design Optimisation[J]. International Journal of Bio-Inspired Computation, 2010, 2(2): 78.
[24] SU K Y, ZHANG L, WANG J Y.License Plate Image Recognition System Based on Firefly Algorithm and BP Neural Network[C]//2023 4th International Conference on Electronic Communication and Artificial Intelligence (ICECAI). IEEE, 2023: 153-157.
[25] MOHAMMADI B.Modeling Various Drought Time Scales via a Merged Artificial Neural Network with a Firefly Algorithm[J]. Hydrology, 2023, 10(3): 58.
[26] BEHNAMIAN J, GHADIMI M, FARAJIAMIRI M.Data Mining-Based Firefly Algorithm for Green Vehicle Routing Problem with Heterogeneous Fleet and Refueling Constraint[J]. Artificial Intelligence Review, 2023, 56(7): 6557-6589.
[27] 谢承旺, 张飞龙, 陆建波, 等. 一种多策略协同的多目标萤火虫算法[J]. 电子学报, 2019, 47(11): 2359-2367.
XIE C W, ZHANG F L, LU J B, et al.Multi-Objective Firefly Algorithm Based on Multiply Cooperative Strategies[J]. Acta Electronica Sinica, 2019, 47(11): 2359-2367.
[28] SALHI S, NAGY G.A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problems with Backhauling[J]. Journal of the Operational Research Society, 1999, 50(10): 1034-1042.