基于GCOA算法的带时间窗车辆路径规划问题研究

张杰飞 王晓丽

摘 要：GCOA算法是对遗传算法的重大改良，不仅加快了遗传算法的收敛速度，而且从一定程度上避免了遗传算法陷入局部最优，并增大了遗传算法获得最优解的能力。本文首先介绍了GCOA算法，然后通过具体问题的解决对比传统遗传算法与GCOA算法，得出GCOA算法在收敛速度及结果优化两方面的有效性，最后将GCOA算法应用于求解VRPTW问题上，得出最优化结论。

关键词：GCOA;时间窗;车辆路径规划

Abstract： The GCOA algorithm is an important improvement of the genetic algorithm， which not only speeds up the convergence speed of the genetic algorithm， but also avoids the genetic algorithm falling into the local optimum to some extent， and increases the ability of the genetic algorithm to obtain the optimal solution. This paper first introduced the GCOA algorithm， and then， by comparing the traditional genetic algorithm and GCOA algorithm through the solution of specific problems， obtained the effectiveness of GCOA algorithm in convergence speed and result optimization; finally， GCOA algorithm was applied to solve VRPTW problem， and obtained the optimization conclusion.

Keywords： GCOA;time window;vehicle routing problem

1 GCOA算法

美国教授霍勒德（J.H.Holland）创建的遗传算法是根据自然界的生物进化原理所构建出的基因搜索算法。该方法根据自然界生物进化过程中“优胜劣汰，适者生存”的规律，利用某种编码技术作用于称为染色体的数字串，进而进行进化寻优[1]。具体来说，对于所要解决的最优解问题，要先将其解空间编码成可以用电脑进行计算的染色体，然后利用遗传算法的选择、交叉、变异等规则进行一代一代的求解，直到最终找到最优解。

遗传算法主要集中在选择、交叉、变异三大步骤上。通过构造不同的选择方式、交叉逻辑、变异规则，就可以对传统的遗传算法进行一定程度的改良，从而用于解决最优解问题。GCOA算法主要对传统遗传算法的选择方式及交叉规则进行了改良，其具体的算法操作过程如下。

1.1 编码

编码过程是对问题进行转换的过程，将问题的解空间转换为可以进行算法运行的基因序列。常见的编码方式有二进制编码和实数编码两种方式，具体选择哪种编码方式，要根据实际情况。在GCOA算法中，编码方式并没有改变。

1.2 选择方式

遗传算法的具体操作包括优选适应性强的个体的“选择”、个体间交换基因产生新个体的“交叉”、个体基因突变而产生新个体的“变异”[2]。

选择就是要从上一代群体中选择一部分群体进行复制操作，而选择留下的群体是否优良应该以适应度函数作为考察。从生物学角度来说，适应度是指生物群体中个体适应环境的能力。对应具体问题来说，就是此个体作为所求问题的一个解，其优秀程度的高低。因此，好的选择方式应该以能留下更多的优秀解作为目标。传统的遗传算法使用轮盘赌注法来进行选择，后来又有些学者使用精英策略来进行选择。GCOA算法使用基于群体竞争的方式进行选择。基于群体竞争的选择方式主要有两种：一种是将染色體两两对比，从而选择强势染色体;另一种是使所有基因序列同时参与竞争，从而选择最优秀的一部分染色体。从表面来看，第二种办法似乎更能将优势染色体流传到下一代，但其会在无形之中破坏全局寻优的能力。因此，本文使用第一种选择方式进行操作。

1.3 交叉逻辑

依照一定的概率从群体中选择个体组，对于每一组中的2个个体进行部分染色体的交换。通过交叉操作来使遗传算法的搜索能力得以迅速提升[3]。

GCOA算法中，交叉是提取上一步选择方式中得出的优良染色体的部分区段，随机放至新产生的染色体中。这样新产生的染色体就部分继承了优良染色体的优秀基因，而新染色体的其余区段可以随机产生，这样就保证了算法的全局寻优能力。GCOA算法的选择与交叉是有别于传统遗传算法的，这是获得最优解的基础。

