带时间窗和充电问题的电动车路径优化及实现

孙屹飞，蒋洪伟，张轶兰

(北京信息科技大学 信息管理学院，北京 100192)

0 引言

从现代物流管理系统的总体构成来看，路径规划问题是物流管理当中的核心问题之一。尤其在互联网电商交易和物流产业快速发展的今天，如何实时、动态、高效地调度车辆并合理规划行车路径一直是学界和业界共同关注的焦点。作为运筹学中一类典型的组合优化问题，经过国内外专家和学者半个多世纪的研究，路径规划问题已由早期的静态问题发展成为动态的、带复杂约束条件、多目标、多车场等类型的路径规划问题。

物流公司的路径规划问题一般表现为车辆路径问题[1](vehicle routing problem,VRP)，它的目标为最小化物流公司的运输成本，条件为每个客户点都只被访问一次，路线的开始和结束在同一仓库。最初的VRP是由Dantzig等[2]提出的。在此之后，VRP的许多变种和扩展被应用于各种场景。研究最广泛的2个扩展为：约束车辆的运力；带时间窗的VRP，一种客户必须在指定时间间隔内到达[3]的约束模型。之后，Erdogan等[4]提出了绿色VRP(green-vehicle routing problem，G-VRP)，一种电动汽车的车辆路径模型，其考虑到车辆的电池容量有限，以及必须在充电站充电，对于每次充电以及访问客户，都要考虑固定的服务时间。本文在基本的G-VRP基础上，还考虑了有限的车辆运输能力和客户时间窗，这是现实世界物流应用中最重要的限制因素。由于模型参数过多无法精确求解，我们设计了邻变域禁忌搜索算法(variable neighborhood search/tabu search, VNS/TS)用于模型求解。

1 电动汽车运输路径优化模型构建

1.1 参数定义

为了更加清晰准确地描述模型，本文对模型中使用到的符号进行如下定义：

N:客户点集合；

K:车辆集合；

M:充电站集合；

O:配送中心，o为起点，o′为终点；

V:充电站、客户点、配送中心点的集合，V=N∪M∪O；

C:运输成本；

dij:点i到点j的路径长度，i,j∈V；

Q:车辆的载重量；

c:用电价格；

P:车辆的电池容量；

qi:点i∈N的需求

ei:客户点i要求的最早服务时间，i∈N；

li:客户点i要求的最晚服务时间，i∈N；

tij:车辆从点i到点j所需要的时间，i,j∈V；

v:车辆在配送过程中的行驶速度；

1.2 数学模型

目标函数：

(1)

约束条件：

同一车辆只经过客户点一次的约束为

(2)

保证进出客户点的车辆数目相等的约束为

(3)

保证车辆到达客户点的时间小于离开的时间约束为

(4)

保证车辆起点、终点都是配送中心的约束为

(5)

(6)

车辆的载重约束为

(7)

车辆离开客户点i的时间等于到达客户点i的时间、服务时间、等待时间三者之和：

(8)

电动汽车到达点j的时间等于电动汽车离开其前一点i的时间加上其从点i行驶到点j所需要的时间[5]，即：

(9)

(10)

在客户点停留过程中不消耗电动汽车自身电能的约束为

(11)

2 求解E-VRP的VNS/TS算法

2.1 预处理阶段

删除不满足时间窗和车载容量约束的边，即将满足式(12)、(13)、(14) 的边(i,j)移除：

i,j∈V∧qi+qj≥Q

(12)

(13)

(14)

2.2 生成初始解

首先，按角度划分，将客户点和配送中心连线，排列连线和水平线的夹角大小[5]，从最小的角度开始，沿着角度增大的方向，画出一个扇形，扇形覆盖的客户点定义为一个“群”，直到“群”中客户点的需求超过车辆车容量限制，则停止。当一个“群”的客户点总需求超过车载容量限制后，取出临界客户点，再通过相同的方法，以该临界点为起点，另起一个“群”。也就是说，这个本文定义的“群”本质上是每辆车的路径。重复运用上述方法，直到所有的客户点都被分到了对应的“群”中；然后，对“群”进行操作，将客户点的最晚可行时间从小到大排序，使每个“群”的点形成一条路径，配送中心为路径的两端，然后以“群”中最晚可行时间最小的客户点作为该“群”路径的第一个客户点，即路径的第二个点。接下来根据式的目标函数值，从小到大依次插入路径中[10]，即

f(S)=C+Ltw(S)+Lcap

(15)

式中：Ltw(S)为时间窗惩罚函数；Lcap为载重量惩罚函数，为常数。

2.3 VNS算法及其结构

为了使搜索过程跳出局部最优[6]，靠近全局最优，VNS算法随机地改变解邻域结构。本文采用4种不同的算子进行求解。分别是or-opt邻域、swap邻域、 2-opt*邻域[7]和cross邻域。

swap邻域操作将当前解S中同一条路径上的2个客户或分别来自不同路径上的2个客户互换得到的新解定义为邻域解。or-opt[11]邻域操作将当前解S中一条路径上顺序相连的一些客户移到同一条路径上的其他位置或不同路径上后得到的新解定义为邻域解。2-opt*邻域结构是求解旅行商问题的2-opt邻域结构在路径间交换的一个扩展。2-opt*邻域[9]操作首先在当前解S中2个不同路径中分别移走2条边，然后针对这2条边对应的4个客户进行操作，将第1条路径上的第1个客户与第2条路径上的第2个客户 相连，第1条路径上的第2个客户与第1条路径上的第1个客户相连，得到的新解作为邻域解。

