Efficient and scalable multi-geography route planning
Efficient and scalable multi-geography route planning
复制标题
高效且可扩展的多地理路线规划
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
N. Venkatasubramanian
中科院分区：
文献类型：
--
作者：
Vidhya Balasubramanian;D. Kalashnikov;S. Mehrotra;N. Venkatasubramanian
研究了多地理环境下的路径规划问题，其中地理信息可能分布在多个异构的互联地图上。我们首先设计了一个灵活的和可扩展的表示模型的各个地理和他们的互连。鉴于这样的表示，我们开发了一种算法，利用预先计算和缓存的地理数据的路径规划。采用基于效用的方法来决定哪些路径进行预计算和存储。为了验证所提出的方法，我们在校园级疏散模拟的工作负载上测试了该算法，该模拟在多个地理位置上规划疏散路线：室内CAD地图、室外地图、步行和交通网络，实验结果表明，MGRP算法与提出的基于效用的缓存策略显着优于国家的最先进的解决方案时，应用于一个大型大学校园数据下，不同的条件。
This paper considers the problem of Multi-Geography Route Planning (MGRP) where the geographical information may be spread over multiple heterogeneous interconnected maps. We first design a flexible and scalable representation to model individual geographies and their interconnections. Given such a representation, we develop an algorithm that exploits precomputation and caching of geographical data for path planning. A utility-based approach is adopted to decide which paths to precompute and store. To validate the proposed approach we test the algorithm over the workload of a campus level evacuation simulation that plans evacuation routes over multiple geographies: indoor CAD maps, outdoor maps, pedestrian and transportation networks, etc. The empirical results indicate that the MGRP algorithm with the proposed utility based caching strategy significantly outperforms the state of the art solutions when applied to a large university campus data under varying conditions.