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

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

基于改进行程时间估计模型的最优路径选择

为解决交通网络最优路径问题，提出改进的行程时间估计模型，并设计基于该模型的最优路径算法。行程时间估计模型在分段截断二次速度轨迹模型的基础上进行改进，用路段节点的到达速度代替同一出发时刻下测得的速度，通过构造在时间和空间上连续的速度轨迹来估计行程时间。首先，基于Yen′s KSP算法以路段距离为阻抗求解K条最短路径；其次，分别用改进的行程时间估计模型估计K条最短路径的行程时间；最后，以行程时间为成本选择最优的路径。通过Sioux Falls网络的数值试验验证模型和算法的有效性和优越性。试验结果表明：改进的分段截断二次速度轨迹模型相比于原始模型精度平均提高了65%；算法的最优路径结果能减少路径经过的交叉口数和缩短最优路径的总长度，而且最优路径的行程时间估计结果 与真实值的MAPE保持在3%内。     

基于改进Dijkstra算法的水平循环类立体车库存取车辆路径优化模型

为缩短水平循环类立体车库车辆存取运行时间和用户平均等待时间,设计了一种改进Dijkstra算法的存取车辆运行路径优化模型。基于水平循环类立体车库存取车辆工作逻辑,在构建存取车辆路径运行时间模型的基础上,建立了立体车库的排队模型;以车辆平均排队队长和车辆排队等候时间为评价指标,在搜索方向、搜索范围及动态节点变化方面引入双向扇形动态Dijkstra算法进行优化。研究结果表明：相比于传统Dijkstra算法,改进Dijkstra算法提升了目标节点的搜索效率,且能弥补其缺乏动态搜索能力的缺陷,输出源节点与目标节点之间的最短路径,有效缩短存取车辆运行时间和用户平均等待时间,提升水平循环类立体车库服务效率。     

基于改进Dijkstra算法的高速公路 应急疏散路径规划

为解决采用传统Dijkstra 算法在高速公路应急疏散规划路径中存在可用性差的缺陷,考虑 高速公路路网中有通行容量及条件限制的节点和路段特征,对其进行改进,提出容量限制节点的 表征方式及流量计算方法,并根据待疏散车辆特征对具有限高、限重属性的路段进行筛选,提出 分类路径规划方法。最后,以河南省高速公路局部路网疏散路径规划问题为基础设计算例,分别 采用传统算法和改进Dijkstra 算法对高速公路应急疏散路径进行求解。结果显示,传统算法得到 的路径规划及交通量分配结果中,容量限制节点上游路段的分配交通量高于节点容量,在节点处 形成疏散瓶颈,且对于规划路径中有限重条件的路段,案例中超重车辆无法使用该路段疏散;相 比而言,由改进算法得到的路径规划及交通量分配结果则不存在上述问题,从而使得疏散效率和 疏散路径的可用性得到了保证。     

���ڽ�ͨԼ���ĸ�Ч·���滮�㷨

分析了路径规划问题及其在交通约束条件下的特点。从算法改进和模型改进两方面对路径规划算法进行了研究,在详细分析Dijkstra算法步骤和对偶法的基础上,给出了交通约束的数学模型及道路网络的相关定理。基于传统Dijkstra算法,对搜索过程中的节点和边的标记方式和规则进行了改进,提出了一种在交通约束条件下的高效路径规划算法。该算法通过减少搜索节点和标记边的次数而减少搜索过程中的运算量。仿真结果表明,该算法对偶法1/3～1/4的运算量。     

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

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

基于MapBasic的战时运输最优路径问题研究

战时运输最优路径问题是一个多目标多约束随机动态路网寻优问题。在分析战时运输最优路径问题特性前提下,着重研究战时运输路阻函数模型,求出时间阻抗、风险阻抗和费用阻抗,标定阻抗参数μ1,μ2和μ3,及确定函数模型的MapBasic表达,在给出最优路径模型基础上,利用改进的Dijkstra算法求解。实例验证表明研究成果满足实用要求。     

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

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

容量限制与运输模式联合选择的综合客运枢纽布局模型(英文)

分析了传统的综合客运枢纽布局优化模型,同时增加运输模式与中转能力的约束条件,提出了改进后的综合客运枢纽布局优化模型,并设计了改进的遗传算法对其求解。应用LINGO软件进行有效性检验,分别计算了8节点与50节点Solomon标准测试数据,并将改进模型与经典算法进行比较。计算结果表明:当应用LINGO软件计算8节点Solomon标准测试数据时,平均运算时间为5 043s,最优成本为1 952 418元,应用遗传算法与MATLAB软件计算的平均运算时间为62s,最优成本为1 955 900元;当应用遗传算法与MATLAB软件计算50节点Solomon标准测试数据时,平均运算时间为574s,最优成本为8 500 600元;当计算25节点的AP数据且枢纽节点数量为3时,平均运算时间为612s,最优成本为155 148元,比经典算法降低了108元。可见,改进模型有效。     

考虑速度与拥堵的多式联运路径优化研究

对多式联运路径优化进行了研究.对于多个城市节点,扩展并建立不规则棱柱模型网络,不仅考虑不同运输方式的成本与时间,还将不同运输方式对应的速度与拥堵纳入模型.基于Dijkstra最短路径算法,创建一个包含速度与拥堵因素多式联运路径优化模型仿真系统,通过模拟动态参数,分析了该组参数下的速度与拥堵对多式联运最优路径选择的影响,为区域运输规划提供了重要的参考价值.     

Dijkstra改进算法在停车场内部路径引导中的应用

