基于逆强化学习的电动汽车出行规划方法研究*

李繁菀，张 莹，华云鹏，李沐阳，陈元畅

(华北电力大学控制与计算机工程学院，北京 102206)

随着社会经济的发展和生活水平的提高，人们对汽车的需求量逐年大幅度上涨，环境问题也随之而来，汽车尾气的排放对环境造成极其严重的影响。面对严峻的环境问题，我国大力推动碳达峰、碳中和各项工作，电动汽车产业普及率不断提升[1]。电动汽车一方面满足人们的短距离出行需求，另一方面它以电作为主要动力源，相比以燃油为驱动的汽车更加节能和环保。目前对于路径规划的研究主要针对燃油汽车，而对燃油汽车的路径规划无须考虑电量的因素，该场景不适用于电动汽车。随着电动汽车的普及，由于电动汽车的特殊属性以及“里程焦虑”[2]，电动汽车的出行规划显得尤为重要。若能有效引导电动汽车用户选择可达目的地、能及时充电、行驶时间短、充电时间短的路线行走，出行效率就能有效提高。

本文提出了一种基于逆强化学习(Inverse Reinforcement Learning，IRL)的电动汽车出行规划(Electric Vehicle Travel Planning,EVTP)方法，将考虑充电行为的Dijkstra算法作为专家示例以保证专家策略的优越性，在对电动汽车进行出行规划时须同时考虑电量和路径两方面因素，从而得到一条满足电量可达条件的最优路径。此外，本文还对充电策略进行考虑，在充电时采用部分充电策略以提高充电效率，使充电时间尽可能短。逆强化学习算法旨在对寻找路径的策略进行学习，因此有别于传统路径规划算法依赖于路网结构的特性。

1 相关工作

电动汽车出行规划(EVTP)问题可以拆分为电动汽车路径规划问题(Electric Vehicle Routing Problem,EVRP)以及充电策略问题。电动汽车的路径规划问题会受到电动汽车电池容量的限制，即电动汽车的电量不能低于某个限定最小值。因此，EVRP也可以被建模为受约束的最短路径规划问题，此类问题与经典的最短路径问题的不同之处在于解决方案必须满足附加约束，这是典型的NP-hard问题[3]。目前，求解受约束的最短路径问题大体上可分为两类方法：精确方法和启发式方法。

精确方法通过严谨的数学模型或数据结构规划问题，利用数学法则或数据结构搜寻的方式求得问题最优解[4]。Lu等[5]提出了一种运用整数线性规划来求解电动汽车最优路线问题的方法，该方法以最小化电动汽车行驶时间为优化目标，然而线性规划的方法计算复杂度较高，仅在小型实例中有很好的表现，一旦应用在大型路网中往往需要很大的存储空间而导致方法不可用，因而其效率取决于实际路网的规模且不可直接迁移到其他未经预处理的路网中。

由于精确方法有较高的计算复杂度而不便应用于实际情况，在此方面有一定改善的启发式方法是EVRP中更为常用的一种求解方法。启发式方法[4]的主要思想是以当前解为基点，在当前解的邻域中寻找较优解赋给当前解，并继续寻找，直到没有更优解为止。Lebeau等[6]对每条路径计算合并一条新路径的成本，对可行路径按成本量排序，再以贪心方式进行归并得到路径集。Felipe等[7]采用两阶段启发法，在得到初始可行解的基础上不断对路径进行调整，以逐渐靠近最优目标，并在每一步更新目标函数的值，反复迭代直到目标函数的值收敛为止。类似地，Dijkstra算法和A*算法[8]在路径规划问题中也被广泛运用，对其稍加修改也可以运用到EVRP中。Cuch等[3]提出了一种基于A*算法计算电动汽车最优路线的方法，并将减少充电行为中的等待时间作为优化的一部分。Kobayashi等[9]提出了一种基于Dijkstra算法的电动汽车路线搜索方法，这种方法对于充电行为也有一定的考虑，但未对充电时间作出优化。虽然启发式方法能有效减少运行时间，但是此类方法仍然不能独立于实际路网，即其运行效率仍与路网规模相关，且应用在不同路网时需要重新进行生成邻接矩阵等数据预处理工作。而本文提出的基于逆强化学习的方法与具体路网结构无关，即在某个路网中训练得到的模型也能在其他路网中有较优的性能。

