基于进化算法和模拟退火
求解VRPTW问题的方法比较
本文提出了求解限制搜索小数量级解决方案的带时间窗的车辆路径问题（VRPTW）的几种方法的分析与设计。所有这些方法将现代启发式算法结合启发式算法的。模拟退火，尝试了不同的进化方法和混合方法。每个策略的初步结果，最好的进化方法和SA的一些迭代创建的组合脱颖而出。关于三种方法表现得更好的一份更详尽的分析报告也证实了以前的结果。不同的策略已经实施并测试了一系列著名的大小多达100个客户的所罗门的基准问题。所描述的方法相结合的局部优化部分，试图优化局部的解决方案正在被一个真正的石油分销方法的一部分使用的，为公司获得非常满意的结果。
关键字：进化搜索；模拟退火；车辆路径问题；时间窗
- 介绍
物流可以定义为从供应点向各个需求点提供商品和服务。它需要有效的运输管理，因为它可以节省公司相当一部分的总开支。路由和调度问题是许多物流方法的重要组成部分。车辆路径问题（VRP）是设计一个目标为总成本最小，由一个车队开始和结束在中央仓库，服务一组客户订单的车辆路线。每个客户都有一个给定的需求，必须由一辆车服务。一辆车服务的客户不能超过它的容量。客户无法随时被服务，即每个客户都有一个允许的交货时间，这被称为时间窗，这个问题就是VRPTW（带时间窗的车辆路径问题）。
在本文中介绍的是为Vda. de Londaiz y sobrinos de Mercadaiz S.A.公司开发的适用于燃料分配实际应用的一个解决VRPTW的部分方法.，其中有一个近25辆车的车队在一个面积约30平方公里的区域内一天大约有170单订单。该公司有自己的车队，开销在工资和车辆必须行驶的距离所产生的主要费用。因此，主要目标是得到一个最大限度地减少车队服务一组订单时所行驶的距离的强大方法，在这种情况下车辆的数量最小化是不太重要的。
VRPTW包含几种NP-hard优化问题，如TSP和装箱问题，所以我们可以说VRPTW问题是NP-hard的。几位作者认为最佳的解决方法只针对于小问题。即使这些方法在解决小问题时得到满意的结果，但当问题的大小增加时他们是不高效的。为了解决更现实的情况下，进行了大量以启发式算法为基础的研究。一些作者采用路径构建启发式算法。一些作者采用结合路径构建启发式算法和局部搜索的改进启发式算法。解决实际问题时最好的结果已经使用现代启发式算法来得出：禁忌搜索，遗传算法和模拟退火（SA）是比较常用的。
解决方法不是影响方法行为的唯一因素，解决问题的不同方式不能被遗忘。解决方案可以是全局的，获得的工作与整个组的订单和车辆，或问题可以分为子问题（分治法）和得到解决局部的全局方法并结合局部解决方案的全局解决方案。当然，它总是存在结合全局和局部战略的可能性。
我们将展示的方法有两个主要部分：一个是全球优化，全套的订单和车辆用来寻找一个好的解决方案。第二部分称为局部优化工作，在方法试图提高一部分解决方案时具体针对路线做后优化操作。本文侧重于全局优化领域不同的启发式技术性能比较（SA，进化方法和混合方法）。
为了评估不同的问题解决方法的性能，使用更知名的所罗门基准实验数据集。
本文为解决VRPTW问题对方法进行详细的分析。第2部分，给出问题的正式定义。而在第3部分，展示建立在进化方法和SA基础上不同的搜索策略或算法的一些初步结果。第4部分，详述混合方法和所得到的结果并做一些更详尽的分析。第5部分致力于提出局部优化和第6部分是两部分并行化的总结。最后，第7部分总结结论。
- 问题说明
VRPTW问题，有一个车容量为和服务时间为的车队在限制时间窗内服务固定需求量为的客户。建立出目标函数（旅行距离之和）最小化的路线，即每条线路最大。我们提出了一个现代启发式与启发式相结合的解决方案。要做到这一点，新建随机排列，并作为初始解建立解决方案。问题的解决方法取决于前面提到的每一个参数：。
启发式算法在实验过程中用以下方式：订单分配给车辆是一个接一个，以他们初始化的顺序，为车辆安排的订单既要满足所有的限制也要更小的成本。这种方式构建的路线是并行处理的。
- 解决VRPTW的策略
本文介绍了一些路线建设启发式算法与现代启发式算法相结合的全局策略。针对在实际使用中所提出的算法，所有这些解决方案的总数量被限制为32K（32768）。
3.1模拟退火算法
真正的方法由SA现代启发式算法与路线建设启发式算法结合而成。置换所有客户的订单作为主要方式，而且置换时刻被用来获取新的解决方案称为算子。一个新的搜索顺序是被应用于：两个订单的排列被随机选择与交换。在情况n中，当的目标函数值比小，则作为。当的目标函数值比大，则以的概率作为新的起点，这取决于解的质量，作为衡量当前解与在和温度参数下找到的最优解的差异。算法1描述了SA算法的架构。
一个广泛的实验已经完成了该算法，以决定最佳的参数设置和更充分的路径建设启发式结合SA。
算法1.SA
我们在表1中只给出每组第一个问题的最终结果。不同的列是指最好的结果，用SA解决20个问题的平均执行结果以及与最佳解决方案的百分比差异。正如所观察到的，即使平均结果离最优结果差距不大，方法的效率取决于问题组。
表1.SA方法结果
即使主要的实验已经用SA实现，如果我们分析其他策略似乎会更成功。下一节提出了分析了结果质量后用一些进化算法和混合方法替换SA的一个实验。现代启发式算法与路由建立启发式相结合的理念仍然没有任何变化。
3.2第一种进化方法：Evolutionary1
定义作为一般模式进化方法的种群的大小和变异算子。在每一次迭代中的一个元素，为突变。一旦发生了突变，中另一个元素，被新的元素锁代替。算法2显示了第一种进化方法的模式。
算法2.解决VRPTW的 Evolutionary1算法框架
基于这个一般模式，针对几个变种进行了研究。在所有种群元素排列为整组的客户和所使用的变异算子一直是投资操作（同一操作用来探索在SA邻域）的每一个选项，但一些其他参数已变化：
种群规模。研究规模为2的幂，从2到2000。
元素突变的选择机制：（a）随机：随机选择一个元素来突变。（b）范围：是由好到差顺序的，基于此，每个元素都有概率被选择变异。概率只取决于顺序和没有值。（c）比例：概率，它的值和最坏解的值的差值成比例被分配给种群中的每个元素。差异较大的元素将有较大的变异概率。
替换标准：分析了两种可能性：（a）随机：选择一个随机元素来代替。（b）最差的：种群中最差的元素被替换。
在实施中的变化影响了所得到结果的质量。与种群规模有关，我们可以说，在独立于其余的参数的情况下，规模较小时解决方案的质量更好。显然，当种群规模越小，方法与SA越相似。本文的的目的，其余几种方法与SA作比较，中间种群规模已经采用了目前所获得的结果。表2中，展示了几种策略的结果；最好的结果明显的标记出来。SA的结果和与最佳参数设置下的结果的差异以百分比的形式包括在内。从表2，可以很容易地推断，替代标准好于选择的效果。即使有一例，最好的比例最好的选择标准榜上有名，而最好的替代标准比它糟糕的。解决方案的质量取决于要解决的问题的集合，当客户的分布群集时它变得更加糟糕。不管怎样，解决方案的质量与SA在每一组问题中的质量相去甚远。
表2. Evolutionary1方法结果
3.3第二种进化方法：Evolutionary2
在研究了第一种方法的结果后，有证据表明需要加快进程，这是第二种方法平行建立更多的解决方案的原因。种群中的每个置换或元素都是突变的，而不是唯一的。新解将在每次迭代中创建新的解决方案。一旦每一个元素被处理，新排列的解决方案是建立一个新的种群必须建立。采用的策略是精英：从整个解集最好的（父母和孩子）选择。选择精英的替代主要在结果的基础上由Evolutionary1方法得到（最好的结果发现，丢弃最糟的解决方案，所以最好的替换策略是糟糕的）。
算法3.解决VRPTW的 Evolutionary2算法框架
表3. Evolutionary2方法结果
使用这种方法得到的解决方案的质量，与以前相比大大提高，但它比SA的结果差一点（见表3）。
表3中的值属于每个问题集得到最好结果的人口规模（在R101中R = 32，在RC101中R = 64和在C101中R = 128）。在R1和RC1中，方法发现获得的解决方案质量与SA类似。但在C1中，有点糟糕。
- 混合方法
由于进化算法的多样性和SA的强化特性，这两组方法都值得结合以评估该算法的质量是否改善。用于建立混合方法的进化方法由于在以前的实验得到的解决方案质量差异，一直是第二个。
4.1多步骤1：先模拟退火后Evolutionary2
在此方法中，SA算法执行搜索良好的排列。这些排列用于创建进化算法中将使用的初始种群。我们的想法是使用SA接近最佳的解决方案，然后探讨更广泛地使用进化算法的环境。解决方案评估总数始终是32K，但不同比例的SA解和进化的解决方案都进行了尝试， 最好的结果中24K解决方案由SA产生和8K由进化算法产生。种群规模的进化部分尝试了32和64，因为他们一直是以前的实验的最好的结果。表4显示了此方法得到的结果，以前的结果和与最佳结果的比较。
表4. SA Evolutionary2方法结果
这似乎不是这两种策略的充分结合，因为解决方案远远没有改善，结果比执行其中一种策略更差。
4.2多步骤2：先Evolutionary2后模拟退火
在此方法中的策略与前一节是反向的。执行进化算法寻找SA算法的一个好起点。首先，我们搜索广泛的解空间找出能使用SA进行更深度搜索的区域。实现的算法与上一个类似但交换子方法的执行顺序不同。不同的种群规模和不同比例的SA和Evolutionary2下的结果质量可以接受，但他们略有不同。最优结果是使用Evolutionary2搜索得到4K解决方案（R = 32的种群规模不超过128代）和使用SA搜索得到28K解决方案。表5显示了与之前的结果相比，这一策略得到的结果。
在每一个问题集，结果的平均改善与其他策略相关。这种策略似乎以适当的方式结合了这两种算法好的优点：进化算法的多样性和搜索广度与SA算法的强化和搜索深度。
表5. Evolutionary2 SA方法结果
4.3混合并行算法：Evolutionary2和模拟退火
在此节中，我们认为两种算法可以互相提升，建议并行执行SA和Evolutionary2算法两个过程。这两个过程之间在不同的节点联系。
当SA过程中发现了优化方案最好的节点，将它引入Evolutionary2算法的种群，更换差的节点。
当SA停止在一个局部最小值时，它无法提高自身解决方案的质量，它需要Evolutionary2算法的最优解。SA过程将继续从该解决方案开始搜索，只有在这种情况下，此解决方案提高了最后一个SA给出的解。
能与之前所有的解决方案的比较结果，总数已经固定为32K。算法5显示SA的过程框架，进化部分是适应它：它将引入种群和当SA要求时提供最好的解决方案。以32和64的种群规模，SA不同的等待时间（100和450），和并行之前执行的一定次数迭代Evolutionary2算法的测试已经尝试。最好的结果是在R = 32，等待时间为100，和在并行之前用Evolutionary2算法搜索4K解决方案。这些结果（hyb-par），和之前的结果在表6中展示。、
表6显示，如果与第二步策略相比结果不会改善，但需要更深入的研究来决定是否值得使用这种策略。
算法5.混合并行算法框架
表6. 混合并行方法结果
表7. 每种问题使用最佳策略的平均结果
为了确保行为是稳定的，三方法在执行第1组整组的问题表现出最好的结果（平均结果见表7）。表7的结果表明，没有方法得到满意的平均结果。这就是导致我们建议在最后的方法中包括一个后优化部分（局部优化）的原因。
- 局部优化
全局优化阶段需要一个高数量的解决方案来实现接近最佳的解决方案。所以我们现在选择对全局优化后最优解得到的车辆对用优化算法，我们称之为局部优化和帮助方法离开局部最小值。部分解决方案是独立建立在对每个车辆和订单上的。在全局优化中使用相同的构造方法和策略来构造每个局部解。全局优化中使用的参数的值是相似的，但在这种情况下，对于每辆车，搜索的解决方案的次数是500。优化后的每辆车，SA也适用于以改善协调
剩余内容已隐藏，支付完成后下载完整资料
英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[139480]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
