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

摘要

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