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

作者：郑四发; 曹剑东; 连小珉

来源：清华大学学报(自然科学版)网络.预览, 2009, (11): 1834-1837.

DOI：10.16511/j.cnki.qhdxxb.2009.11.031

• 最短路径
• 扇面Dijkstra算法
• 集送货问题 shortest route
• sector Dijkstra algorithm
• pickup and delivery problem

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

• 单位
  汽车安全与节能国家重点实验室; 清华大学