计算机工程与应用 ›› 2024, Vol. 60 ›› Issue (13): 319-329.DOI: 10.3778/j.issn.1002-8331.2303-0263

• 工程与应用 • 上一篇    下一篇

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

马艳芳,薛金昭,李保玉,杨屹夫   

  1. 1.河北工业大学 经济管理学院,天津 300401
    2.南开大学 现代物流研究中心,天津 300071
  • 出版日期:2024-07-01 发布日期:2024-07-01

Genetic-RSI Two-Stage Algorithm for Mobile Recharge Stations Location-Routing Optimization

MA Yanfang, XUE Jinzhao, LI Baoyu, YANG Yifu   

  1. 1.School of Economics and Management, Hebei University of Technology, Tianjin 300401, China
    2.Research Center of Logistics, Nankai University, Tianjin 300071, China
  • Online:2024-07-01 Published:2024-07-01

摘要: 在我国“双碳”政策背景下,考虑载重、电量、充电桩服务能力等约束,构建以最小化总配送距离为目标的移动充电桩选址与电动汽车路径规划模型。随后,设计一种两阶段算法求解模型,第一阶段采用遗传算法规划初始配送路径,第二阶段采用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