英语原文共 14 页
随机部分优化循环移位交叉的多目标遗传算法在具有时间窗的车辆路径问题中的应用
Djamalladine Mahamat Pierre, Nordin Zakaria
1. 绪论
考虑时间窗的车辆路径问题（VRPTW）是组合优化问题，其服务的提供受处理时间的约束。该问题可描述为一组卡车离开中心仓库，并为一组地理位置分散的客户提供服务。每个客户都需要在预定义的时间窗口内由卡车满足客户的商品需求。该问题的约束条件还有每个客户必须只被访问一次，并且每辆卡车所服务客户的累积需求不得超过卡车的容量。该问题的目的是成本（距离，时间，卡车数量等）的最小化。
作为有容量约束的车辆路径问题（CVRP）的扩展，以及带时间窗口（TSPTW）的旅行商问题的推广，VRPTW的应用范围从涉及时间和容量限制的现实物流问题的建模到当每台机器上的作业之间存在依赖关系时的作业顺序安排。多目标VRPTW（MOVRPTW）源于许多现实生活问题中，有许多需要同时优化两个或更多目标的实际情况。这个问题在研究人员中特别受欢迎、，因为它被归类为NP完全问题。因此，该问题十分棘手;这迫使研究人员采用专门的启发式算法和元启发式算法来解决该问题。
早期尝试解决VRPTW实例依赖于基于确定性方法的启发式方法。这种启发式方法包括面向时间的最近邻启发法和插值法。除了无法支持多目标优化（MO）之外，确定性方法对于解决大规模问题实例的效率十分低下。多目标遗传算法（MOGAs）是解决MOVRPTW的主要方法，主要有两个原因。首先，它维持一组候选解决方案的能力使其对于解决近似于多目标问题的帕累托最优集合十分适合。其次，作为元启发式方法，它被证明可以在可接受的时间范围内为复杂的优化问题提供近乎最优的解决方案。然而，遗传算法和扩展MOGA在优化复杂问题时容易难以得到较准确的答案且效率低下。为了克服这些弱点，传统的GA算子被修改为采用局部优化技术。这些算子中有交叉算子。插值的交叉算子，例如最佳成本路由交叉（BCRC）或构造算法，已经成功地用于MOGA中以优化VRPTW。但是，必须注意的是，无论找到的解决方案的质量如何，这些交叉算子都采用详尽的技术以便于找到最佳的节点成本位置。
部分优化的循环移位交叉（POCSX）通过在染色体的每个基因位置依次附加两个交配亲本的低成本基因（节点）以结合爬山机制。虽然交叉时间复杂度较低（与插值的交叉相比），但它在VRPTW中的应用中产生了令人失望的解决方案。在本文中，我们介绍了随机POCSX（SPOCXS），它是POCSX的改进。本文的贡献包括：
bull;基于基因序贯附件的新的子构建算法。
bull;一种用于定义潜在节点可行性的数学模型，以确保生成子节点编码可行的解决方案。
bull;附加成本的数学模型，以确保最终的子染色体是父染色体的改进。
bull;随机附属规则，以克服对局部最优的潜在陷阱。
在下文中，第2章主要介绍文献综述。第3章给出了问题的正式定义，第4章对MOGA进行了描述，包括新引入的SPOCSX。第5章描述了实验装置。第6章将进行结果分析。最后，结论在第6章中给出。
2.背景
多年来，为了有效地解决VRPTW问题，国内外已经进行了许多尝试。早期尝试包括解决单一目标的问题解决策略（主要是最小化距离成本）。所罗门早期关于面向时间的最近邻启发法和插值法[1]的研究只是用于解决单目标VRPTW实例。面向时间的最近邻启发法是依次构造基于相邻节点的最低成本的解决方案。另一方面，插值的启发式方法依赖于两个成本函数来确定最佳插入位置和将要插入一系列未布线节点中的最佳节点。所罗门的结果证明，在大多数情况下，插值启发式方法优于基于附属物的启发式方法。所罗门的发现启发了波特文和罗塞乌进一步改进插入启发法，从而产生了[11]中描述的并行构造算法的概念。尽管基于插入的启发式算法已经被证明在寻找最佳结果方面是有效的，但是它们依然依赖于穷举搜索来识别最佳插入位置。
粒子群优化算法是一种基于群体的元启发式算法，产生于对群体(鸟群、鱼群等)社会行为的模拟[12]。。粒子群算法是一种迭代方法，与其他进化算法(即遗传算法)有很多相似之处。粒子群算法保持一群独立的实体或粒子，这些实体或粒子经历变化以实现共同目标:达到给定目标函数的最优或接近最优的点。此外，所选相邻粒子的局部最佳位置也是粒子已知的。所有本地最佳的最佳位置被存档为全球最佳。在迭代过程中，粒子的位置向量和速度向量以这样的方式更新，即粒子的下一个位置与搜索空间中具有最小可能波动的最佳或接近最佳位置相一致。粒子群算法最初是为连续优化而设计的，它的范围已经扩大到各种整数规划问题。PSO已成功应用于解决[13,14]中的小型VRPTW实例。值得注意的是，粒子群算法作为一种基于种群的搜索方法，可以扩展到支持多目标优化。在[15]中，Coello和Lechuga通过在外部档案中跟踪所有非主导的全球最佳状态，奠定了粒子群算法逼近帕累托最优前沿的基础。该方法已应用于[16]中的多目标VRPTW。然而，[17]中的调查发现，这种方法可能对PSO的性能有害，因为在每次迭代中，更新全局最佳的档案库的复杂性会随着目标数的增加和粒子数的增加而增加到(KN2)。近几年来，多目标粒子群算法在整数规划的多目标优化中达到了高度成熟。托拉比等人的工作。关于不相关并行机调度问题的多目标优化[18]是多目标整数规划问题的一个很好的例子。用MOPSO (一种连续方法)处理VRTPW (一种整数规划)的挑战之一是解决方案的表示，在大多数情况下，由研究者来解释问题，从而产生各种各样的间接表示，如[13，14]中粒子位置n 2times;m维表示，[16]中显示的n维粒子位置，或[19]中的2times;n维表示。与每个表示一起，在评估过程之前部署解码方案。
遗传算法（GA）[20]是一种全局优化技术，它包括相互关联的操作，包括初始化，评估，选择，交叉（交配）和/或突变，以及截断（或替换策略）[21]。评估，选择，交叉和/或突变的组合经历迭代过程（进化）直到满足停止条件。与PSO一样，GA在寻找最优或伪最优解的过程中保留了大量潜在解决方案。与PSO不同，在优化过程中，GA的搜索过程基于不断生成新解决方案（后代）而不是改变现有解决方案。基于达尔文的“适者生存”原则，该方法迅速崛起并应用于[22-25]中的各种离散优化问题。然而，在被优化的问题类型的性能、问题的规模和人口的规模之间存在关系。虽然在[26]的调查中显示遗传算法的性能低，人口规模小，Tsoy关于多模态优化的工作导致的结论是，人口规模对结果的影响大于世代数[27]。另一方面，计算负荷和人口规模之间有很强的相关性，正如[28]的计算复杂性所示。
利用GA固有的并行性，在过去的几年中已经部署了许多并行的GA架构来实现更高的搜索效率。细粒度遗传算法[29]、粗粒度遗传算法[30]、主从并行遗传算法[31]、主从并行向量评估遗传算法[32]只是遗传算法并行体系结构的几个例子。并行遗传算法已经成功地应用于[33,34] 的路由问题，[35 ] 中异构分布式环境中的任务动态调度，以及[36] 给定目的地的最优路径搜索。不管它们提供的执行速度如何，这些体系结构都不足以为遗传算法提供处理以复杂适应环境为特征的优化问题的能力。
VRPTW作为一个组合优化问题，其特征是复杂的适应环境，通常由多个峰来识别。这种特性激发了该领域的进一步研究。里维斯已经展示了对搜索环境的理解如何帮助设备更有效的搜索算法[37]。霍恩关于模态(局部最优数)的研究表明，搜索空间中高百分比的点是局部最优的问题可以很容易地用遗传算法[38]来解决。Darwen对搜索环境的调查表明，GA只有在搜索环境强调大峡谷(大吸引力盆地) 时才表现出良好的性能，而包含优先约束(如VRPTW中的时间窗约束)的组合问题[39]在好的解决方案之间表现出很大的不同；因此，利用遗传算法的算子，如交叉和重组，在搜索空间的有希望的流域内寻找替代解，不能产生良好的解决方案。
在典型的遗传算法中，交叉算子的作用仅仅是剥削性的。给定双亲，交叉算子基于双亲中编码的信息创建一个子代。传统的交叉算子，例如单点交叉或两点交叉[40]，仅仅通过在亲代之间交换基因序列来模拟交配。这些交叉算子，不管它们产生新解的能力如何，都有可能降低遗传算法的性能。传统交叉的低性能的一个主要因素是VRPTW约束的不可问责性。给定代表可行解的两个亲代，由亲代匹配产生的子代解可能代表具有重复或省略客户节点的不可行解。针对现有传统交叉的低性能，出现了一系列交叉算子。这种交叉包括部分映射交叉(PMX) [41,42]和统一顺序交叉(UOX) [41]。在[43]进行的实验结果表明，PMX和UOX在硬VRPTW下表现出低性能。尽管遗传算法有能力在搜索空间中识别有希望的盆地，但却缺乏准确性和效率[8]。这些弱点是归因于GA无法处理局部优化[9]。枚举交叉可以轻松克服这些限制
优化的交叉算子首次引入并应用于最大基数和最大权重问题[44]，为[45]中的CVRP和[46]中的VRPTWs提供了良好的解决方案。基于在父染色体中位于不同基因位置的客户节点的脱离集合定义的二分图，优化的交叉计算图中的所有完美匹配。给定具有k个周期的图形，枚举提供高达2k的完美匹配，被认为是潜在的后代。在潜在的后代中，选择成本最低的元素作为子代。不难看出潜在后代的大小是获得良好解决方案过程中的重要因素。然而，这种观点并非纯粹主观。它可以得到非免费午餐的支持，该午餐表明“如果考虑到足够包容的一类问题，那么任何方法都不能超过列举”[47]。后代的大小使得这种交叉对于大规模的NP难问题是不合需要的。
基于插入启发式的交叉算子克服了上述缺点，但计算成本可能很高。最佳成本路由交叉(BCRC) [2]通过在亲代之间交换随机选择的路由节点来生成子代。给定两个父节点，随机选择一条路由，从第二个父节点中移除所选路由的节点，并在产生可行且成本较低的解决方案的位置重新插入。Vaira和Kurasova引入了基于插入启发式的遗传算法[9]。他们的遗传算法遵循一种相当谨慎的方法，即交叉和变异算子都依赖于插入启发式算法，这在某种程度上类似于所罗门在[1]中的插入启发式算法。像所罗门的插入启发法一样，Kurasova的启发法考虑了最低成本的插入位置；与所罗门的插入启发法不同，要插入的客户节点是从未布线的客户节点列表中随机选择的。如[9]所示，提取(或重新插入)的节点数量对交叉算子产生的子节点质量有很大影响。不管它们只影响要插入到最佳位置的特定数量的节点，BCRC和[9]中提出的基于插入的交叉都依赖于穷举搜索策略来识别每个节点的最佳位置。穷举搜索的复杂性为O (N2)。因此，这种复杂性对于具有较长调度周期的问题是不现实的。无论是使用建立优化交叉的枚举技术，还是指导BCRC解决方案构建的穷举搜索，重点都放在结果的质量上，而不是计算时间上；因此，这些概念倾向于偏离元启发式的目的，即在可接受的计算时间内获得接近最优的解。作为回应，我们过去的研究提出了部分优化的循环移位交叉(POCSXm)的概念 [10]。(POCSXm)是启发式贪婪交叉或HGreX [42]对VRPTW的改编。HGreX是专门为TSP设计的，基于顺序节点附属策略。像HGreX一样，POCSXm模拟爬山技术，以连续的方式构思一个子代，一次添加一个节点。选择要附加的节点是从潜在节点池中选择的。上标m是一个常数，表示算法从中选择下一个要追加的节点的潜在节点池的大小。下一个潜在节点的选择基于由最后附加节点和潜在节点定义的边缘的成本。这里的成本是节点之间的欧几里德距离。与插值的交叉不同，这种方法具有低得多的复杂性(在0 (n)的数量级)，并且严重依赖于进化过程来找到最优解。不幸的是，在[10]中进行的一系列测试显示出令人失望的结果。有两个因素可能导致POCSX的低性能。首先，边缘的成本被天真地定义为两个连续节点之间的距离成本。然而，假设实验中使用的VRPTW实例同时考虑了空间(距离)和时间方面(等待时间、时间窗等)的问题，当时定义的边缘成本缺乏问责制。其次，最低成本节点的系统附件可能会将遗传算法陷入局部极小值。最低成本节点的连续附件保证了更高质量的子节点，这种想法假设被优化的问题实例具有大的吸引力。然而，这一想法与Darwen在上述组合优化问题的形式上的工作形成了对比。此外，[48]中进行的有能力VRP的适应环境分析支持Darwen的发现，表明对于大多数CVRP的实例，到全局最优值的距离和适应性之间没有相关性。鉴于POCSX在计算需求方面的吸引力，并理解导致其低性能的因素(成本公式和多模态)，我们有动力重新考虑通过本文提出的新交叉算子解决那些已知的MOGA限制。这项工作是更广泛研究的一部分，旨在检查和解决与调度问题相关的GA限制。
3.问题描述
让我们用N = {0,1，hellip;,n,n 1}一组地理上分散的n 2节点，其中节点0和n 1代表仓库，节点1到n代表客户。每个客户节点I都有对可量化商品di的需求，必须在预定义的时间窗口内交付。客户节点I的时间窗口由最早允许交付时间ei和最晚交付时间li定义。除了时间限制，每个仓库都需要si时间单位来卸载所请求的商品。停车场有数量有限的卡车，由集合V={1,2,hellip;,k}离开仓库，服务一组客户，最后返回仓库。每辆卡车都有有限的容量q，服务客户的累积需求不应超过该容量。每辆卡车访问的节点序列构成一条路线。让我们用xijkisin;{0,1}表示卡车k从节点I行驶到节点j的事件。从节点I行驶到节点j的时间由tij表示。我们表示在节点I由卡车k提供的服务由自行车开始的时间。
该问题的整数规划公式如下所示：
4. VRPTWs的多目标遗传算法
遗传算法是一种模拟自然界进化的搜索方法。遗传算法从随机生成的初始种群(通常也称为个体或染色体)开始，依赖于不断改变染色体种群迭代过程(进化)。在进化过程中以找到最优或接近最优解，表现出更好品质的个体很可能在当代生存下来。进化过程的每次迭代都由四个基本操作符的调用来
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
