车辆路径中的遗传算法外文翻译资料

英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料

车辆路径中的遗传算法

Barrie M.Baker , M.A. Ayechew

摘要

这篇文章主要研究遗传算法（GA）在最基本的车辆路径问题（VRP）上的应用，在基本车辆路径问题中是同一个控制点为客户提供需求。车辆应该要受到载重限制，在某种情况下，也会有距离限制。而且只允许一辆车为客户服务。

使用tabu搜索或模拟退火获得了最著名的基准VRPs结果。遗传算法已经被广泛应用在各种组合优化问题上，包括一些类型的车辆路径问题，特别是带有时间窗的车辆路径问题。可是他们对我们在这里描述的车辆路径问题影响不大。这篇文章里，只对提出来的纯粹的遗传算法给出结果。进一步的结果是由与遗传算法相近的混合搜索算法给出的，同时也展现出这种方法与tabu搜索或模拟退火在解决方案的时间和质量上的差别。

应用范围和目的

基本的车辆路径问题包括一定数量的客户，每一个客户要求一定重量的货物，从单一控制点出发的车辆必须发送要求的货物，然后返回控制点。每一辆车可以承载定量的货物，同时也可能限制车辆的总的行驶路程。只允许一辆车服务每一个客户。这个问题可以描述为：找到一条合适的运输路线满足客户要求并且消耗成本最小。实际情况中，还会要求行驶的路程要最短，或者要使得用到的车辆最少以及所有车辆的总路程最短。

对VRP的研究大多集中在启发式算法的发展上。尽管现代启发式的发展已经取得了相当大的进展，但对改进性能的追求仍在继续。遗传算法已经被用来解决很多的组合优化问题，包括各种类型的车辆路径问题。本文描述了我们为VRP研究的一个遗传算法解决方法，显示了这种方法在解决方案时间和质量方面可以与其他现代启发式技术相竞争。

1简介

基本的车辆路径问题包括大量的客户，每一个有自己要求的需求水平，这个需求必须有单一的控制点提供。车辆的运输路线也是有要求的，起点和终点都在控制点，满足所有的客户要求同时每一个客户都要服务到。会给出车载容量，同时，通常会有车辆的最大能行驶的距离。在后一种情况下，额外消耗可能是与每个客户关联，它被添加到客户分配车辆的总距离。因此，一种访问许多客户的车辆将无法像一种访问相对较少的客户的车辆。指标可以设置为找到使得车辆行驶总路程最小的路线，或者是使得车辆数量最少同时这些车辆的总路程最少。不同的VRP有不同数学公式，例如参考文献^[1].

用启发式算法解决实际问题。这有许多和课题相关的，包括上面说的基本车辆路径问题的拓展。参考文献^[1]给出了一个调查，参考文献^[1]和参考文献^[2]列写出了很多。

在参考文献^[3]和参考文献^[4]中tabu搜索的应用获得了基准的最优秀的成果。不同的作者也发表过相似的成果，包括tabu搜索^[5-8]，或者模拟退火算法^[5,9]。可是，它被研究出这类启发式算法需要大量的计算时间以及参数设置^[10]。

蚁群优化是最近的一种方法，它是一种有教学方法的组合问题，也有一定数量的成果案例，包括VRP^[11,12]。与2-optimal启发式不同，该方法还包括改进由蚂蚁产生的个人路线 结果仅略低于tabu搜索结果。

遗传算法(GA)已经在现代的启发式解法中得到广泛应用，还有一些对于带有时间窗的车辆路径问题的应用^[13-20]。据报道，遗传算法已经应用到带有回程取货的车辆路径问题上^[21]，最少控制点路线问题上^[22]，以及校车路径问题上^[23]。但是，目前看起来遗传算法在计算方面，与其他现代启发式在时间和解决方案质量对基本车辆路线问题的影响并不大。把邻里搜索并入GA的混合的启发式算法，也有被纳入考虑之中。给出了一些基准问题的计算结果，同时也有使用禁忌搜索和模拟退火获得了众所周知的结果。

2 遗传算法基础

遗传算法的原则是众所周知的。这是维持一个种群的解决方案也是一个繁殖过程允许从种群中选择父母的解决方案。后代中也展现出每一个父代的特点。每一个解得适应度与目标函数值有关，例如总行驶的路程，以及违反了约束条件的程度。类似生物过程，有着好的适应度水平的后代更可能存活、繁殖，随着种群适应度的提高，种群也会随着进化而扩容^[25]。

