智能电网下支持充放电策略的电动汽车配送路径优化

李家乐 刘真伯 王雪菲

(河北工业大学 土木与交通学院，天津 300401∥河北省交通基础设施智能建造与管养重点实验室，天津 300401)

随着全球变暖等问题日益严重，降低交通运输领域的温室气体排放逐渐受到人们的重视。新能源汽车具有无污染、节能环保等优点，随着电池技术的不断发展，新能源汽车逐渐被应用于物资运输、个人出行、公共交通等多个交通领域。但由于电池电量限制以及充/换电设施较少，很大程度上限制了新能源汽车在各个领域进一步推广和应用。近年来国内外关于以电动汽车为主的车辆路径规划研究越来越多，绿色交通运输将成为未来几年的重点发展方向。

车辆路径问题(VRP)作为交通方面的经典问题已经发展成熟，新型的电动汽车路径问题(EVRP)是对原有模型的扩展，国内外学者已经开展了一些电动汽车路径规划问题研究，涉及带有时间窗的电动汽车路径问题[1-2]和电池对电动汽车路径影响[3-5]。Yang等[6]提出了一种解决电动汽车到电池交换站的路径模型,考虑了电池交换站的成本，设计了一种改进的禁忌搜索算法。Zhang等[7]通过蚁群算法和自适应大型邻域搜索来解决电动汽车路径问题以及充电站选址，其主要目标函数强调了减少能源消耗，证实了路径最短约束不能代表消耗最少。Wang等[8]通过应用遗传算法(GA)解决了考虑出行费用、能源消耗、出行时间等多目标的电动汽车路径问题。Pelletier等[9]分析了电动汽车能源损耗不确定性的影响，提出了一种基于不确定能耗的新型电动汽车路径问题，设计了具有鲁棒稳定性的优化框架来解决能耗不确定问题，通过两阶段算法计算运输成本的最优解。毛慧婷和葛显龙等[10-11]考虑了两种不同充电方式产生的影响。王健等[12]将出租车更换电池运营成本与传统燃油出租车运营成本比较，证明了纯电动汽车具有一定的运营成本优势。张勇等[13]以社会总成本最小为目标，研究了换电站的建设数量、选址方案和建设时序。Yang等[14]考虑到了电动汽车与可变电价的相互影响，提出了一种帕皮诺遗传算法(PGA)解决路径优化问题以及车辆在线路上的充电时间。Li等[15]提出应用蚁群算法解决可共享电动汽车的城市物流配送路径问题，并且考虑了可变电价使得充电成本最低。

对电动汽车充放电行为进行分析。建立了非线性整数规划模型求解数学问题。提出了一种与局部搜索相结合的改进遗传算法(GA-LS)，提高了最优解的质量。此外，国内学者研究该问题时应用的算例较少。为了防止该模型陷入局部最优解，本文通过25个算例验证了该模型的可行性。文中还分析了快速充电与交换电池两种方式对电网的影响。

1 问题描述

1.1 电动汽车路径

本文中主要研究电动汽车从配送中心出发到各个顾客点运输物资，采取了交换电池的方式，一方面节约了电动汽车在充电站的排队时间和服务时间，另一方面，被替换的电池可以作为分布式电源向电网进行充放电操作，为电网运营者带来利润。Verma[16]证实了电池交换站会给电动汽车带来好的路线选择。在本模型中，电动汽车在配送途中只有经过换电站才能更换电量充足的电池。目标函数是配送费用的最小总成本，包括行驶成本、时间窗成本、承载约束成本。

电动汽车须满足约束：

(1)每个顾客的需求量是固定的，只允许一辆车对其进行服务并且只经过一次;

(2)电动汽车的电量需满足接下来的行程(遇到换电站则更换电池);

(3)每个充电站只对一辆车进行服务并且只服务一次;

(4)电动汽车允许多次访问充电站;

(5)车辆从配送中心出发皆为满电状态，并且最后返回配送中心;

