英文：Adaptive Elitist Genetic Algorithm With Improved Neighbor Routing Initialization for Electric Vehicle Routing Problems(2021)

摘要

        本文将精英遗传算法应用于有时间窗口的电动汽车路由问题。在初始化方面，本文提出了一种改进的邻居路由初始化方法，用于自适应精英遗传算法。改进的邻居路由方法被用来选择最近的电动车客户作为下一个要安排的路线，并在精英主义GA的初始化过程中使路线从合适的第一个客户开始。这使得预定路线从一个相邻的方向性开始，这可以在选择、交叉和变异操作中继承下来。为了有效收j，我们提供了新的自适应交叉概率和变异概率，使算法更快地收j。对随机分布的客户和Solomon基准案例的实验研究表明了该算法的有效性能。

该算法在一个美国的邮政服务系统。模拟中得到了证明。

---

I.引言

        如今，随着消费和购买活动的增加，许多运输车辆被用来将货物或货物从仓库运送到客户手中。如何提高运输效率并使路由成本最小化被称为车辆路由问题（VRP）[1]。在交通方面，电动汽车（EV）比内燃机汽车更有利于节能和减少污染物，许多国家要求在其交通系统中使用电动汽车。因此，电动汽车路由问题（EVRPs）是近年来许多研究的主题[4]。

        EVRP是一个NP-hard优化问题，有许多约束条件，如车辆装载限制、车辆电池限制、客户时间窗口限制等。为了提高效率，应该尽可能地减少电动汽车的数量，一些电动汽车可能需要在交付过程中进行充电服务。因此，应该考虑充电时间和充电成本[8]。每个客户都有自己的时间窗口，这就要求每个客户都应该在一定的时间段内得到服务。如果一辆电动车在这个时隙之前或之后到达，惩罚成本将被添加到路由时间表中。这将增加整个路由成本。这样的问题被称为带时间窗口的电动车路由问题（EVRPTW）[9], [10]。

        对于解决所有这些问题，启发式遗传算法（GA）方法已被证明是有前途的[10] [12]。Braÿsy和Gendreau表明GA是EVRP中最具竞争力的启发式算法之一[10]。Ombuki等人。[11]将GA用于具有时间窗口（VRPTW）的车辆路由问题，并取得了快速融合的结果。Schneider等人。[12]通过应用混合启发式算法将EV引入VRPTW问题，以获得有效的性能。

        在遗传算法迭代中，过早收敛和进入局部最优是遗传算法的主要问题[13]-[15]。为了提高其在EVRPTW中的收敛性能，需要对算法的三个方面进行研究。第一个方面是遗传算法的初始化。传统的遗传算法使用随机初始化，这可能导致局部最优。由于每个EV都会到达相关的相邻客户，因此可以在GA初始化中使用相邻路由调度。Rezgui等人[16]称这种方法为贪婪算法，因为它选择最近的客户来验证路由问题中的所有约束。在邻接表中，靠近仓库的第一个客户是初始路由的关键领导者。然而，如何选择第一个客户还没有提到。提高遗传算法性能的第二个方面是自适应交叉概率和变异概率。它们是调整遗传算法收敛速度的关键参数[17]，[18]。传统遗传算法中固定的交叉概率和变异概率会使收敛速度变慢，尤其是在有大量客户的情况下。Srinivas和Patnaik[17]给出了交叉概率和突变概率的自适应线性函数，这些函数可用于实现。但当适应度接近最大值时，交叉和突变的概率将非常小，从而导致局部最优。提高遗传算法性能的第三个方面是遗传算法的精英性。精英是父代中适应度最好的染色体。它们应该遗传给他们的孩子一代，以使适应度在迭代过程中更好地发展[13]。

        考虑到上述所有问题，本文将精英遗传算法（EGA）应用于EVRPTW。在初始化中，EGA的邻居路由方法（NR-EGA）被用来选择最近的邻居客户作为下一个要安排的服务路线。提出了涵盖第一个客户选择的圆圈，用于改进邻居路由方法，比较结果见表4。基于Srinivas和Patnaik的自适应方法[17]，提出了一个新的交叉和变异概率公式，以便在适配度接近最大值时保持其数值为中等，这可以使NR-EGA在寻找全局最优时保持其多样性。图13中的对比模拟证明了该方法的性能。

本文的新贡献总结如下。

1）提出了一种改进的自适应EGA的邻居路由初始化方法。它使NR-EGA在初始化时选择最近的邻居客户作为合适的第一个客户的下一个服务路线。这使得预定路线从相邻的方向性开始，这使得NR-EGA更快地找到全局最优。