任何遗传算法的起点都在每一个解决方法中或者种群数量中。通常，它会体现为字符串或者染色体的形式。每条染色体上的点被称为基因。尽管在很多遗传算法的研究中二进制字符串已经得到了很多人的青睐，但是一些成功的实现使用非二进制表示。例如，参考文献^[26]中的研究就是利用非二进制解决GAP问题，这个问题要求工作人员按最低总成本分配给代理人 每个代理的资源限制。在他们的描述中，每一个染色体包括一个是十进制的字符串，在作业的索引顺序中，指定每个代理编号进行分配。

过去，VRP与GAP之间的结构相似性已经被发现并被成功地利用^[27,28]。我们的VRP问题描述是和文献^[26]的问题描述是一致的，对每一个顾客，会分配它车辆编号。因此，若是给出n个客户以及m个车辆，对于一个单独个体的染色体以长度n的字符串形式，并且染色体上的基因值从[1,m]之间取值。与一些已经被使用在VRP上的表述不同，这没有明确地指定每辆车应该遵循的路线。可是，对于已知车辆的客户分配，单独的路线是隐士的，包括行驶的总路程以及违反约束函数的程度。旅行商（TSP）的解决方法是每一辆车都需要一个明确的解决方案， 使适应度的值与每个群体成员相关联。

为了尽可能多地保持结构性，需要采取两个步骤。第一，客户排序并编号，这样连续的客户很可能被同一辆车服务。在这个问题中，客户被随机分配到控制点周围，他们根据极角的顺序进行排序。当客户在集群中而不是随机分布的时候，他们根据最近的邻居解决方案进行分类，从控制点开始拜访所有客户。第二，我们试图给车辆编号以使任何车辆，i，对同一地区所有的成员进行操作。我们采用对遗传算法采用通常的生物繁殖过程，产生新的解决方案，与父代共享相同结构。下面几节将详细描述这些方面。GAP事实证明方法是成功的，我们可以合理地期望这样的一个GA产生良好的VRP解决方案。

3 生成初始种群

实验是有随机生成的初始种群，初始种群数量的结构化解决方案，混合的种群包含随机和结构化的解决方案。预期是一个合理的初始种群将会发展，在相对少数几代的GA中提供高质量的解决方案。一个潜在的缺点是这样的种群与使用tabu搜索获得的质量相比将缺乏获得近乎最佳解决方案所需的多样性。

图1 扫描包括最后一个客户条件

两种方法用于生成一系列结构化解决方案。第一个方法是基于扫描方法。对于问题而言客户随机分布在控制点周围，并且按极坐标的增加顺序排列。然后，生成每一个种群成员，在每一辆车的扫描过程中会随机选择一个客户。客户按顺序分配给当前的车辆，直到违反了约束条件。依据规则，在下一辆车进行扫描之前，最后一个客户有可能会或者不会被移除，对于只有容量限制的问题而言，在添加最后一个客户之前，车辆的剩余容量将表示作为该客户需求的一部分，用Rc表示。对于有容量限制以及距离限制的问题而言，在添加最后一个客户之前，额外的距离作为最后一个客户的额外距离，用Rd表示。因此，Rc或Rd的值接近1表示轻微的违反约束，Rc或Rd的值小则表示违反约束的程度大。这个决定规则用于确定最后一个客户是否从考虑到问题紧密性的路线中移除。这个规则在图一中呈现。对于紧密性不严的问题，只有你约束违反不严重的情况下才保留最后赋值；对于较为紧密的问题，允许严重一点的违反约束。

当客户在集群中而不是随机分布的时候，根据对TSP的解决方案进行排序，如上所述的扫描过程无需进一步任何操作。这已经被证明是为客户出现在集群中的问题提供合理的质量解决方案的一种获得初始种群的方法。
生成结构化解决方案的第二种方法是基于Fisher和Jaikumar的通用分配方法^[27]。这些作者提出了一种自动的方法 为每一个车辆生成一个种子位置。通过对所有客户种子分配的距离进行近似计算，得到了一个一般化的分配问题，再将客户分配给满足负载约束的车辆。可是对于遗传算法，我们生成初始种群的解决方案，其中路线结构相当粗糙，并且在其中可能会发生相当程度的约束违反。相对的，我们稍微简化了一下生成种子点的方法，而不是解决一般的分配问题，我们使用随机分配给每个客户的两个最好的种子之一。

