移动充电桩选址-路径优化及遗传-RSI两阶段算法

doi:10.3778/j.issn.1002-8331.2303-0263

摘要/Abstract

摘要： 在我国“双碳”政策背景下，考虑载重、电量、充电桩服务能力等约束，构建以最小化总配送距离为目标的移动充电桩选址与电动汽车路径规划模型。随后，设计一种两阶段算法求解模型，第一阶段采用遗传算法规划初始配送路径，第二阶段采用RSI（recharge stations insertion）算法实现充电桩选址及路径调整。基于CVRP基准案例进行求解，结果表明车辆访问充电桩导致的配送距离平均增长率在5%以下。与粒子群和模拟退火作为一阶段的算法对比，遗传-RSI两阶段算法与这两种算法求解结果的Gap值分别为-4.04%和-3.65%。最后对“电耗率”等模型参数进行灵敏度分析。结果表明在物流公司专用电动车配送中，若使用专用充电桩并接受8%以下配送距离增长及相应的充电服务费，可采取移动充电桩选址与路径联合优化模式。

关键词: 电动汽车, 移动充电桩, 选址-路径问题, 两阶段算法, 连续型选址

Abstract: Driven by Chinese double carbon policy, logistics companies should ensure both environmental preservation and fluency in the last-mile delivery. With the objective of minimizing the total distribution distance, a model for location of mobile recharge stations and the route planning is formulated, which considers some constraints such as load, power and service capacity of recharge stations. Subsequently, a two-stage algorithm is proposed. The genetic algorithm is used to generate the initial routing plans in the first stage, and the RSI algorithm is designed to locate recharge stations and adjust routing plans in the second stage. Tested by the CVRP benchmark cases, the results show that the average increasing rate of travel distances caused by visiting recharge station is less than 5%. Compared with PSO and SA, the results between the proposed algorithm and the other two algorithms are respectively -4.04% and -3.65%. Also, the adaptability of the model is verified through the sensitivity analysis with the main model parameters such as power consumption rate. Therefore, the mode is feasible if logistics companies can afford to use exclusive mobile recharge stations and accept the increase of travel distances which is less than 8%.

Key words: electric vehicle, mobile recharge stations, location-routing problem, two-stage algorithm, continuous location

马艳芳, 薛金昭, 李保玉, 杨屹夫. 移动充电桩选址-路径优化及遗传-RSI两阶段算法[J]. 计算机工程与应用, 2024, 60(13): 319-329.

MA Yanfang, XUE Jinzhao, LI Baoyu, YANG Yifu. Genetic-RSI Two-Stage Algorithm for Mobile Recharge Stations Location-Routing Optimization[J]. Computer Engineering and Applications, 2024, 60(13): 319-329.

参考文献

