车辆路径规划中的Electric Vehicle-Routing Problem简介

今天给大家带来的是电动汽车路径规划问题(Electric Vehicle-Routing Problem, EVRP)的介绍，按照惯例先上目录，其中第三部分的主要内容出自文献“The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations”。

目录

问题简介

VRP与EVRP

E-VRPTW

参考文献

1

问题简介

我们古代的时候有没有类似物流一样的东西呢？我想古代总有到处跑运送物资或者信件的吧，不是还有镖局呢嘛，当然肯定跟我们现在研究的物流有很多不一样的地方。古代运输基本靠动物作为交通工具，到了近代开始有各种机械，比如小时候送信的邮差大多骑的是自行车，现在的物流配送比较多的是用汽车(这里不讨论长距离的)。

我们可以发现业务需求都大同小异，但是运输工具不断变化。我们说的车辆路径规划问题，同样的需求放古代可能就是马匹路径规划问题，虽然作用是一样的，但是由于不同的工具会有不同的特点从而会影响路径的规划。就算都是汽车，大一点小一点也可能会造成路线规划的不同。既然以前的运输交通工具在变化，那么现在的运输交通工具应该也会不断变化。现在是汽车、电动车，以后可能还有会飞的，可能走出地球了要考虑星系中的路径规划了，你看三体里水滴要摧毁人类的舰队不也得解一下路径问题么。

扯远了扯远了，那么今天要说的呢就是用电动汽车作为运输工具的时候的路径规划，也就是电动汽车路径规划(Electric Vehicle Routing Problem, EVRP)。

电动汽车最近几年的发展是比较迅速的，世界上也有很多地方推广用电动的替代燃烧化石燃料的。至于原因，大家可以想到减少尾气的排放让空气质量更好。欧盟在2010年的统计显示交通运输活动排放的温室气体占比将近20%，其中大部分在道路运输的过程中产生。此外还有噪音污染也是存在的，在一些接近高速路的民居附近会安装相应的减少噪音的装置，电动汽车的发动机和传统汽车的发动机不一样，电动汽车的产生的噪声要少得多，而且电动汽车使用的能源是可再生的。

2

VRP与EVRP

既然电动汽车有这么多好处，为啥企业不用呢？当然是因为····贵啊。但是就算现在电动汽车大减价，价格跟燃油汽车差不多，那配送车队会进行更换吗？目前还不一定噢。因为电动汽车要大规模应用还是有些问题要解决的。电动汽车是充电用的，手机也是充电用的，大家出门一天不带充电宝不带充电线，电量很低的时候是不是会很慌？其实开电动车也有这样的顾虑，叫里程焦虑(Range Anxiety)，也就是因担心突然没电引起的精神痛苦或者忧虑（Tredeau and Salameh 2009; Botsford and Szczepanek 2009）。

那燃油汽车就没有这样的焦虑吗？几乎没有，因为加油站到处都有，相当于到处都有你这个手机插座和充电线，而且充电还贼快。即使未来充电站铺设好了，充电速度可能也无法和加油媲美，这样一来配送过程就要多花一些时间在这上面了。此外电池容量低也会导致车辆一次充电的行驶里程相较于燃油的短，而且电池电量还会受环境温度的影响。

充电和电池使得EVRP相较于传统的VRP需要考虑更多东西，在里程比较短，充电站还不够多的情况下，选择在哪个充电站进行充电就需要算法进行选择了，要在电量、里程焦虑、绕路去充电之间作权衡。例如下面这个途中，从顾客2到顾客3的路线可以是去充电然后出发去顾客3。不担心电量的话可以直接出发去顾客3。如果是电量不足以先去服务顾客3再回场站但是又足够回场站的话，就要权衡是不是直接回场站再派另一辆车服务顾客3还是先去充电再接着服务，

还有一个问题是电动汽车充电并不是像汽车加油那样基本是一个线性的过程，汽油在整个加油过程中流速不会有太大的变化。但是电动汽车的电池在充电和放电的效率上并不是线性的，例如在重新充电的时候最后的10%-20%花的时间要比之前的多(Marra et al. 2012)。

由于充电的时间比加油的时间长的多使得充电时间不能被忽视，因此会用一个充电函数来描述这一过程，简化版本的呢会用线性函数来构建，也有研究非线性的充电函数的。但是在实际应用中这两者的差别还是挺大的，使用简化后的线性函数构建充电函数在实际应用中可能会有较大的误差。如下图选取不同的数据作线性函数的拟合，会有相差较大的结果，在实际应用中是需要避免出现这样的问题的。

在现实世界中电量的消耗速度还和载荷、车速、坡度甚至风速等等因素相关。

3

E-VRPTW

在小包裹运输行业，一些大公司，如DHL、UPS和DPD已经开始使用电动汽车进行“最后一公里”的配送，特别是在城市地区。在现阶段而言，路径规划还是能为这些使用电动汽车的企业做些事情的。

今天我们要介绍的是带时间窗约束的车辆的电动汽车路径规划问题，因为时间窗约束在这最后一公里的配送中是比较常见的约束。

文章里使用的算法是变邻域搜索算法和禁忌搜索算法的混合算法。变邻域搜索算法我们曾经仔细地介绍过，这里就不过多的介绍了，补课链接"干货 | 变邻域搜索算法(Variable Neighborhood Search,VNS)超详细一看就懂"。这里的混合变邻域搜索算法跟一般的变邻域搜索算法的shaking阶段是相同的，但是在领域搜索上这里的混合算法使用的是禁忌搜索算法，此外在解的接受上也借鉴了模拟退火算法的思想，也就是说在邻域中搜索得到的解比现有的解差时，算法会以一定的几率接受这个解，如果比现有的解更优的话是一定会接受的。后面会介绍一下一些环节用到的方法。

