订单可拆分的低碳冷链配送选址与多车舱路径优化

doi:10.3778/j.issn.1002-8331.2403-0467

摘要/Abstract

摘要： 冷链物流通过全程管控环境温度保障生鲜品的交付品质，在“双碳”战略目标下面临节能减排的突出矛盾。将多车舱车辆多温共配引入冷链选址-路径决策中，考虑客户时间窗和多车舱能耗与碳排放，建立以系统总成最小为目标、订单可拆分的低碳冷链配送选址与多车舱路径优化模型。设计了混合遗传算法、动态规划与路径重连的求解算法，先协同决策选址与路径，再采用动态规划对路径分组评价，路径重连算法加强对各代最优解的融合邻域结构的局部搜索。通过不同规模的数值算例验证了模型和算法的有效性，结果表明，客户对产品的需求数量和时间要求，不仅影响冷链配送系统的碳排放和总成本，也会对订单拆分配送组织方式产生影响。

关键词: 冷链配送, 低碳选址-路径, 多车舱路径, 碳税

Abstract: The delivery quality of fresh products is ensured by controlling the ambient temperature in the cold chain distribution, which is confronted with the prominent challenge of energy conservation and emission reduction under the “carbon peaking and carbon neutrality” strategy. The mode of multi-temperature joint distribution with multi-compartment vehicles is introduced into the cold chain location routing scheme. With the goal of minimizing the total cost of the distribution system, which includes energy consumption and carbon emissions, a low-carbon location and routing problem for cold chain distribution with multi?compartment vehicles is established considering customers’ time windows and order splitting. A hybrid approach is proposed by combining genetic algorithm, dynamic programming and path relinking. The decisions of location and tour are made cooperatively in the encoding process, and then vehicle routes are clustered and evaluated by the dynamic programming method. The path-relinking algorithm intensifies the optimal solution of each generation by local searches of mixed neighborhood structures. Finally, the effectiveness of the model and algorithm is validated by numerical experiments of different scales. The results show that the demand quantity and time windows not only affect the carbon emissions and total cost of the cold chain distribution system, but also concern the delivery mode of order splitting.

Key words: cold chain distribution, low-carbon location-routing, multi-compartment vehicle routing, carbon tax

吴瑶, 周愉峰, 李峰. 订单可拆分的低碳冷链配送选址与多车舱路径优化[J]. 计算机工程与应用, 2025, 61(8): 339-350.

WU Yao, ZHOU Yufeng, LI Feng. Optimization of Low?Carbon Location and Routing Problem with Multi?Compartment for Cold?Chain?Distribution Considering Order Splitting[J]. Computer Engineering and Applications, 2025, 61(8): 339-350.

参考文献

