交通网络最优路径搜索的蚁群算法

针对交通网络中最优路径搜索问题,本文提出一种基于蚁群算法的新的求解方法。首先从剖析最优路径问题的求解要求出发,探讨蚁群算法求解的优势,由于其并行性、正反馈、协作性等特点,能在较短的时间内发现较优解。然后,根据交通网络的特性,在基本蚁群算法的基础上,引入信息素限定规则,采用平滑机制进行局部更新,改进了全局更新模型等,使该算法更能满足交通系统最优路径的求解要求,降低了路径选择的复杂性,从而提高计算效率。对改进的模型进行的模拟实验和比较分析表明,该模型与算法的效果良好。该研究为交通系统最优路径问题开创了一条新的途径,同时显示出蚁群算法在交通分配中的良好使用前景。     

变权值加快收敛的路径寻优实时算法

为获得满意解为目标的最优路径选择问题, 给出了一种加权的LRTA^* (LearningReal Time A^*) 算法, 通过改变估价函数值更新规则与解时间和解质量的相对折中, 加快算法收敛速度。实例应用表明, 该方法比LRTA^*算法更快地收敛于满意解, 是一种求解大城市稠密路网两点间最优路径的有效方法。     

基于交通限制的路网最优路径算法

为了解决车辆诱导系统中复杂道路结构表达及因为城市道路交通信号管理而产生的最优路径选择求解的复杂性,依据图论中最短路径算法的基本原理,提出了含有禁行路线路网的最优路径求解算法。以行程时间最少为目标,按照网络转化法把含有禁行路线的路网转化为不含有禁行路线的路网,采用邻接节点矩阵和邻接节点权矩阵实现了道路节点关系的表达,改善了传统的Dijkstra算法,将全局节点路径的求解转化为与求解节点紧密联系的局部区域求解,将所研究的网络转化方法和改进的路径寻优算法应用于车辆诱导系统。结果表明应用该算法能够在含有禁行路线的路网中求解最优路径,减少了问题求解的路网节点数,提高了计算效率。     

基于蚁群算法的动态路径选择问题

论述蚁群算法在动态路径选择问题上应用。在蚂蚁寻径原理基础上,建立经济圈公路网蚁群算法模型,并对算法的参数进行标定。针对算法的缺陷,对信息素更新策略进行了优化改进,使其能更快的收敛到全局最优解。该模型算法对经济圈道路交通智能化动态诱导系统的建立大有帮助。     

基于禁忌搜索的动态车辆路径问题研究

在对动态车辆路径问题进行描述的基础上,分析了求解动态车辆路径问题的主要策略.通过将计划周期分片,将动态车辆路径问题转换为一系列的静态子问题,对静态子问题采用禁忌搜索算法进行求解.采用该算法对9个算例进行了测试,与文献中其他算法的计算结果相比较,有3个问题得到了最好解,7个问题得到了最好平均解,表明了算法的有效性.     

A*算法在基于电子地图的动态路径诱导中的应用

动态网络中两节点间最短路径问题是目前尚未解决的一个难题．文中提出利用A＊算法来求解电子地图中的这一问题，并利用电子地图中的地理信息来得到网络中两节点间最短距离的下界，运用这些下界来设计有效的A＊算法．以广州市电子地图为基础，随机产生了一个满足先进先出原则的动态网络，利用这个网络对提出的算法进行了试验及性能分析．试验结果证明了该方法的有效性．     

基于蚁群算法的动态路径选择优化方法

为了确保城市路网交通流平稳运行和各路段交通流量合理分配,提出了一种基 于伪随机状态转移规则的动态路径选择优化方法.该方法首先计算路段上流量和路阻,利 用伪随机状态转移规则和路径、路段信息素更新规则,模拟了出行者在路网节点的择路 行为,实现了路径选择过程中静态先验知识、动态交通状态及路径选择随机性的综合.算 例结果表明,该方法能够体现不同 OD 需求下路径选择的叠加效果和时延效果,相对于 平衡分配法可获得更好的路网交通均衡性,对于时变路况环境下的路径诱导系统也具有 一定的应用价值.     

动态车辆路径问题中的实时最短路径算法研究

分析了现有算法处理动态车辆路径问题时的缺陷,提出了一个动态网络环境下的实时路径评估模型,在此基础之上构造了一个改进的Dijkstra双桶算法.该算法能根据静态和动态的交通信息找出客户之间的实时最短路径,并对车辆的旅行线路进行调整,具有对随机事件和突发事件进行实时处理的能力,已用于解决动态车辆路径问题.实验结果表明,该算法能在动态网络环境下找到实时的最短路径,减少车辆旅行的总成本.     

基于改进免疫遗传机理的动态路径诱导算法研究

针对传统算法存在的不足,提出基于改进的免疫遗传机理的动态路径诱导算法。通过引入单点交叉算子配合控制策略的改进思想,在宏观上控制交叉过程以及构造优化简单的目标函数,较好地弥补了传统遗传算法早熟收敛、陷入局部最优解、运算效率较低等问题。最后采用此算法进行路网实例计算,结果表明该算法能较大程度地提高路网利用率,减少交通拥堵。     

���ص���ϵͳ��̬����·���㷨�о�

