, 左小龙11. 北京交通大学 交通运输学院, 北京 100044;
2. 北京交通大学 综合交通运输大数据应用技术交通运输行业重点实验室, 北京 100044
收稿日期：2022-12-29
基金项目：国家自然科学基金面上项目(72171019);北京交通大学人才基金项目(2023JBRC006)
作者简介：毕军(1973—), 男, 教授
通讯作者：王永兴, 讲师, E-mail: yx.wang@bjtu.edu.cn
摘要：随着电动汽车(electric vehicle, EV)在城市交通系统不断普及, 充电诱导服务成为在充电设施有限条件下解决充电问题的有效手段。在分析电动汽车用户充电满意度的基础上, 提出一种综合用户绕行距离、排队时间和充电费用的电动汽车充电诱导优化模型。为准确推导用户在充电站的排队时间, 充分考虑电动汽车用户充电站选择决策的相互影响, 建立充电站运营状态预测模型。针对模型特点, 结合免疫算法求解模型。通过面向多充电请求的优化算例验证模型的可行性和有效性, 结果表明：通过求解模型可以获得用户综合满意度最大化情况下的用户最优充电站决策及其行驶路径; 与绕行距离最小、排队时间最短和充电费用最少等单目标优化方案相比, 所提模型的充电诱导方案的用户综合满意度分别提升了15.0%、17.8%和11.4%。
关键词：电动汽车充电诱导路径规划用户综合满意度免疫算法
Optimization model of electric vehicle charging induction based on comprehensive satisfaction of users
BI Jun1,2, DU Yujia1, WANG Yongxing1
, ZUO Xiaolong11. School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China;
2. Key Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Beijing Jiaotong University, Beijing 100044, China
Abstract: [Objective] With the increasing prevalence of electric vehicles (EVs) in urban transportation systems, charging guidance service has become an effective means to solve the charging problem in the context of insufficient charging infrastructure. However, for optimizing the charging station selection decision-making plan of users, most existing research studies aim to minimize travel costs, which rarely considers the charging experience of users during travel and ignores the interaction of charging station selection decision-making between multiple users. To enhance the charging experience of users, based on the analysis of charging satisfaction of EV users, an EV charging guidance optimization model that integrates user satisfaction with detour distance, queuing time, and charging cost is proposed in this study. The model aims to maximize the average comprehensive satisfaction of multiple users. [Methods] To quantify the comprehensive satisfaction of users with charging stations during charging processes, evaluation indicators of detour distance, queuing time, and charging cost are constructed. To accurately deduce the queuing time of users at charging stations, this study fully considers the interaction influence of charging station selection decision-making between multiple EV users. Prediction models of the charging station operation state are established by considering several charging scenarios based on the arrival patterns of two successive users. According to the characteristics of the proposed model, an immune algorithm and the Floyd shortest path algorithm are applied to optimize the decision-making plan of charging station selections and the travel paths of multiple users, respectively. A numerical example with multiple charging requests is designed to confirm the feasibility and effectiveness of the proposed model and the algorithms. [Results] The experimental results indicated that optimal charging station selections and driving paths of multiple EVs to maximize average comprehensive satisfaction could be obtained by solving the optimization model. Compared with models with single optimization objectives, namely, minimum detour distance, shortest queuing time, and least charging cost, the average comprehensive satisfaction of EV users was increased by 15.0%, 17.8%, and 11.4%, respectively. The results also showed that average driving speed was a critical factor affecting optimal charging station selection and average comprehensive satisfaction of EV users. By analyzing the arrival patterns of two successive users at the same charging station under different charging scenarios, their queuing time after arriving at the charging station could be accurately obtained. Subsequently, optimal charging station selections by multiple users could be determined by considering the interaction that influences their selections. [Conclusions] The proposed optimization model provides multiple EV users with decision-making support for selecting charging stations by considering their interaction influences. Provided that the threshold values of each satisfaction indicator remain unchanged, the comprehensive average satisfaction obtained by the proposed model is considerably higher than that obtained by models with single objectives: minimum detour distance, shortest queuing time, and least charging cost. Thus, the proposed method can enhance the charging experience of EV users during travel.
Key words: electric vehiclecharge inductionpath planningcomprehensive satisfaction of usersimmune algorithm
电动汽车(electric vehicle，EV)具有节能环保的优势，已逐渐成为人们出行的主要代步工具之一。由于存在充电基础设施不足、充电站布局不合理等问题，电动汽车用户的充电服务便利化程度仍有待提升[1-3]。在智能交通不断发展的背景下，电动汽车充电诱导服务成为解决充电难题的主要手段。充电诱导服务可为电动汽车用户推荐最优的充电站并规划相应的路径方案，因此，如何高效地设计充电诱导方法成为当前的研究热点。充电诱导服务不仅要保证所推荐充电站的可达性，还要考虑用户的充电体验，引导用户顺利、高效地完成充电，提升用户综合满意度。
针对电动汽车充电诱导问题，国内外****从多样化优化目标的角度研究了车辆路径规划方法。Guo等[4]以出行时间、出行距离、能耗、充电成本为优化目标，建立了考虑电动汽车电力供应的出行路径规划模型；Keskin等[5]以总充电成本为优化目标，建立了考虑不同类型充电桩配置下的路径优化模型；Zhou等[6]在考虑电网负载限制的前提下，建立了以出行时间、充电能量、充电费用和充电便利性为优化目标的路径规划模型；Liu等[7]基于充电站的交通信息，建立了预留充电决策的路径优化模型，目标是使充电费用和出行时间最少。上述研究未考虑多样化出行场景影响，鉴于此，部分****从多样化出行场景的角度出发，研究了车辆路径规划问题。Wang等[8]基于时变的道路交通网络，建立了具有动态充电请求特点的出行路径优化模型，目标是使出行距离最小；Basso等[9]考虑时间窗约束对出行路径选择的影响，建立了以能耗为优化目标的出行路径规划模型；Wang等[10]考虑电动汽车的随机行驶状态，建立了面向出行时间、充电费用和出行距离的多目标出行路径优化模型；Zhang等[11]以总出行时间为优化目标，建立了车辆在部分充电场景下的路径规划模型。
综上所述，现有研究主要集中于多目标、多场景下的电动汽车出行路径规划，而很少考虑电动汽车用户充电站选择决策的相互影响。随着电动汽车规模不断扩大，电动汽车用户大量增加，电动汽车用户在选择适宜的充电站为车辆充电时需要承受更高的成本，因此，如何在考虑多充电请求相互影响的情况下为多辆电动汽车提供充电站选择及其行驶路径至关重要。本文针对多用户充电决策间相互影响的路径规划问题，构建了一种以用户综合满意度最大化为目标的电动汽车充电诱导优化模型，并设计免疫算法求解该模型。研究结果可以为电动汽车用户的出行过程提供最优充电站决策信息，帮助用户在选择出行路线的同时决定充电计划，进而为实现智能化充电诱导服务提供决策支持。
1 用户综合满意度指标时间和费用成本是影响用户出行方案选择的主要因素。其中，时间成本主要受车辆行驶时间和充电时间影响，费用成本来源于充电费用。因此，本文以绕行距离、排队时间和充电费用这3个满意度指标构建用户综合满意度函数刻画用户充电体验，并以此为基础为用户分配最优充电站。
1.1 绕行距离绕行距离是指用户为车辆充电而改变原行驶路径时额外行驶的距离。用户行驶时间与绕行距离直接相关，绕行距离越长，用户行驶时间越长，因此，绕行距离是影响用户充电方案选择的重要因素。用户i的绕行距离
| $\begin{gathered}\bar{\delta}_i^{o d}=\delta_i^{o d}-\delta_i^{o d^{\prime}}, \end{gathered}$ | (1) |
| $\delta_i^{o d}=\delta_i^{o j}+\delta_i^{j d} .$ | (2) |
1.2 排队时间电池荷电状态(state of charge, SOC)指电池当前电量与最大容量的比值。假设不考虑动态路网，那么i从o到j的行驶时间tioj和i到达j时的剩余SOC Eijre分别表示如下：
| $\begin{gathered}t_i^{o j}=\frac{\delta_i^{o j}}{v}, \end{gathered}$ | (3) |
| $E_{i j}^{\mathrm{re}}=E_i-\frac{\delta_i^{o j}}{\theta E} .$ | (4) |
因为充电服务调度平台在实际生活中一般存在多个，且部分用户车辆不需要借助充电服务调度平台选择充电站，所以某一区域内的用户车辆不会全部选择同一个充电服务调度平台接受充电调度服务，本文将不由某充电服务调度平台调度的用户车辆统称为外部车辆。电动汽车的充放电过程在特定SOC区间是线性的，如20%~80%范围; 同时为保护电池，避免过充过放，用户会在电池电量完全耗尽前进行充电，并在电池电量完全充满前停止充电。本文采用文[10]关于外部车辆起始和结束充电时电量均值的假设，即外部车辆充电起始电量均值Er=0.2E，充电结束电量均值Ee=0.8E，平均充电量
集合Uj={u1, u2, …, uz}表示先后到达同一充电站j的待分配用户，即u1表示第1个到达充电站的待分配用户，以此类推，uz表示最后1个到达充电站的待分配用户。因此，2个相邻待分配用户的充电场景可分为以下3种：1) 后者到达充电站时，前者已完成充电并离开；2) 后者到达充电站时，前者正在排队等待充电；3) 后者到达充电站时，前者正在接受充电服务。以下是预测每个充电站u1的排队时间的过程。
假设j的车辆到达率λj服从Poisson分布，j内充电桩数量为hj，每个充电桩的功率为pj，u1从o到j的行驶时间为t1oj，则t1oj内到达j的车辆数N1, jA表示如下：
| $N_{1, j}^{\mathrm{A}}=\lambda_j t_1^{o j} .$ | (5) |
| $E_{1, j k}=p_j t_1^{o j} .$ | (6) |
| $\begin{gathered}N_{1, j k}^{\mathrm{L}}=\operatorname{INT}\left(\frac{E_{1, j k}+C_{j k}^0 E-E_{\mathrm{e}}}{\bar{E}}\right)+1, \end{gathered}$ | (7) |
| $N_{1, j}^{\mathrm{L}}=\sum\limits_{k=1}^{h_j} N_{1, j k}^{\mathrm{L}} .$ | (8) |
当u1到达j时，充电站内的车辆数N1, j及k上正在充电车辆的SOC C1, jk分别表示如下：
| $\begin{aligned} N_{1, j}=\max \left\{0, N_j^0+N_{1, j}^{\mathrm{A}}-N_{1, j}^{\mathrm{L}}\right\}, \end{aligned}$ | (9) |
| $C_{1, j k}=\left(E_{1, j k}+C_{j k}^0 E-N_{1, j k}^{\mathrm{L}} \bar{E}\right) / E .$ | (10) |
下一步预测u1的排队时间。当N1, j＜hj时，充电站有充电桩处于空闲状态，u1到达后可直接充电；当N1, j≥hj时，充电站无充电桩处于空闲状态，u1需排队等待充电，其排队时间预测如下。
将C1, j中的元素降序排列后得到新集合C′1, j。由于C1, jk越大的充电桩会越快完成对当前车辆的充电服务，因此将C1, j中的元素降序排列后，排队车辆将按照C′1, j中充电桩的标号顺序依次进行充电。假设u1到C′1, j中充电桩q充电，相关计算表示如下：
| $q=\operatorname{MOD}\left(\frac{N_{1, j}}{h_j}\right)+1$ | (11) |
u1的排队时间t1, jw为其到达充电站时，站内已有车辆选择到q接受服务的充电时间总和，表示如下：
| $t_{1, j}^{\mathrm{w}}=\frac{E_{\mathrm{e}}-C_{1, j q} E}{p_j}+\frac{\left(\operatorname{INT}\left(N_{1, j} / h_j\right)-1\right) \bar{E}}{p_j} .$ | (12) |
若集合Uj中某一用户i(非u1)先到达j，那么其排队时间tijw、充电时间tijc、到达j时各充电桩上正在充电车辆的SOC Cijk和q是已知的，以及j内已有车辆数Nij和tioj内完成充电并离开j的车辆数NijL也是已知的。
用b表示紧邻i后到达j的用户，则b到达j时，j内的车辆数Nbj表示如下：
| $N_{b j}=\max \left\{0, N_j^0+N_{b j}^{\mathrm{A}}-N_{b j}^{\mathrm{L}}\right\}, $ | (13) |
| $N_{b j}^{\mathrm{A}}=\lambda_j t_b^{o j}+n_i .$ | (14) |
用ti表示i与b到达j的时间差，则b到达j时j的运营状态及b的排队时间预测如下：
1) 前者已完成充电并离开。
当ti＞tijw+tijc时，说明当b到达j时，i已完成充电并离开。假设t为b到达j与i离开j的时间差，t=ti-tijw-tijc，则NbjL表示如下：
| $N_{b j}^{\mathrm{L}}=N_{i j}^{\mathrm{L}}+N_{i j}^{\mathrm{wL}}+N_{i j}^{\mathrm{cL}}+N_{b j}^{t \mathrm{~L}} .$ | (15) |
当Nij＜hj时，NijwL=0，否则，NijwL的计算表示如下：
| $N_{ij}^{{\rm{wL}}} = \sum\limits_{k{\rm{ }} = 1}^{{h_j}} {N_{ijk}^{{\rm{wL}}}} ;$ | (16) |
| $\begin{aligned}N_{ijk}^{\operatorname{wL}}=\left\{ \begin{array}{l}\operatorname{IN}\operatorname{T}\Big(\frac{N_{ij}}{h_j}\Big),\quad C_{ijk}\geqslant C_{ijq};\\\operatorname{INT}\Big(\frac{N_{ij}}{h_j}\Big)-1,\quad C_{ijk} <C_{ijq}.\end{array} \right.\end{aligned}$ | (17) |
i刚开始充电时，k上正在充电车辆的SOC Cijkc表示如下：
| $C_{i j k}^{\mathrm{c}}= \begin{cases}E_{i j}^{\mathrm{re}}, & k=q ; \\ \frac{E_{i j k}^{\mathrm{w}}+C_{i j k} E-N_{i j k}^{\mathrm{wL}} \bar{E}}{E}, & k \neq q ;\end{cases}$ | (18) |
| $E_{i j k}^{\mathrm{w}}=p_j t_{i j}^{\mathrm{w}} .$ | (19) |
tijc内离开k的车辆数NijkcL和NijcL分别表示如下：
| $N_{i j k}^{\mathrm{cL}}= \begin{cases}1, & k=q ; \\ \operatorname{INT}\left(\frac{E_{i j k}^{\mathrm{c}}+C_{i j k}^{\mathrm{c}} E-E_{\mathrm{e}}}{\bar{E}}\right)+1, & k \neq q ;\end{cases}$ | (20) |
| $N_{i j}^{\mathrm{cL}}=\sum\limits_{k=1}^{h_j} N_{i j k}^{\mathrm{cL}} ; $ | (21) |
| $\begin{gathered}E_{i j k}^{\mathrm{c}}=p_j t_{i j}^{\mathrm{c}} .\end{gathered}$ | (22) |
i完成充电并离开时，k上正在充电车辆的SOC CijkL表示如下：
| $C_{i j k}^{\mathrm{L}}= \begin{cases}E_{\mathrm{r}}, & k=q ; \\ \frac{E_{i j k}^{\mathrm{c}}+C_{i j k}^{\mathrm{c}} E-N_{i j k}^{\mathrm{cL}} \bar{E}}{E}, & k \neq q .\end{cases}$ | (23) |
| $N_{b j k}^{t \mathrm{~L}}=\mathrm{INT}\left(\frac{E_{b j k}^t+C_{i j k}^{\mathrm{L}} E-E_{\mathrm{e}}}{\bar{E}}\right)+1, $ | (24) |
| $N_{b j}^{t \mathrm{~L}}=\sum\limits_{k=1}^{h_j} N_{b j k}^{t \mathrm{~L}}, $ | (25) |
| $\begin{gathered}E_{b j k}^t=p_j t .\end{gathered}$ | (26) |
b到达j时，k上正在充电车辆的SOC Cbjk表示如下：
| $C_{b j k}=\frac{E_{b j k}^t+C_{i j k}^{\mathrm{L}} E-N_{b j k}^{t \mathrm{~L}} \bar{E}}{E} .$ | (27) |
下一步预测b的排队时间，其方法与预测u1的排队时间一样，用Cbj代替C1, j、Nbj代替N1, j即可，不再赘言。
2) 前者正在排队等待充电。
当0＜ti＜tijw时，说明b到达j时，i仍在排队等待充电。NbjL表示如下：
| $N_{b j}^{\mathrm{L}}=N_{i j}^{\mathrm{L}}+N_{b j}^{t_i \mathrm{~L}}, $ | (28) |
| $N_{b j}^{t_i \mathrm{~L}}=\sum\limits_{k=1}^{h_j} N_{b j k}^{t_i \mathrm{~L}}, $ | (29) |
| $\begin{gathered}N_{b j k}^{t_i \mathrm{~L}}=\mathrm{INT}\left(\frac{E_{b j k}^{t_i}+C_{i j k} E-E_{\mathrm{e}}}{\bar{E}}\right)+1 .\end{gathered}$ | (30) |
此场景下，Cijkc的计算同式(18)，NijwL和NijkwL的计算同式(16)和(17)，Cbjk表示如下：
| $C_{b j k}=\frac{E_{b j k}^{t_i}+C_{i j k} E-N_{b j k}^{t_i \mathrm{~L}} \bar{E}}{E} .$ | (31) |
下一步预测b的排队时间。将集合Cijc中的元素降序排列并得到新集合Cijc′。由于Cijkc越大的充电桩会越早完成对当前车辆的充电服务，因此排队车辆将按照集合Cijc′中充电桩的标号顺序依次充电。假设b到集合Cijc′中标号为q′的充电桩充电，则q′表示如下：
| $\begin{gathered}q^{\prime}=\operatorname{MOD}\left(N_{i b}^{\mathrm{c}} / h_j\right)+1, \end{gathered}$ | (32) |
| $N_{i b}^{\mathrm{c}}=\operatorname{INT}\left(\lambda_j t_i\right)+h_j .$ | (33) |
b到达j后，b的排队时间tbjw为tijw与i开始充电后排在b前并选择到q′充电的车辆充电时间之和，即
| $t_{b j}^{\mathrm{w}}=\frac{E_{\mathrm{e}}-C_{i j q^{\prime}}^{\mathrm{c}} E}{p_j}+\frac{\left(\operatorname{INT}\left(\frac{N_{i b}^{\mathrm{c}}}{h_j}\right)-1\right) \bar{E}}{p_j}+t_{i j}^{\mathrm{w}}-t_i .$ | (34) |
当tijw <ti < tijw+tijc时，说明b到达j时，i正在接受充电服务。设t′为b到达充电站时i已充电的时间，t′=ti-tijw，则NbjL表示如下：
| $N_{b j}^{\mathrm{L}}=N_{i j}^{\mathrm{L}}+N_{i j}^{\mathrm{wL}}+N_{b j}^{t^{\prime} \mathrm{L}}, $ | (35) |
| $N_{b j}^{t^{\prime} \mathrm{L}}=\sum\limits_{k=1}^{h_j} N_{b j k}^{t^{\prime} \mathrm{L}}, $ | (36) |
| $\begin{gathered}N_{b j k}^{t^{\prime} \mathrm{L}}=\operatorname{INT}\left(\frac{E_{b j k}^{t^{\prime}}+C_{i j k}^{\mathrm{c}} E-E_{\mathrm{e}}}{\bar{E}}\right)+1 .\end{gathered}$ | (37) |
当b到达j时，k上正在充电车辆的SOC表示如下：
| $C_{b j k}=\left(E_{b j k}^{t^{\prime}}+C_{i j k}^{\mathrm{c}} E-N_{b j k}^{t^{\prime} \mathrm{L}} \bar{E}\right) / E .$ | (38) |
下一步预测b的排队时间，其方法与预测u1的排队时间相同，用Cbj代替C1, j、Nbj代替N1, j即可，不再赘言。
1.3 充电费用电动汽车的充电费用包括电费、服务费和停车费。假设j的单位电费、服务费、停车费分别为mjel(元/(kW·h))、mjse(元/(kW·h))、mjpa(元/min)，则i在j充电所花费的电费Mijel、服务费Mijse、停车费Mijpa分别表示如下：
| $M_{i j}^{\mathrm{el}}=m_j^{\mathrm{el}}\left(E_{\mathrm{e}}-E_{i j}^{\mathrm{re}}\right), $ | (39) |
| $M_{i j}^{\mathrm{se}}=m_j^{\mathrm{se}}\left(E_{\mathrm{e}}-E_{i j}^{\mathrm{re}}\right), $ | (40) |
| $\begin{aligned} M_{i j}^{\mathrm{pa}}=m_j^{\mathrm{pa}}\left(t_{i j}^{\mathrm{w}}+t_{i j}^{\mathrm{c}}\right) .\end{aligned}$ | (41) |
| $M_{i j}^{\mathrm{c}}=M_{i j}^{\mathrm{el}}+M_{i j}^{\mathrm{se}}+M_{i j}^{\mathrm{pa}} .$ | (42) |
| $f_{i j}(y)= \begin{cases}1, & y <\varOmega_y^{\mathrm{do}} ; \\ \frac{1}{2}+\frac{1}{2} \cos \left(\frac{\pi\left(y-\frac{\varOmega_y^{\mathrm{do}}+\varOmega_y^{\text {up }}}{2}\right)}{\varOmega_y^{\mathrm{do}}-\varOmega_y^{\text {up }}}+\frac{\pi}{2}\right), & \varOmega_y^{\mathrm{do}} \leqslant y \leqslant \varOmega_y^{\text {up }} ; \\ 0, & y>\varOmega_y^{\text {up }} .\end{cases}$ | (43) |
由式(43)可得到i对j绕行距离、排队时间及充电费用的满意度fijD、fijT、fijR，i对j的综合满意度fij表示如下：
| $f_{i j}=\alpha f_{i j}^{\mathrm{D}}+\beta f_{i j}^{\mathrm{T}}+\gamma f_{i j}^{\mathrm{R}} .$ | (44) |
2 充电诱导优化模型在保证每辆待分配电动汽车发出充电请求时的剩余电量都能及时到达充电站的前提下，本文充分考虑待分配用户充电决策的相互影响，提出使待分配用户综合满意度最大化的充电诱导优化模型，并使用免疫算法求解用户的最优充电站决策。
2.1 目标函数本文的目标函数是最大化待分配用户的综合满意度。假设路网中存在τ个待分配用户和?个充电站，则目标函数F表示如下：
| $F=\max \frac{\sum\limits_{i=1}^\tau \sum\limits_{j=1}^\phi f_{i j} x_{i j}}{\tau}$ | (45) |
2.2 约束条件
| $\begin{gathered}E_i E-\frac{\delta_i^{o j} x_{i j}}{\theta} \geqslant 0, \end{gathered}$ | (46) |
| $E_{\mathrm{e}} E-\frac{\delta_i^{j d} x_{i j}}{\theta} \geqslant 0, $ | (47) |
| $N_{i j}+x_{i j} \leqslant Q_j, $ | (48) |
| $\sum\limits_{j=1}^\phi x_{i j}=1, $ | (49) |
| $x_{i j} \in\{0, 1\} .$ | (50) |
3 算法求解基于用户综合满意度的电动汽车充电诱导优化模型属于非确定性多项式难题(non-deterministic polynomial-hard，NP-hard)，可以通过免疫算法获得最优解[15]。免疫算法克服了一般寻优过程易陷入局部最优解的缺点，能够保持解群分布多样性。本文结合该充电诱导问题的特点设计了算法流程，通过求解模型可以得到充电诱导的最优方案，算法流程如图 1所示。
 |