2）提出了一个新的交叉和变异概率公式，当适配度接近最大值时，将交叉和变异概率的值保持在中等水平，使算法更快地趋近。

3） 本文对随机分布的客户和Solomon基准实例[19]进行了几次模拟，以证明NR-EGA算法的性能，并将其应用于美国邮政局（USPS）132个客户的实际路由调度，这可以帮助USPS做出路由决策。

        本文的其余部分组织如下。第二节介绍了带有时间窗口的电动车路由问题。第三节提出了NR-EGA的算法。第四节和第五节证明了NR-EGA在随机分布的客户和所罗门基准实例中的性能。在第六节中，NR-EGA在USPS交付系统中进行了演示，并在第七节中给出了结论。

II.带有时间窗口的电动汽车行驶问题

        图.1.显示了在EVRPTW问题中，从一个仓库到几个客户的路由计划是如何进行的。时间表中有三条电动车路线。他们都从仓库出发，返回仓库。EV1在路线1中为3个客户提供服务，EV2在路线2中为4个客户提供服务并充电一次，EV3在路线3中为3个客户提供服务并充电一次。路由计划的目标是使所有三辆电动车的总服务时间和服务成本最小。

现在，让电动车的数量为m；这意味着有mroutes的送货服务。因此，路由计划的目标是找到最小的M = {1,...,m }电动汽车集合，满足所有客户的需求一次，而且只有一次，都是从仓库开始，在仓库结束，从而使总服务时间（包括驾驶时间，以及电动汽车充电站的充电和等待时间）和总电能成本最小。

        假设有n个客户和f个充电站。将t ij设置为从客户i到客户j的旅行时间；σi为客户服务时间；ck u为EV kat充电站u的充电时间；w u表示在充电站u的等待时间。如果EV-k在拜访客户i之后拜访了客户j，则将xk ij设置为1；否则，将xk ij设置为0。如果电动汽车在充电站u充电，则将yk u设置为1；否则，将yk u设置为0。因此，路由表中的总服务时间可以描述为上述所有时间的总和，如下所示[10]

III.具有改进的邻接路由初始化（NR-EGA）

A.邻居路由初始化

        初始化对于精英主义遗传算法（EGA）的融合非常重要。传统的GA使用随机初始化，这可以导致局部最优。由于在真实的路由计划中，车辆经常选择邻近的客户作为其下一个服务优先级，因此本文提出了EGA的邻居路由初始化方法（NR-EGA）。

        在路由初始化中，从一个客户开始，NR-EGA搜索所有与该客户相连的可用相邻路线，计算所有路线的距离，然后选择路线最短的客户作为下一个客户。图2.显示了这种方法的操作，客户3不是客户1的邻居。当路线从客户1开始时，可用的相邻路线是1→2、1→4和1→5；其中，最短的是1→4。因此，NR-EGA在初始化时将选择1→4作为电动车的路由计划。

这种初始化方法使预定路线从一个相邻的方向性开始。这一特点可以在选择、交叉和变异操作中继承下来，然后使NR-EGA更快地找到全局最优值.

B.初始化中的第一个用户替代物

        邻居路由方法使每个电动车在路由初始化中更合理地选择其下一个客户，但路由初始化中的第一个客户仍从所有客户中随机选择。有时，它使NR-EGA选择一个离仓库很远的客户，这就形成了一条较长的路线，导致了一个局部最优。

每条电动车路线从仓库出发，然后前往第一个客户。所以，第一个客户应该靠近仓库。因此，并不是所有的客户都适合第一个客户的选择。可用的替代数字应在初始化时决定。图3.显示了范围，所有客户都在半径为R max的圆1中，R max是仓库和最远客户之间的距离。半径为 R 2, R 2 < R max 的圆 2 ， 它涵盖了第一个客户的选择。第一个客户可以从所有这些备选方案中随机选择。

        如果有k辆电动车来做交付工作；由于每辆电动车从仓库出发，在仓库结束；将有2k条路线从仓库出发或结束；因此，至少，将有2k个离仓库最近的客户，他们可能被选为第一个客户选择。这意味着R 2的下限值可以是仓库和这2k个最近的客户之间的最大距离（R 2kmax）。所以，R 2的范围是R 2kmax ≤ R 2 < R max，如图3.所示。

        R 2的值决定了初始种群的随机性。大R 2增加了随机性，因为它让圆圈2变大，给第一个客户的替代品增加了更多的客户，这增加了染色体的多样性。但过大的R 2会让一些更远的客户被包括在内。这将导致NR-EGA落入局部最优。反之，小的R 2会降低随机性，因为它限制了第一个客户选择的数量。如果小的R 2使圆圈2包括最佳的第一个客户，那么NR-EGA可以快速融合。但如果不是这样，NR-EGA将很难融合。

