Global Route Planning for Large-Scale Requests on Traffic-Aware Road Network

How to avoid congested roads and spend the least time to reach the destination has become an urgent requirement for citizens. When large-scale origin-destination queries arrive, these queries themselves will affect road congestion. Therefore, it is necessary to plan different routes in advance for these queries to avoid simultaneous occupation of the same roads, thereby reducing congestion and global travel time. Nevertheless, this is not trivial, as calculating which queries will occupy the same road resources is time-consuming. Moreover, re-planning the routes can also affect other queries, and this impact will spread. Existing methods either adopt greedy strategy to consider only the surrounding road condition, or the result quality is poor in the case of dense query. In this paper, we utilize the structural nature of the H2H index, to quickly find potentially conflicting queries and group them together. In this way, only the conflicts within each group need to be resolved in a local area, so the efficiency is improved. Additionally, several alternative paths are calculated and the global optimal routes are found in finite iterations. Extensive experiments conducted on real-world networks with synthetic and real workloads show that our method can provide higher quality results more efficiently.