(6)电动汽车在顾客点等待期间不消耗电量;

(7)电动汽车的额定电量和行驶速度是固定的，不考虑电池损耗和外界因素的干扰;

(8)电动汽车须在规定的时间窗内到达，在时间窗外到达则须支付时间惩罚成本。

1.2 分时电价

分时电价又称可变电价。将一天24 h按照不同的时间段收取价格不同的电费。当电力需求过高或电力系统提供能源不足时，提高电的价格；反之，电价降低。配电网基础负荷参考了肖浩等[17]提供的数据。图2示出一天的分时电价和各个时刻电网负荷。

1.3 充放电策略

由于电动汽车行驶的里程较短，需在运输过程中到充电站进行补给，本文中模拟交换电池的方式，通过电池接入电网(B2G)向电网输送/获取能量，根据分时电价的影响向电力市场出售电力获取利润。为方便进行充放电决策，本文中将一天分为两个时段，这两种状态取决于用户用电、可变电价等数据。当用户用电需求量较大，分时电价较高时，该时段为高峰时段，此时将电池放电直至达到电池容量所允许的最小值，若电力系统产生的电量满足该时段的用户用电需求，则将多余的电量出售到电力市场中获取利润。当用户用电需求量较小，分时电价较低时，该时段为非高峰时段，此时将电池充电直到电池达到最大荷电状态。图1表示换电站与电力系统、电力市场、用户之间的相互关系。各个时段的电价如图2所示，T1、T2分别为高峰时段的开始时间和结束时间。

图1 换电站与电力系统、电力市场、用户之间的相互关系Fig.1 Relationship between electrical changing station and power system,power market and users

图2 电网总负荷和每时刻电价Fig.2 Total grid load and hourly price

1.4 模型参数定义

本文提出的EVRP模型继承传统的VRP模型特点，给定一个图G=(N∪F,A),点集N={0，1,…,n}代表n个顾客所在点的集合，其中0代表配送中心，F={n,n+1,…,n+m}表示m个充电站的集合，A={(i,j)∣i,j∈N∪F,i≠j}代表N∪F中所有可能连接的弧线。模型中的符号说明见表1。

表1 符号说明Table 1 Symbol description

1.5 数学模型

根据对问题描述的分析，以车辆固定成本、行驶成本、惩罚成本以及充放电成本为优化的目标函数，建立了考虑充放电策略的带时间窗电动汽车配送路径优化问题模型。

决策变量：

数学模型：

(1)

(2)

(3)

(4)

0≤Dj≤Cik-Di,i∈V,j∈V,k∈K

(5)

(6)

0≤qajk≤qlik+ηdijXijk, ∀i∈N,j∈N,k∈K

(7)

0≤qajk≤BQ(1-Xijk)-ηdijXijk, ∀i∈G,j∈N,k∈K

(8)

0≤qaik≤BQ, ∀i∈V,k∈K

(9)

qaik=qlik, ∀i∈V,k∈K

(10)

tωi=max[0,(ei-tai)], ∀i∈N

(11)

tμi=max[0,(tli-li)], ∀i∈N

(12)

tli=tai+tsi+tωi, ∀i∈N∪G

(13)

(14)

taj=(tli+tij)Xijk, ∀i∈V,j∈N∪G,k∈K

(15)

Xijk∈{0,1}, ∀i∈V,j∈V,k∈K

(16)

Yk∈{0,1}, ∀k∈K

(17)

(18)

(19)

Pijmin≤Pij≤Pijmax

(20)

QSOCijmin≤QSOCij≤QSOCijmax

(21)