按照上述所有分析，本文使用仓库和所有客户之间的距离的平均值为R 2，可以表示如下。

其中d oi是仓库和客户i之间的距离；m是所有客户的数量。使用平均值使第2圈覆盖所有最近的客户；同时，排除那些远离仓库的客户。在用第一个客户选择相邻的路由初始化后，NR-EGA的初始群体将有更好的染色体来做选择、交叉和变异操作。

C.选择、交叉和突变操作

        当NR-EGA应用于解决电动车路由问题时，所有的仓库、客户和充电站被结合起来，产生NR-EGA的人口。例如，对于一个有9个客户、1个仓库和1个充电站的路由问题，NR-EGA分配数字1到9来表示客户，数字0表示卸货，数字10表示充电站。因此，NR-EGA的人口可以表示为仓库、客户和充电站的随机组合。如果用3辆电动车来做送货服务，NR-EGA群体中的每个个体都可以表示为一个数字串，如图所示。4.在这个数字串中，3个电动车路由时间表是0→2→5→9→6→0；0→4→7→10→0；和0→3→8→1→0。第二个电动车需要在为客户7服务后进行充电

NR-EGA的目标是找到使总服务成本最小的数字串。因此，目标函数可以被描述为五个成本函数的总和

在（11）中，第一项描述了距离成本，第二项描述了充电成本，可以通过（3）计算。第三个描述了违反服务时间窗口的惩罚成本，可以通过（9）计算。最后两个项是路由约束。第四项限制电动汽车的总客户负荷需求不超过电动汽车的负荷容量Q。第五个任务确保所有的电动车都有足够的电池电量来完成交付服务。在前往下一个客户之前，应计算电动车的电池，以满足约束条件（7）和（8）；否则，它应该被充电。为了使这两个约束条件有效，系数M 1和M 2被设置得非常大，例如，M 1 = M 2 = 108。

NR-EGA使用成本函数（11）的倒数作为每个单独的适应度函数fit(i)来进行选择、交叉和变异操作。在一个有数字串的群体中，每个个体都被称为染色体。

1) 选择

        NR-EGA计算所有染色体的适配度fit(i)，并将其相加，sumfit = ∑ fit(i)，其中N是种群大小；然后，计算每个染色体的累积概率，ps(i) = ∑ (fit(i)/sumfit)。如果ps(i)大于[0, 1]中的一个选定的随机数r，ps(i)>r，那么这个染色体将被选中。

2) 交叉

        在选择操作中可以选择两条染色体来进行交叉操作。例如，图5.中所示的两条染色体。被选中。如图6.所示，NR-EGA将它们的随机附属数字串放在前面，从0开始，在0结束。 然后，一个染色体中的其余数字将与另一个染色体的全部数字逐一进行交叉操作。然而，由于客户不应该被服务超过一次，一个染色体中已经在介词串中的数字不能在染色体的其余部分重复使用，而需要被另一个染色体的其余未使用的数字所取代。图7.显示了交叉操作的结果。

        因为数字0也在介词字符串中，一些0在交叉操作后可能不存在；在这种情况下，它们可以被随机地插入到字符串的其余部分，如图7.所示。健身函数fit(i)可以用来评估哪条添加的染色体具有最大的健身能力，这个函数将是交叉结果之一。

3) 突变

进行突变，使NR-EGA搜索到全局最优。交叉操作后，可以随机选择从0开始到0结束的附属数字串来进行变异操作。在突变操作中，NR-EGA颠倒了附属数字的顺序，以确保路线的方向性质量被继承，如图8.所示。

D. NR-EGA的精英

        精英是经过选择、交叉和变异操作后具有最大适配性的p染色体。如图9. 所示，它们被下一代保留和继承。为了保持NR-EGA群体的数量不变，应该拒绝最差的p条染色体。精英主义的保留操作使NR-EGA在每一代中都能记住其最好的染色体。因此，下一代的染色体将比父代的染色体具有更大的适配性；因此，获得全局最优的速度会更快。数字p可以在[5], [10]内设置。

