时变路网下多中心多车型电动卡车联合配送优化研究

doi:10.3778/j.issn.1002-8331.2408-0441

摘要/Abstract

摘要： 在物流行业由高碳排放向绿色低碳的转型中，电动卡车在物流配送领域备受青睐。但考虑到城市路网交通阻抗的时空分布不均衡特性，以及电池充电过程的非线性特性，传统的静态车辆路径优化难以满足现实需求。为提高电动卡车在时变路网下的配送效率，综合考虑多中心多车型联合配送策略、基于非线性充电函数的部分充电策略、时间窗、载重及服务时间窗等因素，构建一个以综合配送成本最小为目标的混合整数规划模型；设计了一个融合改进K-means聚类法且具有记忆功能的模拟退火算法，对所建模型进行求解。以上海市部分物流园为例验证模型及算法的有效性，结果表明：高峰与非高峰时段的配送成本相差约5.7%；多车型联合配送方案相较于单车型配送方案成本降低约5.4%；部分充电策略相较于完全充电策略成本降低约5.4%。研究结果为物流企业进一步优化城市时变路网下电动卡车的配送方案提供了参考依据。

关键词: 绿色物流, 时变路网, 多中心多车型联合配送, 部分充电策略, 非线性充电函数, 改进混合模拟退火算法

Abstract: In the transformation of the logistics industry from high carbon emissions to green and low carbon, electric trucks are favored in the field of logistics distribution. However, considering the uneven temporal and spatial distribution of traffic impedance in urban road networks and the nonlinear characteristics of battery charging, traditional static vehicle routing optimization is difficult to meet actual needs. In order to improve the delivery efficiency of electric trucks in time-varying road networks, a mixed integer programming model with the goal of minimizing the comprehensive delivery cost is constructed by comprehensively considering factors such as multi-center and multi-model joint distribution strategy, partial charging strategy based on nonlinear charging function, time window, load and service time window. An improved K-means clustering method and a simulated annealing algorithm with memory function are designed to solve the model. Taking some logistics parks in Shanghai as an example to verify the effectiveness of the model and algorithm, the results show that the distribution cost difference between peak and non-peak hours is about 5.7%. Compared with the single vehicle distribution scheme, the cost of the multi-vehicle joint distribution scheme is reduced by about 5.4%. The cost of the partial charging strategy is about 5.4% lower than that of the full charging strategy. The research results provide a reference for logistics enterprises to further optimize the distribution scheme of electric trucks under urban time-varying road network.

Key words: green logistics, time-varying road network, multi-center and multi-model joint distribution, partial charging strategy, nonlinear charging function, improved hybrid simulated annealing algorithm

郭嘉炜, 黄志鹏, 贾锦秀, 马晓天, 李建国, 叶彬彬. 时变路网下多中心多车型电动卡车联合配送优化研究[J]. 计算机工程与应用, 2025, 61(23): 340-350.

GUO Jiawei, HUANG Zhipeng, JIA Jinxiu, MA Xiaotian, LI Jianguo, YE Binbin. Research on Joint Distribution Optimization of Multi-Center and Multi-Vehicle Electric Trucks Under Time-Varying Road Network[J]. Computer Engineering and Applications, 2025, 61(23): 340-350.

参考文献