式中：目标函数(1)代表了车辆成本、行驶成本、惩罚成本以及充放电成本四项和的最小值，Sj为分时电价，当电池放电时Sj为负，即充放电成本为负时，说明在充放电过程中总体为获利；约束(2)表示每个顾客都被服务且只服务一次；约束(3)表示每条配送路线只安排一辆运输车辆；约束(4)保证了流量的平衡；约束(5)表示载重量与每个顾客的需求量的关系，例如，车辆在j点的需求量不能超过车辆在i点的剩余量减去i点的需求量；约束(6)表示每条路径的总需求量不得超过车辆的最大承载容量；约束(7)-(8)分别表示顾客i到顾客j、充电站到顾客的电量约束，如约束(7)，点j的剩余电量不得超过点i的剩余电量减去从i到j所消耗的电量；约束(9)表示任意点的剩余电量始终非负；约束(10)表示车辆访问顾客节点的前后电量保持一致；约束(11)-(12)表示电动汽车到达顾客节点i的等待时间和迟到时间;约束(13)表示车辆离开顾客点i的时间为车辆到达顾客i的时间与服务时间、等待时间之和；约束(14)表示车辆从顾客i到j所用时间公式；约束(15)表示车辆到达顾客j的时间等于离开顾客i的时间加从i到j所耗费的时间；约束(16)-(17)为二进制0-1变量；式(18)-(19)为负荷均方差，表示电网负荷的波动情况，均方差越小，电网负荷波动越小；约束(20)表示电池的充放电速率的上下限。式(21)表示电池可用容量约束,QSOCijmin、QSOCijmax表示电池电荷状态的最大值与最小值，为了保证电池的充放电安全以及使用寿命，通常取QSOCijmin为0.2，QSOCijmax取0.9。

2 算法设计

为了解决智能电网中车辆行驶路径优化问题，本文设计了一种改进的遗传算法。遗传算法与传统的优化算法相比，该算法对优化问题没有太多的数学模型要求。由于其进化特性，可以处理非线性、离散等多种形式的目标函数和约束。因此，该算法具有鲁棒性好、求解离散和解决复杂非线性问题高效等优点。

为了使本文中的电动汽车优化结果质量更高，本文中在遗传算法中增加了局部搜索操作，增加了搜索的效率。改进的遗传算法原理见图3。图3中GEN为最大迭代次数。

图3 算法流程图Fig.3 Primary process of GA-LS algorithm

2.1 遗传算法步骤

(1)编码

本文采用了十进制的编码方式。染色体长度为n+nch+k-1，其中n代表客户点的数量，序列号为1,2,…,n，nch代表充电站的数量，序列号为n+1,n+2,…,n+nch。k代表使用电动汽车的数量，同时也代表一共有多少条路径，k-1表示配送中心在染色体上的位置，其序列号为n+nch+1,…,n+nch+k-1。例如模型为5个顾客、3辆车和2个充电站，那么染色体可以是126 845 937,8、9代表配送中心，那么该染色体则被划分为“0-1-2-6-0”、“0-4-5-0”、“0-3-7-0”3条路径(0表示配送中心)。

约束和适应度函数

本文中将旅行成本、惩罚成本、固定车辆成本3项的总成本作为适应度函数。适应度函数如下：

(22)

(23)

式中:F(xi)为染色体i的适应度;f(xi)是以车辆固定成本、行驶成本、惩罚成本为优化的函数;C3为违反电量约束的惩罚成本，在该模型中车辆的行驶里程超过电池额定的行驶里程是不被允许的，所以 设定为1 000 000，避免出现行驶里程超过续航里程的情况。由于电动汽车在换电站交换电池后，多余的电池会作为电网的分布式电源将剩余的电量进行充放电操作，该适应度值不再计算充电成本。

(2)选择

采用轮盘赌选择法，依据适应度的大小，将个体按照适应度由大到小排列，并按照此概率随机生成子代种群。

(3)交叉

本文采取了OX交叉的方式进行交叉，具体操作如下。

步骤1 选取两个父代染色体作为样本，每条染色体上随机选取a和b两个位置，该染色体上a到b则为交叉片段，

步骤2 将父代2的交叉片段放到父代1染色体的前面，将父代1的交叉片段放到父代2的前面。

步骤3 将新得到的父代1和父代2中重复的个体进行标记。

