| 基于路网分层策略的多源点最短距离算法 | |
| 李兵 ; 郑四发 ; 曹剑东 ; 连小珉 ; 李克强 ; LI Bing ; ZHENG Si-fa ; CAO Jian-dong ; LIAN Xiao-min ; LI Ke-qiang | |
| 2010-05-13 ; 2010-05-13 | |
| 关键词 | 多源点 最短距离 分层策略 Dijkstra算法 multi-source shortest distances hierarchical strategy Dijkstra algorithm TP393.01 |
| 其他题名 | Multi-source Shortest Distances Algorithm Based on Road Network Hierarchical Strategy |
| 中文摘要 | 针对动态VRP对计算实时性要求,在计算实际路网中的多源点最短距离问题时,将规模很大的原完整路网划分为不同层次,并分区划分为若干小规模子图,将原大规模路网中的最短路问题近似转化为若干小规模问题,通过反复使用Dijkstra算法求出各点间的距离矩阵,并用精确方法对少数误差较大的情况进行修正。以北京市地图为例,实现了二级分层路网中的最短距离矩阵算法,并应用于配送调度中的车辆路径问题求解。实例结果表明,该方法在带来约8%的VRP结果误差情况下,能够大幅度地缩短计算时间,适用于实时性要求很高的动态调度。; 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. |
| 语种 | 中文 ; 中文 |
| 内容类型 | 期刊论文 |
| 源URL | [http://hdl.handle.net/123456789/31420]  |
| 专题 | 清华大学 |
| 推荐引用方式 GB/T 7714 | 李兵,郑四发,曹剑东,等. 基于路网分层策略的多源点最短距离算法[J],2010, 2010. |
| APA | 李兵.,郑四发.,曹剑东.,连小珉.,李克强.,...&LI Ke-qiang.(2010).基于路网分层策略的多源点最短距离算法.. |
| MLA | 李兵,et al."基于路网分层策略的多源点最短距离算法".(2010). |
| 个性服务 |
| 查看访问统计 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论