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

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

基于最短路径关键转向的交叉口应急交通管制优化

针对"点"对"点"式的救援交通组织问题,研究交叉口应急交通管制的优化方法.将事故点至救护点之间的时间最短路径作为规划救援路径,通过识别最短路径关键转向,并以保障关键转向畅通为主要出发点,对相关交叉口实行交通管制.为寻找救援路径上的关键转向,将道路网抽象为方向性点权网络,给出该类网络中最短路径关键转向的定义,并对Dijkstra算法进行改进,给出在该类网络中寻找最短路径及关键转向的有效算法.最后以一个实例说明了方法的应用.     

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

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

考虑回路因素的电动汽车最短路问题研究

电动汽车保有量迅速增长,但仍存在里程焦虑、充电设施缺乏等问题,导致驾驶员有时必须绕路才能给电动汽车充电. 基于电动汽车在长途出行过程中绕路充电产生的回路现象,对电动汽车最短路径问题进行深入探索. 对路网进行重构,考虑驾驶员在不同充电速度和排队情况下的充电站选择行为,构造寻求电动汽车最短路径的混合整数规划模型,使用成熟的商业规划软件求解. 为提高大型路网下的模型求解速度,基于动态规划的思想提出一种改进的标签设置算法,高效求解路网中存在回路时的电动汽车最短路径问题. 通过算例验证所提模型和算法的合理性及高效性.     

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

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

基于辅助图最短路算法的程序设计及应用

将现状路网转化成可以利用最短路算法求解最小割的路网模式,应用Matlab软件,选取Dijkstra算法对最短路径部分进行计算机编程,并给出实证分析。     

基于标号算法搜索过程的K最短路算法设计

K最短路径问题是最短路径问题中的一个重要分支,它在物流调度、交通流分配、交通网络的路径选择中起着重要的作用.为了提高K最短路的计算效率以及实用性,充分利用传统标号算法搜索过程获得的众多节点临时标号信息,设计了基于搜索过程的Dijkstra标号算法.该算法在搜索过程中得到一条最短路径的同时,获得了大量的临时标号信息;在此基础上,继续采用该算法利用这些临时标号信息进行标号,可以获得其他严密K最短路;将该算法与交叉口有延误的最短路径算法相结合,可方便的计算城市交通网络中交叉口有延误的K最短路径问题;该算法简化了K最短路的计算过程,提高了算法的计算效率.最后,利用一个简单网络介绍了该算法的计算过程.     

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

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

���·�����㷨�ڽ�ͨ�����е�Ӧ��

拍卖算法是由Bertsekas教授提出的一种求解有向网络图最短路径的新算法，已经发展成为求解线性网络流问题的综合算法。应用分析对比法进行研究．介绍了拍卖算法，分析了其特点，与常用的标号设定算法和标号修正算法进行了对比。最短路拍卖算法特别适合于并行计算和大规模稀疏网络的求解，符合现实路网的特点和交通分配的要求，并且便于程序化．通过各种途径对基本算法进行改进、加速，可使计算速度提高数倍。拍卖算法可以快速求出多个起点和一个终点以及一个起点和多个终点的情况，适应不同分配算法的需求。在交通分配中，只要根据需求选择不同的起点集和终点集即可，不必求得所有节点对之间的最短路，避免大量不必要的计算，大大节省计算时间，在交通领域具有广阔的应用前景。     

随机时变路网环境下稳健路径选择及实证研究

交通拥挤、天气、突发事故等不确定性因素影响着城市区域之间的路网提供的 连通服务水平.本文对城市片区间道路连通路径选择进行研究.根据随机时变网络描述和 稳健路径选取原则,建立了最优化模型,并采用改进的Dijkstra 算法.通过深圳实例计算, 分析了出发时刻与最短路径行程时间和路段构成之间关系,并与确定性时变路网环境下 进行计算结果对比.结果表明,随机时变路网环境下鲁棒性最优算法选择稳健路径具有合 理性和可行性,可以很好地应用到区域动态连通情况的研究.     

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

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

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

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

基于Maklink 图和遗传算法的改航 路径规划方法研究

为了保障恶劣天气下的飞行安全,航班需要采取改航策略避开危险区.采用已 有的以改航路径最短为目标,以航段最小距离、避开危险区、转弯角度等为约束条件的规 划模型,设计了3 阶段方法研究改航路径规划.首先应用Maklink 图和Dijkstra 算法规划一 条能够避开危险区的路径,接着应用遗传算法优化路径,最后进行路径调整以满足约束 条件.算例仿真结果显示,应用本文方法得到的改航路径长度较短,转弯次数少、转弯角度 小,计算效率高.仿真结果说明,应用本文提出的方法获得的改航路径满足目标和约束要 求,验证了该方法的可行性和有效性.     

双环网络DL（N,h）（h｜N）的最短路径算法

对双环网络DL（N,h)（满足最大公因数g(N,h)=h)进行了分析,证明了这类双环网络中最短路径形式唯一且可用简单的数学表达来描述,给出了最短路径的公式,在此基础上,给出了一个求最短路径的简便算法,讨论了该类网络的直径等有关问题,证明了两点间的平均距离等于直径的一半。     

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

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

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

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

地表模型上的最短路径算法研究

提出了一种基于空间三角网格的地表模型上的最短路径算法。该算法利用离散点的空间信息计算得到起点So到周围邻接点的最短距离，然后用逐步向外层边界扩展的方法扩大起点的邻接点范围，直到起点的邻接点中包含终点to。此过程可求得So到to的最短路径上的关键点，然后求取无原始边连接的2个关键点之间的精确路径点。     

模糊随机最短路径问题模型与算法

最短路径问题在现实生活中有着广泛应用,许多专家学者对此问题进行了深入研究.到目前为止,所有这些研究都是针对静态最短路径问题以及不确定最短路径问题中具有模糊或随机参数的问题.然而在现实世界中,有些系统中有很多不确定因素,因此很有必要对具有多重不确定参数的最短路径问题进行研究.本文主要研究具有模糊随机参数的最短路径问题,基于机会测度理论,分别建立了模糊随机期望值模型、机会约束规划模型及相关机会约束规划模型,然后设计遗传算法求解.     

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

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

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

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