Search

The order k Voronoi diagram (OkVD) is an effective geometric construction to partition the geographical space into a set of Voronoi regions such that all locations within a Voronoi region share the same k nearest points of interest (POIs). Despite the broad applications of OkVD in various geographical analysis, few efficient algorithms have been proposed to construct OkVD in real road networks. This study proposes a novel algorithm consisting of two stages. In the first stage, a new one-to-all k shortest path finding procedure is proposed to efficiently determine the shortest paths to k nearest POIs for each node. In the second stage, a new recursive procedure is introduced to effectively divide boundary links within different Voronoi regions using the hierarchical tessellation property of the OkVD. To demonstrate the applicability of the proposed OkVD construction algorithm, a case study of place-based accessibility evaluation is carried out. Computational experiments are also conducted on five real road networks with different sizes, and results show that the proposed OkVD algorithm performed significantly better than state-of-the-art algorithms.

Travel times in congested urban road networks are highly stochastic. Provision of travel time distribution information, including both mean and variance, can be very useful for travelers to make reliable path choice decisions to ensure higher probability of on-time arrival. To this end, a heterogeneous data fusion method is proposed to estimate travel time distributions by fusing heterogeneous data from point and interval detectors. In the proposed method, link travel time distributions are first estimated from point detector observations. The travel time distributions of links without point detectors are imputed based on their spatial correlations with links that have point detectors. The estimated link travel time distributions are then fused with path travel time distributions obtained from the interval detectors using Dempster-Shafer evidence theory. Based on fused path travel time distribution, an optimization technique is further introduced to update link travel time distributions and their spatial correlations. A case study was performed using real-world data from Hong Kong and showed that the proposed method obtained accurate and robust estimations of link and path travel time distributions in congested road networks.

Travel times in urban road networks are highly stochastic. However, most existing travel time estimation methods only estimate the mean travel times, while ignoring travel time variances. To this end, this paper proposes a robust travel time distribution estimation method to estimate both the mean and variance of travel times by using emerging low-frequency floating car data. Different from the existing studies, the path travel time distribution in this study is formulated as the sum of the deterministic link travel times and stochastic turning delays at intersections. Using this formulation, distinct travel time delays for different turning movements at the same intersection can be well captured. In this study, a speed estimation algorithm is developed to estimate the deterministic link travel times, and a distribution estimation algorithm is proposed to estimate the stochastic turning delays. Considering the low sampling rate of the floating car data, a weighted moving average algorithm is further developed for a robust estimation of the path travel time distribution. A real-world case study in Wuhan, China is carried out to validate the applicability of the proposed method. The results of the case study show that the proposed method can obtain a reliable and accurate estimation of path travel time distribution in congested urban road networks.

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.