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

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社