2.4 TS算法

通过VNS算法，得到邻域解S′后，将进一步通过TS算法进行优化。TS算法使用的目标函数为式(15)，算法的流程如下：

第一步定义算法初始参数，包括最大迭代次数及禁忌表长度等。输入邻域解S′，将初始解赋值到当前解S″和TS算法的第一阶段的全局最优解S，禁忌表置空，并构造邻域结构集N。

第二步依据TS算法的条件，判断算法是否满足TS算法终止规则，若满足，则S″←S″*，否则转第三步。

第三步选择邻域Nk∈N，基于当前解S″产生邻域解集Nk(S″)，从中随机选择一些解构成候选解集，从候选解中选择最优的解，判断其是否被禁忌，如果被禁忌且不满足特赦规则，则选择候选解集中的次优解，再次进行判断；否则转入第四步。

2.5 VNS/TS算法流程

VNS/TS算法是VNS与TS的混合启发式算法，在国内外的多个组合优化问题上得到了较好的结果。Schneider等[7]首先使用VNS/TS求解电动汽车的带时间窗的车辆路径问题。

VNS/TS算法分为3个阶段。首先是初始化阶段，该阶段的目的是降低网络复杂度，使之后的计算变得简便；然后，通过一个两阶段的算法求解问题得到初始解：使用VNS算法处理初始解，根据定义的邻域结构，求得初始解的邻域解，VNS算法确立邻域解之后TS算法将根据这个解进行进一步的优化；最后，通过基于模拟退火[8]的评估机制来评估算法有效性。如果新解得到了有效性评估，则代替上一步的解成为当前解。VNS/TS算法的具体实施步骤如下：

Step1通过初始化阶段，处理网络中的非可行解并且简化问题网络。

Step2通过VNS和TS两阶段算法得到路径问题的初始解：

Step2.1在忽略电池里程的前提下，求解车辆路径的初始解S0。

Step2.2基于上一步，找出不满足电池里程约束的路径。

Step2.3在不满足电池里程约束的路径上迭代插入充电站，使该路径满足电池里程约束。

Step2.4重复Step2.3直至所有路径都满足电池里程约束，更新初始解S0。

Step3将所得初始解S0记为当前解S，迭代次数t设为0。

Step4更新t：t←t+1。

Step5判断迭代次数是否达到VNS/TS 算法预设最大迭代次数，若是，则停止算法，并输出当前解S，否则继续。

Step6使用VNS算法优化当前解S。

Step6.1定义邻域结构Nk。

Step6.2定义k←1。

Step6.3根据所选邻域结构和选择方法，求得当前解的邻域解S′←Nk(S)。

Step7使用TS算法优化VNS阶段的解S′，得优化解S″。

Step8比较S″和当前解S，如果S″通过了基于模拟退火的评价机制，则S←S″，转回Step4; 否则K←(KmodKmax)+1转至Step6.3。VNS/TS算法流程如图1所示。

图1 VNS/TS算法流程

2.6 新解的评价

为扩大搜索空间，不陷入局部最优，VNS/TS算法在追求不断优化新解的同时，也一定程度上接受恶化解。VNS/TS的新解评价机制基于模拟退火的思想[12]，模拟退火算法能够以一定的概率通过当前的恶化解。用S″表示从TS算法得到的新解，S为当前解，则新解S″被通过的概率根据式(16)计算：

p(S″)=e-(f(S″)-f(S))/T

(16)

式中T的初始值为T0，并在每次迭代后根据更新函数Tn=v·Tn-1更新，更新函数中的v∈(0,1)为一个提前定义的常数。

3 实验结果分析

本文运算的测试环境为英特尔I5处理器，内存4 GB的台式电脑。VNS/TS算法是通过单线程JAVA实现。算例为随机构造而来，名称的含义为客户点-充电站，以K50-6为例，为50个客户点，6个充电站点构成的网络。使用CPLEX和VNS/TS算法对所构造的6个算例进行求解。其中，VNS/TS算法对每个算例执行20次，取最优结果。根据常见做法，对CPLEX的运算时间设置2 h的上限。所得实验数据如表1所示。从表中可以看出，VNS/TS算法的精确性良好，其计算结果与CPLEX算法所得的最优解在小规模问题上没有误差。同时，VNS/TS算法在运算速度上大大优于CPLEX，当CPLEX无法在2 h的运算时间上限内完成K75-10和K100-10的计算时，VNS/TS可以在2 s以内求得可行解。

表1 测试算例运算结果

4 结束语

本文提出了一种求解E-VRP的有效算法。不仅在小规模数据集上可以得到与CPLEX相同的结果，还可在CPLEX无法计算的大规模数据集上得到有效解。算法首先应用两阶段方法产生初始解，再根据变邻域搜索算法机制应用4种不同搜索范围的局域搜索算子对初始解进行改进，之后通过禁忌算法对解进行再次优化。实验结果表明，VNS/TS算法在不同规模数据集上都有良好表现。