1.4 变异规则

对于群体中的每个个体，以某一概率将某一个或数个染色体上的基因进行改变，从而得到不同的个体。这种改变虽然变化不大，但却从一定程度上保障了检索的全局性，避免陷入局部最优而无法跳出。由于编码一般使用两种方法，即二进制法或实数法，所以变异的方式也存在二进制变异和实数变异两种模式。另外，变异的概率不能过大，否则会影响寻优的效率。因此，变异操作的过程是：先以一定的概率确定某个个体是否需要进行变异，如果需要，则随机选择个体需要变异的位置进行变异操作。

2 GCOA算法解决TSP问题

TSP问题（Travelling Salesman Problem）即旅行商问题，是数学中有名的寻求最优解问题[4]。假设有一个商人，要将自己的货物在[n]个城市进行售卖。这个商人就要选择一条能够依次走过所有城市的路径，每个城市都只能被走过一次，最后回到出发城市。而这条路径选择的最终目标就是要在所有可能的路径中寻求最短的一条。所以，TSP问题就是寻找最短路径的问题。

这类最短路径问题实际上可以归结为图论问题，即“已给一个[n]个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。很多学者都发现，这个问题不管难度级别是否一致，但只要能够找到一个有效的算法，所有此类问题就都可以使用這个算法进行求解。

但遗憾的是，到目前为止，还没有对这类问题找到一个有效算法。大部分学者认为这类问题使用精确求解的方式不太现实，应将精力放在寻求近似最优解上。目前，在解决此类问题时普遍采用的遗传算法、蚁群算法、模拟退火算法等智能化算法都在一定程度上将算法的运行时间与算法的结论优化性进行妥协，力求在有限的时间内找到一个近似最优的结论，从而解决实际问题。

在本文，研究者分别使用普通遗传算法与GCOA算法对TSP问题进行求解，并从时间开销、结论优化两方面对这两种算法进行对比。

2.1 问题描述

将前面旅行商的问题具体化，假设商人所要走过的城市是全国的31个省会，行走的方式与前面所提出的方案相同，即每个城市只能走过一次，且最后须回到出发城市。要求最终选择的路径是所有可行路径之中的最短路径。

假设31个省会城市的位置坐标是[1 304，2 312;3 639，1 315;4 177，2 244;3 712，1 399;3 488，1 535;3 326，1 556;3 238，1 229;4 196，1 044;4 312，790;4 386，570;3 007，1 970;2 562，1 756;2 788，1 491;2 381，1 676;1 332，695;3 715，1 678;3 918，2 179;4 061，2 370;3 780，2 212;3 676，2 578;4 029，2 838;4 263，2 931;3 429，1 908;3 507，2 376;3 394，2 643;3 439，3 201;2 935，3 240;3 140，3 550;2 545，2 357;2 778，2 826;2 370，2 975]

2.2 两种算法的解决结果

在使用遗传算法求解时，编码方式采用实数编码，即产生一组1到31随机排列的组合为一个染色体。在MATLAB中使用randperm（31）即可产生一组染色体。计算这组染色体中依次所经过的距离作为适应度，且适应度函数值越小越优秀。采用轮盘赌注法进行染色体选择，交叉时将两个染色体中连续的4个基因组进行交叉，变异时采用0.1的概率改变染色体的一个基因。仿真结果如图1和图2所示。

使用GCOA算法进行求解时，编码方式同普通遗传算法一样。在进行选择处理时，对所有染色体求解适应度，并且两两对比留取数据更小的作为下一代染色体。在进行交叉操作时，从遗传的优良子代中随机选取连续的4位作为交叉基因组。将这组基因序列复制给新的子代，新子代中的其他位置随机产生基因，但要避免产生重复数据。变异时采用0.1的概率改变染色体的一个基因。仿真结果如图3和图4所示。

