一种具有时间窗的车辆日常交付路径问题的替代算法外文翻译资料

 2021-11-28 09:11

一种具有时间窗的车辆日常交付路径问题的替代算法

摘要

本研究试图用时间窗（VRPTW）解决车辆路径问题。该研究首先确定了真正的问题，并就这些问题提出了一些建议。本研究中使用的技术是遗传算法（GA），应用初始化是随机种群方法。该研究的目的是将多个车辆分配给连接客户和仓库的路线，以便最小化行驶的总距离并且在客户请求的时间窗口内完成交付操作。分析表明，具有时间窗的车辆路径中遇到的问题可以通过GA解决并检索以获得最优解。在对VRPTW进行彻底研究后，强烈建议公司实施从研究中获得的最佳路线，以提高时间插入的交付效率和准确性。

关键词

带时间窗的车辆路径问题(VRPTW)，遗传算法（GA），随机种群

1.简介

在日常配送业务活动中，没有公司免于车辆路径选择问题，特别是在最小化配送距离方面。与车辆路径优化问题相关的配送问题，在当今不断增长的业务复杂性的推动下，因其可节约大量人力和物力成本而显得尤为重要[1]。根据King和Mast [2]，交易商品的最终价值的10％至15％来自于其配送代价。运输问题可以以其路线分布的形式表示，许多约束和特殊性，例如车辆的容量，以及在解决现实世界问题时需要考虑时间窗。关于该问题的研究变得流行，因为其应用可以为该行业和其他人做出贡献。

在当今世界，只需点击一下按钮，客户就可以满足一切需求，产品需求变得如此之快。因此，更快，更有效地交付产品变得非常重要。以最低成本交付产品的目标（如本研究前面所述，我们将行驶距离视为成本）涉及其他几个因素。因素包括路线，车辆容量，客户要求和约束等等。为了实现这一目标，前几年引入了几种模型。

具有时间窗的车辆路径问题（VRPTW）涉及在时间间隔内由车队服务的若干客户（节点）并且每个车辆具有其有限的容量。车辆将货物从仓库运送到客户，行程在同一仓库结束。交付产品的尺寸相同，并且消耗每辆车的相同容量。此外，交付地点是唯一的，并且不允许在主仓库以外的节点上为客户提供任何活动。服务水平效率取决于客户所需的时间。因此，该研究的目的是在每次旅行以交付每个客户所要求的物品时最小化车队的总行驶距离。以最小路线行驶可以降低成本并提高服务时间[3]。

车辆路径问题（VRP）被描述为从中央仓库到具有各种需求的一组地理上分散的点的最低成本路线的指定[4]。车辆路径问题（VRP）最初由Dantzig和Ramser [5]提出。这是旅行商问题的延伸。在过去的五十年中，VRP模型得到了迅速发展，许多其他新模型也源于这一原始模型[6]。VRPTW是VRP的扩展，插入了每个客户所需的时间边界。时间窗成为附加约束，由此在实践中可以改变时间窗的限制程度。在极端情况下，车辆需要在时间窗内到达，违反此要求的车辆将被拒绝。在大多数情况下，违反时间窗口是可以接受的，但会受到处罚。VRPTW是一个组合优化问题，属于NP难问题，通过精确算法求解它一般是低效的[7]。在VRPTW中遇到的其他复杂性是由车辆时间窗口和等待时间成本引起的路线约束的长度，这是在车辆到达客户位置太早时产生的[8]。因此，启发式算法在解决VRPTW时变得流行。Solomon [9]开发了一些用于解决VRPTW的启发式方法，包括保存方法，最近邻插入和扫描方法。这些启发式算法是从用于解决VRP的原始版本修改的。

自1999年以来，已经开发出用于求解VRPTW的方法，并且最有效的方法是两阶段混合算法。两阶段混合算法分为两个阶段，即路线数量的最小化和旅行成本的最小化。基本上，两阶段混合算法使用本地搜索程序来最小化路线，然后最小化车辆路线的总成本。Gehring和Homberger [3]引入了两阶段混合搜索，它使用进化策略最小化车辆数量，并使用禁忌搜索算法最小化总距离。Potvin和Bengio [10]使用禁忌搜索的两阶段混合算法，其中在第一阶段，客户被移出路线以减少车辆总数，而第二阶段是关于外部和内部客户之间的交换以减少旅行成本。

遗传算法（GA）因其在合理的时间内为复杂的优化问题获得良好解决方案的贡献而受到欢迎。特别是，近年来已经探索了基于遗传算法的启发式搜索策略，以改进VRPTW问题的解决方案。GA受生物进化过程的启发，该过程发生在每个个体的相对适应性的直接影响下。群体中每个个体的适应性由其解决方案相对于所考虑的目标的质量来定义。这样的设置有助于增加每个后代中群体的平均适应度。经过一代人的努力，我们很可能会得到我们所需要的质量解决方案。GA的适用性分布在各种领域，例如单目标到多目标优化，工程箱式打包，多维数值优化，模式识别和路径选择。然而，由于其高计算成本，GA在车辆路线领域取得了非常有限的成功[11]。

2. VRPTW模型

为了确保数据适合于比较目的，已经调整了模型。与模型一起，已经确定了几个假设来描述模型[12]。假设如下：

1）网络中的每个客户都有需求。

2）用于运输货物的车辆的所有容量都是相同且有限的。

3）客户必须由固定数量的车辆提供服务。

4）车辆必须离开仓库，其货物数量必须等于必须交付给客户的数量。

5）时间窗口以两个值给出，描述为下限（配送车辆在受访客户处的服务开始时间）和上限（配送车辆在受访客户处完成服务的完成时间）。

6）一旦超过最新的时间限制，车辆不应该开始为客户提供服务。

