考虑回路因素的电动汽车最短路问题研究

何 方，罗志雄，杨艳妮，李 萌

(1.清华大学a.工业工程系，b.土木工程系，北京100084；2.首都经济贸易大学管理工程学院，北京100070)

0 引言

为缓解传统机动车尾气排放所引起的环境污染问题，政府采取补贴或优惠方式鼓励人们购买新能源汽车，即纯电动汽车(EV)或者插入式混合动力汽车(PHEV).EV作为一种完全用电能取代燃油，将污染气体排放降至0的新型汽车更加受到民众青睐.受限于电池技术的发展，EV在出行过程中存在里程焦虑和充电时间过长等问题[1].此外，现阶段路网中所布设的充电站数量非常有限，在长途出行中难免存在EV绕路充电、排队充电的现象.

寻找最佳路径是经典的交通网络优化问题之一，在给定的OD对间找到的满足某些目标函数(如最小化旅行时间或距离)的路径被视为最佳路径，一般用Dijkstra等算法进行求解[2].电动汽车的电池容量有限，在出行过程中涉及充电或更换电池等行为，且耗时较长，传统模型和算法很难应用于寻求电动汽车的最佳路径.He等[3-4]考虑电动汽车的充电行为和电量守恒约束，建立以出行花费时间最少为目标的电动汽车最短路径模型，在此基础上构建电动汽车的网络均衡模型，并对充电站布设进行优化.Zündorf[5]考虑多种类型的充电站，假设充电过程为分段线性函数，建立电动汽车最短出行时间目标下的路径规划模型.Montoya等[6]建立的电动汽车最短路径模型中将电池充电水平视为充电时间的曲线函数，提出基于分段非线性充电函数的可行路径求解方法.还有一些研究以能源消耗最少为目标，进行电动汽车最佳路径规划，如Storandt[7]提出一种将电池交换站视为充电的方法.利用预先计算的辅助图来获得能源消耗最少目标下的最短路径.国内学者很少对电动汽车最短路径问题进行专题研究，张建寰等[8]针对不同道路交通状况下电动汽车充电路径选择问题，提出一种路况信息影响下的电动汽车充电路径规划方法；郭放等[9]提出考虑货物分类需求的电动汽车路径优化与换电策略问题，并建立了该问题的整数规划数学模型.

本文在He等[3]建立的EV最短路径模型的基础上，考虑EV长途出行中存在的绕路充电、排队充电等行为，基于重构路网的方法，建立考虑回路因素的电动汽车最短路径混合整数规划模型.并基于动态规划思想，提出改进后的标签设置算法，以提高该问题在大规模路网中的求解效率.

1 路网重构和模型假设

1.1 路网重构

以图1所示案例说明路网重构的过程.假设车辆最大旅行距离为12，各充电站单位充电成本相等，各路段的旅行时间和耗电量数值相等，如图1(a)所示.以初始电量(起点)或最大电量(充电站)出发不经过充电即可到达其他充电站或终点的路径定义为可行路径.对于起终点相同的路径1和路径2，假设其旅行时间分别是t1和t2，电量消耗分别是e1和e2，如果t2≥t1，e2＞e1或t2＞t1，e2≥e1，则称路径2不占优.路网重构步骤如下：

(1)求出起点到各充电站，不同充电站之间，起点至终点，以及各充电站到终点的所有可行路径.

(2)剔除步骤(1)中不占优的路径，将起、终点和充电站视为路网节点，对应路径视为路段，形成初步重构后的路网，如图1(b)所示.

(3)将步骤(2)所形成路网中连接两个节点的不同路段等效为一条广义路段，形成最终的重构路网，如图1(c)所示.

图1(a)原路网中，电动汽车从起点到终点的最短路为1-3-4-5-9-10-15-14-15-22-20，绕路充电表现为“15-14-15”.传统建模中，每一个节点的电量仅由一个变量表示，无法刻画出该绕路充电行为.在重构路网中，电动汽车不可能在同一个充电站进行两次及以上充电，故可以用于绕路充电行为下的最短路径建模.如图1(c)重构路网所示，最短路变化为1-5-14-20.

1.2 模型假设

基于重构的路网构造，考虑回路因素的电动汽车最短路问题的基本假设如下：

①驾驶员以总出行时间消耗最少为目标进行路径选择和充电站选择.总时间成本包括行驶过程经过各个路段的旅行时间与在各个充电站的充电时间之和.

②电动汽车的电量必须保持在安全电量以上.电动汽车在行驶至下一个充电站之前，需要选择可行的路段保证其电量不低于安全电量.电动汽车旅途中会经过数个充电站，不同类型充电站的排队时间和充电速度存在差异，驾驶员在已知这些信息的情况下进行充电站及充电量的决策.