3.1 数学模型

问题定义就不说了吧，带时间窗约束的车辆路径规划我们也做过很多推文了，这里在定义上把汽车限定在了电动汽车。定义上没有特别大的不同，差异主要体现在我们上文中所介绍的充电环节上。

这个模型的充电函数是线性的，以一个稳定的速率充电。具体的定义小编就假设各位读者人均英语四级以上能够看懂啦(因为公众号整公式符号是真滴难受)

其中优化目标是使得行驶距离最短，约束(2)、约束(3)保证访问的顾客节点和充电站节点是连通的；约束(4)则是保证节点的流守恒，即入的流和出的流要相等；约束(5)、约束(6)保证离开节点在时间上的可行性；约束(7)满足时间窗约束；此外约束(5)~约束(7)也能够防止子回路的出现；约束(8)和约束(9)保证顾客的需求得到满足；约束(10)和约束(11)保证汽车电量不会在0以下。在解问题的算法上由于这个问题是NP-Hard问题，因此算法上还是跟我们之前所介绍的差不多，小规模的精确性算法和启发式算法，文献里用的方法是变邻域搜索和禁忌搜索的混合算法。

3.2 初始解的构造

在进行初始解的构造之前，可以根据一些条件去掉图中一些明显不可行的边，这样可以减少搜索域。满足以下约束的边都是不可行的：

不可行的原因是因为满足约束(13)的边是超过容量约束的边，满足约束(14)和约束(15)的边是不满足时间窗约束的边，而满足约束(16)的边则是违反电池的容量约束的边。

去掉上面这些边后随机选择一个顾客点，该点与场站可以确定一条射线，其余的点也可以与场站确定一条射线，这些射线与第一条射线会形成一个夹角。按照夹角角度的大小将顾客顾客节点做一个排序。根据这些排序将顾客一个一个地指派给一辆车辆的行驶路线，并且安排在增加的行驶距离最小的位置上。如果当前的路线已经超过载货容量或者电池容量的限制了则开启新的行驶线路，直到所有的顾客都被安排上。

3.3 目标函数

文章中的优化目标是使得行驶距离最短。变邻域搜索和禁忌搜索很多时候都会允许非可行解的存在以扩大搜索空间，但是在优化的目标函数上会对违反约束的解增加惩罚项。VRPTW问题会惩罚违反容量约束和时间窗约束的解，使用电动汽车的时候，除了上述这两个约束以外还会惩罚违反电池容量约束的解。

至于约束违反如何计算相信就不用过多介绍了，因为容量通过加减就可以计算出来。时间窗和电量都可以通过计算到达每个节点时的时间和剩余电量进行计算。

3.4 变邻域搜索部分

这里的shaking阶段跟一般的VNS相同，局部搜索会用后面介绍的禁忌搜索部分替代。领域结构由循环交换算子定义。举个例子，如果有三条线路参与循环交换，那么循环交换是这样的

文中用到的邻域结构如下：

每一个小表格中的第二列是参与上述算子的路线的数量，第三列是一条路线中允许移动的连续节点的最大数量。实际移动的数量会取路线上的节点数量和这个最大数量中的最小值。

3.5 禁忌搜索部分

这里的禁忌搜索替代一般的VNS中的局部搜索，可以看作是一种改进吧。这里用到的搜索算子有2-opt*、exchange、relocate和根据问题提出的stationInRe。

这个2-opt*可能说的并不多，我们之前的推文有介绍过2-opt算法，算法的操作像下面这样

但是这个算法在有时间窗约束的情况下并不是特别适用，因为这个算法会反转一部分顾客节点的访问顺序，破坏解的可行性的可能性会变大。2-opt*正是为了尽可能避免这种破坏提出来的，即同样是交换一对边，但是保留访问顺序。举个例子，在图上的一条路线是一个环，2-opt*算法就是在两个环上交换一对边，并且保持剩下的节点的访问的先后顺序。如下图

这里要介绍一下文里提出的stationInRe。这里的station是指充电站，In指的是insertion, Re指的是removal。这个算子针对的是所有与充电站相连的边，即边(v,w)，其中点v为充电站，令w-为点w的上一个顾客节点。如果(v,w)不是解的一部分，那么就将这个边插入到(w-,w)之间。反之则将(v,w)移除掉。

至于禁忌规则跟我们以往介绍的差不多，被移除的边在接下来的特定次数的迭代中不能重新插入到一些地方。特赦原则与一般的禁忌搜索相同，接受处于禁忌状态但是比当前最优解更优的可行解。

4

参考文献

参考文献

Schneider M, Stenger A, Goeke D, et al. The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations[J]. Transportation Science, 2014, 48(4): 500-520.

Marra F, Yang G, Larsen E, et al. Demand profile study of battery electric vehicle under different charging options[C]. power and energy society general meeting, 2012: 1-7.

Montoya A, Gueret C, Mendoza J E, et al. The electric vehicle routing problem with nonlinear charging function[J]. Transportation Research Part B-methodological, 2017: 87-110.

Davis B, Figliozzi M A. A Methodology to Evaluate the Competitiveness of Electric Delivery Trucks[J]. Transportation Research Part E-logistics and Transportation Review, 2013, 49(1): 8-23.

Botsford C, Szczepanek A (2009) Fast charging vs. slow charging: Pros and cons for the new age of electric vehicles. EVS24 Internat. Battery, Hybrid and Fuel Cell Electric Vehicle Sympos., Stavanger, Norway.

Tredeau F P, Salameh Z M. Evaluation of Lithium iron phosphate batteries for electric vehicles application[C]. vehicle power and propulsion conference, 2009: 1266-1270.