通过对比仿真结果可以看出，GCOA算法无论从计算速度还是从结果的优化性上，都远远超过了传统的遗传算法。因此，GCOA算法对遗传算法的改良是具有革命性的。

3 GCOA算法求解带时间窗的车辆路径规划问题

车辆路径问题（Vehicle Routing Problem，VRP）的一般定义是，组织合适的行车方案，让众多货车将货物从装货点运送至各个卸货点。在满足车辆容量、卸货点货物需求量、卸货时间要求、行驶里程约束等的条件下，达到一定条件（如总里程最短、总费用最少、总耗时量最小、使用的车辆数最少）的最优化。VRP对应了很多实际问题，包括货物配送、邮件投递、铁路航空调度等。

时间窗是指一个时间段[ETi，LTi]，是由客户卸货点要求的最早到达时间[ETi]和最晚到达时间[LTi]确定的一个服务时间区间。其是在传统VRP问题的基础上给每个卸货点客户加上服务所允许的时间窗（Time Windows）约束，就扩展成了VRPTW。本文采用更接近现实的软时间窗约束进行考虑。软时间窗约束是指如果在[ETi]之前到达则需要进行等待并惩罚，如果在[LTi]之后到达也需要进行惩罚。具体的惩罚函数如下：

接下来解决一个具体的VRPTW问题：现有一配送中心需要向8个客户点运送货物，第[i]个客户点的货物需求量是[qi]，并且每个客户对于到货时间也有一定的需求，分别是[ETi，LTi]，其具体的数值如表1所示。为了使问题相对简单，假设配送中心只具有一种容量的货车，其容量是8 t。现要求合理安排从配送中心出发，经由各客户点后最终返回配送中心的车辆行驶路线，最终使得总运行费用最少。

在这里，假设车辆的行驶时间和距离成正比，每辆车的平均行驶速度为50 km/h。车场各任务点的距离如表2所示。

在进行问题求解时，使用GCOA算法。依然使用实数编码，选择、交叉、变异的规则依据GCOA的处理办法。需要说明的是，在产生各染色体子代的同时，需要另开辟一个数组用以存储间隔位置。例如：2 3 5|4 6|1 7 8表示的是有三条子路径，分别是：配送中心—客户2—客户3—客户5—配送中心;配送中心—子客户4—子客户6—配送中心;配送中心—子客户1—子客户7—子客户8—配送中心。每条子路径中间的“|”表示路径的隔断，另产生的数组以[3，5]的形式存储隔断的位置。这种方法比传统的在隔断处用0表示更容易进行程序处理。适应度函数由符合条件的路径值+惩罚值构成，且数据越小，适应度越好。使用算法求解后得出结论：3 5 2|6 4|8 1 7。各路径的距离分别是：240、265、405 km。取得了最优的结果。

4 结语

本文首先介绍了GCOA算法，说明了此算法是对传统遗传算法的突破性改良;然后，将传统遗传算法及GCOA算法分别应用于TSP问题的求解，得出GCOA算法在收敛速度及结果优化两方面的有效性;最后将GCOA算法应用于求解VRPTW问题上，得出了最优化结论。

参考文献：

[1]王晓丽，贾东明.GCOA算法：一种新的智能优化算法[J].价值工程，2017（8）：170-171.

[2]谢秉磊，李军，郭耀煌.有时间窗的非满载车辆调度问题的遗传算法[J].系统工程学报，2000（3）：290-294.

[3]NAZIF H，LEE L S.Optimized crossover genetic algorithm for vehicle routing problem with time windows[J]. American Journal of Applied Sciences，2010（1）：95-101.

[4]Ben-Tal A，Nemirovski A. Robust solutions of linear programming problems contaminated with uncertain data[J].Mathematical Programming，2000（3）：411-424.