步骤4 按照从前到后的顺序将第2个重复的个体删除，形成两个子代个体。

(4)变异

在经历过选择交叉步骤后，新的个体会有一定的概率发生转变，这里采用较为简便的变异操作，步骤如下：

步骤1 按照预先设置的变异概率判断种群中是否有个体需要变异。

步骤2 若进行变异，则在该染色体上随机选取两个变异位置a、b，随后将两个个体进行交换生成新的染色体。

2.2 局部搜索步骤

为了防止遗传算法陷入局部最优解的情况，插入局部邻域搜索算法，提高最优解的质量。本文采取了随机顾客删除算子，将一定数量η的顾客随机从路径中移除，并删除顾客数为零的空路径。插入算子采取了贪婪插入的方法，计算被移除的顾客与未被移除顾客的相关性，按照相关性的大小依次插入未被移除的顾客集中，随后判断该路径是否违反约束，未违反则记录该点，否则重新插入。此外，本文中通过移除算子破坏掉现有的违反约束的路径，随后通过贪婪插入算子生成新的路径以满足时间窗和电量的约束条件，将部分不可行解转化为可行解，有效提高了搜索可行解的效率。需要注意的是，由于每次顾客点位置都会重新调整，充电站位置也需重新插入，这里将充电站作为顾客点重新插入，并记录插入后路径是否满足电量约束要求。

3 实验设计