对于EVTP问题，为得到一条最优路径，除了路径最短之外，充电策略也是需要重点考虑的因素。Wang等[10]提出了一个基于电量驱动的上下文感知路径规划框架，该算法通过电量的约束限制A*算法对路径进行搜索，并且对于需要充电而绕路的情况给出了最佳方案。然而，此类方法在到达充电站时仍假设电动汽车会将电量充满，这并不适用于实际情况。在现实生活中，电动汽车通常只需要使其电量在接下来的路程中不会低于限定值即可，这样既可以减少充电时间又能满足可达性。此外，电动汽车的充电函数并不是线性的，电动汽车的充电效率会随着电量的变化而变化[11]。因此，本文提出了一种更接近于真实情况的充电策略，即分段充电以及部分充电策略。

2 方法

2.1 问题定义

对于EVTP问题，电动汽车车主通常希望得到一条行驶时间短、充电时间短、充电次数少的可达路径。因此，目标可形式化表达为

此外，在寻找路径的过程中还应满足以下条件：(1)电动汽车选择的每一个节点都在路网的点集G中，选择行走的每一条路径都在边集E中；(2)路网中的边为无向图，选择边(i,j)等价于选择边(j,i)，即xij=xji；(3)选择的任意两个连续的充电桩之间的电量消耗要小于限制条件，即到达充电桩时的电量大于限定的最小电量；(4)充电次数尽可能少。充电次数越多，充电桩总计服务时间越长[12]，从而会降低电动汽车的出行效率。

2.2 马尔可夫决策过程

为将逆强化学习(IRL)算法应用到EVTP问题中，EVTP问题可被建模为马尔可夫决策过程[13,14]。在此场景中的马尔可夫决策过程可由以下5元组表示。

(1)状态集S。在EVTP问题中，状态集S中的每一个状态s由当前电动汽车的电量(pow)、与终点的距离比例(distance_ratio)、行走的角度(degree)、绕路情况(loop)组成。通过pow可以判断当前状态是否满足可达性条件，即行走时电动汽车的电量是否在限定值以上。另外，状态值的其他组成部分也是电动汽车选择路径过程中需要特别关注的因素，状态值中不包含具体位置信息，使得训练得到的模型在新的路网中也能有较好的表现。

(2)动作集A。由于电动汽车的特性，动作集A中的动作a包含两类：行走行为和充电行为。在本文的设定中，动作集中共包含10个动作，前8个动作表示行走行为(假设所有的节点最多有4个邻接节点)，后2个动作表示充电行为，集中离散化的动作用one-hot编码[15]表示。在行走行为中，电动汽车的目标是向更接近终点的方向行驶，且需要为之后可能出现的充电行为做准备。因此，行走行为中的前4个动作对某一位置的相邻点按照(degree,distance_ratio)升序排列，即先按照degree升序排列，若degree相同再按照distance_ratio升序排列；行走行为中的后4个动作对某一位置的相邻充电站按照上述规则排序，以便之后选择充电行为。若选择动作集中后2个动作，即电动汽车选择充电行为，在充电行为中本文对于充电量进行了区分，其中一个动作表示电量充到80%，而另一个动作表示电量充到100%，这种部分充电的策略有利于节省充电时间。

(3)奖励r。传统强化学习算法中的即时奖励r往往是人为设定的，然而在复杂问题中仅凭经验通常无法设置最优的奖励值。例如，本文的场景需要同时考虑行走行为以及充电行为，难以人为设置兼顾二者的最优奖励。奖励是影响强化学习算法性能的重要因素，因此，本文采用基于逆强化学习的方法对奖励值进行设定[16]，通过专家示例以及学习策略过程中得到的轨迹间的交互，求得最优的奖励值。

