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

关键词: 多源点, 最短距离, 分层策略, Dijkstra算法

Abstract: In order to meet the request of high real-time performance of dynamic VRP, for solving the multi-source shortest distances problem in the real road network, the full road network with very large size is decomposed into different layers, and then is distributed into several sub-graphs with small size, therefore, the original shortest distances problem in the large-size road network is approximately transformed into several small-size problems. The distances matrix is calculated by using the Dijkstra algorithm repeatedly, and the distances in which case the error is large are corrected by calculating it again with the exact algorithm. The algorithm in a two-layer hierarchical road network of the map of Beijing is realized, and applied for solving the vehicle routing problem in delivery scheduling. The computing result of the example indicates that the CPU time can be deduced significantly in spite of 8% VRP errors, therefore, the algorithm can be applied in the dynamic scheduling problems which need high real-time performance.

Key words: multi-source, shortest distances, hierarchical strategy, Dijkstra algorithm

中图分类号: 

• TP301.6