基于改进的Dijkstra算法的动态最短路计算方法 被引量：46

1

作者 刘建美 马寿峰 马帅奇 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2011年第6期1153-1157,共5页

首先将所研究的时间段进行时段划分,然后基于每个路段在每个时段内的历史平均速度给出了改进的Dijkstra算法,它可以给出任意时刻从任意节点位置出发到达任一目的地的行程时间最短的路径及其相应的行程时间;其次在允许超车行为存在的条... 首先将所研究的时间段进行时段划分,然后基于每个路段在每个时段内的历史平均速度给出了改进的Dijkstra算法,它可以给出任意时刻从任意节点位置出发到达任一目的地的行程时间最短的路径及其相应的行程时间;其次在允许超车行为存在的条件下将出行者进行分类,并给出了相应的最短路算法.论文最后给出了相应的算例验证了算法的可行性. 展开更多

关键词 最短路 改进的dijkstra算法 速度 超车

原文传递

变电站智能巡检机器人全局路径规划设计 被引量：21

2

作者 陈瑶 陈阿莲 +1 位作者 李向东 陈伟 《山东科学》 CAS 2015年第1期114-119,共6页

针对国内变电站智能巡检机器人行走路线的特点,建立半结构化的道路模型。提出将改进的Dijkstra算法与模拟退火算法相结合,应用到变电站智能巡检机器人的全局路径规划中,在数据库技术的基础上采用VC++对上述算法进行软件设计与实现,构建... 针对国内变电站智能巡检机器人行走路线的特点,建立半结构化的道路模型。提出将改进的Dijkstra算法与模拟退火算法相结合,应用到变电站智能巡检机器人的全局路径规划中,在数据库技术的基础上采用VC++对上述算法进行软件设计与实现,构建具有全局路径规划功能的电子地图系统。该系统已在变电站的智能巡检机器人系统平台下进行实验并投入使用,现场运行结果证明该方法高效可行。 展开更多

关键词 半结构化 改进的dijkstra算法 模拟退火算法 路径规划

下载PDF 职称材料

基于城市配电网的无线自组传感器网络结构研究 被引量：10

3

作者 戴莹 王建平 张崇巍 《电子测量与仪器学报》 CSCD 2012年第10期864-869,共6页

数据通信是变配电自动化系统不可或缺的重要组成部分。在10kV以下的电力系统中,对电网数据的采集、处理、显示和控制尚无统一的通信组网模式。运用图论的方法分析城市配电网架构模式,提出一种基于改进的Dijkstra最短路径算法的无线自组... 数据通信是变配电自动化系统不可或缺的重要组成部分。在10kV以下的电力系统中,对电网数据的采集、处理、显示和控制尚无统一的通信组网模式。运用图论的方法分析城市配电网架构模式,提出一种基于改进的Dijkstra最短路径算法的无线自组传感器网络路由算法,在仿真结果的理论依据上实现了无线传感器节点的合理部署,使得无线自组传感器网络通信模式和拓扑结构的数据传输效率最高,并成功应用于黄山市配电网的监测中。 展开更多

关键词 无线自组传感器网络 城市配电网 图论 改进的dijkstra算法

下载PDF 职称材料

基于改进Dijkstra算法的配用电通信网流量调度策略 被引量：9

4

作者 向敏 陈诚 《计算机应用》 CSCD 北大核心 2018年第6期1715-1720,共6页

针对配用电通信网中数据汇聚易产生拥塞的问题,提出了一种复合边权值流量调度路由算法。首先,依据跳数建立节点分层模型;然后,划分配用电业务优先级和节点拥塞等级;最后,以跳数、流量负载率和链路利用率为综合指标计算边权值,对需要流... 针对配用电通信网中数据汇聚易产生拥塞的问题,提出了一种复合边权值流量调度路由算法。首先,依据跳数建立节点分层模型;然后,划分配用电业务优先级和节点拥塞等级;最后,以跳数、流量负载率和链路利用率为综合指标计算边权值,对需要流量调度的节点根据改进的Dijkstra算法进行路由选择,同时对重度拥塞节点按照配用电业务优先级进行调度。与最短路径(SPF)算法和贪婪背压算法(GBRA)相比,在数据生成率为80 kb/s时,所提算法紧急型业务丢包率分别减少了81.3%和67.7%,关键型业务丢包率分别减少了79%和63.8%。仿真结果表明,所提算法能有效缓解网络拥塞,提高网络有效吞吐量,降低网络端到端时延和高优先级业务的丢包率。 展开更多

关键词 电力通信网 改进的dijkstra算法 流量调度 复合边权值 业务优先级