(4)动作价值Q。Q(s,a)表示选择了动作a之后直到到达终点的奖励总和的期望，即

本文用Dueling DQN算法[17]近似动作价值Q，即将某一时刻的状态st作为输入，输出对每个动作a的价值预测。此时Q值被定义为Q(s,a;θ)，其中θ为神经网络中的参数。

(5)策略π。策略π(st)依据当前状态对动作进行选择。在本文中使用ε-greedy以一定的概率进行探索，即大概率选择动作价值最大的动作，以极小的概率对动作进行随机选择来避免陷入局部最优。ε-greedy的计算公式如下：

π(st)=

根据上述5元组，对算法整体流程表示如图1所示。

图1 算法整体流程图

2.3 状态特征选择

状态是马尔可夫决策过程中的重要组成部分，状态的选择尤为重要。特征是状态到真实值的映射，包含一些重要的属性，且与奖励值有密切关系。在本文中将EVTP问题的特征定义为5个方面。

(1)电量pow。pow表示电动汽车是否迫切需要充电。此特征用当前状态下电动汽车的剩余电量来定义，剩余电量越少越迫切需要充电。

fpow(st)=Soct。

(2)充电时间charge_time。充电时间是电动汽车需要重点考虑的特征之一。充电时间过长会导致旅程时间过长，从而导致效率过低；充电时间过短可能会使电量不能满足接下来旅程的需要，从而导致目的地不可达。电动汽车的充电时间需要在满足可达的条件下尽可能短。

fcharge_time(st)=

式中，C表示充电桩节点的集合；location(t)表示t步所在位置，location(t)∈C即t步时所在节点为充电桩节点；charge_index表示充电指示，由t步时选择的动作决定，charge_index(t)=1即表示在t步时需要充电；ct表示计算得到的在t步时的充电时间。

(3)角度degree。degree表示当前状态所在位置与终点的连线以及起点与终点的连线之间的夹角，夹角越小说明电动汽车行驶的方向与终点方向越接近。

fdegree(st)=|getdegree(origin,destination)-getdegree(location(t),destination)|，

fdegree(st)=min(fdegree(st),360-fdegree(st))，

式中，getdegree表示得到两点之间方位角的函数；origin表示路径的起点；destination表示路径的终点。

(4)距离比例distance_ratio。distance_ratio表示当前所在位置与终点的距离以及起点与终点的距离之间的比例关系，比例越小则越接近终点，所有距离均用haversine公式[18]进行计算：

fdistance_ratio(st)=

式中，haversine (A,B)表示点A与点B之间的haversine距离。

(5)绕路loop。loop表示寻找某起点终点对的路径过程中是否重复访问某一位置。

式中，runway_history表示电动汽车走过的节点位置的集合，若当前位置已经在runway_history中，则说明电动汽车已经访问过该节点，即出现了绕路。若出现绕路往往说明某步的决策不是最优，因此并不希望路径中出现绕路的情况。绕路情况如图2所示。

图2 绕路情况

给定起点、终点对(A,H)，电动汽车由E到达D后，在D点若根据角度选择下一个点，极有可能选择点E，此时便出现了绕路，虚线表示可能出现的绕路情况。

在上述特征中，电量对逆强化学习算法得到的奖励产生正向影响，充电时间、角度、距离比例、绕路均对奖励产生负向影响。

在对特征进行选择时，路径因素以及充电因素都需要被考虑以适用于EVTP问题，从而得到一条兼顾行驶和充电的最优路径。

2.4 Dueling DQN

除了对特征的选择外，对动作的选择在逆强化学习中也十分重要。逆强化学习算法与传统强化学习算法的区别仅在于奖励函数，虽然其算法流程与传统强化学习相似，但是在得到奖励函数之后仍需要正向训练更新Q值来学习策略。可用Q(s,a)近似累计奖励，即