| 图 1 考虑用户综合满意度的充电诱导模型算法流程 |
| 图选项 |
3.1 抗体编码本文将每个用户所选充电站的整数编号视为1个基因，则每条抗体的基因数量等于网络中待分配用户数量。假设路网中存在7个待分配用户和4个充电站，则种群中的1条抗体[1, 2, 3, 1, 2, 3, 4]表示7个待分配用户分别选择编号为1、2、3、1、2、3、4的充电站接受充电服务。
3.2 解的评价1) 抗体浓度。
抗体浓度Gσ为抗体σ占种群全部抗体的相似比例，表示如下：
| $\begin{gathered}G_\sigma=\frac{\sum\limits_{\mu=1}^H S_{\sigma, \mu}^{\prime}}{H}, \end{gathered}$ | (51) |
| $\begin{gathered}S_{\sigma, \mu}^{\prime}= \begin{cases}1, & S_{\sigma, \mu}>\varepsilon ; \\0, & S_{\sigma, \mu} \leqslant \varepsilon .\end{cases}\end{gathered}$ | (52) |
2) 期望繁殖率。
σ的期望繁殖率Pσ由其与抗原间的亲和度Sσ(即目标函数值)和Gσ共同决定，表示如下：
| $P_\sigma=\omega \frac{S_\sigma}{\sum\limits_{\mu=1}^H S_\mu}+(1-\omega) \frac{G_\sigma}{\sum\limits_{\mu=1}^H G_\mu} .$ | (53) |
3.3 种群更新1) 交叉。
使用两点交叉法实现交叉操作，先对抗体进行两两分组，再随机产生2个整数并将位于整数区间内的基因互换。抗体交叉操作如图 2所示。
 |