[1] 郭戈, 张振琳. 电动车辆路径优化研究与进展[J]. 控制与决策, 2018, 33(10): 1729-1739.
GUO G, ZHANG Z L. Status and development of electric vehicle routing optimization[J]. Control and Decision, 2018, 33(10): 1729-1739.
[2] FAN L J. A hybrid adaptive large neighborhood search for time-dependent open electric vehicle routing problem with hybrid energy replenishment strategies[J]. Plos One, 2023, 18(9): e0291473.
[3] ZHANG R Y, GUO J M, WANG J W. A time-dependent electric vehicle routing problem with congestion tolls[J]. IEEE Transactions on Engineering Management, 2020, 69(4): 861-873.
[4] SCHNEIDER M, STENGER A, GOEKE D. The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation Science, 2014, 48(4): 500-520.
[5] 揭婉晨, 杨珺, 陆坚毅. 基于分支定价算法的电动汽车车辆路径问题[J]. 运筹与管理, 2016, 25(4): 93-100.
JIE W C, YANG J, LU J Y. Electric Vehicle routing problem based on a branch-and-price algorithm[J]. Operations Research and Management Science, 2016, 25(4): 93-100.
[6] 周筝, 龙华, 李帅, 等. 多因素下基于路网拓扑的电动汽车充电路径规划策略[J]. 四川大学学报(自然科学版), 2024, 61(1): 229-238.
ZHOU Z, LONG H, LI S. et al. Electric vehicles charging path planning method based on road network under multi parameters[J]. Journal of Sichuan University(Natural Science Edition), 2024, 61(1): 229-238.
[7] 陈治亚, 高辉, 徐光明, 等. 考虑随机需求和硬时间窗的多目标车辆路径优化方法[J]. 铁道科学与工程学报, 2021, 18(12): 3110-3120.
CHEN Z Y, GAO H, XU G M, et al. A multi-objective vehicle routing optimization method based on stochastic demand and hard time window[J]. Journal of Railway Science and Engineering, 2021, 18(12): 3110-3120.
[8] 王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.
WANG W Q, DING D, CAO S Y. Hybrid variable neighborhood search algorithm for the multi-trip and heterogeneous-fleet electric vehicle routing problem[J]. Journal of System Simulation, 2022, 34(4): 910-919.
[9] SHEN L, TAO F M, WANG S Y. Multi-depot open vehicle routing problem with time windows based on carbon trading[J]. International Journal of Environmental Research and Public Health, 2018, 15(9): 2025.
[10] WANG Y, ZHOU J X, SUN Y Y, et al. Collaborative multidepot electric vehicle routing problem with time windows and shared charing stations[J]. Expert Systems with Applications, 2023, 219: 119654.
[11] KESKIN M, ?ATAY B. Partial recharge strategies for the electric vehicle routing problem with time windows[J]. Transportation Research Part C: Emerging Technologies, 2016, 65: 111-127.
[12] MONTOYA A, GUéRET C, MENDOZA J E, et al. The electric vehicle routing problem with nonlinear charging function[J]. Transportation Research Part B: Methodological, 2017, 103: 87-110.
[13] 汪山颖, 靳文舟. 基于非线性混合充电策略的电动车物流配送路径规划模型[J]. 交通信息与安全, 2022, 40(2): 116-125.
WANG S Y, JIN W Z. Routing of electronic automobileswith hybrid nonlinear charging strategy for logistics distribution[J]. Journal of Transport Information and Safety, 2022, 40(2): 116-125.
[14] 张得志, 龚浩翔, 李双艳, 等. 在时变速度下的车辆出行时刻和路径联合优化[J].铁道科学与工程学报, 2017, 14(3): 642-648.
ZHANG D Z, GONG H X, LI S Y, et al. Research on joint optimization for vehicle schedule and route problem with time-varying speeds[J]. Journal of Railway Science and Engineering, 2017, 14(3): 642-648.
[15] 马昌喜, 薛凡松, 麻存瑞, 等. 时变路网下基于混合调整策略的生鲜品配送路径优化研究[J]. 交通运输系统工程与信息, 2023, 23(4): 298-306.
MA C X, XUE F S, MA C R, et al. Route optimization of fresh food distribution under time-varying network and hybrid adjustment strategy[J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(4): 298-306.
[16] 温廷新, 李可昕, 赵琳琳, 等. 时变路网下电动汽车冷链配送路径规划研究[J]. 大连理工大学学报, 2022, 62(6): 641-649.
WEN T X, LI K X, ZHAO L L, et al. Research of route planning for electric vehicle cold chain distribution under time-varying road network[J]. Journal of Dalian University of Technology, 2022, 62(6): 641-649.
[17] 范厚明, 孙秀娜, 张跃光, 等.时变路网下带混合时间窗的车辆路径问题[J]. 计算机工程与应用, 2022, 58(16): 292-302.
FAN H M, SUN X N, ZHANG Y G, et al. Vehicle routing problem with mixed time windows under time-dependent network[J]. Computer Engineering and Applications, 2022, 58(16): 292-302.
[18] LI L Y, CHEN J, SUN Y P, et al. Application of new energy logistics vehicle based on urban distribution[C]//E3S Web of Conferences, 2021: 01065.
[19] 路世昌, 邵旭伦, 李丹. 卡车-无人机协同救灾物资避障配送问题研究[J]. 计算机工程与应用, 2023, 59(2): 289-298.
LU S C, SHAO X L, LI D. Research on truck-drone coordinated disaster relief supplies obstacle avoidance distribution[J]. Computer Engineering and Applications, 2023, 59(2): 289-298.
[20] 黎芯郁, 王晓光. 基于物流金融的动态质押物配送路径优化[J]. 铁道科学与工程学报, 2017, 14(8): 1775-1782.
LI X Y, WANG X G. Based on logistics financial distribution route optimization of dynamic pledge[J]. Journal of Railway Science and Engineering, 2017, 14(8): 1775-1782.
[21] LI Y. Research on logistics distribution vehicle path optimization based on simulated annealing algorithm[J]. Advances in Multimedia, 2022, 2022(1): 7363279.
[22] LIN B L, ZHAO Y N, LIN R X, et al. Integrating traffic routing optimization and train formation plan using simulated annealing algorithm[J]. Applied Mathematical Modelling, 2021, 93: 811-830.