下载PDF 职称材料

基于遗传算法和改进的Dijkstra算法的电缆敷设优化研究 被引量：8

5

作者 李治 韩丹 +1 位作者 任兴龙 马晓燕 《数学的实践与认识》 北大核心 2016年第17期160-167,共8页

首先结合电缆敷设相关标准建立了基于多种条件限制的电缆敷设优化的多目标规划模型,将分层序列法的思想运用于模型的求解中.将总敷设路线最短作为第一目标,转弯数最少作为第二目标,错层数最少作为第三目标.求解时首先将遗传算法和改进的... 首先结合电缆敷设相关标准建立了基于多种条件限制的电缆敷设优化的多目标规划模型,将分层序列法的思想运用于模型的求解中.将总敷设路线最短作为第一目标,转弯数最少作为第二目标,错层数最少作为第三目标.求解时首先将遗传算法和改进的Dijkstra算法相结合,共同进行第一目标和第二目标的求解;对于第三目标错层数最少,在运用改进的Dijkstra算法得出待敷设路线后,设计了基于贪心准则的贪婪敷设算法来满足错层数最少的要求.最终通过MATLAB编程实现以上思想并分别对30条和100条电缆的敷设进行实例验证. 展开更多

关键词 遗传算法 分层序列法 电缆敷设 改进的dijkstra算法 多目标规划

原文传递

Dijkstra算法在矿井水灾动态避灾路径中的改进与应用 被引量：8

6

作者 周越 朱希安 王占刚 《煤炭工程》 北大核心 2019年第3期18-22,共5页

针对矿井水灾发生时,随时间动态变化的水位高度对矿工逃生路径选择的影响,开展动态最短路径算法在矿井水灾动态路径选择中的研究。为判断水位高度不断变化对矿工逃生路径选择的影响,本文在将逃生路径选择数学模型最优化的基础上,将所研... 针对矿井水灾发生时,随时间动态变化的水位高度对矿工逃生路径选择的影响,开展动态最短路径算法在矿井水灾动态路径选择中的研究。为判断水位高度不断变化对矿工逃生路径选择的影响,本文在将逃生路径选择数学模型最优化的基础上,将所研究的时间段进行划分,根据不同时段下每条巷道中的平均逃生速度求得时间当量长度,以此作为邻接矩阵的权值。本文突破传统Dijkstra算法在矿井水灾最优路径搜索中不能有效用于动态环境下的弊端,实现了改进的Dijkstra算法在矿井突水时期动态选择最优路径的应用,具有更高的实用价值与精确度。并且,在后期的矿井虚拟现实/增强现实水灾模拟应用中具有较大的意义。 展开更多

关键词 矿井水灾 动态路径选择 改进的dijkstra算法 优化模型 时间当量长度

下载PDF 职称材料

基于轨迹数据的出租车司机寻客路径优化方法

7

作者 周旦 孙家煜 +2 位作者 顾国斌 钟楚捷 王涛 《重庆交通大学学报（自然科学版）》 CAS CSCD 北大核心 2024年第1期83-90,共8页

出租车寻客路径规划是降低出租车空载率的重要手段。为高效解决出租车寻客路径规划问题,综合考虑载客概率、空载行驶时间和区域供需比3个指标,提出一种出租车寻客路径优化方法。在此基础上,基于改进的DBSCAN聚类算法和灰色综合评价法挖... 出租车寻客路径规划是降低出租车空载率的重要手段。为高效解决出租车寻客路径规划问题,综合考虑载客概率、空载行驶时间和区域供需比3个指标,提出一种出租车寻客路径优化方法。在此基础上,基于改进的DBSCAN聚类算法和灰色综合评价法挖掘滴滴快/专车载客热点区域并确定寻客目标点,通过引进标号永久化新规则和双向搜索改进的Dijkstra算法获取出租车寻客路径。最后,使用成都市核心城区的滴滴订单数据对算法进行实例验证。结果表明:改进的Dijkstra算法较Best-first、Foyld等算法相比具有更快的最短路径搜索速度;同时,通过该方法获取的寻客路径与常见寻客路径相比,寻客距离减少约21.33%,寻客时间减少约22.16%。该方法能有效指导出租车司机选取较优的寻客路径,为出租车调度和城市交通建设提供有效指导。 展开更多

关键词 交通工程 DBSCAN聚类 灰色综合评价 改进的dijkstra算法 轨迹数据

下载PDF 职称材料

面向随机因素的多式联运动态路径优化 被引量：6

8

作者 陈丹丹 洪卫 贾禹 《重庆交通大学学报（自然科学版）》 CAS 北大核心 2015年第2期112-117,共6页

