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

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

来源：计算机工程, 2008, (12): 37-39.

• 多源点
• 最短距离
• 分层策略
• Dijkstra算法 multi-source
• shortest distances
• hierarchical strategy
• Dijkstra algorithm

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

• 单位
  汽车安全与节能国家重点实验室