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

摘要：

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

关键词：集送货问题、最短路径、扇面Dijkstra算法

所属期刊栏目：49

分类号：U492(交通工程与公路运输技术管理)

资助基金：北京市科委科技奥运专项基金H030630020520

在线出版日期：2010-03-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：1834-1837