英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
参考文献2翻译
网址：www.sciencedirect.com
ScienceDirect
蚁群优化算法实现动态牛奶物流
摘要
与高容量相结合的灵活性是牛奶物流成为最受欢迎的内部物流解决方案之一的主要原因。在大多数情况下，它们仅用于静态路线，以始终将相同的素材传送到相同的电台。但是，在工业4.0的背景下，牛奶运输物流在很多情况下非常流行，因为在很短的时间内需要将不同的物料传送到不同的站点，因此无法再提前计划路线。由于装载和卸载牛奶需要大量时间，除了路由问题本身之外，还必须考虑驾驶和装载时间。特别是在需要高度灵活性的情况下，这些时间会有很大差异，因此是获得最佳解决方案的关键因素。虽然含有随机分量，但可以通过考虑交付的最佳时间点来预测这些时间。因此，短期路线和最佳交付时间之间的最佳折衷有利于最短路线。为了解决这个优化问题，生物学启发法 - 蚁群优化算法 - 得到了增强，以获得关于上述方面的最佳解决方案。制造业场景被用来证明算法在现实世界问题中的能力。它还展示了通过动态建模和模拟内部物流过程，非常快速地适应制造系统变化的能力。本文描述了蚁群优化算法和必要的扩展以使其能够用于牛奶运输问题。另外解释了在实践中应用该算法的实施软件环境。
关键词：工业4.0;牛奶物流; 生物启发优化
一，简介
随着对生产中短暂反应时间的需求不断增加，内部物流也必须应对这些新挑战。为了在保持灵活性的同时实现高效率，牛奶运输已成为向生产区运送物料的最流行的内部物流解决方案之一，因为它们的高容量[1]。在许多情况下，静态路线是可能的，因为相同的材料总是以相同的顺序被传递到同一台。但是，有一些新的用例，特别是在工业4.0的情况下，灵活性和动态变化的掌握是一个主要重点。这种挑战与对高效物流的更高要求相结合，导致使用牛奶运输，甚至在车站的材料要求不可预测且运输时间窗口很短的场合。在那些环境中，路线不能再提前计划。此外，加载和卸载时间需要大量的时间，这不是恒定的，而是取决于交付时间。这些时间必须被预测并且需要被用作优化动态路线以获得可以在实践中使用的解决方案的基础。
像这样的问题可以用数学车辆路径问题（VRP）来近似，其中一组客户的需求需要以最优的顺序分配给不同的路线[2,3]。 VRP的问题描述接近于工厂中实际的牛奶运行问题，但需要通过几种真实环境的特殊情况加以改进。因此，解决方法也必须进行调整。
有许多可能性来为这些问题获得最佳解决方案，但是由于VRP在数学意义上太硬，需要在很短的时间内计算解决方案，因此不可能使用这些确切的方法。相反，启发式算法大多应用在合理的时间内获得了良好的解决方案，但不能保证最佳的解决方案。一种已经证明其具有VRP潜力的算法是蚁群优化（ACO），该算法也用于本文。然而ACO有几种方法来解决VRP，但由于VRP必须由几个基本的约束条件来加强，所以ACO也必须适应新的挑战。
本文首先描述了对VRP的必要改进以及对ACO的影响。 逐步详细描述这些变化，以便授权蚁群优化算法解决将物料请求结合到牛奶运行路线并将单个牛奶运行路线分派到其路线的问题。
2.车辆路线问题
车辆路径问题是研究最多的组合问题之一。 它基于旅行商问题（TSP），其中推销员必须访问一定数量的城市，并尽量减少他的总旅行距离。
车辆路径问题（VRP）也由不同的客户组成，这些客户必须被访问一次。 每个顾客都要求一定数量的商品。 为了装载和卸载，每个客户都要消耗一个特定的服务时间。 在特殊用例中，客户还可以要求将一定数量的商品带走。 与TSP相反，有几辆车从同一地点出发，可以相互分担负荷。 在VRP的标准变体中，每辆车具有最大容量，因此该问题也称为容量化车辆路径问题（CVRP）。 因此，客户被分配到不同的旅程，如图1所示。
图1.客户和家庭基地构建车辆路线问题
VRP的众多变体确实存在[4]。 VRP的一个非常常见的扩展是具有时间窗（VRPTW）的车辆路径问题。对于每一位顾客而言，最早的服务时间以及最近的时间都是最短的。如果车辆到达太早，则必须等到时间窗口开始。相反，如果车辆在时间窗结束后到达，解决方案将无效并因此必须被拒绝。如果采用这种解决方案，可能会对生产过程产生很大的负面影响。线路上只应用了小缓冲区。这个约束是一个所谓的硬约束，即满足时间窗口是强制观察给定问题的有效解决方案。相反，如果约束无法实现，软约束不会导致解决方案失效，但只会对解决方案的评级产生负面影响。此外，考虑可变时间的问题的扩展，例如，如果两个客户之间有交通拥堵[5]。这些可以根据交货时间而改变，并因此产生动态问题。
这些问题的复杂性上升得非常快（问题是NP-hard [6]），所以不可能为更大的问题获得最优解[7]。即使找到一个初始的解决方案，它只需要是有效的，但不需要最优化，对于受约束的VRP而言是NP-hard[8]。
3.蚁群优化
在这种方法中，基于Dorigo思想的蚁群优化（ACO）[9]被用于解决数学问题。 ACO的基本思想是，大量代理人可以基于简单的基本通信规则为困难的组合问题构建好的解决方案。
为此，ACO模拟蚂蚁的觅食行为。对食物的搜寻工作如下：只要自然界的蚂蚁不知道他们的食物的位置，他们随意四处游荡，直到他们意外发现食物来源。然后他们开始放回所谓的信息素 - 一种可以被其他蚂蚁检测到的化学物质。这让蚂蚁有可能通过修改环境间接沟通。信息素的踪迹为蚂蚁提供了一种分布式的记忆，这种记忆在所有的蚂蚁之间共享并且标记食物的踪迹。其他寻找食物的蚂蚁利用这些信息，通过追踪信息素轨迹向信息素浓度最高的方向快速找到食物来源的路径。由于信息素会随着时间的推移而蒸发，所以短路径（只需要很短时间走路）的信息素浓度会比长径迹高，因此当在两个信息素路径中进行选择时，它们将是首选（见图2）。
图2.蚂蚁群落的觅食和招募行为[10]
Dorigo [11]已经将这种行为适应了数学意义上的组合问题。为了给算法提供必要的信息，这个问题必须转换成一个图，其中一群人工蚂蚁试图找到从开始节点到结束节点的最短路径。在大多数情况下，人造蚂蚁对于下一个节点继续前进将有多种可能性。蚂蚁通过随机决定决定继续前进的位置，其中每个潜在后续节点的概率由所谓的状态转换规则计算：
在这个公式中，连接两个节点的边上的信息素浓度。值越高，蚂蚁选择边缘的概率就越高。第二个影响因素是启发式价值。通过这个因子，蚁群优化算法结合了给定问题的现有知识，例如在距离最小化问题的情况下，距离下一个节点的距离的倒数。因此，在这个例子中，一个更近的节点比远方的节点有更高的选择概率，一般来说，启发式值有利于在最终解决方案中具有更高概率的节点。计算启发式值的适当函数可以显着提高解决方案的质量并缩短获得解决方案的时间。信息素浓度和启发式值通过两个值彼此加权
在所有蚂蚁完成解决方案的构建之后，新的信息素将被放置在图表上。 文献中讨论的这个步骤有不同的策略：与生物现象最好匹配的行为是每个单独的蚂蚁将信息素的浓度与其解决方案的质量相比，与其他蚂蚁相比。 然而，模拟研究表明，所谓的精英蚂蚁策略（EAS）[12,13]，其中只有蚂蚁具有迭代的最佳解决方案的地方费洛蒙导致优越的结果[14]。 然后通过以下两个公式执行最佳解决方案边缘上的信息素更新：
信息素更新的数学表示由两个公式组成，其中第一个公式实现两个不同的逻辑函数。左加数实现了已经放置在边缘上的信息素的蒸发。去做
因此，边缘上的实际信息素值乘以因子以减少该边缘上的信息素值。系数表示信息素在0和1范围内的蒸发速率。该公式的右侧部分负责在边缘上放置新的信息素。增量值ȟ通过公式（3）计算，其中是一个常数，并且是到目前为止最佳解决方案的评估值。由于最有名的解决方案永远不会变得更糟，因此新放置的信息素数量会随时间而下降，从而导致算法后期循环中的信息素变化更小。
为了解决VRP问题，必须将问题描述转化为图形，蚂蚁可以通过沿着边缘移动来寻找最短路径，以获得最短的时间顺序，以便为问题中的所有客户提供服务。在这张图中，有需求的顾客由节点表示，边缘表示顾客之间的距离（见图1）。
为了设置算法，必须生成初始解决方案。该解决方案对解决方案的质量没有特殊要求，但需要有效。在第一步中，创建图形，并且对于给定的初始解决方案，将信息素放置在图上，以便人造蚂蚁可以沿着这些方向进行导航，以开始接近给定解决方案的优化（参见图3）。
然后如[15]中所提出的，两个版本的ACO算法并行启动（参见图3）。 第一种算法试图找到一种解决方案，该解决方案目前使用与最佳解决方案相同数量的车辆，但需要更少的时间将所有需求提供给客户。 无论交付所有订单需要多少时间，第二种优化算法都会试图找到一种解决方案，其中一种车辆比当前最佳解决方案少。 如果第二个优化算法发现了一个新的有效解，则两个优化算法都停止，数学图更新，新的最佳解决方案的信息素将被放置在新图上作为两个算法的起始值。 接下来，两个算法将重新启动，以改进新的给定解决方案。
这种结构导致期望的行为占优势的目标功能是减少总体时间以减少目标上的车辆。
图3.算法的不同部分的协作
4.处理内部物流的特殊要求
由于上述ACO的效率，在短时间内甚至可以解决大型车辆路线问题。为了将该算法用于内部物流中的挑战，必须引入若干增强，因为标准理论VRP并未涵盖实际生产环境中的所有需求。在本文中，正在讨论几个要求并给出了一个可能的解决方案：
与仅在单一行程中运行车辆的标准VRP相比，工厂里的牛奶运动员在完成巡视后会定期返回到本地，以便开始新的巡视。创建解决方案时必须考虑这一点。
对于给定的问题，牛奶运输将一个新的材料容器交付给客户，并将旧容器一起带走。如果容器还没有倒空，牛奶运输的司机必须将零件从旧的容器转移到新的容器中。在优化最佳路线时，这个过程需要花费很多时间。装载时间取决于容器中的填充水平，因此牛奶运输到达站点时的时间是一个函数。除了人体工程学原因外，还应该避免转换材料。
在处理理论问题时，给定车辆路径问题的时间窗通常是以存在有效解决方案的方式。这在实际问题中不一定是这种情况，因此也需要逻辑来处理这些情况。
上述要求只是对VRP模型的最重要的扩展，但当然在实践中使用该模型时要考虑更多的小约束条件。以下各节将讨论超越的要求。
在几乎所有的VRP变体中，总需求被分成几个由不同车辆操作的巡回路线。只要没有时间窗口，优化算法根本没有区别，无论是只有一辆车返回车厂，然后从下一个巡回路线开始，或者与巡视车辆数量相同。一旦考虑到顾客的时间窗口，就需要定义每一次旅程的起点。现有解决方案以及常用基准[16]总是使用计算时间的起点作为每条路线的起点，这相当于每次巡视使用一辆车。为了在牛奶运行计划中使用，需要使用这两种行为的组合 - 有多种牛奶运行返回到下一个旅程的仓库，但由于时间窗口，单个车辆无法处理所有客户。此外，如果充分利用第一次牛奶运输的能力，并且必要时仅使用第二次牛奶运输，目标是完全使用。同样的逻辑适用于后续的牛奶运输，也只会在需要时使用。
为了计算解决方案，通过检查其当前旅程及其预期返回时间来确定每个牛奶运行的最早开始点。该算法中的蚂蚁试图在给定的开始时间内将尽可能多的客户放在第一次牛奶运行时满足时间窗口。通过估算巡回的持续时间，可以计算返回时间，并因此计算出同一个牛奶运行的下一个潜在起始时间。 ACO的人造蚂蚁重复这个过程，直到没有进一步的可能性为这个牛奶运动员分配需求。然后同样的程序适用于第二个和所有后续牛奶运输。这导致解决方案对当前需求的车辆要求最低。
第二个方面考虑了在许多情况下加载和卸载时间不是固定时间的事实。当一个新的容器交付时，旧的容器必须带着牛奶运输带回收，这就产生了这种效应。如果旧容器中的物料未完全消耗，则必须将其转移到新的容器中，这需要花费相当多的时间，因此不应忽视以获得最佳解决方案。由于材料的消耗量与时间大致成正比，因此最佳时间应恰好在最新的交货时间点。如果牛奶运输到达较早，那么将物料从旧容器转移到新容器所需的时间可以通过：
在这个公式中是恒定的加载时间。 它描述了驾驶员卸下车辆，步行到拖车，将新的集装箱移到车站，将旧车辆移回到拖车，走回车辆并重新安装的时间。 这个时间对于所有工作站都是一样的，并且不依赖于容器的填充水平，因为它不考虑这些步骤。 相反，该参数描述加载时间的可变部分，这是将旧部件手动移动到新容器所需的持续时间。 常数Cv乘以最近可能到达的时间点之间的时间差，这相当于时间窗口的结束，以及实际到达车站的时间
为使算法起作用，必须对所有巡视的最短时间进行优化，因为在目标函数中可以考虑可变服务时间。通过最小化牛奶物流的总时间，该算法自动使用最短驱动时间和短时间加载之间的最佳时间，这在大多数情况下将是竞争目标。
如前所述，ACO需要图的每个边的启发式值才能有效地计算好的解。确定这个值的函数需要被调整，以及图中的表示。在图中的标准表示中，每个节点都有一定的服务时间，蚂蚁可以在解决方案的构建过程中请求这些服务时间，以确定该客户是否适合牛奶运行的下一站。考虑可变加载时间时，此行为完全改变。节点必须计算关于牛奶运行到达时间的具体加载时间。因此用于计算的时间对于每个构建的解决方案都是不同的。由于这个时间是计算启发式价值函数的主要方面之一，启发式值也会随着每个构建解决方案的蚂蚁而发生变化。由于信息素浓度不会快速变化，如果启发式值和信息素浓度之间的权重选择不当，这可能导致收敛行为不合适。
本文讨论的第三个延期是紧急订单的补贴。 在实践中，如果材料请求延迟提交或者材料本身没有足够快的速度交付，那么可能会发生这些订单。 这种问题在理论基准中不会出现，但如果不考虑这种偏差，则在实践中测试算法会导致严重的麻烦。
为了解决这些问题，必须在算法中实施不同的策略。 在正常情况下，对于那些紧急交货而言，
全文共7664字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[10736]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
