不确定需求下异构电动物流车辆的路径优化研究

doi:10.3778/j.issn.1002-8331.2406-0354

摘要/Abstract

摘要： 随着国家政策的推动和新能源技术的发展，电动物流车辆在财政补贴、限行政策、节能环保和运营成本等方面相较于传统燃油车辆展现出显著优势，因而越来越多的物流企业在城市配送中采用电动物流车。研究了异构电动车队在应对客户需求不确定性和时间窗要求时的路径优化问题，并针对电动车辆续航里程有限和配送途中充电等实际约束，构建了一个以最小化配送总成本为目标的优化模型。为有效求解该模型，提出了一种结合遗传算法与模拟退火算法的混合方法。实验结果表明，所提出的模型和算法能够显著降低物流配送成本，并为交通和物流企业解决路径优化问题提供了有力的理论支持。

关键词: 车辆路径问题, 异构车型, 电动物流, 遗传-模拟退火算法

Abstract: With the development of new energy technologies and the implementation of supportive national policies, electric logistics vehicles have demonstrated significant advantages over traditional fuel vehicles in terms of financial subsidies, traffic restrictions, energy savings, environmental protection, and operating costs. As a result, more logistics companies are adopting electric vehicles for urban deliveries. This paper investigates the vehicle routing optimization problem for heterogeneous electric vehicle fleets, considering the uncertainty of customer demand and time window constraints. Given the practical challenges of limited driving range and the need for recharging during deliveries, a cost-minimization optimization model is proposed. To solve this model effectively, a hybrid algorithm combining genetic algorithms and simulated annealing is developed. Experimental results show that the proposed model and algorithm significantly reduce logistics costs, providing strong theoretical support for transportation and logistics companies in solving vehicle routing optimization problems under uncertain demand conditions.

Key words: vehicle path problem, heterogeneous vehicle models, electric logistics, genetic-simulated annealing algorithm

初良勇, 王嘉宁, 丁静茹. 不确定需求下异构电动物流车辆的路径优化研究[J]. 计算机工程与应用, 2025, 61(8): 294-306.

CHU Liangyong, WANG Jianing, DING Jingru. Vehicle Routing Optimization for Heterogeneous Electric Logistics Vehicles Under Uncertain Demand[J]. Computer Engineering and Applications, 2025, 61(8): 294-306.

参考文献

