基于混沌蚁群算法的最短路径选择研究

如何解决最短路径选择问题一直是城市交通流诱导系统的关键之一.基于群体仿生理论的蚁群算法是解决此问题的一种方法,针对采用蚁群算法进行最短路径选择时易出现的陷入局部最优解问题,引入混沌理论,采用混沌蚁群算法利用混沌初始化进行改善个体质量和利用混沌扰动避免在蚁群算法搜索过程中陷入局部极值,同时降低了蚁群算法的时间复杂度,从而更好的解决了最短路径选择问题.     

基于铁路运输网络的最短路径及次短路径研究

在铁路运输网络中,经常要计算最短路问题,Dijkstra算法和Floyd算法是求最短路径的最常用最有效的两种方法。首先从不同方面对Dijkstra算法和Floyd算法进行了比较分析,然后对次短路问题做了简要介绍。     

最短路径子图

在大型网络中两节点之间的最短路径常常不止一条，而且在带限制条件的路径选择等应用上，常常需要找出多条最优或近优的路径．一些经典的单源最短路径算法，如Dijkstra算法，能找出一条从起始点到目的点的最短路径，但并不能求解两点之间的所有最短路径．本文给出了最短路径子图的概念，用于存储图中两节点之间所有最短路径信息，能够节约存储空间．并给出了最短路径子图构造算法SPSG，其时间复杂度为O(n e)，比同类算法时间复杂度更低．随机网络模型的仿真结果表明：SPSG算法效率更高，     

基于Dijkstra的最短路径改进算法

针对如何利用Dijkstra算法来高效地查找图中任意两结点之间的最短路径这一问题,提出了2种优化方法:其一是应用图中各结点的出入度来简化查找任意两结点之间的最短路径;其二是利用已求出的两点之间的最短路径来快速获得其他结点之间的最短路径。     

基于混沌蚁群算法的最短路径选择研究

如何解决最短路径选择问题一直是城市交通流诱导系统的关键之一.基于群体仿生理论的蚁群算法是解决此问题的一种方法,针对采用蚁群算法进行最短路径选择时易出现的陷入局部最优解问题,引入混沌理论,采用混沌蚁群算法利用混沌初始化进行改善个体质量和利用混沌扰动避免在蚁群算法搜索过程中陷入局部极值,同时降低了蚁群算法的时间复杂度,从而更好的解决了最短路径选择问题.     

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

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

考虑转向延误的最短路径的节点标号算法

拥堵时段车辆在城市路网中交叉口处的延误甚至会大于其在路段的行驶时间,因而拥堵情况下在城市路网上应用不考虑转向延误的最短路径算法无法反映真实的交通状况.分析既有的考虑转向延误的最短路径算法,扩展网络法因过大的时间和空间开销而欠缺实用性,其余算法包括对偶网络法、节点标号算法和弧标号算法本质均为求包含节点权重和边权重的最短路径问题,最后求解均为节点标号算法.对典型节点标号算法Dijkstra算法进行改进,通过记录节点的紧前节点完成转向判别,并通过最小堆优化将该算法的时间复杂度从O(n2)优化为O(nlogn),并给出算法的数据结构,完成了软件编码,并通过计算实例对算法进行了验证.结果表明:考虑交叉口延误后城市路网最短路径发生变化,同时经过堆优化后算法的时间复杂度下降.     

在交通网络图上实现可视化路径查找

在交通网络图中，解决最短路径已有许多成功的算法，一般只以文字形式给出最短路径长度和路径上的顶点，很不直观。笔者研究了以图形方式表示最短路径的方法，以便对汽车行驶有更好的导向作用。     

城市道路网络交通特性仿真模型及最短路径算法

就城市道路网系统宏观仿真中存在的问题进行研究，提出了更符合城市道路网系统实际特性的仿真模型，该模型对城市道路网交通特性空间分布的方向性差异及交叉口延误进行了抽象，并设计了基于该仿真模型的最短路算法。     