针对随机因素影响下多式联运所表现的动态性和随机性,在引入惩罚因子控制运输质量的基础上,以总费用最小化为目标,建立了具有软时间窗约束的动态路径优化模型;运用基于Dijkstra算法的改进路径优化算法求解模型;设计了一个基于铁路、公... 针对随机因素影响下多式联运所表现的动态性和随机性,在引入惩罚因子控制运输质量的基础上,以总费用最小化为目标,建立了具有软时间窗约束的动态路径优化模型;运用基于Dijkstra算法的改进路径优化算法求解模型;设计了一个基于铁路、公路、航空及水运等4种运输方式的多式联运问题的算例,验证了模型的实用性和有效性。 展开更多

关键词 交通运输工程 多式联运 随机因素 动态路径优化 改进的dijkstra算法

下载PDF 职称材料

基于权值时变模型的矿井突水最优逃生路径的动态选择 被引量：4

9

作者 于丹 颜伟 李劭昱 《科学技术与工程》 北大核心 2022年第12期4762-4771,共10页

为了减少矿井突水发生时造成的矿工伤亡,为井下矿工动态选择出合理的逃生路径。综合考虑随时间变化的水位高度和水的流速对矿工逃生路径选择的影响,将其量化为对人体稳定性的影响,并将所研究的时间进行分段,根据不同时段下巷道内平均水... 为了减少矿井突水发生时造成的矿工伤亡,为井下矿工动态选择出合理的逃生路径。综合考虑随时间变化的水位高度和水的流速对矿工逃生路径选择的影响,将其量化为对人体稳定性的影响,并将所研究的时间进行分段,根据不同时段下巷道内平均水流速与临界流速之比求得动态危险系数,并实时加权到邻接矩阵上,建立以巷道初始当量长度与危险性程度为衡量最优路径的权值时变数学模型,运用改进的Dijkstra算法进行求解,并结合W煤矿矿井进行实例分析。结果表明:优化后的模型更能反映突水时巷道内的实际情景,同时,改进的Dijkstra算法能够有效应用于突水时期最优逃生路径的动态选择中,使选择的逃生路径更加安全可靠。 展开更多

关键词 矿井突水 危险系数 时变网络 改进的dijkstra算法 最优逃生路径

下载PDF 职称材料

基于策略的矿井水灾避灾路径动态规划 被引量：1

10

作者 马旭伟 徐华龙 《矿冶》 CAS 2023年第4期12-18,共7页

为了解决现有静态路径规划方法无法满足煤矿井下突水灾害动态变化需求,以及传统最短路径算法运行效率有待提升等问题,提出一种基于策略的矿井水灾避灾路径动态规划方法及系统。该方法考虑水流对人员逃生的影响,首先将巷道环境影响因子... 为了解决现有静态路径规划方法无法满足煤矿井下突水灾害动态变化需求,以及传统最短路径算法运行效率有待提升等问题,提出一种基于策略的矿井水灾避灾路径动态规划方法及系统。该方法考虑水流对人员逃生的影响,首先将巷道环境影响因子对避灾路径的影响程度量化为巷道距离当量长度;然后以时间最短为原则,引入人员逃生速度,计算逃生通过每条巷道的时间,构建以逃生时间为邻接矩阵的数学模型;并结合安全监控、水文监测系统联动策略,根据实时监测的井下环境情况,动态修改巷道节点属性,开发基于三维GIS一张图的矿井水灾避灾路径三维动态规划系统。最后,结合矿井实例进行测试分析,验证了算法设计的有效性,可以指导井下人员安全撤离,提高煤矿安全管控能力。 展开更多

关键词 矿井突水 最优避灾路径 改进的dijkstra算法 联动系统 应急救援系统

下载PDF 职称材料

复杂地形条件下供水管线点对间线程的离散优化方法 被引量：4

11

作者 晋良海 胡瑶 +1 位作者 朱忠荣 蔡汝香 《水电能源科学》 北大核心 2015年第2期108-110,共3页

针对山区等复杂地表不能用数学函数表达导致管网长度优化工作中点对间最短线程无法采用解析法求解的问题,通过计算点间距离,建立Delaunay三角网离散化地面模型,构建赋权的无向网络图,并采用提高计算效率的改进Dijkstra优化算法计算点对... 针对山区等复杂地表不能用数学函数表达导致管网长度优化工作中点对间最短线程无法采用解析法求解的问题,通过计算点间距离,建立Delaunay三角网离散化地面模型,构建赋权的无向网络图,并采用提高计算效率的改进Dijkstra优化算法计算点对间最短线程,使得管线布置在满足工程条件下线程最短,以降低工程成本,为山区管网优化布置提供依据。金蟾水库纳雍供水管网部分总干线的计算表明,该方法能有效缩短管线线程,具有较强的工程可行性和推广价值。 展开更多

