最小化期望成本的动态需求冷链配送路径优化研究

doi:10.3778/j.issn.1002-8331.2412-0047

摘要/Abstract

摘要： 针对冷链配送需求动态出现导致调度困难和高配送成本的问题，提出一种融合需求预测的前摄性配送模式。为平衡提前处理动态需求造成的空间浪费与实时响应需求产生的额外派车成本，充分利用动态需求产生概率的信息，在配送前进行路径规划，以降低期望配送成本。构建动态需求预测模型，获得动态需求产生概率；并建立针对静态需求的冷链配送路径优化模型，以静态模型为基础考虑动态需求是否产生与是否同批配送的不同情景，构建以最小化期望成本为目标的动态冷链配送路径优化模型。再设计两阶段求解算法：针对静态需求，设计改进的遗传算法生成初始预优化路径；针对动态需求，以静态需求的预优化路径为基础设计了期望路径调整算法，在配送前规划出最小化期望成本的配送方案。通过重庆市某医药冷链物流公司的实际案例分析以及不同规模算例的测试，将该配送模式与提前处理所有动态需求模式和实时响应需求模式进行对比分析，全面验证了模型和算法的有效性，结果表明该配送模式能够更加合理规划动态冷链配送路径，显著降低总配送成本，为动态需求的冷链配送路径优化提供参考。

关键词: 动态需求, 冷链配送, 期望成本, 车辆路径问题

Abstract: To address the challenges of scheduling difficulties and high delivery costs caused by dynamically emerging cold chain delivery demands, this study proposes a proactive delivery model that integrates demand forecasting. To balance the spatial waste caused by early handling of dynamic demands with the additional vehicle dispatching costs incurred by real-time demand responses, the model leverages the probability of dynamic demand occurrence to plan delivery routes in advance, aiming to minimize the expected delivery cost. The first step involves developing a dynamic demand forecasting model to estimate the probability of demand occurrence. A cold chain delivery path optimization model for static demand is then constructed. Based on this static model, a dynamic cold chain delivery routing optimization model is constructed, considering different scenarios of dynamic demand occurrence and joint delivery with static demands, with the objective of minimizing expected costs. A two-stage solution algorithm is designed. For static demands, an improved genetic algorithm is proposed to generate an initial pre-optimized route. For dynamic demands, an expected route adjustment algorithm is designed based on the pre-optimized static demand route to plan a delivery scheme that minimizes expected costs before dispatch. Finally, the proposed delivery model is validated through a case study of a pharmaceutical cold chain logistics company in Chongqing, China, along with tests on datasets of varying scales. Comparative analyses are conducted against models that handle all dynamic demands in advance and models that respond to demands in real-time. The results demonstrate the effectiveness of the proposed model and algorithm, showing that this delivery model can more efficiently plan dynamic cold chain delivery routes and significantly reduce total delivery costs, providing valuable insights for optimizing cold chain delivery routing under dynamic demand conditions.

Key words: dynamic demand, cold chain delivery, expected cost, vehicle routing problem

余海燕, 林宇婷, 吴腾宇. 最小化期望成本的动态需求冷链配送路径优化研究[J]. 计算机工程与应用, 2025, 61(18): 347-357.

YU Haiyan, LIN Yuting, WU Tengyu. Dynamic Cold Chain Delivery Route Optimization for Minimizing Expected Costs[J]. Computer Engineering and Applications, 2025, 61(18): 347-357.

参考文献