Q(s,a)=E[rt+γ·rt+1+γ2·rt+2+…|st=s,at=a,μ]。

根据上述设定，需要求得最优动作值Q*，最优动作值函数基于贝尔曼方程[19]，表示如下：

Q*(s,a)=Es′[r+γ·maxa′Q*(s′,

a′)|s,a]。

式中，α和β分别为价值函数和优势函数的参数。

在普通DQN算法中，若想更新某个动作的Q值会直接更新Q网络，使得该动作的Q值改变。然而在Dueling DQN算法中，由于所有动作的优势函数A值的和为0，不便于对优势函数进行更新，因此Q网络将优先对价值函数进行更新，即相当于对所有动作的Q值均进行更新，从而提升学习效果。Dueling DQN的网络结构如图3所示。在得到所有动作的Q值后，ε-greedy可被应用于动作的选择中。

图3 Dueling DQN的网络结构

2.5 逆强化学习

在马尔可夫决策过程中，除状态和动作外，奖励也尤为重要。无论是传统强化学习还是逆强化学习，最基本的假设都是最大化累积的奖励，因此奖励的设计非常关键。传统强化学习的即时奖励通常凭借经验人为设定，然而像电动汽车出行规划等复杂问题，仅凭经验设置奖励往往难以精准量化，因此，逆强化学习算法应运而生。本文将逆强化学习方法应用到电动汽车出行规划中以得到最优的奖励函数。

逆强化学习的思想与模仿学习有一定的相似之处，均需要借助专家示例库对问题进行优化。行为克隆是最早的模仿学习形式，与行为克隆简单学习一个状态到动作的映射不同，逆强化学习算法中奖励函数的学习方法原理如下：假设专家策略本身是根据某种奖励学到的最优策略，那么专家示例即可取得最优奖励值。根据此假设，设置参数化的奖励函数，并且寻找参数使得专家示例的奖励优于其他任意数据，这样即可求解出奖励函数。然而，上述“其他任意数据”并不具备可操作性，因此常采用迭代过程：根据当下学到的奖励函数学习策略并生成轨迹数据，该轨迹数据替代“其他任意数据”，对比专家示例和生成的轨迹数据，来学习下一轮奖励函数。逆强化学习的流程如图4所示。

图4 逆强化学习流程图

奖励被定义为线性结构，即特征向量的加权和，表示如下：

r(st)=θTf(st)，

式中，θ=[θ1,θ2,…,θK]为K维权值向量，K为特征向量维度；f(st)=[f1(st),f2(st),…,fK(st)]为根据状态定义的与奖励相关的特征向量。因此，一条轨迹ζ的奖励可以表示为

R(ζ)=∑tr(st)=θTfζ=θT∑st∈ζf(st)，

给定Dijkstra算法得到的专家示例集D={ζ1,ζ2,ζ3,…,ζM}，其中M为专家示例轨迹的数目，问题转化为找到参数θ使得专家示例的奖励最优。因此，目标函数如下：

由上述奖励函数的表示方式，目标函数转化为

奖励函数参数θ的更新使用了梯度上升的方法，直到其收敛。为防止过拟合，本文引入了参数θ的L2正则化，目标函数改写为

式中，λ为正则化参数，且满足λ>0。

因此，梯度公式变为两轨迹集间特征期望的差异加上正则化项的梯度：

参数θ的更新公式为

θ=θ+α∇θJ(θ)，

式中，α表示学习率。

经过上述过程的迭代，即可求得最优参数θ，从而得到最优的奖励函数。然而，上述算法如果被运用，还需要得到专家示例库，才可通过与专家策略进行对比求得奖励函数的参数。

2.6 构建IRL专家示例