| 图 2 抗体交叉操作 |
| 图选项 |
2) 变异。
使用两点互换法实现变异操作，先使用随机函数产生2个整数，再将抗体对应整数位置的基因交换。抗体变异操作如图 3所示。
 |
| 图 3 抗体变异操作 |
| 图选项 |
为保证每条抗体对应的充电诱导方案能完全满足模型的约束条件，每次迭代前对抗体进行检查操作。若抗体不满足任一约束，则亲和度为0；否则，亲和度为其真实计算结果。
4 算例分析本节设计的数值算例是1个存在多充电请求、考虑外部车辆影响的用户充电站选择决策方案优化及路径规划问题，目标是最大化用户综合满意度。交通路网由29个节点和45条双向路段组成，线段上的数字表示每条路段的权值(km)，图 4给出了具体的路网结构。路网中存在9个待分配充电车辆和5个充电站，其中，车辆的出发地节点分别为1、7、8、13、20、21、23、25、26，其目的地分别对应节点11、16、19、24、2、29、6、27、10；充电站节点分别为4、9、14、17、28。假设9个待分配用户同时发出充电请求，且其出发时的剩余SOC分别为0.38、0.30、0.31、0.35、0.42、0.32、0.36、0.34、0.35。表 1给出了充电站初始车辆数、充电桩数量等静态信息，表 2为充电站各充电桩初始充电状态。假设E=24 kW·h，v=42 km/h，θ=5.8 km/(kW·h)。基于用户偏好，通过模糊层次分析法获得的3项满意度指标权重系数分别为α=0.2、β=0.5、γ=0.3。
 |