7）如果车辆在最早的时间限制之前到达，则拒绝该配送路线并分析搜索新路线。

8）为每个车辆分配服务时间，用于向网络中的每个客户装载和卸载货物。

9）每辆车的总路线时间计算为行驶时间（与行驶距离成比例），等待时间和服务时间之和。

10）车辆行驶的最大路线必须高于总路线行驶距离。

以下是用于描述模型的符号：

：最大车辆数量

：车辆容量

：车辆可行驶的最大距离

：客户总数

：客户i和j之间的距离

：通过车辆k在客户i处开始服务时间

：在客户i开始服务时间

：客户服务时间i

：客户要求的需求i

VRPTW模型采用[13]并重写如下：

约束条件：

， （1）

， （2）

， （3）

， （4）

， （5）

， （6）

， （7）

， （8）

VRPTW模型的目标函数是最小化距离行程。约束1）确保每个客户都被车辆访问，而约束2）确保同一车辆到达和离开其服务的每个客户。约束3）确保使用最多k个车辆，约束4）表示动态需求的流动方程。约束5）是交付需求的流量方程，约束6）是确保需求仅在确切的路径中传输。约束7）是时间窗约束，约束8）定义决策变量的性质。

3.遗传算法在VRPTW中的应用

有许多研究使用已经完成的GA解决VRPTW。然而，在这项研究中，该应用程序不仅专注于试验解决方案，而且还生成初始解决方案。在这样做时，随机群体初始化（GA / R）用于生成候选解。此外，本研究的适应度函数是所有路径的行进距离的总和，如[14]。然后将该方法与最近邻（GA / NN）和贪婪随机自适应搜索程序（GRASP）的其他初始化GA进行比较，以观察其性能。在此过程中，初始种群是随机选择的，种群大小定义为n，其中n在过程中不发生变化，每个个体都是一个n维解向量，表示顾客数量的排列。然后从第一染色体数量同时检查容量约束，时间约束和最大距离约束。如果它没有违反约束，则考虑下一个数字，如果它违反约束，则将应用来自其他车辆染色体的下一个数字。重复该过程，直到所有客户都得到服务[15]。在这项研究中，MATLAB编程软件用于分析数据。

VRPTW中的改进遗传算法包括三个阶段：1）群体的初始化和染色体表示; 2）选择; 3）交叉和变异。所有三个阶段都详细讨论如下。

3.1 人口和染色体表示的初始化

这是GA从一组染色体开始的第一个阶段。在收敛到解决方案所花费的时间更长的情况下，随机生成初始种群。使用的初始种群大小为100.它定义了GA中每一代的种群大小。因此，创建了100组随机整数N，其中N是问题中的客户数量。如果种群大小太小，则算法可能无法充分探索解空间。增加种群规模使GA能够搜索更多的点，从而获得更好的结果。然而，人口规模越大，GA计算每一代的时间越长[16]。

在该研究中，染色体表示是由长度为N的整数串给出的网络配置形式。给定染色体中的基因是分配给顾客的点。染色体串中的基因序列是客户访问的顺序。图1给出了导致网络解决方案的染色体实例[4]。基于图1，染色体由一系列数字表示。该数字表示车辆的访问顺序。染色体由1-3-5-7-6-8-9-4-2表示。它描述了第一辆车离开仓库，前往1号客户，然后是客户3号，5号和7号，然后是6号，8号 ，9号，4号和2号，最后返回仓库。

3.2 选择

选择功能用于基于适应度函数的评估来选择预期父母。然后，通过交叉算子重新选择所选择的父染色体以产生新的群体。本研究使用锦标赛选择，其中保留两个相同的人口副本。对于每一代，逐个比较群体的一个拷贝中的相邻染色体，然后选择具有更大适合度值的染色体。应用锦标赛选择是因为遗传上适合的染色体在这种机制中被优先考虑[16]。

3.3 交叉和变异操作符

交换图2中整个部分的单点交叉算子用于创建新的后代。

图1 染色体表示。

图2 单点交换交叉。

图3 交换突变。

这项研究使用交换突变，其中选择对于字符串中的两个段是随机的，然后交换它们。图3显示了基于Eiben和Smith的交换突变过程[17]。

迭代过程将在终止前运行一百次。

4.实验结果和比较

分析分为两个阶段; 第一阶段分析是在没有时间窗的VRP上进行的，第二阶段的分析是在VRPTW上进行的。在第一阶段，使用包括中小尺寸的两组数据来验证所提出的算法（随机种群初始化（GA / R））在求解VRP中的性能。在第二阶段，使用相同的数据集来验证所提出的算法（随机群体初始化（GA / R））在求解VRPTW时的性能。与其他类型的初始化，GA / NN和GA / GRASP进行比较。以下是每个参数的条件：

1）种群大小（Popsize）定义为每代（10,20,40和60）染色体的数量。

2）最大生成（Maxgen），其是终止标准，其将最高得分染色体返回之前生成的染色体群的最大数量设置为搜索答案（100）。

3）交叉概率是一对染色体交叉的概率（0.95）。

4）突变概率是染色体上的基因随机突变的概率（0.01）。

4.1第一阶段（VRP）结果

在此测试阶段，结果表明GA / R的性能与其他竞争启发式相比更好。此外，GA / R也是计算结果的最快速度。通过观察所有三种算法和不同问题大小的最短距离，GA / R通过产生最小的标准偏差提供了优异的结果。对于GA / R，当使用的群体大小为10时，最小的计算时间为2.49。表1和表2总结结果。因此，获得的最佳途径来自10的种群大小.GA / R在每个种群大小中非常快地达到最佳解。除此之外，与GA / NN和GA / GRASP相比，通过这种初始化获得的距离是最小的。此外，观察表明，当种群规模较小时，

英语原文共 9 页

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章