文献翻译：
基于分布式蚁群算法的校车调度问题的路径优化
摘要：
在目前的工作中，我们对解决校车调度问题（SBDP）的分布式架构感兴趣。我们的目标是创建一条路径规划，以最大限度地降低运输成本，同时满足几个约束条件，如每辆公交车的行驶距离和每辆车的运力。 metaheuristics方法，即蚁群系统算法能够解决组合问题。提出了一种基于改进的蚁群优化算法的分布式求解校车路线问题的方法，该方法利用多智能体系统来创建能够共同解决问题的智能体。在本文中，我们提出了一种基于聚类策略的分布式模型，用于创建子区域，根据地址和停靠点位置生成聚类。改进的蚁群系统算法用于找到学校和使用分布式代理的学生组之间的最短路径。准备设置表明，所提出的模型可适用于实际案例。
第一节：导言
实际上，旅行者的运输组织特别是公共汽车运输正面临与公共区域和监管程序基础设施演变并行的局限性。这些组织应该能够合作解决路径规划和车辆路线问题。在我们的学生交通主要案例中，公交指导问题被称为校车指导问题[4]，[7]。
校车之旅旨在提高服务质量并降低运输成本。问题被看作是一组分布在不同区域的学生，他们需要交通。主要目标是将学生分配到最近的公交站点，通过最大限度地减少交易总成本，同时满足这个问题的限制来产生通向学校的最佳路线。
在某些情况下，学校路由问题与智能交通系统研究文献中广泛研究的车辆路径问题（VRP）有关[14]，这是一个组合优化问题，我们试图根据一组约束。
在校车调度中，我们尝试优化一系列元素，例如学生人数，距离和时间间隔较短的路径，在定义起点到终点后选择拾取学生的最佳路线。
在这项研究中，我们将关注这类问题，并限制穿越的距离和运输能力。最初，我们有一组学生分布在不同的地点，必须乘坐固定数量的公交车去学校。其次，生成的路线应考虑一系列约束条件，如：
我们需要提取所有学生，并且尊重每辆车所用公共汽车的容量，重要的是要考虑每辆公共汽车的限制容量。
这个问题的目的是找到巴士站和学校之间的最短路径，最大限度地减少学生运输的巴士数量。
本文的目的是建立一个分布式系统，以解决校车旅行使用多个智能代理[13]，[6]，其中拟议的系统协调学生的位置，为每条可用公共汽车生成路径规划（见图1）。在这个解决方案中，（i）我们有一个中心位置是管理可用公共汽车并根据每辆公共汽车的容量在不同区域之间共享它们的学校，（ii）分布式蚁群优化方法用于建立路径基于多智能体系统的规划和（iii）基于分配路由定位策略的聚类方法被用来定义一组包含多名学生的公交车站点。
这个问题的主要目标是根据其容量为每个总线创建一组路径规划。 BDP是一个难题，可以使用元启发式方法[12]解决，如蚁群优化[6]，[9]，[5]遗传算法[10]，它们能够找到一组最优在合理的时间内解决问题。本文组织如下：第2节介绍相关工作。问题定义在第3节中介绍。第4节描述了ACO算法。在第5节中，提出的新颖方法是在新的分布式体系结构中引入的。在第6节中，我们介绍实施我们的解决方案的准备设置并讨论模拟结果。最后，第7节得出结论和观点。
第二节：文献综述
图 [3]提出了一个解决校车路线问题的新公式，在这个架构中，他们使用了一组可能的公交车站点以及几个可以走向这些车站之一的儿童。主要目标是创建一个巴士站的子集，这些巴士站将由几辆公共汽车访问，在可用的公交车站之间调派学生，并产生一组将由每辆校车前往的路线。
在[11]中已经制定了一个数学模型来解决单一校车路线问题，其主要思想是尽量减少所有公共汽车消耗的总行程时间，实施案例研究，我们所有的公交车站线性分布在学校巴士容量。根据学校的限制，使用禁忌搜索法来寻找最佳解决方案。
在论文[2]中，已经做了一个概述性研究来描述SBRP的行为，它定义了几个概念，如预备数据，公交车站选择，施工路线，校车调度等。
[15]中的作者提供了一种通用的战略分析，使用连续逼近架构来评估混合负载适合有利的条件。他们将他们的方法应用于半农村学校，以展示模型在实践中的应用。
第三节：校车调度问题
校车指导试图为车队建立有效的路径规划，每个车辆从几个公共汽车站接送学生并将他们送到他们的学校，而不会忘记一些限制，例如学生在公共汽车上的最长旅行时间，最大容量的校车。
校车调度可分为一组子概念：i）环境准备，ii）公交车站确定和iii）路径规划生成。
环境准备包括创建一个分布式网络，包括学生宿舍，公交车站，学校。
公交车站确定使用以前的环境来生成公交站的位置。在这一步中，可以使用一组约束条件，例如学生宿舍和公交车站之间的最大距离。这个选择步骤基于两种行为：i）生成巴士站，ii）将学生分配到最近的公共汽车站。
在我们的案例中，我们将该学校的位置放在搜索区域的中间。学生的所有地点都标有蓝色的星星点，它们分布在学校附近。可以通过使用每个位置的经度和纬度来定义可用于将每个路径与其他路径链接起来的几条路线，从而将问题显示在实际地图上。图4显示了学生的位置与学生的位置。我们使用分配路由定位策略[1]来实现我们的聚类，以定义所有节点之间的路由路径。聚类的主要行为是影响每个学生到最近的公共汽车站，然后构建一组连接这些节点的行程。聚类过程可以在图5中定义。我们创建了一组呈现子聚类的圆，我们定义每个圆的半径等于600米。每个圈子包含一组学生，这个子群的中心被认为是公共汽车站。
路径规划生成，我们从之前的数据中创建一组路线。这个步骤从经典的VRP（车辆路径问题）延伸出来，例如系统应该通过考虑一些约束来创建最佳路线。在我们的案例中，我们假设我们只有一所学校，校车的容量不一样。路径规划是使用公交站点位置生成的，每个位置的特征都是一组属性，例如其坐标GPS和将从该位置取得的子项的数量。这个问题可以用一组节点和边来模拟，在我们的例子中，这个图的节点由停止位置表示，边是它们之间的路径。
这个问题可以考虑如下：我们有一套公共汽车，将用于从学校的几个点向学校挑选学生。校车应该使用相同的路线运送学生（上车或下车）。除此之外，接载的学生总人数不应超过公共汽车的最高容量，每辆汽车的行驶距离应小于每辆汽车所允许的最大行驶距离。
学校指导问题可以作为一个完全连通的图（G）分布，从一组完全连接并从学校开始的路线建立。这个问题的目标功能是尽量减少运输总成本，同时尊重能力和距离，这是两个主要的制约因素。
该问题表示在完全连通的图G（N，E）上，N是一组节点，E代表边。参数d（i，j）表示两个相邻节点（i，j）之间的距离，节点iiisin;N处学生的数量用q（i）表示。总线数由V表示。
我们问题的输入参数定义如下：
V：所有可用校车的数量。
q（i）：分配给这个节点的学生数量i。
Q：校车的最大容量。
T：每条路线的总长度。
c（i，i）：边缘（i，i）的成本。
SBDP的目标函数表示如下：
参数alpha;是调度公交车的单位成本。 等式（2）表明，所有用于接载学生的可用公共汽车不应超过公共汽车的最大容量。 每个节点应该访问一次，并且只能通过一条总线检查，这个约束由（3）和（4）定义。 我们的问题的定义要求运输学生的总人数必须少于公交车的容量。
第四节：蚁群优化算法
蚁群优化（ACO）是群体智能的一部分，其中已经开发了许多研究来模拟这些昆虫的社会行为。基于蚁群优化算法的行为，人工智能算法已被应用于解决复杂和难以解决的问题。 ACO是一种元启发式方法，它使用人造蚂蚁来寻找组合问题的最优解。 ACO的技术受到真正蚂蚁行为的启发，当他们试图找到他们的巢穴和食物来源之间的最短路径时。人工蚂蚁可以并行工作来寻找和收集解决复杂问题的最佳解决方案，并使用称为信息素的化学物质进行交流。
当人造蚂蚁行进时，它将信息素铺设在小径上以标记他的路径，并且将被其他蚂蚁使用。一开始，蚂蚁会从巢穴中随机走动，它会评估每条路径上信息素的数量，以便使用过渡规则选择要遵循的最佳路径。
蚂蚁越多使用路径，它们对其他蚂蚁就越有吸引力。当一只蚂蚁发现巢穴和食物来源之间的最短路径时，它将能够将其路径标记两次。信息素的数量将积累在最短的路径上，因为在其他路径上它们不会吸引蚂蚁。信息素的量在蚂蚁较少使用的小径上会减少，这个过程是通过蒸发技术来完成的，在这种技术中我们减少信息素的数量以减少这些路径的吸引力。更多的蚂蚁发现路线，当障碍物出现在最短路径上时，将计算和使用更多的解决方案。
蚁群系统[8]，[13]，[5]是该算法中最初ACO的扩展版本; ACS已经取得了一些改进，如：
路由建立：在这一步中，蚂蚁将选择使用随机比例参数从当前节点i移动到节点j。如果qgt; q0或使用方程（6），则使用随机参数q [0]，[1]来定义基于规则（5）将使用哪种方法来选择下一个节点。
q是[0]，[1]之间的随机启发式变量。 q0是定义哪个规则用于移动到下一个节点的参数。 使用这个参数，我们可以在随机节点之间进行选择，也可以选择信息素的数量和边缘的可见性来选择下一个访问节点。
节点i上的一只蚂蚁将选择移动到下一个邻居节点j，其概率P * ij显示在公式中：
pij是从i开始前往巴士站j的概率。 tau;ij是链路（i，j）上的信息素沉积量。 eta;ij是边缘（i，j）的可见度。 参数alpha;和beta;是反映信息素量和能见度影响的两个可调参数。 参数Omega;表示一组未访问节点。 在q = 0的情况下，蚂蚁将根据信息素的数量和启发式参数选择移动到下一个节点，而在另一种情况下，蚂蚁将仅使用启发式信息来决定哪个节点将被访问 下一个。
信息素更新
在ACS中，信息素更新基于两个级别：本地和全局更新。 当蚂蚁遍历一条边时，它执行一个本地更新，如下面的函数所示：
在这个等式中：
（1-p）是信息素降低参数（0 lt;p lt;1），代表踪迹蒸发或蒸发速率。 参数m是蚂蚁的数量，Lk是由蚂蚁k执行的巡回的长度，Q是任意常数。
全部更新在所有蚂蚁完成巡回演出时执行，并且只有创建最佳路线的最佳蚂蚁才允许使用以下等式在其边缘添加更多信息素：
蚁群算法的伪代码总结如下（图2）：为了在分布式架构中使用这个算法，我们应该能够理解这个算法的两个主要行为：
第一个，该算法基于顺序行为。每个蚂蚁构建自己的解决方案，然后开始本地信息素更新过程。全部信息素更新在所有蚂蚁完成游览时执行。一旦这一步完成，每个蚂蚁将重新开始构建步骤，并再次构建新的解决方案。
第二，为了启动全球信息素更新，我们应该比较蚂蚁提出的所有旅程，然后找到最佳旅程，因此此过程基于集中行为。
在ACS上进行了一些修改：i）使用新的体系结构，我们避免了在ACS中使用的标准迭代，所提议的系统基于并行和异步迭代（我们不需要等到每个蚂蚁构建一个巡视） ; ii）在经典的ACS中，每次迭代之后，我们需要比较最佳游览，所以我们只允许最好的蚂蚁在它们的边缘添加更多的信息素。我们通过允许蚂蚁将他们的解决方案与从上次访问的节点代理收到的最后一次旅游进行比较来避免这种情况（集中式和同步行为）。 iii）在ACS中，所有的蚂蚁都依次移动，而在我们的体系结构中，蚂蚁将平行移动。
第五节解决方法
在本文中，我们使用部署在分布式环境中的ACS的改进版本，我们选择一个改进的策略来开发我们的解决方案，它只需要很少的信息，并保证我们系统的融合速度以找到最佳解决方案。该政策的主要目标是同时运行一组人工蚂蚁，重复交流过程，直到基于给定的约束满足最短路径。
A.系统架构
开发了多个代理来创建我们的分布式架构。第一个是学校代理，它的功能是通过绘制问题图并控制系统的初始参数来与外部环境进行交互。第二个是公共汽车站代理，这是为了根据每个位置的学生人数生成公共汽车站，并创建一个子群来定义一组包含给定位置的最近学生的区域，使用分配路由定位策略。学校代理将使用此生成的图形计算每辆车的最佳路径规划。另一个人工实体是路由代理，它包含一组名为蚂蚁代理（AA）的智能代理，它们并行工作，根据SA提出的子图计算每辆车的最短路径。在图3中，我们描述了用于所提出解决方案的架构。
1）校代理
SA代理通过其坐标经度和纬度控制所有位置。这些位置是自专用于构建环境地图的用户界面创建的。 SA代理与公共汽车站相互作用，在该容器中，我们管理可从几个公交车站运送学生的车辆，每个车辆都有自己的能力，当SA选择其中一个用于学校运输时，应该遵守这些能力。
在我们的案例中，学校被视为我们地图的中心（图4），例如每辆公共汽车都应该从学校出发，拿起一组学生，然后在旅行结束时返回学校。 SA使用一组节点（学校，小孩的位置，公共汽车站）和定义两个位置之间的路线的边缘来管理图形，每个边缘的成本由这两个节点之间所需的时间来标记。开始时，SA将通过生成一个包含一组学生位置的图形来初始化我们问题的参数，然后请求BSA生成一组子集，这将创建一组子图，每个子图包含一组学生位置和一站式巴士。在第二步中，所提出的图将被RA用作输入数据来计算该图的最佳路径规划。最后，SA将选择一组车辆并为每个车辆定义一条路线，以便从一组公交车站中选取一组学生。
2）巴士站代理
该代理人的目标是根据每个学生的位置选择一组公共汽车站位置。我们假设学生们应该从他们的房子走到一个公共汽车站，然后他们会乘坐公共汽车去学校。巴士站应该是静态的，在我们的解决方案中，它们被假定为由系统用户给出。
为了将学生分配到公交站点，我们基于分配路线定位策略（参见图5）将一组学生分为子组。 首先，将儿童分为子集群，为每个集群分配几名学生，同时满足公交车容量限制和从房子到公交车站的最大步行距离。 最后
全文共7567字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[17092]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
