目的 应对各大制造中心构建完备供应链带给物流配送企业的压力和挑战,研究多中心联合配送模式下的带时间窗装卸一体化车辆路径问题。方法 首先,以总成本最小为优化目标,建立考虑多项成本的数学优化模型,提出变邻域萤火虫算法求解。其次,针对萤火虫算法初始种群分布不均、对步长参数依赖较大等问题,引入Lévy flight随机扰动机制进行干预,扩大算法搜索空间;提出随机扩张因子策略,以增加萤火虫位置更新的移动步长,避免发生种群集中现象,突破种群束缚,改善种群在算法搜索空间的分布性,通过3组实验来验证本文模型和算法的有效性。结果 无论是求解质量还是求解速度方面,所设计算法均优于对比算法,并分析比较了多中心联合配送与传统配送模式之间的差异和优势,进一步验证了本文所提出模型及算法的优越性和普适性。结论 可为多中心联合配送模式下的车辆路径问题提供理论依据及决策参考。
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
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[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.
基金
国家自然科学基金（51565036）; 湖北省教育厅科学技术研究项目（B2023497）; 湖北职业技术学院课题重点项目（2024A04）
PDF(1852 KB)
渝公网安备 50010702501716号 渝ICP备15012534号-2