针对大型停车场泊位引导效率低以及管理系统不完善等问题进行分析,对停车场内的路网特征进行研究。从用户角度分析其对最优泊位选择的影响因素,以寻找最优泊位为目的,提出一种Dijkstra改进算法,并在MAT‐LAB环境下进行仿真。改进的Dijkstra算法要比传统Dijkstra算法的计算效率提高65％,为用户进入大型停车场提供向导服务,帮助其尽快找到合适泊位,进而对提高停车场管理系统的智能化程度以及停车效率作出贡献。     

基于多Agent的机场场面最优滑行路径算法

为了保障机场安全,提高机场运行效率,建立了依据进出港航班滑行时间最短为决策的多Agent模型,模型以多Agent技术为基础,融合了Dijkstra算法的最优路径选择和合同网协议的思想,形成了基于多Agent的滑行路径优化算法,并依据该算法进行了仿真分析.仿真结果表明:与指定航班优先级相比,使用基于多Agent的优化算法处理同优先级航班,总运行时间可减少15 s;基于多Agent的场面运行调整算法可以有效地把航班和机场上分布的滑行道、跑道、停机位等资源组织起来,智能地发现冲突、躲避冲突,达到全局滑行时间最短,因此,该算法可行.     

基于出行决策的公路网多目标最优路径算法

为使公路网静态最优出行路径能综合表达道路环境影响因素与出行者的路径选择偏好,研究了GIS环境下的用户-系统最优出行路径决策模式.基于层次分析法,构建了综合考虑行程时间、舒适安全性与行程费用的公路网路段交通阻抗评价指标体系,提出了对定性与定量化参评指标进行综合一致性处理的方法.通过用户-系统共同决定的路段交通阻抗的综合评价过程,将最优路径问题转化为最短路径问题,采用各路段各出行目标的标准化值之和作为评价指标,采用Dijkstra算法实现最优路径的搜索.实例验证结果表明:最优路径比距离最短路径出行距离增加8%,出行时间减少7%,舒适安全性提高17%,出行费用增加13%,所得最优路径是针对特定用户的多目标路径,明显异于单目标最短路径,表明该方法可行.     

Research on the Best Routing Algorithm of Terminal Distribution Based on the Random Factor of Road Hustling Degree

Dijkstra algorithm is a basic algorithm to analyze the vehicle routing problem (VRP) in the terminal distribution of logistics center. According to the actual client demands of service speed and quality, the conceptions of economical distance of delivery and the best routing algorithm were given on the base of the Dijkstra algorithm with consideration of a coefficient of the road hustle degree. Economical distance of delivery is the shortest physical distance between two customers. It is the value of goods delivery in shortest distance when concerning factors such as the road length, the hustle degree, the driveway quantity, and the type of the road. The improved algorithm is being used in the development and application of a distribution path information system in the terminal distribution of logistics center. The simulation and practical case prove that the algorithm is effective and reasonable.     

基于网络图论的中小城市公交线网规划

针对中小城市公共交通的特点,在传统最短路径直达客流量最大的规划方法基础上。采用改进Dijkstra算法对线网进行规划,对于提高直达乘客运送量、减少乘客换乘比例、提高公交企业效益发挥很大作用。     

基于乘客路径选择的多制式轨道交通客流分配

为量化换乘对乘客出行路径选择的影响程度,在单层网络中添加虚拟换乘站,构建无隐性连接的三层多制式轨道交通拓扑网络模型.基于时间、换乘节点衔接性,计算线网间衔接性系数;利用Dijkstra法搜索模型各起讫点间的K短路径,以乘客感受到的线网复杂度及乘客出行计划确定时间,建立乘客对线网的熟悉度函数;根据乘客路径选择影响因素构建...     

基于交叉口函数的城镇指路标志设置模型

结合路网的拓扑结构,定义了用于确定指路标志的状态函数集,给出了3个描述路网拓扑特征的交叉口函数:邻近结点集、结点-弧段夹角集和连通结点集,基于Dijkstra最短路径的思想,运用交叉口函数建立了城镇指路标志的标识模型:以待标识城镇为中心,在城镇的影响区域内,通过向外搜索交叉口邻近结点集来确定指路标志的设置,并使每个结点上标识的路径都是最优的。实例分析表明,该模型生成的指路标志,能有效地指引道路使用者前往目的地。     

Optimal Genetic View Selection Algorithm for Data Warehouse

To efficiently solve the materialized view selection problem, an optimal genetic algorithm of how to select a set of views to be materialized is proposed so as to achieve both good query performance and low view maintenance cost under a storage space constraint. First, a pre-processing algorithm based on the maximum benefit per unit space is used to generate initial solutions. Then, the initial solutions are improved by the genetic algorithm having the mixture of optimal strategies. Furthermore, the generated infeasible solutions during the evolution process are repaired by loss function. The experimental results show that the proposed algorithm outperforms the heuristic algorithm and canonical genetic algorithm in finding optimal solutions.     

客运班轮动态船队规划数学模型及其求解方法研究

通过对定期客运班轮运输特点分析,构建出能全面反映运量增加显著和运量增加缓慢情况下的运力更新、运力闲置、运力购置的多目标动态船队规划数学模型,模型根据绿色的定义给出了技术、经济、环保性目标函数.其数学模型具有大规模、离散和整数的特点,计算速度随着船舶数量和船型的增加以指数形式递增,造成"维数灾"难题.采用混沌初始化、维更新、非支配档案更新及基因交换对多目标离散粒子群优化算法进行改进使其适用于大规模动态船队规划,最后通过实例验证该方法的可行性并得到了相应的船队规划结论.