一种寻求多条最短路的新算法——生长路径法

为了寻找栅格状轨道交通运输网络中任意两个节点间的全部最短路径,根据数据结构中堆栈数据“后进先出”的原理,提出了生长路径法,它将从起点发出的初台最短路径压入堆栈,并利用边的编号和路径长度对堆栈内的路径进行生长和判断,合格的路径进栈,不合格的路径剔除,直到堆栈内所有的路径都生长至终点为止,利用这种算法可求出无负向边的有向网络中任意两节点间所有的最短路径。     

结合概率搜索定界的入度统计最短路径算法

Dijkstra 经典最短路径算法包括大量的排序运算,且需要对图中所有顶点进行计算,效率较低.本文针对有向网络,提出了与概率搜索定界结合的入度统计最短路径算法.该算法通过按概率搜索得到一条较短路径,依据路径长度和有向网络结构特征确定和顶点序号相关的节点阻抗最大值;采用入度统计算法代替经典的标号算法,在计算过程中根据节点阻抗最大值,采取一定方式剔除无效顶点(不在最短路径内的顶点),简化网络结构.本文提出的算法不需要进行排序运算,简化了运算过程,并且可以剔除大量的无效顶点,降低了网络复杂度.算例分析表明,相对于Dijkstra算法,结合概率搜索定界的入度统计算法大幅度提高了运算效率,具有实用性.     

面向城市交通网络的 K 最短路径集合算法

在城市交通网络中,为了优化交通流,需要搜索到符合出行需求 K 最短路径,并 将 OD（Origin-Destination）交通流合理分配到这些路径上.本文主要对搜索符合出行需 求的 K 最短路径搜索算法进行了研究,解决了已有算法仅能搜索出单条满足最短及 K 最 短条件路径的问题.根据 Wardrop 第二原则及路段阻抗函数理论,分析了路径集合搜索方 法对优化城市交通流的必要性,并定义了城市交通网络中 K 最短路径集合的概念及选择 条件,提出了一种面向城市交通网络的具有多项式时间复杂度的 K 最短路径集合搜索算 法.仿真结果表明,本文所提算法可以搜索出满足出行需求的所有 K 最短路径集合,在该 路径集合上进行交通流分配的效果明显优于传统方法.     

距离加权公交换乘复杂网络最短路算法研究

为研究乘客使用公共交通的实际出行距离,基于公交复杂网络中的换乘网络Space P拓扑结构,结合公交车站的经纬度坐标,建立以距离为边权的加权公交换乘网络。基于该加权网络,设计了综合考虑换乘次数和路径长度的最短路算法,该算法可保证在站间换乘次数最少的基础上通过的路径也相对最短。利用成都市公交网络进行实例分析,并与Floyd算法进行对比,结果显示,由该算法得到的平均最短路径长度增加3.7 km,但平均换乘次数下降0.64次,更符合乘客的出行习惯;随机选择一些车站进行最优换乘路径选取试验,结果表明,由该算法得到的方案在保证换乘次数最少基础上,得到的路径也基本最短,证明了算法的有效性。     

求网络中全部最短路的径路延伸算法

在分析已有最短路问题研究成果的基础上,提出了最小最短路网络的概念,给出了求网络上始点到所有顶点间全部最短路的径路延伸算法以及最小最短路网络、最小最短路树的算法.通过算例,验证了算法的可行性.算法简便,易于理解.     

考虑交叉口延误的城市道路最短路径

在利用G IS建立城市道路网并通过空间分析判断节点方位和路径走向的基础上,提出了一种具有节点阻抗的F loyd算法来解决城市道路网中的最短路径问题,这里直行、左转或右转的分流向延误得到了充分考虑。最后利用所提出的算法对重庆市石桥铺街道路网进行了分析计算,得出了比传统方法更合理的结果。     

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

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