Efficient Geo-Computational Algorithms for Constructing Space-Time Prisms in Road Networks
Efficient Geo-Computational Algorithms for Constructing Space-Time Prisms in Road Networks
复制标题
DOI：
10.3390/ijgi5110214
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
Hui-Ping Chen;B. Chen;Yafei Wang;Qingquan Li
中科院分区：
文献类型：
--
作者：
Hui-Ping Chen;B. Chen;Yafei Wang;Qingquan Li
时空棱镜(STP)是时间地理学中的一个重要概念，用于分析各种时空约束下的人类活动-旅行行为。现有的时间-地理研究大多使用一种简单的算法来构造路网中的STP，方法是使用两个一对所有的最短路径搜索。然而，考虑到STP中可访问的链路通常只占整个网络的一小部分，这种简单的算法可能会带来相当大的计算开销。针对这一问题，提出了一种高效的地理计算算法NTP-A*。提出的NTP-A*算法采用A*和分枝定界技术，在两次最短路径搜索过程中丢弃不可达链路，从而提高了STP的构造性能。通过大量的计算实验，验证了该算法的计算优势。讨论和分析了几种实现技术，包括标签校正技术和混合链路节点标签技术。实验结果表明，与已有算法相比，提出的NTP-A*算法能够显著提高大规模道路网络中STP的构建性能100倍。
The Space-time prism (STP) is a key concept in time geography for analyzing human activity-travel behavior under various Space-time constraints. Most existing time-geographic studies use a straightforward algorithm to construct STPs in road networks by using two one-to-all shortest path searches. However, this straightforward algorithm can introduce considerable computational overhead, given the fact that accessible links in a STP are generally a small portion of the whole network. To address this issue, an efficient geo-computational algorithm, called NTP-A*, is proposed. The proposed NTP-A* algorithm employs the A* and branch-and-bound techniques to discard inaccessible links during two shortest path searches, and thereby improves the STP construction performance. Comprehensive computational experiments are carried out to demonstrate the computational advantage of the proposed algorithm. Several implementation techniques, including the label-correcting technique and the hybrid link-node labeling technique, are discussed and analyzed. Experimental results show that the proposed NTP-A* algorithm can significantly improve STP construction performance in large-scale road networks by a factor of 100, compared with existing algorithms.