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

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

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

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

考虑交叉口转向延误的最短路径拍卖算法

为了改进传统算法求解最短路径时运算量大且无法计算交叉口转向延误的不足,提出可直接求解受限路网中两点之间最短路径的改进拍卖算法.将价格矢量扩展至二维,解决了价值量被不同转向行为共用的问题.设计了节省存储空间的数据存储结构,可准确描述交叉口转向行为,且便于检索.针对不同规模和密度的随机路网,比较了改进算法和Dijkstra算法求解单一起、终点之间的最短路径问题.结果表明,在含5 000个结点、20 000条路段的高密度路网中,改进拍卖算法的搜索时间约为Dijkstra算法的30%,能准确求解受限路网中的最短路径,并保留了原Auction算法可并行计算的基本性质.     

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

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

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

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

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

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

转向约束网络中的对偶最短路径树原理及其原型算法

为比较有无转向约束条件下最短路径特征及其搜索算法的异同点,基于对偶图理论证明了转向约束网络中从单个源点到所有弧的最短路径集构成其对偶网络的生成树,提出了对偶最短路径树(DSPT)概念,并利用其分析算法之间的关系。研究结果表明:转向约束下的现有求解方法包括弧标号算法、节点标号算法和对偶网络法都可以统一到DSPT算法框架内,而且与无转向约束的最短路径树(SPT)算法在路径搜索策略上是相同的;对于转向约束网络中的最短路径问题可建立一个DSPT原型算法,结合各种SPT标号技术能设计出更多的有效算法。     

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

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

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

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

基于转向的Logit交通分配算法

为避免交通分配中传统的网络扩展法在处理转向延误时的缺陷,通过分析网络基本要素节点、路段和转向之间的拓扑关系,借鉴Dial算法的基本框架,设计了一个基于转向的Logit交通分配算法。该算法以源点至路段的含转向延误的最短路径长度为依据处理各条路段,正向计算转向权重,反向分配路段流量和转向流量。算法计算结果与Logit路径流量和Dial算法数据相一致,该算法可直接求解既满足Logit路径选择概率又考虑转向延误对交通分配影响的路段流量和转向流量模式,而且Dial算法是其在转向延误为零时的一个特例。     

用于结构可靠指标计算的随机梯度算法

提出了一种基于几何原理求解结构可靠指标的高效实用算法,即随机梯度算法.该算法根据随机搜索方向的梯度反馈信息,采取有效的优化策略对随机搜索方向加以调整,缩短搜索路径,使目标的搜索方向更为准确,搜索效率更高.编制了相应程序对该算法的计算过程进行跟踪演示,以便直观形象地了解程序执行运作情况和算法性能,便于进行参数分析.经3个工程算例验证,该算法适用于结构可靠指标计算,计算精度令人满意.     

公路旅客最少换乘次数乘车方案选择算法

对公路旅客最少换乘次数乘车方案选择算法进行了研究,建立了描述公路客运换乘网络的有向无权图模型,将两站之间最少换乘次数乘车方案选择问题,转换为在权图中搜索两顶点间的最短路径问题,同时给出求解换乘网络中单一最短路径的基本广度优先搜索算法和求解全部最短路径的改进广度优先搜索算法,并通过算例验证算法的正确性.最后对算法的执行效率进行了分析.     

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

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

最短路拍卖算法在交通流分配中的应用

拍卖算法是由Bertsekas教授提出的一种求解有向网络图最短路径的新算法,并已经发展成为求解线性网络流问题的综合算法.本文首先介绍了拍卖算法,分析了其特点,并将其与常用的标号设定算法和标号修正算法进行了对比.深入分析了交通路网的特点和交通分配中最短路求解的特性.研究结果表明,最短路拍卖算法特别适合于并行计算和大规模稀疏网络的求解,符合现实路网的特点和交通分配的要求.最短路拍卖算法应用于交通分配能避免大量不必要的计算,大大节省计算时间,在交通领域具有广阔的应用前景.     

城际公共交通系统最短路算法

在借鉴城市公共交通最短路算法的基础上,针对城际网络的特点,研究了城际交通换乘路径的选择问题。以最小换乘次数为首要目标,并以此为基础,综合考虑时间、票价等因素,获取城际交通系统最短路。首先提出一种基于Flord算法的最小换乘矩阵及多条最短路的获取方法,然后利用最小换乘路径进行站线搜索与广义费用计算,获取城际交通的最短路,最后通过算例证明了本算法的可行性。     

�������������ͻ����ɢ�����Ż�ģ��

针对疏散过程中交叉口易造成延误的问题,构建了基于消除交叉冲突的疏散网络优化双层模型,上层以总疏散时间最短为目标,对各车道转向进行最优设置,下层基于随机用户平衡原理进行路径选择,并运用遗传算法与逐次平均算法结合对该模型进行求解,最终实现疏散交通组织与路径规划的集成优化.本文基于简单实验对模型的收敛性与有效性进行校验,实验表明,运用本文所提出的模型能够有效求解消除交叉冲突下的疏散网络优化问题,且算法的收敛速度较快;基于实际案例证明,本文提出的疏散网络优化模型能通过对交叉口处部分转向的禁行,消除交叉冲突,避免其余转向交通流的中断,从而提高疏散效率.     

多目标最短路径模型及算法

为获得满足决策者需要的多目标最短路径问题的有效路径,建立了多目标最短路径模型,并提出了综合k-最短路径算法和多目标格序决策方法的多项式算法.该算法根据决策者可以接受的各单目标的上限,用k-最短路径算法,分别确定各单目标的可行路径集及其交集.再用多目标格序决策方法,比较交集中的有效路径,最终获得决策者满意的路径.     

基于半监督哈希算法的交叉口交通状态识别

准确辨识交叉口交通状态是实施有效交通控制策略的前提. 传统交通状态识别方法是利用占有率、排队等统计数据设计指标实现状态识别，存在只能从单一角度刻画交叉口交通需求的问题. 对此，提出基于半监督哈希算法的交叉口交通状态识别方法. 从原始数据丰富特征入手，构建交叉口有效检测区域的图像化模型；将交叉口交通状态识别转化为图像搜索问题，利用监督哈希算法实现基于部分标签信息的图像搜索，进而得到交叉口的交通状态；最后，利用仿真对该方法进行了验证. 结果表明，所提方法在识别精度和速度上具有可行性和有效性.     

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

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

基于改进HH算法的路径规划系统设计与实现

HH (Highway-Hierarchical)算法是近年来一种高效路径规划算法,但存在的路网压缩成环问题、预处理数据存储问题和完整最短路计算问题,采用无环压缩策略、分层存储策略和局部最短路存储策略对算法进行了改进.以改进的算法为核心,在Internet环境下,运用WCF分布式技术,设计与实现了高效路径规划系统.系统测试结果表明,改进HH算法在时间效率上平均是原算法的5.03倍,在空间效率上约是原算法的4倍.在性能上,路径规划系统能满足互联网环境下用户并发访问的高效性需求;在功能上,系统提供了最短路的里程、行程时间、行程费用、主要路段及文字描述等.