在逆强化学习中，专家示例的选择会直接影响策略的学习，因此，如何构建专家示例十分关键。Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径的问题，在路径规划问题中得到了广泛的应用[23,24]。考虑到Dijkstra算法能生成最短路径的特点，本文将Dijkstra算法生成的路径设置为专家示例。然而，传统的Dijkstra算法只考虑最短路径的问题，而无法同时考虑选择充电点以及计算充电时间等充电相关动作，因此需要在传统Dijkstra算法上做出一定改进。在本文中，给定起点、终点对，需要先利用传统Dijkstra算法得到最短路径，再考虑该条最短路径有哪些点在充电桩节点的集合中，由这些点作为分割点得到子路径Sub_path。对于每条子路径Sub_pathi的耗电量情况进行分析，充电指示charge_index取值如下：

charge_index=

式中，use_power(Sub_pathi)表示子路径Sub_pathi的耗电量；Soci-1表示电动汽车在最短路径中第i-1个充电桩节点时的剩余电量；limitbatt表示电动汽车的最低电量，本文设定limitbatt=0.1。charge_index=1时表示需要充电，即对于某一个路径中的充电桩节点，若下一条子路径耗电量大于剩余电量与最低电量之间的差值，则在该充电桩节点需要充电。

对于充电的目标电量，本文采取部分充电的策略[25]：若下一条子路径的耗电量小于等于0.7，则在此充电桩将电量充到0.8；若下一条子路径的耗电量大于0.7，则此次充电需要将电量充到1。此外，为了更接近现实中的情况，本文也考虑了分段充电的策略，从电量0充到目标电量x的充电时间charge_time如下：

charge_time=

式中，电动汽车的电量达到0.8之前的充电效率高于其电量达到0.8之后的充电效率，这与现实中的设定相同。为简化运算，本文将电量达到0.8之后所需的充电时间也用线性函数表示。关于电量的充电时间函数如图5所示。

图5 充电时间函数

因此，一条包含充电策略的最短路径可被求得，并将此路径作为专家示例。Dijkstra算法在较小的路网中有较好的性能，然而当其运用在大型路网中，该算法需要花费很长的时间得到邻接矩阵，且它的运行效率与路网规模成正比。而本文基于逆强化学习的方法是在专家示例中学习其行走与充电的策略，这种策略对于不同的路网或大型路网也同样适用，而无需对模型重新进行训练。

3 实验验证

3.1 数据集

选用两个路网分别对模型进行训练，两个路网均是北京市路网中的一部分。路网Ⅰ包含76个节点以及105条边，纬度为39.893°-39.898° N，经度为116.390°-116.405° E。路网Ⅱ包含75 956个节点以及101 052条边，纬度为39.4°-40.4° N，经度为115.8°-117.0° E。路网的数据集由两部分构成：点集与边集，其中点集中包含各点的经纬度信息，边集中包含每条路径起点、终点的经纬度以及起点、终点之间的距离，由点集与边集构成的路网如图6所示。由于充电桩节点的数据集未公开，且关于充电桩的布局不是本文的研究重点，因此随机选择点集中的点作为充电桩，这对实验结果并不影响。

图6 北京市部分路网

3.2 基准方法

通过将所提出的方法与以下基准方法进行比较，开展性能验证。

(1)Dijkstra &完全充电策略(Dijkstra & Full charge)。Dijkstra算法在小型路网中能够高效地得到最短路径，但未考虑充电策略。如2.6节所示，此基准方法对Dijkstra进行改进并采用完全充电策略，即每次在充电桩节点充电时都将电量充满，以验证部分充电策略的有效性。

(2)RL & Dueling DQN。与本文相同，此方法结合Dueling DQN算法对Q值进行近似。然而，强化学习中的奖励凭借人为经验进行设置，用此基准方法可验证逆强化学习算法获得的奖励函数的优越性。

(3)RL & DQN。与方法(2)相同，此方法的奖励同样人为给定,且与方法(2)设置相同的奖励，并通过经典的DQN算法对Q值进行近似，此方法用来验证Dueling DQN算法的有效性。

3.3 评价标准

