基于混合蛙跳的路网应急车辆动态最短路径

来源：交通运输系统工程与信息杂志2016年第3期北京时间：

作者：段晓红，赵建东，宋守信

单位：北京交通大学a. 机械与电子控制工程学院；b. 经济管理学院，北京100044

摘要：针对路网离散动态特性，提出一种求解应急车辆最短路径的混合蛙跳算法.首先设计一种随机编码方案，并引入节点时间度概念对编码方案进行了改进.然后，提出一种逆向标记迭代策略，通过对比优势族群与劣势个体的进入节点时刻和路段行程时间，促使车辆在最佳时刻进入最短路段.最后，以北京市东城区和朝阳区路网为例，将服从正态分布的动态路段行程时间作为权值，对算法进行了验证.验证结果表明，所提混合蛙跳算法能在1s内求得最短路径，基于节点时间度编码方案的混合蛙跳算法较随机编码方案计算速度提高一倍，平均计算准确率提高4.3%.

关键词：公路运输,非FIFO动态最短路径,混合蛙跳算法,路网,应急车辆最短路径

基金资助：中央高校基本科研业务费专项资金/The Fundamental Research Funds for the Central Universities（2016JBM053）.