E. 交叉和突变概率

        交叉概率Pc和突变概率Pm用于调整NR-EGA的速度。传统的遗传算法通常使用常数P c和P m，这使得NR-EGA在迭代开始时收敛较慢，在迭代结束时收敛较快，从而导致局部最优。Srinivas和Patnaik[17]提出了第一个线性自适应遗传算法。但在该方法中，当适应度接近最大值时，Pc和Pm将非常小，这将导致局部最优，尤其是在迭代开始时。在此基础上，本文对自适应P c和P mas进行了如下调整

在（12）和（13）中，当适配度接近最大值时，P c和P m可以保持中位数。这使得NE-EGA中的染色体在寻找全局最优时保持其多样性。

---

IV.随机分布的客户端的模拟

为了证明NR-EGA的路由能力，对一个有25个客户的送货问题进行了数值模拟。如图10.所示，这25个客户随机分布在[0-110公里，0-110公里]区域。它们的坐标已经知道。每个客户 i 都有其所需的交付时间窗口 [Ti 1, Ti 2] 。在路由区域，有两个充电站，分别在[83, 45]和[32, 40]，在图10.中缩写为CS。[56, 56]的仓库（Depot）使用电动车来提供送货服务

        在初始化过程中，采用了改进的邻居路由方法。如图10所示，在圆圈内选择第一个客户备选方案。根据函数（10）计算图3中圆的半径R2。

        为了找到描述目标函数（11）中前两个项的电能成本（3），设置电动车速度v为常数，（3）中的电能消耗bk ij可以通过电动车-k的行驶距离来评估。由于电价r ijt和充电价格r ut在服务时间内通常是恒定的，所以它们可以分别设为常数r和r u。在模拟中，每辆电动车以全电池容量开始服务，并在充电后获得全电池容量。如果满电池可以为电动车提供一个固定的行驶距离D max，那么（3）中的充电成本可以通过电动车-k充电后的行驶距离来评估。经过上述分析，设定dk ij为充电前从客户i到客户j的行驶距离的电动车；设定dk′ ij为充电后的距离；那么总的电能成本可以评估如下

从（14）中，总行驶距离是计算总电能成本的关键值。这个值可以在NR-EGA迭代过程中计算出来。为了找到时间窗口的惩罚成本，可以用（9）来计算，其中惩罚价格pun1和pun2可以设置为常数。所有的电动车参数都在表1给出。

为了找到成本最低的路由时间表，NR-EGA使用100个群体进行更新，迭代500次。NR-EGA的参数显示在表2中。所有的算法都在2018年MATLAB平台上实现。

经过500次的迭代，NR-EGA找到了路由时间表。该时间表使用三辆电动车来进行交付。对于每个电动车的路线安排，旅行距离和负载能力见表3。同时，这三条路线也被画在图11. 中。用三种不同的颜色表示。从表3的路线安排来看，在交付过程中，2号和3号电动车需要分别在CS1和CS2充电站充电；因此，这两辆电动车的总行驶距离超过了160公里的有限里程。同时，每辆电动汽车的需求负荷能力不大于5吨的有限负荷能力。

为了分析NR-EGA的性能，模拟比较了三种不同算法的服务成本。NR-EGA、随机初始化的EGA、没有精英主义的NR-GA。所有算法在2018年MATLAB平台上都取得了最佳性能。随机初始化的EGA是传统的EGA。没有精英主义的NR-GA不一定为下一代保留最佳种群。

服务成本由距离成本和惩罚成本组成。作为比较，所有的模拟都以相同的参数进行，如表1所示。图12.给出了这三种算法的仿真结果，其中观察到以下几点。NR-EGA得到最低的成本，并迅速融合。具有随机初始化的EGA收敛快，但它到达了一个局部最优。服务成本比NR-EGA高得多。没有精英主义的NR-GA不能记住来自父母世代的最佳种群，所以它不仅进入了局部最优，而且还在缓慢地趋近。

        为了分析具有交叉概率P c和突变概率P m的NR-EGA的性能，模拟比较了具有三种不同P c和P m的NR-EGA的服务成本，在（12）和（13）中改进了自适应P c和P m，Srinivas和Patnaik[17]分别改进了自适应P c和P m，以及恒定的P c和P m

        对于改进的自适应公式和Srinivas和Patnaik公式，参数P c和P m，被约束在表2中定义的最大和最小范围内。对于常数P c和P m，它们被设定为P c = 0.99，P m = 0.05。仿真结果如图所示。13

从图13.中可以看出。，所有的方法在最后都趋于一致，但采用改进的自适应P c和P m的NR-EGA获得了最快的趋于一致的速度，而采用常数P c和P的NR-EGA则保持最慢。Srinivas和Patnaik的自适应方法在开始时收=快，但随着迭代的进行，P c和P m的值迅速减少，收=慢。改进的自适应P c和P mcan使NR-EGA具有更快的融合速度。

