城市道路交通网中最短路径搜索算法设计及其实现

交通网络中最短路径的搜索是地理信息科学与计算机科学等领域的研究热点。本文以石家庄市中心区域部分道路网为实践对象,结合道路网络的特点,在自定义节点一链拓扑结构表达路网的基础上,提出了一种适于最短路径算法的空间数据组织方式,运用迪杰斯特拉(Dijkstra)最短路径算法,以MapInfo的二次开发语言MapBasic为开发工具,在电子地图环境下实现了道路网络中任意两节点间最短路径的快速解算与刷新显示。     

一类点权网络的最小费用流问题

以城市路网为背景求最小费用流时不能忽略交叉口的费用和通行能力限制,但由于交叉口延误等费用和通行能力具有方向性,普通最小费用流算法无法直接应用于这类问题.文中以节点权重表示交叉口的延误和通行能力,将城市道路网表示为一个节点具有分方向权重的点权网络,提出了一个改进的最小费用路算法求解这类点权网络中的最小费用流问题.算法计算时间复杂性为O(nmf0).以一个数值算例说明了算法的应用.     

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

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

城市道路网拓扑结构的复杂网络特性研究

以城市道路网中的连续道路中心线作为网络拓扑结构的基本分析单元,作者采用对偶法对我国12个不同规模和形态的城市道路网的拓扑结构进行了抽象,在此基础上分析了我国城市道路网拓扑结构具有的普遍复杂网络特性。研究指出,我国城市道路网的拓扑结构一方面具有较小的特征路径长度和较大的聚类系数,是典型的小世界网络;另一方面其度分布函数为幂律形式,又具有典型的无标度特性。     

城市OD区间道路总容量的模型研究

定义了城市OD间路网总容量,根据交通流平衡分配原理,以路径走行时间与路径上交通流量之间的关系为基础,建立了利用路段观测交通量和OD区路径走行时间推算城市OD间道路网容量的数学模型。证明了该模型存在唯一的解,通过算例对该模型进行了验证,表明模型能逼近实际。     

重大灾害条件下基于GIS的最短路径改进算法

利用经典的Dijkstra算法,对重大灾害条件下Dijkstra算法进行了改进,构建了惩罚因子函数,结合GIS软件二次开发模块,通过Visual C++6.0实现了复杂网络的分析功能。分析了重大灾害条件下节点数量对于道路可靠性以及最优路径选取的影响,综合考虑距离、行程时间以及节点数量因素,证明了改进Dijkstra算法对于最优路径选择的优越性。分析结果表明:利用改进Dijkstra算法、经典Dijkstra算法计算出的路径节点数分别为31、59,行程时间基本相同。可见,改进算法能有效减少疏散路径中的节点数量,降低车辆在节点处的延误损失和风险。     

交叉口有延误的交通网络最短路径算法研究

在交通规划和VRP研究中,考虑道路网交叉口的延误将更加切合实际,对于节点分方向有延误的最短路问题,传统的Dijkstra不再适用．考虑交叉口分方向的延误情况,给出了一个求此类问题最小时长路径的标号算法,其时间复杂性为O(n^2)．     

道路网形态与公交线网关系的研究

论文在对城市道路网形态论述的基础上,以国内牡丹江、常州、扬州、德州四个城市的城市道路网与公交线网的关系为例,对公共交通的线网形态受到城市道路网形态的影响和制约进行了较为详细的论述,最后对道路网布线方法与道路网形态适应性进行了研究,并提出了研究展望,以期对国内公交线路规划起到一定的促进作用。     

基于有效路径集合的节点间连通度估计方法研究

对交通网络而言,节点间并非所有路径都作为出行者备选路径.与纯网络连通可靠性评价方法考虑节点间的所有可能路径不同,文中把节点间有效路径集合作为评价载流交通网络节点间连通可靠性的依据.节点间的有效路径集合可以通过Dial算法得到,在得到节点间有效路径集合后,利用BDD算法得到有效路径集合的不交化表示,进而得到节点间连通度的精确值.     

城市道路网规划指标体系

分析了城市道路网质与量的功能,研究了城市道路网的规划指标体系,提出城市道路网规划指标体系宜划分为空间指标体系和交通质量指标体系两大类,并分别确定了7个空间指标和3个交通质量指标的定义及量化方法.应用结果表明,指标量化计算中所需要的基础数据在城市道路网规划阶段便于获取,便于不同城市结合自身特点确定规划指标.     

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

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

应急车辆动态路径选择的两阶段优化模型

为研究突发事件情境下交通路网动态变化时的应急车辆路径选择问题，提出应急车辆动态路径选择的两阶段调度优化模型。通过结合路网动态状况和应急救援特征，建立基于最大路径可靠度和最短行程时间的两阶段优化模型；通过混沌搜索改进布谷鸟算法初始种群，并加入蛙跳算法改进局部搜索操作，设计混合布谷鸟算法，改善全局寻优能力；以某市某区部分区域路网为例，将该区域路网实时交通数据应用于模型和求解算法中。实验表明，利用两阶段优化模型和算法编码方案能成功获得出发点到救援点的动态可靠路径，相同行驶路径情况下模型与算法求解的最短行程时间与实地驾车获得的最短行程时间最大误差不超过8%，说明优化模型可行。3 种不同算法求解K最短路径的结果发现，混合布谷鸟算法得到的最短行程时间比粒子群算法和 经典布谷鸟算法得到的结果都要小，且计算时间最短，表明混合布谷鸟算法求解的结果最优，性能最好。     

城市道路网双层规划模型及其应用

