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

用于车辆路径问题的遗传算法

Barrie M. Bakerlowast;, M.A. Ayechew

考文垂大学数学与信息科学学院，Priory Street，考文垂CV1 5FB，英国

抽象

本研究考虑了遗传算法（GA）在基本车辆路由问题中的应用（VRP），其中已知需求的客户从单个仓库提供。车辆受制于重量限制，在某些情况下，限制行驶距离。只允许一辆车供应每个客户。

已经使用禁忌搜索或模拟退火获得了基准VRP最为人熟知的结果。广泛应用于各种组合优化问题，包括某些类型特别是在包括时间窗口的情况下。但是如此处所述，迄今为止他们似乎没有像VRP的影响那么大。在本文中给出了提出的纯遗传算法的计算结果。使用这个GA与邻域的混合来给出进一步的结果搜索方法，表明这种方法与禁忌搜索和模拟退火有竞争力的解决时间和质量。

范围和目的

基本车辆路线问题（VRP）由多个客户组成，每个客户需要一个特定的客户货物重量要交付。从单个仓库发货的车辆必须交付所需货物，然后返回仓库。每个车辆可以承载有限的重量，在总计中达到它可以旅行的距离也可能会被限制。只允许一辆车访问每个客户。问题是找一套满足这些要求的交货路线，并最小化总成本。在实践中，这相当于最小化所行驶的总距离，或最小化使用的车辆数量然后最小化这一数量的车辆的总距离。

大多数发表的VRP研究集中在启发式的发展。虽然现代启发式的发展已经取得了长足的进步，但提高绩效的追求仍在继续。遗传算法（GAs）已被用于解决许多组合问题，包括某些类型的车辆路由问题。但是，在这里描述的GAs似乎还没有对VRP有很大的影响。本文介绍了我们为VRP开发的GA，显示了这种方法可以在解决时间和质量方面与其他现代启发式技术竞争。 copy;2002年Elsevier科技有限公司保留所有权利。

关键词：路由; 启发式 遗传算法

*通讯作者。

电子邮件地址：b.baker@coventry.ac.uk（B.M.Baker）。

PH：S0305-0548（02）00051-5788 B.M. Baker，M.A.A Ayechew / Computers＆Operations Research 30（2003）787-800。

1.介绍

基本车辆路线问题（VRP）由大量客户组成，每个客户都有已知需求水平，必须从单个仓库提供。交通路线车辆需要，在仓库开始和加工，以满足所有客户的要求，每个客户只能乘坐一辆车。车辆的能力是经常出现的，是每个车辆可以行驶的最大距离。在后一种情况下，可能出现下降容限与每个客户相关联，其被添加到由车辆行驶被分配的客户的总距离。因此，访问许多客户的车辆将无法与访问相对较少客户的车辆一样运行。可能的目标可能是找到一组路线使行进的总距离最小化，或者使所需车辆的数量最小化以及车辆的总距离最小化。由例如Laporte [1]给出各种数学公式VRP。

使用启发式来解决实际尺寸的问题。有很多贡献主题，包括上述基本问题的各种扩展。 Laporte [1]给出了一个Laporte和Osman已经编制了一个广泛的参考书目[2]。

Taillard [3]和Rochat和Taillard [4]的禁忌搜索实现已经获得最着名的基本VRP的计算结果。各种作者报道了类似的结果，使用禁忌搜索[5-8]或模拟退火[5,9]获得。然而，Renaud等人[10]已经观察到了这样的启发式需要大量的计算时间和几个参数设置。

蚁群优化是另一种最近的方法，用于报告许多成功应用程序的组合问题，包括VRP [11,12]。使用改进由蚂蚁生产的个体路线，纳入了第二优启发式，这种方法的结果只是略逊于禁忌搜索。

遗传算法（GAs）已被广泛应用于超启发式算法，包括几种已经报道了的带时间窗口的VRP的应用[13-20]。 GA也应用于具有回程的VRP[21]、多站点路由问题[22]和校车路线问题[23]。使用神经网络和GAs进行车辆路由的混合方法也被提出来了。但是到目前为止，GAs似乎并没有对基本的VRP产生很大的影响。本研究的目的是为基本的VRP提出一个概念上直观的GA，在计算时间和解决方案质量方面与其他现代启发式竞争。将邻域搜索引入我们的GA的混合启发式也被考虑。靠其中的一些使用禁忌搜索和模拟退火获得基准问题的计算结果是众所周知的结果。

2.遗传算法的基础