为评价模型和算法的性能，本文中选取20个测试算例和5个海口市的案例进行实验。其中测试算例来源于Zhang等[18]的共享数据库(https://doi.org/10.6084/m9.figshare.10288326)。在这些算例中，每个顾客的需求不同，分别为50、100、150 kg。为了对比不同充电站的影响，充电站数量分别设为2、4、6、8。顾客数量设为30到200之间。每个算例都具有不同的充电站和顾客数量，例如，算例“r-4-c-50”代表了该算例具有4个充电站和50个顾客。为了测试GA-LS算法的性能，分别与自适应大邻域搜索(ALNS)[19]、邻域搜索(LNS)[20]和变邻域搜索(VNS)[21]3个不同的算例进行对比。此外，为验证模型的运行效率和最优解的质量，随机选取了5组海口市2017年6月的网约车出行数据，该数据来自滴滴出行“盖亚”数据开放计划(https://gaia.didichuxing.com)。每个数据包含了网约车的订单起点坐标和终点坐标。图4表示5组算例顾客点和充电站的分布情况。在本文中，由于企业的服务能力有限，过多的顾客点会超出该企业的服务能力上限，这里分别随机选取了30，60，90，120，160个订单终点设为顾客点。假定这些订单的起点相同(起点设为配送中心)，由多辆电动公交依次将乘客送往目的地。每个目的地到达的乘客分别为1，2，3人。电动汽车可以多次访问充电站。充放电调度部分通过Matlab/Simulink进行仿真。表2为模型初始参数的设定值。

表2 模型的初始参数Table 2 Initial parameters of model

图4 各个算例点的分布Fig.4 Distribution of each example points

3.1 改进遗传算法的优化效果

GA-LS算法的实验结果。

表3为GA-LS与其他3种算法的比较结果，发现GA-LS算法相较于其余的3种算法优化结果更好。相较于LNS、VNS、ALNS分别减少了1 112.3、216.5、869.9 km。该实验结果证明GA-LS的优化结果显著高于LNS与ALNS，并且当模型容量越大时，优化效果越好。证明该算例对于大容量的模型具有更强的计算能力。

表3 四种算法最优解对比Table 3 Comparison of the optimal solutions of four algorithms

图5和图6为改进遗传算法的路径规划和改进效果对比。试验结果表明，GA-LS算法增强了全局的最优解搜索能力，提高了最优解的质量。当顾客点为30个时，配送成本降低42%，当顾客点为160个时，配送成本降低47%。另一方面，由于该实验采取的是电池交换方式，运营者要承担高额的电池费用，改进的遗传算法通过局部搜索的移除算子和插入算子每次都将原有的路径重新规划，减少了多余路径和违规路径的出现，降低了电动汽车的使用数量，减少运营者的用车成本。当顾客为160时，改进遗传算法使用21辆车完成配送，相比传统遗传算法减少用车9辆。在迭代次数方面，改进的遗传算法具有很强的局部搜索能力，因此可以在较少的迭代次数中获得更高质量的解决方案，如图7所示。以海口市的4个充电站、60个目的地为例，实验结果证明，改进的遗传算法在76次迭代时已经完全收敛，而传统的遗传算法在450次才完全收敛，并且最优解的质量远低于改进的遗传算法。

图5 各个算例的路径规划图Fig.5 Route planning for each example目的地 换电站 配送中心 与分别表示不同路径

图6 GA-LS和GA的结果对比Fig.6 Results contrast of GA-LS and GA

图7 GA-LS和GA的收敛速度对比Fig.7 Convergence rates contrast of GA-LS and GA

3.2 充放电策略对比分析

随着电动汽车的数量和充电功率的逐年增加，电动汽车在机场、校园和社区等区域的应用也逐渐增多。使得电动汽车运输车队对局部电网产生较大影响。Trivio-cabrera等[22]评估了在V2G模式下电动汽车车队对电网的影响。结果表明电动汽车车队充放电模式稍有偏差，就会导致电网负荷有明显的转移。本文基于海口市案例“r-4-c-30”，分析了快速充电和交换电池两种不同充电策略对电网产生的影响，将3种场景下的负荷曲线进行对比，如图8所示。表4统计计算并对比了相应的负荷特性指标、充电成本和总成本 。

表4 不同场景下的负荷特性指标和充电成本Table 4 Load characteristic index and Charge the cost in the different scenarios

图8 并入电动汽车后电网的负荷曲线Fig.8 Load curve of the grid with electric vehicle

(1)当电动汽车采用快速充电方案时，充电时间大部分集中在9：00到19：00，该时段正处于用电高峰时期，峰值负荷由原来的875.236 3 kW增大到890.433 7 kW，峰谷差率增大到42.19%。降低了电网的安全性，同时该时段的电价较高，进而导致充电成本较高，为244.08元。

(2)当采用交换电池方案时，充电时间大部分集中在21：00到次日3：00，该时段处于非用电高峰时期。峰谷差率由原来的41.18%降到39.46%。另一方面，由于交换电池方案在电价较低时充电，电价较高时放电，所以总的充电成本为盈利状态，为201.17元。充分表明了所提出的电动汽车优化充电方案具有削峰填谷和降低充电成本的作用。

4 结论

(1)为提高电动汽车并入电网后电池的利用率以及缩短配送路径的距离，综合考虑时间窗约束、载重约束、里程约束以及充放电决策。提出了智能电网下支持充放电策略的电动汽车配送路径问题，并应用整数混合规划建立模型。

(2)应用了结合局部搜索的遗传算法求解模型，优化包含出行时间、出行路线、出行车辆利用率在内的配送方案。通过局部搜索算法，提高了迭代效率和最优解的质量。通过20组算例证明了模型的可行性和优化效果。

(3)结合海口市的实例，对5组分布不同、数量不同的案例进行分析。绘制了行车的配送路径，降低了配送成本和车辆的使用数目，对于大容量的模型有更好的优化效果。当顾客点为30，配送成本降低42%，车辆数减少1辆。当顾客点为120时，配送成本降低47%，车辆数减少9辆。

(4)基于V2G模式和交换电池模式，通过将电动汽车并入电网来获取、输送能量。结合海口市“r-4-c-30”案例，分析了交换电池与快速充电两种充电方式对电网产生的影响。实验结果表明，交换电池优化方案相较于快速充电使得峰谷差降低，且均方差降低。相较于原电网，峰谷差率降低。该优化方案在降低充电成本的同时，有效利用了电动汽车的充放电决策来降低系统的负荷峰谷差。