英语原文共 19 页，剩余内容已隐藏，支付完成后下载完整资料
高速公路网蚁群路由算法
丛喆, Bart De Schutter, Robert Babuscaron;ka
代尔夫特系统与控制中心，代尔夫特理工大学，2628 CD Delft，荷兰
摘要：
动态交通路由是指根据不断变化的交通状况（重新）在交通网络中的交叉口指导车辆的过程。交通管理中心为驾驶员确定期望路线，以便通过动态交通路线来优化交通网络的性能。然而，交通网络可能有成千上万的线路和节点，导致出现大规模和计算复杂的非线性、非凸优化问题。为解决这个问题，本文选取蚁群优化算法（ACO）作为优化方法，因为它对组合优化问题具有强大的优化启发式搜索。蚁群优化算法在线实现以确定控制信号，即每个节点的裂解率。然而，使用标准蚁群优化算法进行交通路由具有四个主要缺点：1、不能区分不同起讫点的交通流量；2、所有的蚂蚁可能会聚合到一条路线，造成拥堵；3、不考虑约束条件； 4、不考虑动态链接成本。这些问题通过采用具有臭味信息素和有色蚂蚁的新型蚁群优化算法来解决，称为蚁群路由（ACR）。通过臭味信息素，蚁群路由算法可以将交通工具分布在交通网络上，使交通堵塞较少或没有，并减少一些敏感区域附近的车辆数量，例如医院和学校。使用有色蚂蚁可以表示多个起点和终点的交通流量。所提出的方法也在荷兰Walcheren地区的基于仿真的案例研究中得到实施，说明了该方法的有效性。
关键词：蚁群优化，模型预测控制，动态交通路由，臭味信息素
1 引言
交通网络控制涉及与交通流动态、驾驶行为和交通需求相关的复杂交通状况。 随着人口的迅速增长和不同地区就业分布的不平衡，我们比以往任何时候都更需要交通网络的有效和高效运行。现在，增加和扩大基础设施是昂贵和不切实际的，它往往只是暂时减轻交通网络的负担，而不是在寻求长期的解决方案。因此，交通控制策略的发展更为可取。动态交通路由是这类有前途的方法之一，通常用于指导交通网络中的驾驶员实现某些目标，如用户均衡或系统最优（Wardrop，1952）。
针对这一课题存在着大量文献（Peeta和Ziliaskopoulos，2001；Ziliaskopoulos，2000； Carey和Subrahmanian，2000；Ran等人，1993；Mahmassani和Peeta，1993，1995）。 Peeta和Ziliaskopoulos（2001）总结了从数学规划（Ziliaskopoulos，2000；Carey和Subrahmanian，2000）到最优控制（Ran等，1993； Kotsialos 等，2002）再到基于仿真方法（Mahmassani和Peeta，1993,1995）等主要的动态交通分配方法。具体而言，在数学规划模型中，问题通常以离散时间设定。Ziliaskopoulos（2000）利用所谓的细胞传播模型将单目标系统最优动态交通分配问题看作一个线性规划问题。Carey和Subrahmanian（2000）也提出了一个线性系统最优公式，旨在获得对动态交通分配模型性质的见解。对于最优控制方法，Ran等（1993）通过定义链路流入和流出作为控制变量来获得瞬时用户均衡动态交通路径问题的凸集模型。Kotsialos等（2002）将动态交通路由作为系统最优解的离散时间最优控制问题，并采用数值非线性优化算法进行求解。基于仿真的方法专注于交通模拟而不是分析评估。Mahmassani和Peeta（1993,1995）使用介观交通模拟器DYNASMART和迭代算法来寻求系统最优和用户平衡的解决方案。其他工作，（例如Bottom等，1999；Paz和Peeta，2009b，a）侧重于驾驶员对路线选择机制中提供的指导信息的反应。Bottom等（1999）使用实时测量和短期预测，开发了生成路线指导说明的分析框架。Paz和Peeta（2009b，a）在明确说明驾驶员对实时信息的可能反应的同时旨在提高交通网络性能。
上述一些研究使用数值非线性优化方法，这些方法需要极高的计算负担，而另一些牺牲性能来提高计算速度。为了在性能和计算速度之间找到一个均衡的平衡点，本文提出了一种基于人工蚂蚁的新型动态交通路线选择算法。自然界中的蚂蚁显示出令人惊讶的智能集体行为，以找到他们的巢穴和食物来源之间的最短路线，尽管每只蚂蚁仅仅具有非常有限的搜索能力。这是由于蚂蚁使用称为信息素的媒介相互沟通以便它们可以间接交换信息。蚁群优化算法（Dorigo和Stuuml;tzle，2004）源于蚂蚁的这种自组织行为，并且已经发展用于解决一些组合优化问题，例如最短路径问题、最佳任务分配问题 、最优路线方案问题等等。此外，学者们通过使用标准的ACO算法在解决动态交通路线问题方面也做了一些研究（Tatomir和Rothkrantz，2006；Alves等，2010）。然而，大多数文献提出的算法都有其局限性。Tatomir和Rothkrantz（2006）使用了路由表，其中包含每个网络节点中可能的交通量裂解率。在每个节点，蚂蚁从表格中选择一组裂解率应用于交通网络。当网络中添加更多节点时，这种方法可能导致计算负担呈指数级增长，使得该算法效率较低。此外Alves等（2010）仅调查单一起讫点网络，他们使用静态交通模型，其中交通条件为时间不变。
事实上，使用标准的蚁群优化算法进行动态交通路由会遇到四个主要问题：
1. 蚁群优化算法中，蚂蚁没有单独预先指定的目的地，而交通网络中的每辆车都有自己的预定目的地。
2. 蚂蚁只争取用户均衡，而交通管理有全球目标。
3. 蚂蚁网络对链路没有限制能力，而交通网络受链路容量限制。
4. 蚂蚁网络中的链路成本是固定的和静态的，而交通网络的链路成本动态 依赖于时变的交通状况。
受上述四个问题的启发，本文介绍了一种基于蚂蚁的交通网络路由算法，称为蚁群路由。Cong等（2011）通过引入蚁群优化算法的一种变体，称为臭气信息素蚁群优化（ACO-SP），解决了第一个问题，它是为解决网络路由问题而提出的。臭气信息素与标准ACO算法中的常规信息素具有相反的功能，为了系统范围的目的，它被用于在网络上分散蚂蚁。 为了解决第二个问题，我们提出了有色蚂蚁的新概念，其中每种颜色被分配到相应的目的地，而有色蚂蚁只对它们自己的颜色敏感。此外，通过适当选择恶臭信息素功能来解决容量限制以及对链路上车辆数量的其他限制。最后，在蚂蚁网络的链路成本中考虑从动态流量模型中获得的时变交通量，并且使用迭代算法来获取动态特性。
蚁群路由算法将应用于模型预测控制（MPC）（Maciejowski，2002； Rawlings和Mayne，2009；Hegyi等，2005）框架内。但在此之前，我们首先实施网络修剪步骤。这是因为交通网络可能涉及成千上万的链路和节点，并且一些链路和节点组成可能相对较长的线路，使得它们可能不被驾驶员选择。因此，我们使用网络修剪步骤来移除这些“不必要的”链路和节点以降低交通网络的复杂性，并减少蚁群路由算法的运算负担。网络修剪步骤涉及静态优化问题，该问题不是由蚁群优化算法解决，而是由线性规划解决，并且仅执行一次。对于线上动态交通路由，MPC控制器通过使用蚁群路由算法作为优化方法被重复执行。具体而言，在每个控制步骤中，我们首先测量交通网络的当前状态，并使用动态交通模型来预测某个预测期间的未来状态。然后使用当前状态和预测状态来计算分配给蚂蚁网络中的每条链路的链路成本，并且使用ACR算法来优化路由问题。因此，交通网络中的控制信号——裂解率由蚂蚁网络中每条链路上行进的蚂蚁数决定。我们继续执行相同的控制步骤运行这样一个预测优化循环，直到满足给定的收敛条件，然后我们将得到的裂解率应用于实际的交通网络。接下来，我们将MPC的控制范围和预测范围向前移动一个采样时间步，并重复整个过程。控制策略结构图如图1所示。
图1 动态交通路由控制策略结构图
本文的其余部分结构如下。第2节定义了动态交通路由问题。第3节简要概述了ACO-SP算法。第4节说明了解决动态路由问题的ACR算法。在第5节中详细阐述了两步控制策略——网络修剪和MPC。第6节介绍了使用荷兰Walcheren地区高速公路网研究案例的新动态交通路线控制方法。最后一节第7节简短地总结了本文主题和工作展望。
2 问题陈述
本文研究目标是双重的：
1. 我们的目标是找到一个最优的路由解决方案，以减少交通网络的旅行成本（本文中花费的总时间（TTS））；
2. 我们的目标是减少交通网络中每个环节的车辆数量，尤其是在敏感区域，例如医院和学校附近，以提高安全性并减少噪音和污染。
与其他大多数基于优化的交通控制方法不同，我们在ACR算法中不使用明确的总体目标函数，因为上面介绍的两个子目标分别由ACR中的成本函数和恶臭信息素函数评估。更具体地说，第一个子目标是基于人造蚂蚁总是争取最佳解决方案的事实，第二个子目标是当蚂蚁聚合在同一个链路上时通过恶臭信息素将人造蚂蚁推开而实现的。通过这种吸引和排斥机制，这两个子目标可以间接地包含在ACR算法中。本文旨在找到子目标1和2之间的均衡权衡。实际上，这种权衡取决于交通管理部门制定的交通政策。
接下来，我们将介绍本文使用的一些与交通网络相关的重要概念。交通网络，尤其是高速公路网络，可以用带有节点和链路的有向图表示，如图2所示。在交通网络中，一条具有统一特征的道路——即没有任何入口坡道或出口坡道，几何形状没有任何重大变化——被称为链路（由系数m表示）。为了更精确的建模，每个链路m的长度Lm被分成Nm段（由指标i表示）。如果链路的特征发生重大变化，则在该处放置节点并启动新的链路。网络中有三种不同类型的节点，起点（由指标o表示），终点（由指标d表示）和中间节点（由指标n表示）。从起点o到终点d，不包含循环的链路被定义为路由（由指标r指示）。表1列出了本文使用的所有重要符号。
图2 OD对（o,d）的流入量qin o,d(k)分布在多线路图例
本文考虑交通网络的离散时间设置。模拟采样时间T用于描述交通模型，控制采样时间用Tc表示。相应地，我们将k定义为仿真步骤计数器，将kc定义为控制步数计数器。为简单起见，我们假设Tc是T的整数倍：Tc = M*T，其中M为整数。
对于每个OD对（o,d）isin;Otimes;D，其中O是起点集，D是终点集，qin o,d(k)是在仿真步骤k处终点d进入原点o的交通流入量。对于链路m isin;M的每个分段i，其中M是所有链路的集合，在仿真步骤k中向终点d行驶的车辆的流量由qm,i,d(k)表示。不失一般性，从现在开始我们假定每个起点oisin;O只有一个输出链路，每个终点disin;D只有一个输入链路。对于特定节点nisin;N，其中N是网络的中间节点集，在仿真步骤k中进入终点d的总流入量Q n,d(k)由下式给出：
Q n,d(k) = sum;qmrsquo;,Nmrsquo;,d(k)
其中I(n)是节点n的输入链路的集合，并且qmrsquo;,Nmrsquo;,d(k)表示在仿真步骤k处输入链路mrsquo;isin;I(n)的最后段（指标Nmrsquo;表示）的车流量。在仿真步骤k的输出链路misin;O(n)的初始段（指标l）处的交通量qm,l,d(k)，然后由在步骤k处的裂解率
beta;n,m,d(k)相应的控制步骤kc，由kc(k)表示，其中kc = floor（k / M），其中函数floor（x）表示小于或等于x的最大整数：
qm,l,d(k) =beta;n,m,d(kc(k))Qn,d(k)
如第1节所述，通过每个节点中的裂解率beta;n,m,d(kc(k))应用最佳的交通路由解决方案。换言之，ACR算法的目标也可以被认为是确定交通网络中的最优裂解率beta;n,m,d(kc(k))。
3 蚁群优化算法与臭味信息素
ACO-SP算法（Cong等，2011）通过使用人造蚂蚁来解决网络路由问题。该算法旨在通过网络分散蚂蚁，而不会导致所有蚂蚁都在可能导致拥塞的最佳路线上行驶。
更具体地说，ACO-SP中的蚂蚁总是在优化开始时努力找到最佳路线；如果最好的路线对于蚂蚁来说过于拥挤，那么蚂蚁会争取第二条最佳路线；如果第二条最佳路线也满载，则会选择第三条最佳路线等等。蚂蚁分散而不是聚合到同一路线的原因是因为ACO-SP具有两种类型的信息素：标准ACO算法中相同的常规信息素以及新引入的恶臭信息素。前者用于将蚂蚁吸引到网络中的最佳路径上，以保证算法的有效性，后者用于降低弧上信息素水平的总量，以防止常规信息素在同一弧线上积累过多。以这种方式，一部分蚂蚁被推离他们之前选择的路线，并开始在网络中选择另一条路线。蚂蚁网络是蚂蚁走过的一个网络。根据特定的优化问题，通常将其建模为加权图（参见Stuuml;tzle和Dorigo，1999；Salari和Eshghi，2008；Rivero等，2012）。此外，蚂蚁网络中的特定路径ra是由蚂蚁a从起始顶点到目的地顶点选择的弧(s, t)，其中顶点s和t由弧(s, t)连接。信息素变量tau;s, t与网络中的每个弧(s, t)相关联，并且它表示蚂蚁随着时间的推移获得关于最优解的知识。在ACO-SP算法开始时，所有的信息素变量应该被设置为初始值
tau;<su
全文共9141字，剩余内容已隐藏，支付完成后下载完整资料</su
资料编号：[15393]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