GAs的原理是众所周知的。生殖过程允许从人口中选择父母解决方案是维持种群解决方案。 后代解决方案是这些产品具有每个家长的一些特征。每个解决方案的适应度可以与目标函数值相关，在这种情况下行驶的总距离和任何约束违规的级别。类似于生物过程，具有相对较好适应度的后代更有可能存活和繁殖，随着种群的不断发展，种群的期望值水平将会有所改善。更多细节由Reeves [25]给出。

任何GA的起点都是每个解决方案或人口成员的代表。通常，这将是一个字符串或染色体的形式。每个染色体内的个体位置被称为基因。虽然二进制字符串已被许多遗传算法研究者青睐，一些使用非二进制表示成功的实现。例如Chu和Beasley [26]在广义赋值方法中使用非二进制表示问题（GAP），要求以最小总成本分配给代理人工作，但须遵守每个代理的资源限制。在它们的表示中，每个染色体由一个字符串组成的十进制数，以作业的索引顺序指定每个作业所在的代理编号分配。

例如Fisher和Jaikumar [27]和Baker and Sheasby [28]，已经注意到并且成功地利用了VRP与GAP之间的结构相似性以往。我们的VRP代表类似于Chu和Beasley的GAP表示和规范，对于每个客户，分配给其的车辆编号。因此，给予n个客户和m个车辆，染色体对于单个解决方案具有长度为n的串的形式，每个基因值在该范围内[1; m]。与一些用于VRP的表示不同，这并不明确指定每个车辆应遵循的确切路线。然而，随着客户对已知车辆的分配，隐含地指定了各个路线，包括行驶的总距离以及任何约束违规的等级。旅行推销员问题（TSP）的解决方案是为了从隐式到明确的解决方案进行转换，使适合度值与每个群体成员相关联。

采取两个步骤来保持尽可能多的结构。首先，客户进行排序并被编号，以便连续的客户可能由同一辆车服务。对于客户随机分布在仓库周围的问题，按照排序以增加极角的顺序。当客户位于集群而不是随机时，它们根据TSP的最近邻解决方案进行排序，从仓库开始拜访所有客户。其次，我们试图对车辆进行编号，以便在所有人口成员的大致相同的地区运营任何车辆。然后，我们应用通常的生殖为群众提供广告流程，生成与他们的父母共享某些路线结构的新解决方案。以下部分将对这些方面进行更详细的描述。因为类似方法已经证明了GAP的成功，我们可以合理地期望这样的GA能产生良好的VRP解决方案。

3.生成初始人口

进行实验，初始人口随机生成，初始种群结构化解，并且混合随机和结构化群体，期望的解决方案是，在相对较少数量的GA的高质量解决方案，解决方案的初始人口将会合理结构化。但是，有可能出现这样的缺点是人口将缺乏获得接近最佳解决方案所需的多样性，与使用禁忌搜索获得解的质量相当。

使用两种方法来生成一组结构化解决方案。第一种方法是基于吉列和米勒的扫荡方法[29]。对于客户随机的问题分布在仓库周围，根据极角的增加顺序进行分类描述。然后，为了产生每个人口成员，随机选择一个客户开始一个车辆的扫描过程。客户分配到当前车辆的顺序它们已被排序，直到发生约束违规。遵循规则，最后一名客户可能会也可能不会从车辆上取下来，然后再继续下一次车辆扫地。对于容量限制的问题，车辆的剩余容量在添加最后一个客户之前，表示为该客户的需求的比例，而且是由Rc代表。对于容量和距离限制的问题，额外的距离在添加最后一个客户之前车辆可能已经旅行的比例被表示为比例包括最后一位客户所需的额外距离（包括任何跌落津贴）和由Rd代表。因此，Rc或Rd的值接近1表示轻微违反了约束，而较小的Rc或Rd值表示更显着的违规。，为了确定最后一个客户是否从路线中移除的决策规则，考虑问题紧张性，客户的总需求除以总容量在这里定义为初始车辆。对于不紧的问题，只有在约束违规是次要的情况下才保留最后一次转让；对于紧张的问题，更多允许有重大约束违规。

当客户位于集群而不是随机的，并根据最近的排序对于TSP的相邻解决方案，如上所述的扫描过程没有任何应用进一步修改。这已被证明是获得初始种群的有效方法合理的质量解决方案，解决客户出现在群集中的问题。