[1] 程坦, 陈鹏, 张国伟, 等. 部分充电策略下的多车型电动汽车车辆路径优化问题研究[J]. 交通运输工程与信息学报, 2022, 20(2): 105-114.
CHENG T, CHEN P, ZHANG G W, et al. Heterogeneous electric vehicles routing problem under partial charging strategy[J]. Journal of Transportation Engineering and Information, 2022, 20(2): 105-114.
[2] GE X, ZHU Z, JIN Y. Electric vehicle routing problems with stochastic demands and dynamic remedial measures[J]. Mathematical Problems in Engineering, 2020, 2020: 1-15.
[3] GUTIERREZ A, DIEULLE L, LABADIE N, et al. A hybrid metaheuristic algorithm for the vehicle routing problem with stochastic demands[J]. Computers & Operations Research, 2018, 99: 135-147.
[4] QIN J, YE Y, CHENG B, et al. The emergency vehicle routing problem with uncertain demand under sustainability environments[J]. Sustainability, Multidisciplinary Digital Publishing Institute, 2017, 9(2): 288.
[5] SUBRAMANYAM A, REPOUSSIS P P, GOUNARIS C E. Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty[J]. INFORMS Journal on Computing, 2020, 32(3): 661-681.
[6] 范厚明, 刘鹏程, 刘浩, 等. 多中心联合配送模式下集货需求随机的VRPSDP问题[J]. 自动化学报, 2021, 47(7): 1646-1660.
FAN H M, LIU P C, LIU H. et al. The multi-depot vehicle routing problem with simultaneous deterministic delivery and stochastic pickup based on joint distribution[J]. Acta Automatica Sinica, 2021, 47(7): 1646-1660.
[7] 张景玲, 赵燕伟, 王海燕, 等. 多车型动态需求车辆路径问题建模及优化[J]. 计算机集成制造系统, 2010, 16(3): 543-550.
ZHANG J L, ZHAO Y W, WANG H Y, et al. Modeling and algorithms for a dynamic multi-vehicle routing problem with customers dynamic requests[J]. Computer Integrated Manufacturing Systems, 2010, 16(3): 543-550.
[8] PENNA V P H, AFSAR H M, PRINS C, et al. A hybrid iterative local search algorithm for the electric fleet size and mix vehicle routing problem with time windows and recharging stations[J]. IFAC-PapersOnLine, 2016, 49(12): 955-960.
[9] 闫淼, 初良勇. 不同车型新能源车在城市冷链物流配送中的路径优化[J]. 上海海事大学学报, 2022, 43(4): 51-59.
YAN M, CHU L Y. Route optimization of different types of new energy vehicles in urban cold chain logistics distribution[J]. Journal of Shanghai Maritime University, 2022, 43(4): 51-59.
[10] FRANCESCHETTI A, HONHON D, WOENSEL V T, et al. The time-dependent pollution-routing problem[J]. Transportation Research Part B: Methodological, 2013, 56: 265-293.
[11] 李顺勇, 但斌, 葛显龙. 多通路时变网络下低碳车辆路径优化模型与算法[J]. 计算机集成制造系统, 2019, 25(2): 454-468.
LI S Y, DAN B, GE X L. Optimization model and algorithm of low carbon vehicle routing problem under multi-graph time-varying network[J]. Computer Integrated Manufacturing Systems, 2019, 25(2): 454-468.
[12] ?IMEN M, SOYSAL M. Time-dependent green vehicle routing problem with stochastic vehicle speeds: an approximate dynamic programming algorithm[J]. Transportation Research Part D: Transport and Environment, 2017, 54: 82-98.
[13] ZULVIA F E, KUO R J, NUGROHO D Y. A many-objective gradient evolution algorithm for solving a green vehicle routing problem with time windows and time dependency for perishable products[J]. Journal of Cleaner Production, 2020, 38(3): 759-768.
[14] 刘长石, 申立智, 盛虎宜, 等. 考虑交通拥堵规避的低碳时变车辆路径问题研究[J]. 控制与决策, 2020, 35(10): 2486-2496.
LIU C S, SHEN L Z, SHENG H Y. et al. Research on low-carbon time-dependent vehicle routing problem with traffic congestion avoidance approaches[J]. Control and Decision, 2020, 35(10): 2486-2496.
[15] HOU D, FAN H, REN X, et al. Time-dependent multi-depot heterogeneous vehicle routing problem considering temporal-spatial distance[J]. Sustainability, 2021, 13(9): 4674.
[16] GMIRA M, GENDREAU M, LODI A, et al. Tabu search for the time-dependent vehicle routing problem with time windows on a road network[J]. European Journal of Operational Research, 2021, 288(1): 129-140.
[17] 周鲜成, 吕阳, 贺彩虹, 等. 考虑时变速度的多车场绿色车辆路径模型及优化算法[J]. 控制与决策, 2022, 37(2): 473-482.
ZHOU X C, LYU Y, HE C H, et al. Multi-depot green vehicle routing model and its optimization algorithm with time-varying speed[J]. Control and Decision, 2022, 37(2): 473-482.
[18] HESAM S M E, ?ATAY B, AKSEN D. An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems[J]. Computers & Operations Research, 2021, 133: 105269.
[19] WANG Y, ZHOU J, SUN Y, et al. Collaborative multidepot electric vehicle routing problem with time windows and shared charging stations[J]. Expert Systems with Applications, 2023, 219: 119654.
[20] COEDEAU J F, LAPORTE G, MERCIER A, et al. A unified tabusearch heuristic for vehicle routing problems with time windows[J]. Journal of the Operational Research Society, 2001, 52: 928-936.