We study stochastic routing in the PAth-CEntric (PACE) uncertain road network model. In the PACE model, uncertain travel times are associated with not only edges but also some paths. The uncertain travel times associated with paths are able to well capture the travel time dependency among different edges. This significantly improves the accuracy of travel time distribution estimations for arbitrary paths, which is a fundamental functionality in stochastic routing, compared to classic uncertain road network models where uncertain travel times are associated with only edges. We investigate a new formulation of the shortest path with on-time arrival reliability (SPOTAR) problem under the PACE model. Given a source, a destination, and a travel time budget, the SPOTAR problem aims at finding a path that maximizes the on-time arrival probability. We develop a generic algorithm with different speed-up strategies to solve the SPOTAR problem under the PACE model. Empirical studies with substantial GPS trajectory data offer insight into the design properties of the proposed algorithm and confirm that the algorithm is effective. This report extends the paper "Stochastic Shortest Path Finding in Path-Centric Uncertain Road Networks", to appear in IEEE MDM 2018, by providing a concrete running example of the studied SPOTAR problem in the PACE model and additional statistics of the used GPS trajectories in the experiments.
The edge-centric uncertain road network model has been applied extensively in stochastic routing @cite_16 @cite_17 @cite_15 @cite_11 @cite_12 @cite_23 @cite_10 @cite_3 @cite_7 @cite_21 @cite_4 @cite_22 . In the edge-centric model, each edge is associated with an uncertain travel time and different edges' uncertain travel times are independent. Given a path, the uncertain time of the path is derived by convoluting the uncertain times of the edges in the path. However, uncertain travel times among different edges in a path are often dependent but not independent. The edge-centric model is unable to capture the dependency and thus results in inaccurate uncertain travel times for paths. To contend with this, the PAth-CEntric (PACE) model is proposed recently @cite_19 @cite_18 . PACE also associates some paths with joint travel time distributions that well capture the dependency of the uncertain travel times of the edges in the paths.
@cite_18 @cite_4 @cite_22 @cite_7 @cite_21 @cite_17 @cite_3 @cite_19 @cite_23 @cite_15 @cite_16 @cite_10 @cite_12 @cite_11
2010567219 2785409760 2525908418 2398179450 2573698050 2795142517 2155044259 2005854848
Tracking and managing the locations of moving objects are essential in modern intelligent transportation systems (ITSs). However, a number of limitations in existing methods make them unsuitable for real-world ITS applications. In particular, Euclidean-based methods are not accurate enough in representing locations and in analyzing traffic, unless the locations are frequently updated. Network-based methods require either digital maps to be installed in moving objects or transmission of prediction policies, which inevitably increase the cost. To solve these problems, we propose a network-matched trajectory-based moving-object database (NMTMOD) mechanism and a traffic flow analysis method using the NMTMOD. In the NMTMOD, the locations of moving objects are tracked through a dense sampling and batch uploading strategy, and a novel edge-centric network-matching method, which is running at the server side, is adopted to efficiently match the densely sampled GPS points to the network. In addition, a deviation-based trajectory optimization method is provided to minimize the trajectory size. Empirical studies with large real trajectory data set offer insight into the design properties of the proposed NMTMOD and suggest that the NMTMOD significantly outperforms other mobile-map free-moving-object database models in terms of precision of both location tracking and network-based traffic flow analysis. We address the problem of choosing the best paths among a set of candidate paths between the same origin–destination pair. This functionality is used extensively when constructing origin–destination matrices in logistics and flex transportation. Because the cost of a path, e.g., travel time, varies over time and is uncertain, there is generally no single best path. We partition time into intervals and represent the cost of a path during an interval as a random variable, resulting in an uncertain time series for each path. When facing uncertainties, users generally have different risk preferences, e.g., risk-loving or risk-averse, and thus prefer different paths. We develop techniques that, for each time interval, are able to find paths with non-dominated lowest costs while taking the users’ risk preferences into account. We represent risk by means of utility function categories and show how the use of first-order and two kinds of second-order stochastic dominance relationships among random variables makes it possible to find all paths with non-dominated lowest costs. We report on empirical studies with large uncertain time series collections derived from a 2-year GPS data set. The study offers insight into the performance of the proposed techniques, and it indicates that the best techniques combine to offer an efficient and robust solution. Reduction of greenhouse gas (GHG) emissions from transportation is an essential part of the efforts to prevent global warming and climate change. Eco-routing, which enables drivers to use the most environmentally friendly routes, is able to substantially reduce GHG emissions from vehicular transportation. The foundation of eco-routing is a weighted-graph representation of a road network in which road segments, or edges, are associated with eco-weights that capture the GHG emissions caused by traversing the edges. Due to the dynamics of traffic, the eco-weights are best modeled as being time dependent and uncertain. We formalize the problem of assigning a time-dependent, uncertain eco-weight to each edge in a road network based on historical GPS records. In particular, a sequence of histograms is employed to describe the uncertain eco-weight of an edge at different time intervals. Compression techniques, including histogram merging and buckets reduction, are proposed to maintain compact histograms while retaining their accuracy. In addition, to better model real traffic conditions, virtual edges and extended virtual edges are proposed in order to represent adjacent edges with highly dependent travel costs. Based on the techniques above, different histogram aggregation methods are proposed to accurately estimate time-dependent GHG emissions for routes. Based on a 200-million GPS record data set collected from 150 vehicles in Denmark over two years, a comprehensive empirical study is conducted in order to gain insight into the effectiveness and efficiency of the proposed approach. We consider the stochastic on-time arrival (SOTA) problem of finding the optimal routing strategy for reaching a given destination within a pre-specified time budget and provide the first results on using preprocessing techniques for speeding up the query time. We start by identifying some properties of the SOTA problem that limit the types of preprocessing techniques that can be used in this setting, and then define the stochastic variants of two deterministic shortest path preprocessing techniques that can be adapted to the SOTA problem, namely reach and arc-flags. We present the preprocessing and query algorithms for each technique, and also present an extension to the standard reach based preprocessing method that provides additional pruning. Finally, we explain the limitations of this approach due to the inefficiency of the preprocessing phase and present a fast heuristic preprocessing scheme. Numerical results for San Francisco, Luxembourg and a synthetic road network show up to an order of magnitude improvement in the query time for short queries, with even larger gains expected for longer queries. With the growing volumes of vehicle trajectory data, it becomes increasingly possible to capture time-varying and uncertain travel costs in a road network, including travel time and fuel consumption. The current paradigm represents a road network as a weighted graph; it blasts trajectories into small fragments that fit the under-lying edges to assign weights to edges; and it then applies a routing algorithm to the resulting graph. We propose a new paradigm, the hybrid graph, that targets more accurate and more efficient path cost distribution estimation. The new paradigm avoids blasting trajectories into small fragments and instead assigns weights to paths rather than simply to the edges. We show how to compute path weights using trajectory data while taking into account the travel cost dependencies among the edges in the paths. Given a departure time and a query path, we show how to select an optimal set of weights with associated paths that cover the query path and such that the weights enable the most accurate joint cost distribution estimation for the query path. The cost distribution of the query path is then computed accurately using the joint distribution. Finally, we show how the resulting method for computing cost distributions of paths can be integrated into existing routing algorithms. Empirical studies with substantial trajectory data from two different cities offer insight into the design properties of the proposed method and confirm that the method is effective in real-world settings. Motivated by the increasing availability of vehicle trajectory data, we propose learn-to-route, a comprehensive trajectory-based routing solution. Specifically, we first construct a graph-like structure from trajectories as the routing infrastructure. Second, we enable trajectory-based routing given an arbitrary (source, destination) pair. In the first step, given a road network and a collection of trajectories, we propose a trajectory-based clustering method that identifies regions in a road network. If a pair of regions are connected by trajectories, we maintain the paths used by these trajectories and learn a routing preference for travel between the regions. As trajectories are skewed and sparse, and although the introduction of regions serves to consolidate the sparse data, many region pairs are not connected by trajectories. We thus transfer routing preferences from region pairs with sufficient trajectories to such region pairs and then use the transferred preferences to identify paths between the regions. In the second step, we exploit the above graph-like structure to achieve a comprehensive trajectory-based routing solution. Empirical studies with two substantial trajectory data sets offer insight into the proposed solution, indicating that it is practical. A comparison with a leading routing service offers evidence that the paper's proposal is able to enhance routing quality. We are witnessing increasing interests in the effective use of road networks. For example, to enable effective vehicle routing, weighted-graph models of transportation networks are used, where the weight of an edge captures some cost associated with traversing the edge, e.g., greenhouse gas (GHG) emissions or travel time. It is a precondition to using a graph model for routing that all edges have weights. Weights that capture travel times and GHG emissions can be extracted from GPS trajectory data collected from the network. However, GPS trajectory data typically lack the coverage needed to assign weights to all edges. This paper formulates and addresses the problem of annotating all edges in a road network with travel cost based weights from a set of trips in the network that cover only a small fraction of the edges, each with an associated ground-truth travel cost. A general framework is proposed to solve the problem. Specifically, the problem is modeled as a regression problem and solved by minimizing a judiciously designed objective function that takes into account the topology of the road network. In particular, the use of weighted PageRank values of edges is explored for assigning appropriate weights to all edges, and the property of directional adjacency of edges is also taken into account to assign weights. Empirical studies with weights capturing travel time and GHG emissions on two road networks (Skagen, Denmark, and North Jutland, Denmark) offer insight into the design properties of the proposed techniques and offer evidence that the techniques are effective. Different uses of a road network call for the consideration of different travel costs: in route planning, travel time and distance are typically considered, and green house gas (GHG) emissions are increasingly being considered. Further, travel costs such as travel time and GHG emissions are time-dependent and uncertain. To support such uses, we propose techniques that enable the construction of a multi-cost, time-dependent, uncertain graph (MTUG) model of a road network based on GPS data from vehicles that traversed the road network. Based on the MTUG, we define stochastic skyline routes that consider multiple costs and time-dependent uncertainty, and we propose efficient algorithms to retrieve stochastic skyline routes for a given source-destination pair and a start time. Empirical studies with three road networks in Denmark and a substantial GPS data set offer insight into the design properties of the MTUG and the efficiency of the stochastic skyline routing algorithms.