基于路网分层策略的多源点最短距离算法

• 作者: 曹剑东 李克强 李兵 连小珉 郑四发
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 多源点 最短距离 分层策略 Dijkstra算法
• 年，卷（期）: 2008,（12）
• 所属期刊栏目: 博士论文
• 页码范围: 37-39
• 页数: 3页
• 分类号: TP301.6
• 字数: 3193字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2008.12.013

摘要

针对动态VRP对计算实时性要求,在计算实际路网中的多源点最短距离问题时,将规模很大的原完整路网划分为不同层次,并分区划分为若干小规模子图,将原大规模路网中的最短路问题近似转化为若干小规模问题,通过反复使用Dijkstra算法求出各点间的距离矩阵,并用精确方法对少数误差较大的情况进行修正.以北京市地图为例,实现了二级分层路网中的最短距离矩阵算法,并应用于配送调度中的车辆路径问题求解.实例结果表明,该方法在带来约8%的VRP结果误差情况下,能够大幅度地缩短计算时间,适用于实时性要求很高的动态调度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郑四发	清华大学汽车安全与节能国家重点实验室	76	880	17.0	27.0
2	连小珉	清华大学汽车安全与节能国家重点实验室	161	2717	28.0	44.0
3	李克强	清华大学汽车安全与节能国家重点实验室	233	4346	35.0	54.0
4	李兵	清华大学汽车安全与节能国家重点实验室	44	590	13.0	23.0
5	曹剑东	清华大学汽车安全与节能国家重点实验室	9	139	5.0	9.0