复杂路网下多客户间最短路径的扇面Dijkstra算法

• 作者: 曹剑东 连小珉 郑四发
• 来源期刊: 清华大学学报（自然科学版）
• 学科: 交通运输
• 关键词: 集送货问题 最短路径 扇面Dijkstra算法
• 年，卷（期）: 2009,（11）
• 所属期刊栏目: 汽车工程
• 页码范围: 1834-1837
• 页数: 4页
• 分类号: U492
• 语种: 中文

摘要

复杂路网模型下多客户之间最短路径的计算,直接影响市区集送货问题的求解效率.该文提出多客户间最短路径扇面Dijkstra算法.该算法首先由客户在路网的分布确定出最小扇形区域及扇面搜索区域,并将路网节点分为拓展点集、邻节点集.然后在搜索过程中通过优化到达邻节点的通行代价来确定新的拓展点集、邻节点集.算法通过限制搜索区域、减少遍历节点的数量来缩短搜索时间.100个分布于北京市的客户间最短路径的计算表明,相对于Dijkstra算法,扇面Dijkstra算法能够在保证精度的前提下,降低15%的最短路径求解时间.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郑四发		76	880	17.0	27.0
2	连小珉		161	2717	28.0	44.0
3	曹剑东		9	139	5.0	9.0