目前用于车载导航系统最优路径搜索算法大多数只能适应静态交通环境,当交通环境或者出行者位置发生改变时,需要重新计算修改整个最优路径,速度较慢. 在LPA算法的基础上,首先将出行者位置不断变化而目的地位置固定不变的问题转化为起点固定终点固定的问题,另一方面结合增量搜索的思想,利用先前搜索的结果不断更新当前搜索过程中的遗传值,来提高搜索的效率,并最终提出了可用于车载导航系统的动态最优路径搜索算法. 实验结果表明, 在交通环境和出行者位置同时发生变化的情况下,最优路径搜索时间要比静态算法小很多. 最后将算法部署在Windows Mobile手机移动平台上,实际结果表明, 该算法较好地解决了动态最优路径问题,具有理论参考价值和实际意义.     

基于布尔可满足性的动态路径优化算法

在对现有的经典路径优化算法性能进行分析基础上,指出现有算法的缺点。通过对布尔可满足性理论的研究,提出基于布尔可满足性的路径优化算法,并结合记忆机制,将其应用在动态路径优化中,减少最短路径的搜索时间和不必要的重复搜索,体现该算法的优势。最后,利用该算法对一简单路网进行验证。     

基于城市道路数据库的最短路径搜索

在智能交通的导航／动态路线诱导系统中，最短路径搜寻是其重要功能，根据城市交通路网建设的实际，研究了描述城市交通网络图的城市道路数据库的组织结构。在此数据结构的基础上依靠GIS技术的支持，采集了大量具体道路信息，采用Dijkstra算法实现了快速最短路径搜索。根据城市的交通状况对交通网络图的边值赋予不同的权值可实现最优路径搜寻。给出了在广州市电子地图上搜索的一个实例：一个包含61个交通路口的最短路径搜索结果的搜索时间约为2．2s。     

���ڡ�������������̾�·�㷨

最短径路是网络优化中的一个经典问题，Dijkstra算法被公认为是一种十分有效的最短径路的搜索求解算法．本在研究网络一般结构特点的基础上，发现传统Dijkstra算法在每次迭代过程中都需要搜索所有节点的这一缺陷，通过向搜索节点中引入“度”的信息，提出了基于“度搜索”的改进算法，并根据网络的特点，给出了有向网络和无向网络两种情况下存在“度”差异的算法设计方法；算法的整体结构与Dijkstra保持了一致性，没有算法结构的突变，因而通过修改原有Dijkstra程序和重新设计“度搜索”程序都十分容易实现．该算法提高了最短径路的搜索效率，特别是对稀疏网络，算法效率更为明显，其复杂度小于O(｜V｜^2)．     

基于路径关联性的交叉口群动态划分方法

交叉口群是路网交通流协调控制的基本单元,其动态范围划分与路网协调控制效益直接相关。在对经典Whitson路段关联性模型进行改进的基础上,考虑局部路网上交通流OD的空间分布特征建立了相邻交叉口之间的路径关联性模型;基于路径关联性模型计算结果,应用层次聚类方法对信号控制交叉口群进行动态划分。最后对路段关联性和路径关联性的交叉口群动态划分方法进行了算例验证和对比分析。研究结果表明,考虑路径关联性动态划分交叉口群可以减少对局部路网中主要OD路径的分割,从而降低主干道交通流的总停车次数和停车延误。     

动态规划算法在最优航路规划中的应用

通过对船舶最优航路概念的分析,提出了一种基于动态规划算法的船舶最优航路规划。实现了船舶最优航线的自动生成,不仅可大大减轻航海作业人员的工作强度,同时也能增强航线的安全性和可靠性．     

公交网络最优路径求解算法

求解公交网络最优路径是进行公共交通系统规划的一项关键技术.通过对多种现有算法的分析,利用公交换乘矩阵性质,本文提出了一种求解公交网络最优路径的标准算法.新算法考虑了公交换乘次数、换乘点选择以及出行总成本对求解最优路径的综合影响.通过建立换乘步行时间矩阵,并将过去求解最小换乘次数的换乘矩阵乘法运算变为相应的换乘步行时间矩阵和公交出行时间矩阵的加法运算,得到新算法.新算法可顺利实现在单一OD对、单起点多终点以及任意节点间求解最优路径的转化.文中给出了新算法的详细求解步骤,而且通过一个算例对新算法的有效性进行了验证.     

广义关联规则基及其挖掘算法

为了解决传统的关联规则挖掘中产生大量规则的问题，提出了项目集上闭集和广义关联规则基的概念，并得出了闭项目集的上闭集是它本身、上闭集是惟一的等性质．基于这些性质，给出了事物数据库的广义关联规则基，不仅保留了数据库中所有关联规则的信息，而且规则有一致的结构，从而最大限度地减少了规则生成的数量．此外，还设计了广义关联规则基的挖掘算法，并通过实例验证了它的正确性．     

网络最短路径定界搜索算法

用Dijkstra算法求解大规模网络两顶点间最短路径时，需计算大量与最短路径无关的顶点，效率较低，双向定界搜索算法是首先对网络进行双向搜索，得到一条经任意点的最短路径，一般情况下，这条路径已非常接近、甚至等于最短路径。然后，以此路径的标号(即路径长)作为搜索计算的界，进行双向标号计算，对超过界的顶点不再计算，以提高计算效率．算法分析表明，用该算法可使计算效率提高约一倍。