[1] THOMAS B W. Waiting strategies for anticipating service requests from known customer locations[J]. Transportation Science, 2007, 41(3): 319-331.
[2] MA S H, FILDES R. A retail store SKU promotions optimization model for category multi-period profit maximization[J]. European Journal of Operational Research, 2017, 260(2): 680-692.
[3] 葛显龙, 温鹏哲, 薛桂琴. 基于需求预测的两级动态配送路径优化研究[J]. 中国管理科学, 2022, 30(8): 210-220.
GE X L, WEN P Z, XUE G Q. Two-echelon dynamic vehicle routing problem with request forecasting[J]. Chinese Journal of Management Science, 2022, 30(8): 210-220.
[4] LIMA C A F, LUZ B M, TAKEMOTO S T, et al. Strategic modeling for the characterization of the conditions that allow the anticipation of the consumer’s requests[J]. Open Journal of Social Sciences, 2015, 3(10): 146-160.
[5] HE B, YIN L J. Prediction modelling of cold chain logistics demand based on data mining algorithm[J]. Mathematical Problems in Engineering, 2021, 2021(1): 3421478.
[6] JIANG J M, FENG T, LIU C X. An improved nonlinear grey bernoulli model based on the whale optimization algorithm and its application[J]. Mathematical Problems in Engineering, 2021, 2021(1): 6691724.
[7] SHAHRABI J, HADAVANDI E, ASADI S. Developing a hybrid intelligent model for forecasting problems: case study of tourism demand time series[J]. Knowledge-Based Systems, 2013, 43: 112-122.
[8] ZHU S, DEKKER R, VAN JAARSVELD W, et al. An improved method for forecasting spare parts demand using extreme value theory[J]. European Journal of Operational Research, 2017, 261(1): 169-181.
[9] CHUNG B D, LI J H, YAO T. Dynamic pricing and inventory control with nonparametric demand learning[J]. International Journal of Services Operations and Informatics, 2011, 6(3): 259.
[10] MIAO F, HE S H, PEPIN L, et al. Data-driven distributionally robust optimization for vehicle balancing of mobility-on-demand systems[J]. ACM Transactions on Cyber-Physical Systems, 2021, 5(2): 1-27.
[11] 马向国, 刘同娟, 杨平哲, 等. 基于随机需求的冷链物流车辆路径优化模型[J]. 系统仿真学报, 2016, 28(8): 1824-1832.
MA X G, LIU T J, YANG P Z, et al. Vehicle routing optimization model of cold chain logistics based on stochastic demand[J]. Journal of System Simulation, 2016, 28(8): 1824-1832.
[12] 丁秋雷, 胡祥培, 位娟, 等. 动态需求下蓄冷式多温共配多目标优化模型及算法[J]. 运筹与管理, 2021, 30(12): 13-19.
DING Q L, HU X P, WEI J, et al. Research on multi-objective optimization model and algorithm of cold storage multi-temperature joint delivery under dynamic demand[J]. Operations Research and Management Science, 2021, 30(12): 13-19.
[13] 王祺, 肖青. 模糊需求下的多中心冷链配送车辆路径问题[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.
[14] 许可心, 林婧, 杨泽鹏. 基于动态加权融合模型的快速路交通量预测[C]//绿色数智提质增效——2024年中国城市交通规划年会论文集, 2024: 167-177.
XU K X, LIN J, YANG Z P. Traffic volume prediction on expressways based on a dynamic weighted fusion model[C]//Green Intelligence: Improving Quality and Efficiency—Proceedings of the 2024 China Urban Transportation Planning Conference, 2024: 167-177.
[15] SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265.
[16] 张晓楠, 范厚明. 求解带时间窗车辆路径问题的混合Memetic算法[J]. 运筹与管理, 2021, 30(7): 128-135.
ZHANG X N, FAN H M. Hybrid memetic algorithm for vehicle routing problem with time windows[J]. Operations Research and Management Science, 2021, 30(7): 128-135.
[17] 张文博, 苏秦, 程光路. 基于动态需求的带时间窗的车辆路径问题[J]. 工业工程与管理, 2016, 21(6): 68-74.
ZHANG W B, SU Q, CHENG G L. Vehicle routing problem with time windows based on dynamic demands[J]. Industrial Engineering and Management, 2016, 21(6): 68-74.
[18] 何美玲, 魏志秀, 武晓晖, 等. 基于改进蚁群算法求解带软时间窗的车辆路径问题[J]. 计算机集成制造系统, 2023, 29(3): 1029-1039.
HE M L, WEI Z X, WU X H, et al. Improved ant colony optimization algorithm for solving vehicle routing problem with soft time windows[J]. Computer Integrated Manufacturing Systems, 2023, 29(3): 1029-1039.
[19] 王勇, 罗双, 苟梦圆, 等. 考虑动态需求的生鲜商品物流配送优化方法研究[J]. 包装工程, 2024, 45(7): 148-158.
WANG Y, LUO S, GOU M Y, et al. Fresh commodity logistics distribution optimization considering dynamic demands[J]. Packaging Engineering, 2024, 45(7): 148-158.
[20] 吴暖, 代焕杰, 李季涛, 等. 考虑时间容忍度的冷链物流配送路径多目标优化[J]. 交通运输系统工程与信息, 2023, 23(2): 275-284.
WU N, DAI H J, LI J T, et al. Multi-objective optimization of cold chain logistics distribution path considering time tolerance[J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(2): 275-284.
[21] 范厚明, 吴嘉鑫, 耿静, 等. 模糊需求与时间窗的车辆路径问题及混合遗传算法求解[J]. 系统管理学报, 2020, 29(1): 107-118.
FAN H M, WU J X, GENG J, et al. Hybrid genetic algorithm for solving fuzzy demand and time windows vehicle routing problem[J]. Journal of Systems & Management, 2020, 29(1): 107-118.