V.与Solomon基准数据的比较

        本文进一步  用Solomon VRPTW基准数据[19]来评估NR-EGA算法。VRPTW基准数据被设计用来评估路由和调度算法的行为。

        由于电动汽车在服务过程中可能需要充电，充电站应该被添加到基准数据图中。在下面的模拟中加入了两个坐标为[25, 43], [75, 60]的充电站。他们的时间窗口与仓库相同。每个充电站的充电时间与每个客户的服务时间相同

        仿真使用VRPTW基准数据：聚类客户集（C201，C205）、随机客户集（R201，R205）和随机聚类客户集（RC201，和RC205），并选择50个客户和100个客户来比较[20]中的原始算法和NR-EGA算法。这些数据有大量的客户。设定每个电动车的车辆负荷能力足够大，以提供交付服务。表5显示了比较结果，其中，第一列显示了基准中的选定数据和选定的客户数量。例如，我们把C201.50和C201.50都看作是在数据C201中选择前50个客户，而我们把C205.100都看作是在数据RC205中选择了全部100个客户。

        由于所有的VRPTW基准数据都没有单位，将表1中的EV参数设置为r = 1，r u = 1，pun 1 = 0.1，pun 2 = 0.1，以使距离成本和惩罚成本具有相同的权重。其他NR-EGA参数的设置与表2相同。所有的性能都在2018年MATLAB平台上实现。

        与随机客户集以及随机和集群客户集的混合相比，在原始算法结果中，集群客户集上使用的总路线距离和车辆总数更少。随着客户数量的增加（从50个增加到100个），表5中的总路线距离和使用的车辆总数也会增加。

        在NR-EGA算法中，两个不充电的电动车被用来解决C201和C205的路由问题。两辆一次性充电的电动车被用来解决其他有50个客户的数据中的路由问题。在有100个客户的RC201和RC205中，使用了3辆一次性充电的电动汽车。使用的电动车总数比原始算法结果中的要少得多。该算法节省了大量的车辆，显示了NR-EGA的适用性。

        在NR-EGA的结果中，对于有50个客户的数据，电动车的负载能力限制不超过600。在RC201和RC205中，随着客户数量从50增加到100，每辆电动车应该为更多的客户提供服务，所以电动车的负载能力限制也应该增加。然而，这些限制并不比原始算法结果中的限制多。

        由于在NR-EGA中使用的电动车数量较少，每辆电动车应该为更多的客户提供服务。如果在一次电动车服务中，一些客户处于同一时间窗口，由于一次电动车不能在同一时间窗口为一个以上的客户提供服务，这种服务将产生惩罚。表5给出了有时间窗口和无时间窗口情况下的总距离。它表明没有时间窗口的总距离比有时间窗口的短。

        为了研究电动车数量和时间窗口惩罚之间的关系，本文在RC205.100数据上用不同数量的电动车进行了NR-EGA模拟。表6给出了仿真结果。

        同时，当电动汽车的数量下降时，每辆电动汽车应该行驶更长的距离。如果距离大于电动汽车的全电池容量所能提供的距离，则应为电动汽车充电。在表6中，当使用3辆电动汽车时，一次性充电的总距离将是最短的。当使用4辆电动汽车时，无需充电即可完成整个配送服务。因此，如果将距离和充电时间作为优先事项，那么在路线安排中可以使用较少数量的电动汽车来提供送货服务。

---

结论

针对有时间窗约束的电动汽车路由问题，提出了一种改进的邻居路由初始化方法和自适应精英遗传算法。改进的邻居路由方法从一开始就赋予所有染色体方向性特征，使精英遗传算法比随机分布染色体算法收敛更快。自适应交叉概率和变异概率使精英遗传算法具有较快的收敛速度。即使在最大适应度下，概率也可以保持在中等水平，并帮助算法避开局部最优。仿真验证了该方法的有效性能。同时，通过对美国邮政投递服务的仿真验证了该方法的实用性。

本文中带有时间窗口的电动车路由模型仍然是一个统计模型，假设电池电池电池持续时间及其充电时间是恒定的，这将在实际交付案例中带来差异和误差[21], [22]。为了解决这些问题，在未来的研究中应该讨论动态电池模型的电动汽车路由问题。另外，充电价格对能源成本也有深刻的影响[23]。应讨论不同充电站和不同充电时间的价格。因此，针对充电价格的电动汽车路由问题的动态精英遗传算法可能是未来研究的主要课题。