关键词 供水管网 离散化 Delaunay三角划分 最短线程 改进的dijkstra算法

下载PDF 职称材料

基于飞行区知识图谱的停机位分配研究与设计

12

作者 李一鸣 林珂仰 +2 位作者 蒋逸凡 李松林 都思琦 《电子技术与软件工程》 2023年第4期246-253,共8页

本文基于国内某大型机场运行实景,首先,建立了飞行区停机位知识图谱,可视化停机位知识;然后提出停机位-航班多约束模型,实现航班可用停机位的智能预分配,能够根据突发情况实时调整停机位的分配;最终,引入转弯点优化算法,改进Dijkstra算... 本文基于国内某大型机场运行实景,首先,建立了飞行区停机位知识图谱,可视化停机位知识;然后提出停机位-航班多约束模型,实现航班可用停机位的智能预分配,能够根据突发情况实时调整停机位的分配;最终,引入转弯点优化算法,改进Dijkstra算法实现最短滑行路径推荐的同时转弯最少,从而进一步缩短滑行时间。实验结果表明,本系统能够成功应用于机场的停机位分配具有实际的应用价值。 展开更多

关键词 知识图谱 最短滑行路径推荐 停机位-航班多约束模型 改进的dijkstra算法

下载PDF 职称材料

用路由矩阵搜索法实现智能公交系统的快速查询 被引量：2

13

作者 王防修 《武汉轻工大学学报》 2020年第1期57-61,共5页

给出了在网络环境下实现智能公交系统快速查询的方法。首先,设计了用Dijkstra算法实现从源站点到目的站点的最优乘车方案的查询。然后,通过对Dijkstra算法进行改进,在一定程度上提高了公交系统的查询速度。最后,设计了路由矩阵搜索法,... 给出了在网络环境下实现智能公交系统快速查询的方法。首先,设计了用Dijkstra算法实现从源站点到目的站点的最优乘车方案的查询。然后,通过对Dijkstra算法进行改进,在一定程度上提高了公交系统的查询速度。最后,设计了路由矩阵搜索法,通过它极大地提高公交系统的查询速度。算法分析表明,路由矩阵搜索法的时间复杂度小于Dijkstra算法。系统测试表明,在进行同一乘车路线的查询时,路由矩阵搜索法比Dijkstra算法及其改进算法所花的时间要少得多。与Dijkstra算法及其改进算法相比,路由矩阵搜索法能大大提高智能公交系统的查询速度。 展开更多

关键词 dijkstra算法 改进的dijkstra算法 路由矩阵搜索法

下载PDF 职称材料

基于车牌数据和LSTM的动态交通分配研究 被引量：1

14

作者 张南 谢薇 《综合运输》 2022年第8期92-99,共8页

动态交通分配是交通控制与诱导的重要理论基础,传统的数学解析模型和交通仿真模型存在求解困难和参数标定繁琐等问题,在大规模实例路网上应用具有一定局限性。车牌数据具有样本量大、覆盖面广、精度高等优势,本文选取15min作为统计时间... 动态交通分配是交通控制与诱导的重要理论基础,传统的数学解析模型和交通仿真模型存在求解困难和参数标定繁琐等问题,在大规模实例路网上应用具有一定局限性。车牌数据具有样本量大、覆盖面广、精度高等优势,本文选取15min作为统计时间间隔从车牌数据中获取动态OD和路段转弯流量,在确定OD矩阵在路网的最大影响时段数后,作为LSTM的输入输出数据建立动态交通分配模型。以某市核心区域为例,选取历史数据构造训练集,并用测试集评估训练好的模型。结果表明模型分配速度较快,分配结果与实际路段流量相比,不论是同时段还是同路段,分配值和观测值的拟合度均较高,且整体误差较小,说明了模型的可行性和有效性。 展开更多

关键词 城市交通 动态交通分配 长短时记忆网络 车牌数据 改进的dijkstra算法

原文传递

城市交通系统最优路径算法研究 被引量：2

15

作者 孙静霞 谭德荣 《自动化信息》 2010年第9期52-53,79,共3页