生成的种子点集如下。顾客是通过方向线来减少的，根据订单的顺序，将相邻客户之间的角度一分为二^[27]。然后，汽车锥体是由骨组织形成的。客户锥和客户锥的分数，以获得相等的需求分布车辆锥。每颗种子都位于一条射线上，这条射线平分了相应车辆的角度锥。仓库中每粒种子的距离等于客户距离的最大值。假设一个对称的距离矩阵，dij,0代表仓库 将客户j分配给种子的成本可以描述为：

cij = d0j dij - d0i:

然后，如果aj和bj是客户j的最小和第二最小的种子分配成本客户被分配到最好的种子或者是它的第二个最好的种子，给出的概率为bj=(aj bj)和aj=(aj bj)。

然后用2 -最优方法找到单独的车辆路线。在分配过程中，不要尝试满足负载或距离约束。通过重复随机分配过程可以生成额外的种群成员。

在这两种情况下，如果一个个体复制另一个个体，就不允许进入种群。大小为30的种群是用于最小的测试问题(50个客户)和大小50的用于更大的问题。扫描和归纳分配方法是每一个都被用来产生一半的初始人口。在实验中期，在获得最佳解决方案的质量中使用随机在人口中产生的个体只会减缓步态的收敛速度，所以随机生成的个体不包括在最后的遗传算法结果版本中。

4 生产过程

双亲的解决方案是通过二进制从人群中选择的。因此，从种群中随机的选择两个父代。有着更好适应度的作为第一个父代。重复的过程会包含第二个父代。

两个父代会利用一个标准的交叉过程产生后代。最好的的是利用两点交叉产生的后代，在染色体中这两个点是随机选择的。一个后代包括了第一个点的左边的的基因值以及第二个点的右边的基因值，以及两个点之间的基因值。第二个后代只是交换了父代，其产生过程是一致的。与现存个体一致的子代会被摒弃。

正如我们前面提到的，对于种群，其目的是为所有的车辆编号，使所有拥有相同数量的车辆在大致相同的区域运行。然后，在一个典型的VRP示例中，如果控制点与客户大致集中一致的分布，两点交叉相当于把平面分成两类，在一个部分中使用来自一个父代的车辆分配，另一部分中使用来自第二部分的其他父代。为了实现车辆编号， x坐标和y坐标的平均值是为每个车辆所访问的客户计算的，给予点(xi;yi)，i = 1,hellip;hellip;,m。然后这些点的极坐标被用来给车辆排序，最接近0的为车辆1（或者比360小一点），然后，剩余的车辆以角度的增加进行排序。在两个父代交叉之前，如果在双亲中的车辆1的角度与车辆2的角度相比，它更接近于车辆1的角度，然后，一名父代的车辆将被重新编号，以使车辆1的角度更匹配。

图2介绍了有20个客户的问题的两点交叉的应用，其中应用四辆车解决。正如先前描述的，客户和车辆根据角度进行编号。图2的a和b展示了两个父代结构，如下：

在6和7以及15和16之间形成交叉点。以虚线表示，在图2中也插入到相同的位置，分成两个部分。两点交叉应用产生需要的解决方案，每一个车辆配置由P1的一部分以及P2的另一部分组成。

图2c展示了子代O1，它是在四个方案中最好的一个路线结构。

一个车辆路线的可能性大部分或完全在一定范围内是允许的。对于所有点，如果从一个点到控制点的距离小于另一个点到控制点的距离的一半，那么在车辆角度之间是小雨180/m，然后这两个车辆序号交换，因此，内部路线总是先于外部路线。

在拥有1000000自带的这一代中，可能会出现三到四次两点交叉产生的一对子代并没有用到全部车辆的的情况。当这种情况出现时，用均匀交叉产生子代，其中从两个父代相对应的基因值中随机选取一个基因值。

通过将一个简单的突变应用到新的子代，我们的遗传算法的性能得到了改善，即随机选择两个基因并交换它们的值。除了被选中的客户恰好在同一辆车上，不然就进行交换。其他类型的突变性能不好，如改变一个或更多随机选中的顾客。

图2 (a)父代 (b)父代 (c)子代

5 方案

我们开发的遗传算法使用了稳态方法，即符合条件的子代一旦他

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[141867]，资料为PDF文档或Word文档，PDF文档可免费转换为Word