生成结构化解决方案的第二种方法是基于Fisher和Jaikumar的广义赋值方法[27]。这些作者提出了一种为每个车辆自动生成初始位置的方法。使用初始解对应于所有客户分配的行进距离的近似，解决了广义分配问题，以实现将客户分配给满足负载限制的车辆。然而，对于GA，我们正在生成最初的解决方案群体，其中路由结构可能相当粗糙，并且可能发生相当程度的约束违规。因此，我们略微简化了生成初始点的方法，而不是求解广义赋值问题将每个客户的随机分配用于其两个最佳初始解之一。

初始点的集合生成如下。按照Fisher和Jaikumar [27]的描述，客户的分区是通过绘制射线根据他们的顺序平分相邻客户之间的角度进行排序。然后通过聚集B.M形成车辆扇形面。 客户分区获得相等的需求分配扇形面。每个初始解沿着对应相应车辆的角度的射线定位分区。每个初始点与仓库的距离等于客户距离的最大值为该车扇形面。假设一个对称距离矩阵，dij，其中0表示仓库将客户j分配给初始解i的成本近似于cij = d0j dij - d0i:

然后，如果aj和bj是客户j的每个最小和第二小的分配成本，客户被分配给其最佳种子或其最佳种子，具有给定的概率bj =（aj bj）和aj =（aj bj）。

然后使用第二优方法发现个体车辆路线，然后进行3次优化。没有尝试在分配过程中满足负载或距离限制。可以通过重复随机分配过程来生成其他种群成员。

在这两种情况下，如果个人重复其他成员，则个人不得进入种群。最小种群的测试问题（50个客户）使用了30的尺寸，尺寸50用于较大尺寸的问题。扫描和广义转让方法是每个用于产生一半的初始种群。在初步实验中，随机使用种群中生成的个体只能减缓GA的收敛，在获得的最佳解决方案的质量上没有改善，因此在最后版本的GA不包括随机生成的个体。

4.生殖过程

通过二元比赛方法从群体中选择两个父母解决方案。从而，随机从人群中选出两个人。具有较好适应度值的个体是被选为第一代父代。重复该过程以获得第二亲本。

后代是使用标准交叉程序从两个母体解决方案生成的。最好使用2点交叉获得结果，随机选择染色体中的两个点。一个后代由父母的基因值组成，分别位于第一个点左侧和第二个点的右侧，以及来自亲本两个的基因值在染色体中的两个选择点之间。 第二个后代是通过交换产生的，然后使用相同的步骤。与现有成员重复的后代被丢弃。

如上所述，目的是为车辆编号，对所有人口成员来说，具有相同数量的车辆在大致相同的地区运行。然后，在一个典型的例子中VRP，如果仓库大致位于中心位置，客户均匀分布，则为2点交叉相当于将平面划分为两个随机绘制的两个扇区该车站使用一个部门内的一个家长的车辆分配和车辆分配来自第二部门的其他父母。实现车辆编号，平均对每个访问的客户计算x坐标和y坐标的平均值车辆，给点（N xi; y N i）; i = 1; ：：： m。然后使用点的极角（N xi; y N i）订购车辆，车辆1对应于最接近零的角度（可能是一个角度小于360°），此后，其余的m - 1辆车辆的编号为792BM。 增加角度。在交配两个选择的父母之前，如果任一父母中车辆1的角度更接近另一方的车辆2的角度，而不是车辆1的角度一名父母的车辆将重新编号，使第二辆车的角度更匹配密切。

图2说明了二点交叉对20个客户的问题的应用，其中寻求有四辆车的解决方案。 客户和车辆已按照编号以增加极角，如前面段落所述。 图 2（a）和（b）显示两个结构良好的家长，其陈述如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
P1: 1 1 1 1 2 2 2 3 3 2 3 3 3 3 4 4 4 4 4 1
P2: 1 1 2 2 1 2 2 2 2 3 3 3 3 3 4 4 4 4 1 4

客户6和7以及客户之间产生了交叉点如图中虚线所示的光线被插入到图6中的相应位置。 如图2所示，将该地区划分为两个部门。 2点交叉解决方案应用于产生后代，每个都具有在一个扇区内的父级P1的车辆分配以及来自父级P2的解决方案在其他部门。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
O1: 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 1
O2: 1 1 2 2 1 2 2 3 3 2 3 3 3 3 4 4 4 4 1 4

图2（c）显示了后代 O1，它们在四种解决方案中具有最佳的路由结构。

允许一条车辆路线大部分或全部位于另一车辆内的可能性。如果距离（N xi 1; y N i 1）的仓库的距离小于（N xi; y N i）的仓库距离的一半我和车辆角度之间的距离小于180◦=

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

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