本文从有效性和高效性两方面对模型进行评价。在有效性评估方面，对于电动汽车的出行规划，行驶时间(Tpath)以及充电时间(Tch)两个基本评价指标尤为重要，直接影响电动汽车的出行效率。此外，充电频率(Frqch)高会导致充电服务时间长，因此充电频率也是一个重要的评价指标，本文用路径中包含的充电次数对该指标进行衡量。除上述3个评价指标外，由于用户在行驶过程中希望尽可能避免绕路，因此绕路次数也值得关注，这一指标用loop值衡量。因此本文对于有效性的评价指标包括：行驶时间、充电时间、充电频率、绕路次数。本文用Gap来量化所提出的方法与基准方法之间的差异，前两个指标的Gap表示为

式中，ExistF表示基准方法的性能，PropF表示本文提出的方法的性能；GapTpath和GapTch分别表示两种方法之间行驶时间以及充电时间的差异。由于后面两个指标中PropF的值可能为0，因而直接用两种方法的差值表示Gap，类似地可表示为

Gap(Frqch)=ExistF(Frqch)-PropF(Frqch)，

Gap(loop)=ExistF(loop)-PropF(loop)。

Gap的值越大，说明本文提出的方法性能相对基准方法越好。

对于高效性的评估，使用运行模型所需的时间作为评价指标在不同的模型之间进行比较。模型运行时间越短，说明模型越高效。

3.4 实验结果

表1 路网Ⅰ及路网Ⅱ中本文方法与基准方法的效果比较

通过Gap详细对比不同方法生成的每条路径，将起点、终点对相同的路径归为一组，路网Ⅰ中的结果对比如图7所示，路网Ⅱ中的结果对比如图8所示。本文模型在绝大多数路径中表现最为优秀。

图7 路网Ⅰ中不同方法生成的路径结果对比

图8 路网Ⅱ中不同方法生成的路径结果对比

为验证模型的高效性，对路网Ⅰ、Ⅱ模型的运行时间进行对比，如图9所示。在高效性验证中，Dijkstra算法在较小的路网中运行时间略微短于强化学习以及逆强化学习模型。然而Dijkstra算法的运行时间与路网规模强相关，因此在大型路网中，Dijkstra算法的运行时间远远长于强化学习模型与逆强化学习模型。这也证明了本文模型在大型路网中的高效性。

图9 模型运行时间对比

该模型的收敛性如图10所示，在训练一定轮数后每一轮获得的奖励值趋于稳定且神经网络的参数也逐渐收敛。

图10 模型收敛性

此外，训练出来的模型也能较好地直接应用在其他路网上而无需重新训练，而Dijkstra算法不具备此特点。处理不同的路网时，Dijkstra算法需要重新进行数据预处理而不能将原有模型直接应用在新路网中，即不具备迁移性。本文在两个未经训练的新路网中运行模型用以验证迁移性，在路网Ⅲ和路网Ⅳ中随机设置起点、终点对运行模型，观察能否得到可达路径，利用可达路径的比例评估不同模型的迁移性。在两个路网中各模型的可达路径比例如表2所示，本文模型在两个路网中均表现最佳。

表2 模型迁移性对比

4 结论

本文将考虑充电行为的Dijkstra算法生成的轨迹作为专家示例，使用Dueling DQN算法对Q值近似，提出了一种基于逆强化学习的电动汽车出行规划方法。该方法能够有效引导电动汽车用户选择一条可达目的地，并且行驶时间短、充电时间短、充电频率少的路线行走。通过引入分段充电以及部分充电策略，使研究场景更接近现实情况，从而有效地提高了充电效率；并利用北京市真实路网中的部分路网图对模型进行评估，结果表明，本文提出的方法优于其他基准方法。此外，本文方法具有很好的迁移性，可以有效地应用在其他未经训练的路网中。在后续的研究中，基于现有方法策略以及实验结果，本文模型可引入非线性奖励函数形式，进一步挖掘特征向量之间的联系以得到更适用的奖励函数，从而提升模型的性能。