[1] 马艳芳, 应斌, 周晓阳, 等. 基于冲突合作关系的生鲜选址-路径多主体优化模型与算法[J]. 系统工程理论与实践, 2020, 40(12): 3194-3209.
MA Y F, YING B, ZHOU X Y, et al. Multi-agent optimization model and algorithm for perishable food location-routing problem with conflict and coordination[J]. Systems Engineering—Theory & Practice, 2020, 40(12): 3194-3209.
[2] 牟进进, 陈莒伟, 王淑云. 蓄冷式多温集配路径优化模型[J]. 中国管理科学, 2020, 30(10): 236-246.
MOU J J, CHEN J W, WANG S Y. Optimization model of cold accumulated multi-temperature joint pickup and distribution[J]. Chinese Journal?of?Management?Science, 2020, 30(10): 236-246.
[3] HüBNER A, OSTERMEIER M. A multi-compartment vehicle routing problem with loading and unloading costs[J]. Transportation Science, 2019, 53(1): 282-300.
[4] OSTERMEIER M, HENKE T, HUEBNER A, et al. Multi-compartment vehicle routing problems: state-of-the-art, modeling framework and future directions[J]. European Journal of Operational Research, 2021, 292: 799-817.
[5] 王旭坪, 詹红鑫, 孙自来, 等. 基于蚁群禁忌混合算法的成品油多舱配送路径优化研究[J]. 系统工程理论与实践, 2017, 37(12): 3215-3226.
WANG X P, ZHAN H X, SUN Z L, et al. Route optimization for the refined oil multi-compartment distribution based on ant colony and tabu search hybrid algorithm[J]. Systems Engineering—Theory & Practice, 2017, 37(12): 3215-3226.
[6] SUN L, ZHANG Y, HU X. Economical-traveling-distance-based fleet composition with fuel costs: an application in petrol distribution[J]. Transportation Research Part E: Logistics and Transportation Review, 2021, 147: 102223.
[7] 肖建华, 张文雪, 潘钰雅, 等. 基于分类垃圾收运时效性的多周期多车舱路径优化研究[J/OL]. 中国管理科学(2023-07-13)[2024-02-20]. https://doi.org/10.16381/j.cnki.issn1003-207x.2023.0050.
XIAO J H, ZHANG W X, PAN Y Y, et al. A multi-period multi-compartment vehicle routing problem for sorted-waste collection with timeliness[J/OL]. Chinese Journal of Management Science[2023-07-13]. https://doi.org/10.16381/j.cnki.issn1003-207x.2023.0050.
[8] FALLAHI E A, PRINS C, CALVO W R. A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem[J]. Computers & Operations Research[J]. 2008, 35: 1725-1741.
[9] CHEN L, LIU Y, LANGEVIN A. Multi-compartment vehicle routing problem in cold-chain distribution[J]. Computers & Operations Research, 2019, 111: 58-66.
[10] CHEN J, DAN B, SHI J. A variable neighborhood search approach for the multi-compartment vehicle routing problem with time windows considering carbon emission[J]. Journal of Cleaner Production, 2020, 277: 123932.
[11] 刘晓燕, 邱华昕, 王杜娟, 等. 考虑优先级和需求可拆分的灾后应急血液多车舱调度[J]. 系统管理学报, 2024, 33(6): 1447-1460.
LIU X Y, QIU H X, WANG D J, et al. Research on multi-compartment emergency blood scheduling considering priority and split demand[J]. Journal of Systems & Management, 2024, 33(6): 1447-1460.
[12] 王锋, 张令荣, 鲁渤. 考虑碳排放的冷链物流多温共配时变路径研究[J/OL]. 中国管理科学(2024-01-18)[2024-02-20]. https://doi.org/10.16381/j.cnki.issn1003-07x.2022.2318.
WANG F, ZHANG L R, LU B. Research on time-varying path of multi-temperature co-distribution in cold chain logistics considering carbon emissions[J/OL]. Chinese Journal of Management Science(2024-01-18)[2024-02-20]. https://doi.org/10.16381/j.cnki.issn1003-207x.2022.2318.
[13] WANG X, LIANG Y, TANG X, et al. A multi-compartment electric vehicle routing problem with time windows and temperature and humidity settings for perishable product delivery[J]. Expert Systems with Applications, 2023, 233: 120974.
[14] MICHAEL D, SCHNEIDER M. A survey of variants and extensions of the location-routing problem[J]. European Journal of Operational Research, 2015, 241(2): 283-308.
[15] HUANG S H. Solving the multi-compartment capacitated location routing problem with pickup—delivery routes and stochastic demands[J]. Computers & Industrial Engineering, 2015, 87: 104-113.
[16] MOON I, SALHI S, FENG X. The location-routing problem with multi-compartment and multi-trip: formulation and heuristic approaches[J]. Transportmetrica A: Transport Science, 2020, 16(3): 501-528.
[17] SHANG C, MA L, LIU Y. Green location routing problem with flexible multi-compartment for source-separated waste: a Q-learning and multi-strategy-based hyper-heuristic algorithm[J]. Engineering Applications of Artificial Intelligence, 2023, 121: 105954.
[18] 马艳芳, 李保玉, 杨屹夫, 等. 客户分类下生鲜配送两级路径问题与算法研究 [J]. 计算机工程与应用, 2021, 57(20): 287-298.
MA Y F, LI B Y, YANG Y F, et al. Two-echelon capacitated vehicle routing model and algorithm for fresh products distribution with customer classification[J]. Computer Engineering and Applications, 2021, 57(20): 287-298.
[19] RAHMANIFAR G, MOHAMMADI M, GOLABIAN M, et al. Integrated location and routing for cold chain logistics networks with heterogeneous customer demand[J]. Journal of Industrial Information Integration, 2024, 38: 100573.
[20] 王淑云, 孙虹, 牟进进. 随机需求下蓄冷式多温共配优化模型[J]. 系统管理学报, 2018, 27(4): 712-721.
WANG S Y, SUN H, MOU J J. Optimization of cold-storage multi-temperature joint distribution based on stochastic demands[J]. Journal of Systems & Management, 2018, 27(4): 712-721.
[21] 张硕航, 郭改枝. 多旅行商模型及其应用研究综述[J]. 计算机科学与探索, 2022, 16(7): 1516-1528.
ZHANG S H, GUO G Z. Review of multiple traveling salesman model and its application[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(7): 1516-1528.
[22] 潘震东, 唐加福, 韩毅. 带货物权重的车辆路径问题及遗传算法[J]. 管理科学学报, 2007, 10(3): 23-29.
PAN Z D, TANG J F, HAN Y. Vehicle routing problem with weight coefficients[J]. Journal of Management Sciences in China, 2007, 10(3): 23-29.
[23] PRINS C, LACOMME P, PRODHON C. Order-first split-second methods for vehicle routing problems: a review[J]. Transportation Research Part C: Emerging Technologies, 2014, 40: 179-200.
[24] CORMEN T H, LEISERSON C E, RIVEST R L. Introduction to algorithms[M]. New York: MIT Press, 1990.
[25] WU W, ZHOU W, LIN Y, et al. A hybrid metaheuristic algorithm for location inventory routing problem with time windows and fuel consumption[J]. Expert Systems with Applications, 2021, 166: 114034.
[26] 周愉峰, 刘思峰, 苏加福, 等. 碳税政策下分销网络选址——路径问题的鲁棒优化[J]. 计算机集成制造系统, 2021, 27(4): 1167-1177.
ZHOU Y F, LIU S F, SU J F, et al. Robust optimization of distribution network location-routing problem under carton tax policy[J]. Computer Integrated Manufacturing System, 2021, 27(4): 1167-1177.
[27] 邱晗光, 李海南, 宋寒. 需求依赖末端交付与时间窗的城市配送自提柜选址——路径问题[J]. 计算机集成制造系统, 2018, 24(10): 2612-2621.
QIU H G, LI H N, SONG H. Reception box locating-vehicle routing problems in urban distribution considering demand depending on last-mile delivery and time slots[J]. Computer Integrated Manufacturing Systems, 2018, 24(10): 2612-2621.
[28] 闫芳, 彭婷婷, 申成然. 基于时空聚类求解带容积约束的选址——路径问题[J]. 控制与决策, 2021, 36(10): 2504-2510.
YAN F, PENG T T, SHEN C R. Time-space cluster based location-routing problem with capacitate constraints[J]. Control and Decision, 2021, 36(10): 2504-2510.