2 混合整数规划模型的建立

基于上述模型假设和重构路网，建立一个混合整数规划模型描述存在回路的电动汽车最短路径问题.假设重构路网为G(N′),A′，N′表示路网中所有节点n的集合，N′c代表所有充电站的集合，A′表示所有广义路段a集合，Ka表示组成广义路段a的实际路段总数.在已知特定旅程起终点分别为o和d的前提下，该混合整数规划模型可以刻画出行者如何选择行驶路段、充电站及充电量，最终生成一个总旅途时间最小的行驶路径.模型具体形式为

图1 路网重构示例Fig.1 Road network restruction example

式中：xa为0-1变量，如果广义路段a被使用，则xa=1，否则xa=0；为0-1变量，如果广义路段a中的第k条路段被使用，则为0-1变量，充电站n被选择进行充电，则xn=1，否则xn=0；yn为在充电站n的充电量；Ln为离开节点n时的电量；分别为广义路段a中第k条路段上的旅行时间，充电站n的排队等待时间、单位充电时长；Δ为节点路段连接矩阵；H(o,d)为起点对应值为1，终点对应值为 -1，其他元素均为零的向量；Li和Lj分别为广义路段a=i→j起点和终点的电量；yj为在节点j的充电量；e(k)a为广义路段a中第k条路段上的耗电量；Lo表示电动车在起点时电量值；Einitial表示初始电量；M是一个足够大的数，取M=Emax-Esafe，其中，Emax为最大电量，Esafe为安全电量.和Ln为决策变量，均为已知参数.

目标函数为最小化道路旅行时间、充电等待时间和充电时间之和.约束条件：式(1)为道路流量守恒约束；式(2)表示若广义路段a被使用，则只使用其中一条路段，否则该广义路段中的所有路段均不会被使用；式(3)表示每一条广义路段上的电量守恒，当广义路段a被使用时，，否则无约束；式(4)保证电动汽车能够顺利通过广义路段a=i→j；式(5)保证电动汽车的电量不超过电池的最大值；式(6)表示起点时的电量等于初始电量；式(7)为充电电量约束；式(8)和式(9)均为0-1变量约束；式(10)表示非充电站的节点不能选择充电.

上述混合整数规划模型可使用商业规划求解软件进行求解.但当自变量很多，且应用于大型路网时，求解速度很慢，这是因为充电站和起终点间可行占优路径的枚举极其耗费计算资源.受动态规划思想的启发，提出改进的标签设置算法(Revised Label-setting Algorithm)进行求解.

3 改进的标签设置算法

该算法既适用于原始路网，也适用于重构路网.以原始路网为例，给出算法流程.为简单起见，将电动汽车电量的单位设为km，充电成本单位设为min.定义一个标签为一个向量，即其中：Nc代表当前节点，Np为之前节点，若Nc为起点，则Np=0；Tc,Ec,Wc,Sc分别表示从起点到达上一个进行充电的充电站的时间成本、电量消耗，以及该充电站的排队时长、单位充电成本(min/km)；tc,ec分别表示从上一个进行充电的充电站出发后，到达当前节点的时间成本、电量消耗.如果汽车到达当前节点之前没有充电，则Tc,Ec,Wc,Sc均为0，tc,ec表示从起点出发到达当前节点的时间成本和电量消耗.算法具体步骤如表1所示.

表 1 改进的标签设置算法步骤Table 1 Steps of revised label-setting algorithm

3.1 标签生成规则

Step 1中，对于起点，标签为lo=如果起点是电站，多生成一个标签，代表在起点充电的选择，其中，Wo，So分别代表起点充电站的排队时长、单位充电成本.

Step 2中，为不失一般性，以ℜ1中的一个标签lc=[Np,Nc,Tc,Ec,Wc,Sc,tc,ec]和其直接相连的下一个节点Ns进行说明.令a代表路段(Nc,Ns)，并令ea代表该路段的电量消耗.若Emax-(ea+ec)≥Esafe，则电动汽车能够到达Ns(当Tc=Ec=Wc=Sc=0，条件为Einital-(ea+ec)≥Esafe).若电动汽车能够到达Ns，根据以下4种情形，生成对应的标签，如表2所示.

情形1Ns不是充电站，生成标签ls,1.

情形2Ns为充电站，且是第1次充电，生成标签ls,1和ls,2.

情形 3Ns为充电站，非第1次充电，且Ss≤Sc，生成标签ls,1和ls,3.

情形 4Ns为充电站，非第1次充电，且Ss＞Sc，生成标签ls,1和ls,4.