[1] 胡剑鹏, 罗霞, 甘易玄. 基于列生成算法的鲁棒电动车路径问题[J]. 计算机集成制造系统, 2023, 29(7): 2427-2439.
HU J P, LUO X, GAN Y X. Robust electric vehicle routing problem based on column generation algorithm[J]. Computer Integrated Manufacturing Systems, 2023, 29(7): 2427-2439.
[2] WANG H, ZHAO D, MENG Q, et al. A four-step method for electric-vehicle charging facility deployment in a dense city: an empirical study in Singapore[J]. Transportation Research Part A: Policy and Practice, 2019, 119: 224-237.
[3] HULAGU S, CELIKOGLU H B. Electric vehicle location routing problem with vehicle motion dynamics-based energy consumption and recovery[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 23(8): 10275-10286.
[4] SCHIFFER M, WALTHER G. An adaptive large neighborhood search for the location-routing problem with intra-route facilities[J]. Transportation Science, 2018, 52(2): 331-352.
[5] LIU H, GAO B, LIU Y. Battery swap station location routing problem with capacitated electric vehicles and time windows[C]//Proceedings of the 2019 IEEE 6th International Conference on Industrial Engineering and Applications (ICIEA), Tokyo, Apr 12-15, 2019. New York: IEEE, 2019: 832-836.
[6] ZHANG S, CHEN M, ZHANG W. A novel location-routing problem in electric vehicle transportation with stochastic demands[J]. Journal of Cleaner Production, 2019, 221: 567-581.
[7] AGHALARI A, SALAMAH D E, MARINO C, et al. Electric vehicles fast charger location-routing problem under ambient temperature[J/OL]. Annals of Operations Research(2021-10-31)[2022-10-05]. https://doi.org/10.1007/s10479-021-04375-8.
[8] 杨珺, 冯鹏祥, 孙昊, 等. 电动汽车物流配送系统的换电站选址与路径优化问题研究[J]. 中国管理科学, 2015, 23(9): 87-96.
YANG J, FENG P X, SUN H, et al. Battery exchange station location and vehicle routing problem in electric vehicle distribution system[J]. Chinese Journal of Management Science, 2015, 23(9): 87-96.
[9] YANG J, SUN H. Battery swap station location-routing problem with capacitated electric vehicles[J]. Computers & Operations Research, 2015, 55: 217-232.
[10] SHAO S, GUO S, QIU X. A mobile battery swapping service for electric vehicles based on a battery swapping van[J]. Energies, 2017, 10(10): 1667-1688.
[11] HUANG S, HE L, GU Y, et al. Design of a mobile charging service for electric vehicles in an urban environment[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 16(2): 787-798.
[12] RAEESI R, ZOGRAFOS K G. The electric vehicle routing problem with time windows and synchronised mobile battery swapping[J]. Transportation Research Part B: Methodological, 2020, 140: 101-129.
[13] QURESHI U, GHOSH A, PANIGRAHI B K. Scheduling and routing of mobile charging stations with stochastic travel times to service heterogeneous spatiotemporal electric vehicle charging requests with time windows[J]. IEEE Transactions on Industry Applications, 2022, 58(5): 6546-6556.
[14] 杨磊, 郝彩霞, 唐瑞红. 基于电动物流车的充电和换电设施选址模型[J]. 系统工程理论与实践, 2019, 39(7): 1781-1795.
YANG L, HAO C X, TANG R H. Location models of charging and battery swapping facilities based on electric vehicles[J]. Systems Engineering Theory and Practice, 2019, 39(7): 1781-1795.
[15] HIERMANN G, HARTL R F, PUCHINGER J, et al. Routing a mix of conventional, plug-in hybrid, and electric vehicles[J]. European Journal of Operational Research, 2019, 272(1): 235-248.
[16] FAZAYELI S, EYDI A, KAMALABADI I N. Location-routing problem in multimodal transportation network with time windows and fuzzy demands: presenting a two-part genetic algorithm[J]. Computers & Industrial Engineering, 2018, 119: 233-246.
[17] SCHIFFER M, WALTHER G. The electric location routing problem with time windows and partial recharging[J]. European Journal of Operational Research, 2017, 260(3): 995-1013.
[18] WANG Y, LEI L, ZHANG D, et al. Towards delivery-as-a-service: effective neighborhood search strategies for integrated delivery optimization of E-commerce and static O2O parcels[J]. Transportation Research Part B: Methodological, 2020, 139: 38-63.
[19] 康凯, 韩杰, 普玮, 等. 生鲜农产品冷链物流低碳配送路径优化研究[J]. 计算机工程与应用, 2019, 55(2): 259-265.
KANG K, HAN J, PU W, et al. Optimization research on cold chain distribution routes considering carbon emissions for fresh agricultural products[J]. Computers Engineering and Applications, 2019, 55(2): 259-265.
[20] CHEN S, CHEN R, WANG G G, et al. An adaptive large neighborhood search heuristic for dynamic vehicle routing problems[J]. Computers & Electrical Engineering, 2018, 67: 596-607.
[21] 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.
[22] YANG S, NING L, TONG L C, et al. Integrated electric logistics vehicle recharging station location-routing problem with mixed backhauls and recharging strategies[J]. Transportation Research, Part C: Emerging Technologies, 2022, 140: 103695.
[23] RIEMANN R, WANG D Z W, BUSCH F. Optimal location of wireless charging facilities for electric vehicles: flow-capturing location model with stochastic user equilibrium[J]. Transportation Research, Part C: Emerging Technologies, 2015, 58: 1-12.