Route Planning for Electric Vehicle Delivery Considering Charging Queuing Delay
-
摘要: 电车配送中负载以及传动等因素使得耗电呈现非线性，同时充电及排队时延将会影响路径规划的配送效率。针对此问题，研究了应用动态能耗模型的优化充电站选择与充电时间的配送路径规划方法。采用电车动态能耗率（energy consumption rate，ECR）模型，建立与货物载重相关的非线性能耗函数关系。针对电车排队充电过程，基于排队论模型分析电车到达率、服务率以及充电站容量与排队时延（charging queuing delay，CQD）的函数关系。结合上述ECR能耗与CQD时延分析，建立以最小化总行驶时间为目标的路径规划模型，联合访问约束、电车负载约束以及电量约束，以确保模型在多车辆、多任务以及多充电站场景下的可行性与精确性。为了高效求解上述模型，设计了基于深度强化学习（deep reinforcement learning，DRL）的优化算法。其中，针对排队与充电时机决策问题，设计利用充电站实时信息的动态决策算法，以降低DRL模型学习的难度，提高算法的计算效率。最后，通过多尺度算例仿真实验验证所提方法的有效性。实验结果表明：该方法有效优化了充电排队时间，平均减少每车配送总行驶时间0.14 h；与多种典型智能优化算法进行对比实验，对比结果为每车配送总行驶时间平均减少0.52 h，同时算法求解效率提升75.4%。Abstract: The load and transmission in electric vehicle delivery make the power consumption nonlinear. Meanwhile, charging and queuing delays will affect the efficiency of delivery. To address this issue, a delivery route planning method for optimizing the selection of charging stations and charging time by applying a dynamic energy consumption model is studied. By adopting the electric vehicle dynamic energy consumption rate (ECR) model, a nonlinear energy consumption function relationship related to the load is established. Meanwhile, for the charging process of electric vehicles in queues, based on the queuing theory model, the functional relationships between the arrival rate of electric vehicles, service rate, charging station capacity and charging queuing delay (CQD) are analyzed. Then, based on the above analysis of ECR energy consumption and CQD latency, a route planning model aiming to minimize the total travel time is established. The model considers the access constraints, electric vehicle load constraints, and battery charge constraints to ensure its feasibility and accuracy in scenarios involving multiple vehicles, multiple tasks, and multiple charging stations. To efficiently solve the model, an optimization algorithm based on deep reinforcement learning (DRL) is designed. Specifically, for the problem of queueing and charging timing decisions, a dynamic decision-making algorithm using real-time information from charging stations is developed to reduce the difficulty of learning process of the DRL and improve the computational efficiency. Finally, the effectiveness of the proposed method is verified through multi-scale simulation experiments. The experimental results show that this method effectively optimizes the charging queuing time, reducing the average total driving time per vehicle by 0.14 hours; compared with various typical intelligent optimization algorithms, the comparison results show that the proposed method achieves an average reduction of 0.52 hours in travel time per vehicle and improves computational efficiency by 75.4%.
-
表 1 变量说明
Table 1. Variable description
变量 释义 C 客户点集合，$C={1, 2, \cdots, m}$ o 仓库点 D 仓库点和客户点集合，$D=C \bigcup o$ K 充电站点集合，$K=\{1,2, \cdots, n\}$ Z 所有点的集合，$Z=D \bigcup K$ $\lambda^{i}$ 节点i的配送需求，其中$i \in D$ V 电车集合$V=\left\{v^\eta \mid \eta=1,2, \cdots, u\right\}$ $d(i, j)$ 节点$i, j$ 的欧式距离 Q 电车的额定负载量 $E^{ \eta}$ 电车返回仓库所需充电量 $ \tau$ 电车充电效率 $p_{e}$ 充电接口功率 $e_{i}^{ \eta}$ 表示电车$ \eta$到达i节点的电量，$i \in Z$ $ \delta_{i j}^{ \eta}$ 0/1决策变量，1代表电车$ \eta$经过边$(i, j)$ ，否则为0，其中$i, j \in Z$ $ \theta^{ \eta}$ 0/1决策变量，1代表电车$ \eta$需要充电，否则为0 $T_{c}^{ \eta}$ 电车$ \eta$ 在充电站的总用时 $T_{w}$ 电车充电站等待时间 $T_{s}$ 所有电车的派送行驶时间之和 $l_{i j}^{ \eta}$ 电车$ \eta$离开客户点i到达客户点j 前的剩余负载，$i, j \in Z$ f 车辆速度 $C^{ \eta}$ 电车$ \eta$的消耗的总电量 
下载: 导出CSV
表 2 ECR参数值
Table 2. Parameter values of the ECR
符号 值 符号 值 ρ 1.293 αD βD γD 0.044 8，0.250 2，65.542 A 2.341 CD 375 Cd 0.23 PA PB 2000，180 W 2169 ϕ 2 g 9.81 α 0 Cr 0.013 M 0~1200
下载: 导出CSV
表 3 总平均行驶时间
Table 3. Average total travel time
算法 20算例 30算例 50算例 ACO-CQD 9.676 13.04 16.36 DE-CQD 9.252 14.16 17.57 DPSO-CQD 9.72 14.9 17.89 DQSP-CQD 10.12 15.18 18.24 GA-CQD 9.74 14.76 18.35 DQL-CQD 9.18 12.78 15.55
下载: 导出CSV
表 4 算法平均运行时间
Table 4. Average algorithm runtime
算法 20算例 30算例 50算例 ACO-CQD 4.81 6.02 6.31 DE-CQD 4.55 5.79 9.98 DPSO-CQD 4.70 6.28 10.26 DQSP-CQD 5.34 5.34 11.33 GA-CQD 4.25 6.58 10.52 DQL-CQD 1.48 1.52 1.65
下载: 导出CSV
表 5 不同速度和电池容量下的平均总行驶时间
Table 5. Average total travel time of different speeds and battery capacities
速度（km/h） CB = 55 kW·h DRL - CQD CB = 55 kW·h DRL - wi th out - CQD CB = 65 kW·h DRL - CQD CB = 65 kW·h DRL - wi th out - CQD 20 30 50 20 30 50 20 30 50 20 30 50 45 8.36 11.51 13.82 8.45 11.74 14.33 8.14 11.13 13.47 8.28 11.54 14.06 50 7.49 10.31 12.58 7.57 10.52 12.81 7.31 10.19 12.37 7.45 10.31 12.58 60 6.32 8.74 10.56 6.47 8.96 10.87 6.61 8.58 10.21 6.71 8.73 10.51
下载: 导出CSV
-
[1] 朱成, 刘頔, 滕欣余, 等. 新能源汽车综合经济性对比分析及预测研究[J]. 汽车工程, 2023, 45(2): 333-340.ZHU C, LIU D, TENG X Y, et al. Comparative analysis and forecasting research on the comprehensive economic performance of new energy vehicles[J]. Automotive Engineering, 2023, 45(2): 333-340. (in Chinese) [2] 聂小虎, 田伦, 潘晓锋, 等. 公路交通基础设施绿色化水平评价指标权重计算方法[J]. 交通信息与安全, 2024, 42(5): 54-62. doi: 10.3963/j.jssn.1674-4861.2024.05.006NIE X H, TIAN L, PAN X F, et al. Calculation method for weights of evaluation indicators of greening level of road traffic infrastructure[J]. Journal of Transport Information and Safety, 2024, 42(5): 54-62. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2024.05.006 [3] 胡杰, 朱琪, 陈锐鹏, 等. 引入必经点约束的智能汽车全局路径规划[J]. 汽车工程, 2023, 45(3): 350-360.HU J, ZHU Q, CHEN R P, et al. Global path planning of intelligent vehicles with mandatory waypoint constraints[J]. Automotive Engineering, 2023, 45(3): 350-360. (in Chinese) [4] CONRAD R G, FIGLIOZZI M A. The recharging vehicle routing problem[C]. Industrial Engineering Research Conference, Reno, ⅡSE Norcross, GA, 2011. [5] 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. doi: 10.1287/trsc.2013.0490 [6] 揭婉晨, 杨珺, 陆坚毅. 基于分支定价算法的电车车辆路径问题[J]. 运筹与管理, 2016, 25(4): 93-100.JIE W C, YANG J, LU J Y. Electric vehicle routing problem based on branch-and-price algorithm[J]. Operations Research and Management, 2016, 25(4): 93-100. (in Chinese) [7] 葛显龙, 李祖伟, 葛小波. 考虑灵活充电策略的带时间窗物流配送路径优化研究[J]. 控制理论与应用, 2020, 37(6): 1293-1301.GE X L, LI Z W, GE X B. Logistics distribution route optimization with time windows considering flexible charging strategy[J]. Control Theory and Applications, 2020, 37(6): 1293-1301. (in Chinese) [8] KESKIN M, ÇATAY B. A matheuristic method for the electric vehicle routing problem with time windows and fast chargers[J]. Computers & Operations Research, 2018, 100: 172-188. [9] 程坦, 陈鹏, 张国伟, 等. 部分充电策略下的多车型电车车辆路径优化问题研究[J]. 交通运输工程与信息学报, 2022, 20(2): 105-114.CHENG T, CHEN P, ZHANG G W, et al. Research on multi-vehicle electric vehicle routing optimization with partial charging Strategy[J]. Journal of Transportation Engineering and Information, 2022, 20(2): 105-114. (in Chinese) [10] LIU, H M, YIN W Q, NIU M. Reserving charging decision-making model and route plan for electric vehicles considering information of traffic and charging station[J]. Sustainability, 2018, 10(5): 1324. doi: 10.3390/su10051324 [11] WANG Y X, BI J, LU C R, et al. Route guidance strategies for electric vehicles by considering stochastic charging demands in a time-varying road network[J]. Energies, 2020, 13 (9): 2287. doi: 10.3390/en13092287 [12] 葛显龙, 李婷, 王博, 等. 考虑负效应最小化的电车补能诱导研究[J]. 交通运输系统工程与信息, 2022, 22(3): 74-83, 111.GE X L, LI T, WANG B, et al. Research on energy replenishment guidance for electric vehicles considering minimization of negative effects[J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(3): 74-83, 111. (in Chinese) [13] 毕军, 杜宇佳, 王永兴, 等. 基于用户综合满意度的电车充电诱导优化模型[J]. 清华大学学报(自然科学版), 2023, 63(11): 1750-1759.BI J, DU Y J, WANG Y X, et al. Optimization model for electric vehicle charging guidance based on comprehensive user satisfaction[J]. Journal of Tsinghua University(Science and Technology), 2023, 63(11): 1750-1759. (in Chinese) [14] 张建华, 南莹. 交通信息影响下的电动汽车充电路线规划[J]. 计算机应用, 2016, 36(2): 282-285.ZHANG J, NAN Y. Electric vehicle charging route planning under the influence of traffic information[J]. Computer Applications, 2016, 36(2), 282-285. (in Chinese) [15] 张书玮, 冯桂璇, 樊月珍, 等. 基于信息交互的大规模电车充电路径规划[J]. 清华大学学报(自然科学版), 2018, 58 (3): 279-285.ZHANG S W, FENG G X, FAN Y Z, et al. Large-scale electric vehicle charging path planning based on information interaction[J]. Journal of Tsinghua University (Science and Technology), 2018, 58(3): 279-285. (in Chinese) [16] 赵姣, 杨倩倩, 胡大伟, 等. 基于排队模型的电车充电站选址和运输路径问题[J]. 山东大学学报(工学版), 2024, 54 (2): 47-59.ZHAO J, YANG Q, HU D W, et al. Location and transportation routing problem of electric logistics vehicle charging stations based on queuing model[J]. Journal of Shandong University(Engineering Edition), 2024, 54(2): 47-59. (in Chinese) [17] 庞燕, 罗华丽, 邢立宁, 等. 车辆路径优化问题及求解方法研究综述[J]. 控制理论与应用, 2019, 36(10): 1573-1584.PANG Y, LUO H L, XING L N, et al. Research review on vehicle routing problem and solution methods[J]. Control Theory and Applications, 2019, 36(10): 1573-1584. (in Chinese) [18] XIAO Y, ZHANG Y, KAKU I, et al. Electric vehicle routing problem: A systematic review and a new comprehensive model with nonlinear energy recharging and consumption[J]. Renewable and Sustainable Energy Reviews, 2021 151: 111567. doi: 10.1016/j.rser.2021.111567 [19] WILLIAMS R J. Simple statistical gradient-following algorithms for connectionist reinforcement learning[J]. Machine Learning, 1992, 8(3): 229-256. [20] 王愚勤, 胡卉, 刘富鑫, 等. 智能网联下无人车配送路径优化[J]. 运筹与管理, 2021, 30(8): 52-58.WANG Y Q, HU H, LIU F X, et al. Optimization of delivery routes for unmanned vehicles in intelligent networks[J]. Operations Research and Management, 2021, 30(8): 52-58. (in Chinese) [21] KANCHARLA S R, RAMADURAI G. Electric vehicle routing problem with non-linear charging and load-dependent discharging[J]. Expert Systems with Applications, 2020, 160: 113714. doi: 10.1016/j.eswa.2020.113714 -
点击查看大图
图(10) / 表(5)
计量
- 文章访问数: 5
- HTML全文浏览量: 2
- PDF下载量: 2
- 被引次数: 0