表2 标签构造结果Table 2 Labels' formulation

标签生成中，上一次充电的最优电量(情形3和4)满足“高少低多”原则，即如果上一次充电的充电站的充电成本高于或等于当前充电站，则在上个充电站充刚好到达当前充电站的电量，否则在上个充电站选择充满.

3.2 标签占优性规则

对于路径中的任何节点Nc，标签将会比lc占优，如果终点时，对于任何源于lc的标签，都存在一个源于且成本更低或相等的标签.显然，在标签设置算法中(Step 3)，剔除一些不占优的标签也不会失去最优选择.标签的占优性测试方法如下.

推论1如果同时成立，则标签占优.

证明若lc代表的任一选择在到达Nc时，旅行成本为TNc，剩余电量为ENc，总存在对应的一种选择，其具有旅行成本则标签会比lc占优，即下述不等式成立.

式中：yc和是上一次充电量.对于任何yc，令，则可推导推论1中的占优测试条件.

标签生成规则能够生成最优选择，最优选择对应的各个标签是占优的，不会被删除掉.由此，算法能够生成最优路径选择结果.该算法总标签数为O(2CN2)，其中，C为充电站数量，N为路网节点数量.若充电站数量已知，该算法为多项式时间算法.

4 算例分析

4.1 与传统模型对比

将所建立的EV最短路模型与传统模型，即He等[3]建立的EV最短路径模型，进行对比分析.实验路网为Sioux-Falls路网，如图2所示，图中各双向对称路段括号内两个数值分别表示旅行时间(min)和路段长度(km).充电站分别设置在节点11和16，等待时间分别2 min和14 min.测试OD对及初始里程分别为：(1，13)，55 km；(5，24)，45 km；(7，20)，35 km.

图2 Sioux Falls路网Fig.2 Sioux Falls network

本算例假设：电动汽车的最大电池容量为30 kWh，充电速度为2 min/kWh；电动汽车每kWh电量平均行驶里程为5 km，电动汽车里程焦虑值为25 km，对应电量为5 kWh.通过换算，电动汽车每分钟补充里程为2.5 km，最大里程为150 km.运用两个不同的模型求解电动汽车最短路径，结果如图3所示.可以看出：由于OD对(1，13)初始里程较高，在此过程中无需充电，两个模型求解结果相同；OD对(5，24)行程较远，需要在途中充电，但无须绕路充电，两种模型最终选择结果均一致；OD对(7，20)，考虑到18～20为城市快速路网，旅行时间较短，选择路径1(7-18-16-18-20，时间成本为33.04 min，充电里程为11.6 km)比路径2(7-18-16-17-19-20，时间成本为34.96 min，充电里程为13.4 km)总成本更少，故选择路径1更有优势.算例结果表明，本文基于路网重构所提出的模型能够求解出存在回路的路径，克服了传统模型的缺点.

图3 两种模型对比结果Fig.3 Comparing results of two models

4.2 算法求解速度对比

本算例仍基于Sioux Falls路网，从已有研究的数据中选取了76个OD对[10]，并设定初始里程均为35 km.为比较不同模型及算法求解速度的差异：首先，通过Matlab调用商业规划软件(Cplex12.8)直接求解传统模型和考虑绕路因素的新模型；然后，与改进后的标签设置算法求解速度进行对比.求解平均耗时结果如表3所示，针对76个OD对求解的时间分布图如图4所示.

求解效率方面，运用商业规划软件求解所提的新模型稍快于求解传统模型，耗时离散程度较小，这是由于新模型是基于重构路网建立的，与原始路网相比，节点和路段数量明显缩减，使新模型的求解速度较快.此外，运用所提的改进的标签设置算法进行求解的效率显著高于商业规划软件，且耗时离散程度大幅减小，证明该算法能够高效求解存在回路的大规模路网中出行需求旺盛时的电动汽车最短路径问题，为快速求解电动汽车的交通均衡问题奠定了重要基础.

表 3 不同求解算法的平均耗时Table 3 Average solving time of different algorithm

图4 不同模型算法求解时间分布图Fig.4 Solving time distribution under different model and algorithm

5 结论

本文针对电动汽车绕路充电现象下的最短路径问题，提出路网重构的思想，基于重构路网建立混合整数规划模型，克服已有模型无法求解路网中存在回路这一难点.为进一步提高在大规模路网中的求解效率，提出改进的标签设置算法.经验证，该算法极大地提高了大规模路网且存在回路的电动汽车最短路问题的求解速度.实现快速枚举最短路，为求解电动汽车网络均衡问题奠定了重要基础，对于开发完善的电动汽车路径导航系统具有一定的参考价值.