| 图 4 交通路网结构 |
| 图选项 |
表 1 充电站静态信息
| 参数 | 充电站节点 | ||||
| 4 | 9 | 14 | 17 | 28 | |
| Nj0/辆 | 3 | 12 | 5 | 11 | 5 |
| hj/个 | 3 | 8 | 4 | 8 | 4 |
| λj/(辆·min-1) | 0.10 | 0.15 | 0.11 | 0.15 | 0.11 |
| pj/(kW·h·min-1) | 0.53 | 0.57 | 0.53 | 0.50 | 0.47 |
| mjel/(元·(kW·h)-1) | 1.27 | 1.27 | 1.27 | 1.27 | 1.27 |
| mjse/(元·(kW·h)-1) | 0.60 | 0.90 | 0.90 | 0.90 | 0.70 |
| mjpa/(元·min-1) | 0.06 | 0.06 | 0.06 | 0.06 | 0.18 |
| Qj/辆 | 15 | 18 | 16 | 18 | 16 |
表选项
表 2 充电站各充电桩初始充电状态
| 充电站节点 | 充电桩标号 | Cjk0 |
| 4 | 1 | 0.41 |
| 2 | 0.62 | |
| 3 | 0.52 | |
| 9 | 1 | 0.17 |
| 2 | 0.19 | |
| 3 | 0.18 | |
| 4 | 0.16 | |
| 5 | 0.26 | |
| 6 | 0.27 | |
| 7 | 0.20 | |
| 8 | 0.22 | |
| 14 | 1 | 0.53 |
| 2 | 0.60 | |
| 3 | 0.36 | |
| 4 | 0.55 | |
| 17 | 1 | 0.27 |
| 2 | 0.37 | |
| 3 | 0.29 | |
| 4 | 0.21 | |
| 5 | 0.32 | |
| 6 | 0.25 | |
| 7 | 0.35 | |
| 8 | 0.18 | |
| 28 | 1 | 0.55 |
| 2 | 0.37 | |
| 3 | 0.52 | |
| 4 | 0.39 |
表选项
免疫优化算法的相关参数如下：迭代次数为100，种群大小为50，记忆细胞大小为10，交叉概率为0.9，变异概率为0.1，ε=6。表 3给出了绕行距离、排队时间及充电费用3个指标的满意度阈值。
表 3 满意度阈值
| 指标 | Ωydo | Ωyup |
| 绕行距离/km | 15 | 40 |
| 排队时间/min | 15 | 30 |
| 充电费用/元 | 20 | 50 |
表选项
本文利用免疫算法求解用户的最优充电站决策，图 5为免疫算法收敛曲线。可以看出，在迭代20次后算法收敛到最优解，最大用户综合满意度为0.753，算法得到的用户最优充电站选择方案为9、4、9、14、14、17、14、28、17。表 4给出了每个待分配用户的充电站选择及其最优出行路径。
 |