分析了城市道路网规划的目标以及现有规划模型在应用时存在的不足之处.采用双层规划模型构建了城市路网规划模型.用迭代算法对该模型求解.以兰州市为例,结合城区实际交通状况和交通需求,采用该模型及算法进行路网规划,获得了兰州市道路网规划方案.在该方案中从快速路至支路初步形成了“金字塔”形分布.     

基于模拟退火算法的物流配送路径优化问题分析

模拟退火算法是解决NP完全组合优化问题的有效近似算法,将该算法应用于路径优化问题中,利用该算法对类似货郎担问题的路径问题进行求解。针对城市道路行走不同的目标条件（路径最短、时问最短）进行优化,选择最佳行走路径,并用该算法优化得到的计算结果,结果表明该算法在解类似货郎担交通路径方面问题时具有较高的精确性。因而,该算法在解决城市道路交通问题方面具有一定的实用价值。     

�ںϳ��⳵��ʻ����IJ��·���滮����

出租车驾驶员对城市道路交通状况较为熟悉,他们选择的路径具有代表性,因此将出租车驾驶员路径选择经验融合到路径规划算法中,对提高出行效率具有重要的意义.本文提出一种融合出租车驾驶经验的层次路径规划方法,主要包括三部分：首先,从出租车GPS数据中提取出出租车载客行驶轨迹;然后,根据各路段出租车行驶频率高低对路网进行分层,构建基于出租车经验路径的分层路网;在此基础上,使用Dijkstra算法实现层次路径规划.最后,本文以广州市为研究区域,将该方法得到的规划路径与经典路径规划算法的结果进行比较.结果表明,融合出租车驾驶经验的路径规划方法所得路径在行程时间上占有一定的优势.     

城市路网模块结构探测及Hub路段诊断算法

为了剖析城市路网拓扑结构的复杂性,识别路网中的关键路段,根据模块结构理论,分析了城市路网的聚类特性,提出了一种适用于城市路网模块结构划分和Hub路段诊断的算法——GN-T算法.该算法通过逐条移除介值最大的路段实现模块结构的划分,从而诊断出路网中的Hub路段.为确定模块结构的最佳划分,提出了一个改进的模块度函数.以武昌区路网为例对该算法进行验证,结果显示:武昌区路网模块度的最大值为0.41,表明该路网具有明显的模块结构特性;利用该算法诊断出的Hub路段与实际情况相符,证明了该算法的有效性和实用性.      

交通路况感知下的自适应动态路径规划方法

针对传统路径规划算法在动态网络中的时效性和可用性不足，本文提出一种适用于时变 路网环境下的自适应动态路径规划方法。通过引入动态网络流式图划分思想，构建一种分层路 网的状态树索引，有效降低了动态路网中路径查找的计算代价，并扩展了传统路径规划算法在动 态路网中的普适性。在此基础上，将区域路况的时空变化信息融合到索引树中，进一步提出一种 基于时空层次网络的路径映射方法。并按照访问节点的距离逐步收缩最小包含区域来减少路径 查找视野，将路径查找过程转化为在层次图中的小范围寻址。为适应路网动态变化特征，路径映 射采用多路并行的双向探测策略，使得路径搜索迅速收敛于一个最优解，在动态路况变化和旅行 代价之间寻求平衡。最后，结合北京市实时交通路网数据集进行实验评估，在查询性能和自适应 调整方面验证了所提出方法的有效性。     

Logit�����������ģ�͵ĸĽ�Dial�㷨

研究Logit随机网络配流模型及实现模型求解的Dial算法,针对原模型及算法的缺陷,通过引入路段长度相关的容错系数指标重新定义有效路径的判定条件,在此基础上提出一种改进的Dial算法,并应用于Logit随机网络配流模型中.改进算法在不降低原算法精度下不仅保留了原算法的无需路径枚举、计算效率高等优越性,而且满足实际出行者偏好在较短路段上“迂回”选择潜在有效路段的特点.最后通过一个路网实例对2种算法的配流结果进行了对比.结果表明,改进的算法避免了原算法缺陷导致的结果异常,配流效果更加符合实际,其计算效果明显优于原算法.     

车行指路系统信息连续性分析及量化算法

指路标志信息连续性是驾驶者在复杂路网中顺利出行的保障. 本文以路网指路标志信息系统为研究对象,从宏观、中观、微观3 个层面分析指路系统信息的连续性,提出系统、频度信息项、区域、方位、路径等不同层级的连续性量化指标,利用空间聚类分析识别指路信息项目标地的辐射方位,基于有效路径三原则筛选每个方位的路径集;考虑路径各节点指路信息项的前后承接特征、道路及交通设施条件量化驾驶人心理预期,即节点信息连续度;设计了路网及指路信息项、转向特征等属性的数据存储结构,提出指路系统连续度量化算法,以实现其信息连续性计算. 最后,以重庆市渝中区路网指路信息系统为例,对连续性分析模型及量化算法进行验证.     

车行指路系统信息连续性分析及量化算法

指路标志信息连续性是驾驶者在复杂路网中顺利出行的保障. 本文以路网指路标志信息系统为研究对象,从宏观、中观、微观3 个层面分析指路系统信息的连续性,提出系统、频度信息项、区域、方位、路径等不同层级的连续性量化指标,利用空间聚类分析识别指路信息项目标地的辐射方位,基于有效路径三原则筛选每个方位的路径集;考虑路径各节点指路信息项的前后承接特征、道路及交通设施条件量化驾驶人心理预期,即节点信息连续度;设计了路网及指路信息项、转向特征等属性的数据存储结构,提出指路系统连续度量化算法,以实现其信息连续性计算. 最后,以重庆市渝中区路网指路信息系统为例,对连续性分析模型及量化算法进行验证.