一种改进的车辆路径规划问题的群体优化算法
摘要-车辆路径选择系统（VRS）是世界上最著名的硬件问题之一，VRS的许多扩展都是针对许多场景开发的。很多研究人员已经做了工作来创建适合于几种情况的通用解决方案，但反馈有限。此外，现有提议的解决方案基于静态方案，其中使用现有数据创建最佳路线并且所有数据优先地被识别。使用一组分布式智能代理可以获得这些动态数据，这些智能代理协作创建最佳路线，然后将静态VRS转换为分布式VRS。在本文中，我们实现了解决垃圾收集问题的系统。提出的解决方案试图建立一个垃圾运输和收集的分散系统。实施改进的蚁群优化以创建访问所有集合点的最佳最短路线，例如每个集合点被访问一次。
关键词：蚁群优化，人工智能，多智能体系统，车辆路径问题，群体智能，K均值算法，路径规划。
Iota;.简介
实际上，随着城市化进程的加快，一些城市被巨大的住房所包围，这个问题涉及到管理这些人口的风险。一个特定区域的垃圾量是从一组家庭产生的一系列垃圾中累积而来的。主要目标是创建一种基于最新技术管理这些废物的有效方法。我们需要收集来自多个地点的所有废物，并将它们送往中央点。收集废物的距离成本是垃圾处理系统的主要制约因素之一，该成本是用于优化的关键部分即所有车辆覆盖的距离。因此，收集废物的问题可能类似于车辆路线问题[1]，每辆车都试图通过最短路径创建自己的旅程，以访问位于给定区域中的一组废物点。
VRS和提出的问题有几点区别。在提出的问题中，每个点的垃圾数量是未知的，每辆车的容量是有限的。 在开始时，每辆车将根据预先计算的最短行程开始使用与静态VRS相同的逻辑，可以看出，车辆在行程的一半时已经达到其最大行程量，然后应该返回在返回到下一点之前清洗集装箱，并重新开始垃圾收集之旅。采用传统的静态车辆路径问题的方法，我们不能用另一辆车来完成先行车辆的未完成任务。另外，如果增加车辆数量以避免中途返回并覆盖所有收集点，则可能会发现大多数车辆将仅使用其一半的车辆容量来收集所有废物。实际上，随着时间的推移，我们需要创建一种新的机制来控制分配给每辆车的路径，采用这种方法，我们根据每辆车的总容量分配所有的垃圾点，使用这个系统，我们减少往返。实际上，我们可以使用一组通信系统来收集每个车辆在每个点的当前容量的所有数据，并且指引每个车辆朝向新的预先计算的最短路径。因此，我们收集废物的问题是基于动态输入来计算每辆车的最佳最短路径，并优化每辆车行驶的距离，新系统可以模拟为动态车辆路径问题。方法的效率取决于不同垃圾收集点的分布情况。如果每个单位的收集的废物数量在所有点上都是相同的，那么该系统将会更好地工作，以便组合的负荷将分配到所有单位。我们创建一组聚类以将该区域划分为小部分，我们使用K均值聚类方法来创建具有相同大小的房屋的一组区域。基于这种聚类，垃圾位置使用这些聚类进行分类，并与每个家庭等距分布，我们考虑这些点在道路上的位置。
我们使用分布式蚁群优化算法[2]来解决垃圾收集问题，为每个采集单元创建基于多智能体系统结构的最短路径[10,11]。本文组织如下：第2节提出问题定义。相关工作在第3节中介绍。第4节介绍了ACO概念。在第5节中，提出的新颖的方法是在新的分布式体系结构中引入的。 在第6节中，我们介绍实施解决方案的准备工作。 第7节讨论模拟结果。最后，第8节得出结论和观点。
Ⅱ.问题定义
本文的主要目标是创建一个基于多代理系统的分布式解决方案，以便为每个收集单元动态生成最佳最短路径，并使用来自环境的实时信息进行垃圾管理。即：
·优化每辆车所覆盖的总距离
·最大限度地提高每辆车运输的废物数量
·为每辆车的改道准备动态计划
为了评估我们提出的解决方案的性能（涉及垃圾收集成本的分析和研究），我们将分布式系统的行为与传统的车辆路径问题进行比较。我们使用多代理系统创建了我们的分布式方法，用于控制垃圾收集以及基于从环境接收的动态数据重新路由所有车辆。每个代理都有自己的行为，具体取决于提出的请求，并且它们使用一组用于共享信息的消息相互交互。
Ⅲ.相关工作
几种方法被用来解决使用元启发式方法获得最佳解决方案的车辆路径问题。 在论文[4]中，作者创建了一个多智体系统来解决这个问题。 该解决方案的主要思想是使用扫描算法创建多个群体，然后用户代理根据初始参数定义一个策略，用于指导拟议解决方案向最优解的收敛。
在[5,6]中提出了一种改进的蚁群优化体系结构，它具有解决旅行商问题（TSP）的高级参数。最初，所有的蚂蚁都放在每个城市。建议的解决方案使用ACO帮助推销员访问所有城市，并创建穿越所有城市和每个城市一次的最短旅程。该解决方案基于寻找最佳解决方案的顺序行为，整个系统可视为一个集中单元，根据每个蚂蚁收到的数据计算最佳最短路径，我们的解决方案基于分布式系统，该系统允许每个代理创建自己的解。此外，所提出的解决方案基于用于控制系统收敛的分散架构。
在论文[7]中，改进的ACO被定义为解决时间相关的车辆路径问题。 所提出的解决方案是基于动态信息素更新和利用路径规划策略来平衡每个车辆使用的路径的新方法。车辆路径问题是一个多目标问题，这意味着所提出的解决方案应该尊重一系列与行驶距离，每辆车的容量，时间窗限制有关的约束条件。
在论文[8]中，作者提出了一种基于复杂通信消息“智能消息”在代理之间进行通信的并行方法。 这种实现基于代理移动性来控制通过网络实体的通信系统。他们使用协调代理通过ACO的分布式多代理来控制这些消息。 他们没有描述表示通信消息的序列模型。
IV．蚁群优化概念
蚁群优化是群体智能（也称为集体智慧）的一部分，灵感来自居住在殖民地的真正蚂蚁的行为，以找到食物来源和巢穴之间的最短路径。 ACO结构是由一组（蚂蚁）设计而来的，它们随机地位于环境中，应该是一个由弧和节点组成的图。
ACO算法模拟真蚁群的行为，找到巢穴和食物来源之间的最短路径。 蚂蚁从巢穴走到食物源，然后返回巢穴，在路上释放信息素。
在我们的解决方案中，我们提出了一个基于多智能体系统的分布式体系结构[3]来创建并行ACS（蚁群系统）算法，该新方法基于蚁群系统算法。ACS是著名的ACO算法之一，在这个版本中，每个蚂蚁都试图根据顺序过程来搜索最佳解决方案。对于我们的方法，我们设计了一个i）新的分布式系统来控制代理之间的通信过程，ii）使用分散系统来管理系统向最佳解决方案的收敛，iii）实现并行ACO算法以找到最优解。
V.使用多代理系统解决垃圾收集问题的分布ACO
A.系统结构
·GUI代理
·主要代理
·聚类代理
·ACO代理
·车辆代理
图1：垃圾收集的分布式体系结构
- GUI代理
GUI Agent控制所有位置，每个位置都由其坐标经度和纬度来控制。 自专用于构建环境地图的用户界面以来，会创建或上传这些职位。GUI代理可以将地理空间文件转换为地图，车辆将使用它来进行收集点的本地化，如图2所示。
GUI代理与知识库交互，这是我们系统的大脑，在这个容器中，我们存储了与执行环境相关的所有信息以及每个实体的进化过程。该系统中存储了多个数据，该地图用于覆盖所有车辆将要访问的所有区域，用于垃圾收集的单位数量。此外，该系统记录了为每辆车辆生成的新计算路径以及发送的不同请求由每个车辆代理开始生成新路径的过程。
图2：由地理空间数据制成的图表
- 主要代理
该系统的主要代理人控制车辆代理的请求并计算每辆车的最短路径为主代理。该代理的行为分为两个主要模块，即蚁群优化。
方法和聚类机制。聚类过程用于创建小区域，将附近的房屋联合分组，使得所有收集点均匀分布，并且在重新路由过程的创建区域之间保持短的链接。创建的集群存储在知识库中。主代理将根据静态VRP中使用蚁群优化的相同行为为每辆车建立初始路径规划。实体以最初建议的路线开始他们的收集过程，并且车辆代理更新车辆未使用空间的状态。剩余的体积将由主代理用于车辆的重新布线。
a）聚类代理
聚类代理基于K-means算法为我们的图创建一个子组。在开始时，我们确定了用于垃圾收集的车辆数量，这个车辆数量假定了创建的集群（kclusters）的数量。主要目标是设置k个质心，每个簇为每个簇。给定的质心应该以一种聪明的方式定位。所以，最好的选择是让他们彼此远离。第二阶段是获取数据集中的每个节点并将其加入最近的质心。重复此过程，直到所有点都连接到更近的质心。
在这一步结束时，完成一个初始区域。 我们需要创建一个k个新的质心作为初始步骤产生的区域的重心。 在这一点上，我们开始新的集群和数据集中的点之间的绑定。 我们重复前面的迭代，我们看到所有质心都是动态移动的，直到没有更多变化完成，我们看到所有质心都是稳定的，参见图3。
图3：k均值聚类的例子
b）ACO代理
在新方法中，我们将问题设计为具有多个节点的图，每个节点由一个代理[9]表示。在此分布式体系结构中，使用了两种具有不同目标的代理。第一种类型是工作者代理（WA），并且它正在不断构建新的解决方案。第二组代理是Controller代理（CA），其功能是搜索优化当前解决方案组并优化最佳解决方案。在图4中，我们介绍了我们的架构，用于对新的分布式ACS算法进行建模。
图4：ACO Agent的多代理体系结构
两个智能代理之间的通信过程如下：
·在开始时，worker代理向controller代理发送包含上次访问的CA的消息。
·在后台，CA选择i）接下来要访问的一组候选节点，ii）计算其他CA的每个边缘的信息素的成本和数量，iii）存储在CA中的当前最佳旅程，其中 会员一些介绍了实现这个CA的最佳路径。
·工作人员代理使用此收到的信息来计算最佳转换并选择下一个要访问的CA. 另一方面，我们使用局部信息素更新来选择下一个要访问的邻居，方法是在此路径上添加更多的信息素。如果此代理使用的路径成本高于当前CA存储的路径，则它们将更新其通过新接收路径到达此CA的路径。最后，WA将它的解决方案（它的路径成本）与环境中的最佳解决方案（存储的最佳成本）进行比较。 如果WA使用的路径成本小于环境中的最短路径，WA将通过使用全局信息素更新在此路径上添加更多量的信息素，并且此路径将成为环境中最佳的路线。
·CA将通过使用从WA收到的最新更新来更新其信息。它将更新用于WA下次访问的CA选择的路径上的信息素量。
- 车辆代理
车辆代理被开发用于控制车辆的容量，在收集点和该车辆之后的路径（在该车辆的当前节点到主代理）之间移动之后发送每个实体的可用容量。基于这些信息，当车辆达到其最大容量时，MA将触发重新路径的过程。同时，MA通知其他车辆代理在完成当前勘探时等待，直到基于接收到的每辆车的剩余容量产生新的路径规划。随后，所有车辆将根据新路线重新开始巡视。
B.多智能体交互模型
在图5中，所提出的通信模型由一组消息组成，例如：
─用户启动垃圾场地图，用于垃圾收集的可用车辆。GUI代理存储所有这些信息，然后将其发送给主代理。
─主代理接收初始参数并向聚类代理发送请求消息，以使用K均值算法创建子区域。
─聚类代理将新的Map发送到主代理，该Map将被发送到ACO代理，以应用ACS算法来查找每个聚类中的最短路径。
─提出的解决方案将与每个车辆代理进行通信，并且可以通过访问其区域内的所有节点来启动自己的行程。
─当车辆达到极限时，车辆代理向主代理发送紧急请求，在这种情况下，系统中的所有车辆应该准备好使用最新参数进行新路径规划。
在每个步骤中，所有事务都存储在GUI代理的知识库中，这将用于分析系统的收敛性并帮助代理程序重新路由以进行路径规划。
图5：用于解决动态车辆路线的分布式通信系统
- 准备工作安排
A.初始化
用户可以绘制自己的包含一组节点的地图，每个节点模拟收集点，并且他们将能够链接每个节点与一组链接（边缘），每个链接代表两个节点之间的道路。此外，用户可以使用用户界面导入地图，系统会将该地图转换成包含一组节点和边的图。集群代理将根据输入数据生成一组区域。这些地区将由工人代理人用于建造新的最短路径。
B.解决传统垃圾收集问题
根据应用K-means算法的可用车辆的数量，创建的节点被分成更小的组。因此，生成的组可以被看作是一个以一组浪费点作为节点并且在这些点之间具有一组道路的图形，节点之间的每个链接都用实际距离加权。在这一点上，我们可以应用蚁群优化技术来找到这个图的最佳解决方案。
C.解决分布式垃圾收集
在车辆容量溢出的情况下，MA将重新开始寻找新路径规划的行为。一开始，当容量溢出发生时，所有车辆都应该等待直到基于未被访问节点的新图形的产生。根据每个车辆代理收到的数据，使用新的组和探索图生成新的路径规划。最后，系统将通知所有实体使用新计划开始他们的巡视。
Ⅶ．计算实验
提出的解决方案是使用JADE框架（Java代理开发环境）实现的，用于创建基于多代理实体的分布式系统以解决垃圾收集问题。 我们的解决方案的效率使用所有实体覆盖的总距离来检查所有废物点，作为估计分布式解决方案性能的一个约束条件。在我们的实施中使用了几辆车。超过容量的车辆的数量是预先确定的。表1显示了所有使用这些输入参数的车辆消耗的距离。得到的结果显示，无论初始条件或用于垃圾收集的单位数量如何，我们都可以看到，在所有情况下，我们都能够使用我们的分布式解决方案减少所有车辆覆盖的总距离。
|
全文共6239字，剩余内容已隐藏，支付完成后下载完整资料
英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料 资料编号：[13153]，资料为PDF文档或Word文档，PDF文档可免费转换为Word |
||
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
