摘要
智慧城市中使用导航系统的车辆在逐渐增加。为了避免中出现密集规划而导致的某些道路负载过高而拥堵的情况,大规模路径规划近来成为了研究热点。从含有宏观连续模型中Lighthill-Whitham-Richards(LWR)模型的宏观基本图(Macroscopic Fundamental Diagram,MFD)推导得出,在城市路网环境中,使用道路负载率作为优化对象的大规模路径规划具有相较其它方案最低的时间成本。因此以LWR作为理论基础,设计负载均衡路径规划算法(Load Balancing Algorithm,LBA)。该算法以边的负载率作为评价指标,为单源查询批次Q中的每个查询找到一个最短路树。LBA构造超源节点将多源问题转化为单源问题。LBA使用网络扩张方法为可能出现的超负荷运转情况确定无拥堵路径,并使用Rtree索引的路网任意两点间最短路缓存加快算法运行速度。实验得出,与最先进算法相比在全局通行时延中减少了5.33%,CPU时间减少了54.58%。LBA在大规模路径规划场景中显著具有优越性。
The number of vehicles using navigation systems in smart cities is gradually increasing.To avoid traffic congestion caused by excessive load on certain roads due to dense planning,large-scale path planning has recently become a research hotspot.Derivedfrom the Macroscopic Fundamental Diagram(MFD)which includesthe Lighthill Whitham-Richards(LWR)model,a macroscopic continuous model,it isconcluded that in urban road network environments,large-scale path planning with road load rate as the optimization target has the lowest time cost compared to other schemes.Therefore,based on the LWR as the theoretical foundation,a Load Balancing Algorithm(LBA)for path planning is designed.This algorithm uses the load rate of edges as the evaluation index to find a shortest path tree for each query in the single-source query batch Q.LBA constructs a super-source node to convert the multisource problem into a single-source problem.LBA uses a network expansion method to determine congestion-free paths for possible overload situations and employs an Rtree-indexed shortest path cache between any two points in the road network to accelerate the algorithm's operation.Experiments show that compared with the most advanced algorithms,the global travel delay is reduced by 5.33%and the CPU time is reduced by 54.58%.LBA has significant advantages in large-scale path planning scenarios.
作者
岳盛
王新南
YUE Sheng;Wang Xin-nan(School of Computer Science and Technology,Soochow University,Suzhou Jiangsu 215006,China;School of Electronic and Information Engineering,Tongji University Shang hai 200032,China)
出处
《计算机仿真》
2025年第11期320-325,共6页
Computer Simulation