针对目前交通拥挤现象提出了城市交通诱导系统，最短路径寻求是其主要问题之一。通过对最短路径实现算法的分析和研究，本文对传统的Dijk—stra算法和启发式搜索算法As算法进行了详细的探讨。基于GIS特性对最短路径算法进行优化，改进了... 针对目前交通拥挤现象提出了城市交通诱导系统，最短路径寻求是其主要问题之一。通过对最短路径实现算法的分析和研究，本文对传统的Dijk—stra算法和启发式搜索算法As算法进行了详细的探讨。基于GIS特性对最短路径算法进行优化，改进了Dijkstra算法。 展开更多

关键词 静态路网 最短路径 改进的dijkstra算法

下载PDF 职称材料

Dijkstra算法在园区消防车最优路径中的应用

16

作者 张滔 李德堂 郑开举 《管理观察》 2016年第35期61-64,共4页

本文针对当前园区消防车辆到达受灾点的事故蔓延状况随到达时间的延长而加重的问题,研究并提出了改进的Dijkstra算法。并且通过对传统Dijkstra算法与改进的Dijkstra算法进行比较,得出改进的Dijkstra算法求得的最优路径使消防车到达的时... 本文针对当前园区消防车辆到达受灾点的事故蔓延状况随到达时间的延长而加重的问题,研究并提出了改进的Dijkstra算法。并且通过对传统Dijkstra算法与改进的Dijkstra算法进行比较,得出改进的Dijkstra算法求得的最优路径使消防车到达的时间更短。 展开更多

关键词 园区事故 dijkstra算法 改进的dijkstra算法

下载PDF 职称材料

奥运公交线路选择的数学模型 被引量：1

17

作者 张鸿艳 诸秉政 +1 位作者 徐晶 李文宇 《哈尔滨师范大学自然科学学报》 CAS 2008年第3期36-38,共3页

采用改进的Dijkstra算法和多目标规划方法,综合考虑时间、费用等因素建立了公交线路选择模型,解决了奥运期间观众出行面临多条线路选择的问题,使得公众的出行更加通畅、便利,最后对模型进行了综合评判,指出该模型具有一定的实用价值.

关键词 改进的dijkstra算法 多目标规划 线性加权法

下载PDF 职称材料

改进的Dijkstra算法在科技支前保障路线选择中的应用

18

作者 林俊 《情报探索》 2008年第10期67-68,共2页

针对科技支前保障演练方案中的最佳保障路线选择问题,提出了改进的Dijkstra算法,用C#语言设计相应程序验证了此算法。

关键词 科技支前 最佳保障路线 改进的dijkstra算法

下载PDF 职称材料

基于角改进的城市交通网络实时最短路径算法研究 被引量：8

19

作者 王洪德 张俊 《安全与环境学报》 CAS CSCD 北大核心 2009年第3期166-169,共4页

针对城市交通网络中车流量的实时、动态变化特性,分析现有算法在处理动态车辆路径问题时存在的缺陷。综合道路条件、天气状况、交通堵塞和人口密度分布状况,构建动态交通网络环境下的实时路径评估模型。提出基于±90°角(源点... 针对城市交通网络中车流量的实时、动态变化特性,分析现有算法在处理动态车辆路径问题时存在的缺陷。综合道路条件、天气状况、交通堵塞和人口密度分布状况,构建动态交通网络环境下的实时路径评估模型。提出基于±90°角(源点与汇点连线的夹角)范围改进的Dijkstra最短路径算法,并给出具休实现过程。实例研究表明,基于角改进的Dijkstra算法无需遍历交通网络中所有路径,根据实时更新的交通状况和气象信息即可得到最短通行路径,提高了对交通网络中随机事件和突发事件的实时诗处理能力。 展开更多

关键词 交通运输安全工程 城市交通网络 最短路径 角改进的dijkstra算法

下载PDF 职称材料

多因素影响下的无人驾驶汽车最短路径规划

20

作者 曾爽 《区域治理》 2020年第45期265-266,共2页

本文首先构建了路段属性的层次结构模型,通过专家打分计算出影响无人驾驶汽车路径规划因素的权重。研究发现,路段通行时间和路段平均行驶速度对路径选择的影响占比为55.4%。在此基础上,构建了道路综合权重模型,将模型计算结果作为Dijks... 本文首先构建了路段属性的层次结构模型,通过专家打分计算出影响无人驾驶汽车路径规划因素的权重。研究发现,路段通行时间和路段平均行驶速度对路径选择的影响占比为55.4%。在此基础上,构建了道路综合权重模型,将模型计算结果作为Dijkstra算法搜寻最短路径的依据。通过研究发现改进权值的Dijkstra算法搜寻的最短路径更为合理。 展开更多

关键词 无人驾驶 路径规划 层次分析法 改进权值的dijkstra算法

下载PDF 职称材料