| 图 5 免疫算法收敛曲线 |
| 图选项 |
表 4 用户充电站选择及最优出行路径
| 出发地节点 | 最优出行路径 |
| 1 | 1—8—9(充电站)—10—11 |
| 7 | 7—4(充电站)—5—11—16 |
| 8 | 8—9(充电站)—13—18—19 |
| 13 | 13—14(充电站)—19—23—24 |
| 20 | 20—19—14(充电站)—10—9—6—2 |
| 21 | 21—17(充电站)—18—19—20—25—29 |
| 23 | 23—19—14(充电站)—10—9—6 |
| 25 | 25—24—28(充电站)—27 |
| 26 | 26—21—17(充电站)—12—13—14—10 |
表选项
表 5给出了各满意度指标阈值不变条件下，分别以绕行距离最小、排队时间最短、充电费用最少为单目标优化方案的用户综合满意度及充电站决策。结果表明，模型获得的充电诱导方案的用户综合满意度比绕行距离最小、排队时间最短和充电费用最少等单目标优化方案分别增加了15.0%、17.8%和11.4%。
表 5 单目标优化方案的用户综合满意度及充电站决策
| 单目标优化方案 | 用户综合满意度 | 最优充电站选择 |
| 绕行距离最小 | 0.603 | 9, 9, 14, 14, 17, 17, 14, 28, 17 |
| 排队时间最短 | 0.575 | 9, 4, 9, 14, 9, 9, 17, 14, 17 |
| 充电费用最少 | 0.639 | 4，4，9，14，14，17，14，14，17 |
表选项
算例中模型关键参数对用户综合满意度的影响如下：车辆平均行驶速度决定了待分配用户到达充电站时，站内已有的车辆数Nij；而Nij的大小决定了先后到达同一充电站的2个待分配用户的充电场景；充电场景不同会直接影响每个待分配用户的排队时间和充电费用，进而显著影响用户综合满意度。因此，本文选取v作为变量进行灵敏度分析，其他参数取值不变。表 6给出了平均行驶速度对用户充电站决策及满意度的影响。
表 6 平均行驶速度对用户充电站决策及满意度的影响
| | 用户综合满意度 | 最优充电站选择 |
| 36 | 0.715 | 9, 4, 17, 14, 14, 17, 14, 28, 17 |
| 39 | 0.717 | 9, 4, 9, 9, 14, 17, 14, 14, 17 |
| 42 | 0.753 | 9, 4, 9, 14, 14, 17, 14, 28, 17 |
| 45 | 0.729 | 9, 4, 9, 14, 14, 17, 14, 28, 17 |
| 48 | 0.738 | 9, 4, 9, 9, 14, 17, 14, 28, 17 |
| 51 | 0.751 | 9, 4, 9, 9, 14, 17, 14, 28, 17 |
| 54 | 0.741 | 9, 4, 9, 9, 14, 17, 14, 28, 17 |
| 57 | 0.731 | 9, 4, 9, 9, 14, 17, 14, 28, 17 |
| 60 | 0.752 | 9, 4, 9, 14, 14, 17, 14, 28, 17 |
| 63 | 0.764 | 9, 4, 9, 14, 14, 17, 14, 28, 17 |
表选项
从表 6可以看出，v显著影响用户综合满意度和最优充电站决策方案。当v∈[36, 45]km/h时，用户的最优充电站决策不变，综合满意度呈先上升后下降的变化趋势，这是因为在该区间内当v小幅增大时，待分配用户到达充电站时排队的外部车辆数减少，排队时间缩短，充电费用降低，用户综合满意度上升；当v再小幅增大时，待分配用户到达充电站时排队的外部车辆数增加，排队时间延长，充电费用增加，用户综合满意度下降。当v继续增大时，用户的最优充电站决策发生改变，这是因为用户采用新充电站决策方案时获得的综合满意度比保持原有决策方案更高。由于本文的优化目标是最大化用户综合满意度，因此用户会放弃原有方案，选择综合满意度更高的新充电站决策方案。
5 结论本文构建了以绕行距离、排队时间、充电费用为满意度评价指标，以用户综合满意度最大为优化目标的考虑用户充电决策间相互影响的充电诱导模型。采用了免疫优化算法求解该模型中待分配用户充电决策的最佳方案，结合算例获得了用户的最佳充电站决策及相应最优路径，并探究了平均行驶速度对用户综合满意度及充电站选择决策的影响。结果表明，各满意度指标阈值不变时，所提模型的充电诱导方案的用户综合满意度比绕行距离最小、排队时间最短和充电费用最少等单目标优化方案分别提升了15.0%、17.8%、11.4%。
研究发现，某个用户改变充电站选择决策会改变其他用户到达充电站时充电场景，进而影响其排队时间和充电费用。因此，通过优化用户的充电站选择决策方案，改变其到达充电站时的充电场景，可以提高用户的充电满意度。然而，本文仅研究了确定状态下的充电诱导问题，未考虑动态变化情况。因为在电动汽车的实际行驶过程中，其速度、能耗及路网状态都是动态变化的。如何根据动态要求合理优化用户的充电决策将是下一步研究的内容。
参考文献
| [1] | 张书玮, 冯桂璇, 樊月珍, 等. 基于信息交互的大规模电动汽车充电路径规划[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. DOI:10.16511/j.cnki.qhdxxb.2018.25.008 (in Chinese) |
| [2] | 杨珍珍, 高自友. 数据驱动的电动汽车充电站选址方法[J]. 交通运输系统工程与信息, 2018, 18(5): 143-150. YANG Z Z, GAO Z Y. Location method of electric vehicle charging station based on data driven[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(5): 143-150. (in Chinese) |
| [3] | 任其亮, 吴丽霞, 靳旭刚, 等. 电动汽车充电站分层递进式选址方法研究[J]. 重庆交通大学学报(自然科学版), 2018, 37(6): 121-126. REN Q L, WU L X, JIN X G, et al. Research on site selection of electric vehicle charging stations using analytical hierarchy process[J]. Journal of Chongqing Jiaotong University (Natural Science), 2018, 37(6): 121-126. DOI:10.3969/j.issn.1674-0696.2018.06.20 (in Chinese) |
| [4] | GUO D, LI C C, YAN W, et al. Optimal path planning method of electric vehicles considering power supply[J]. Journal of Central South University, 2022, 29(1): 331-345. DOI:10.1007/s11771-022-4924-x |
| [5] | 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. DOI:10.3969/j.issn.1001-3695.2018.01.036 |
| [6] | ZHOU Z, LIU Z T, SU H Y, et al. Intelligent path planning strategy for electric vehicles combined with urban electrified transportation network and power grid[J]. IEEE Systems Journal, 2022, 16(2): 2437-2447. DOI:10.1109/JSYST.2021.3075088 |
| [7] | LIU H M, YIN W Q, YUAN X L, et al. 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 |
| [8] | 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 |
| [9] | BASSO R, KULCSAR B, EGARDT B, et al. Energy consumption estimation integrated into the electric vehicle routing problem[J]. Transportation Research Part D: Transport and Environment, 2019, 69: 141-167. DOI:10.1016/j.trd.2019.01.006 |
| [10] | WANG Y X, BI J, GUAN W, et al. Optimising route choices for the travelling and charging of battery electric vehicles by considering multiple objectives[J]. Transportation Research Part D: Transport and Environment, 2018, 64: 246-261. DOI:10.1016/j.trd.2017.08.022 |
| [11] | ZHANG Y, ALIYA B, ZHOU Y T, et al. Shortest feasible paths with partial charging for battery-powered electric vehicles in smart cities[J]. Pervasive and Mobile Computing, 2018, 50: 82-93. DOI:10.1016/j.pmcj.2018.08.001 |
| [12] | YAGCITEKIN B, UZUNOGLU M. A double-layer smart charging strategy of electric vehicles taking routing and charge scheduling into account[J]. Applied Energy, 2016, 167: 407-419. DOI:10.1016/j.apenergy.2015.09.040 |
| [13] | 朱建东, 王红蕾, 李倩倩. 考虑引力因素与时间满意度的充电站竞争性选址问题研究[J]. 数学的实践与认识, 2018, 48(24): 59-65. ZHU J D, WANG H L, LI Q Q. Competitive location problem of charging station considering gravity and time satisfaction[J]. Mathematics in Practice and Theory, 2018, 48(24): 59-65. (in Chinese) |
| [14] | 崔梦麟, 李广华, 王芳, 等. 计及碳排放与变工况特性的IES多目标优化调度[J]. 电工电气, 2023(1): 8-14, 54. CUI M L, LI G H, WANG F, et al. Multi-objective optimal scheduling of integrated energy systems in consideration of carbon emission and variable working condition[J]. Electrotechnics Electric, 2023(1): 8-14, 54. (in Chinese) |
| [15] | 高阳阳, 陈双艳, 余敏建, 等. 改进人工免疫算法的多机协同空战目标分配方法[J]. 西北工业大学学报, 2019, 37(2): 354-360. GAO Y Y, CHEN S Y, YU M J, et al. Target allocation method of multi-aircraft cooperative air combat based on improved artificial immune algorithm[J]. Journal of Northwestern Polytechnical University, 2019, 37(2): 354-360. (in Chinese) |
