Search

Autonomous vehicles maneuver in traffic through road networks without requiring humans as supervisors or decision makers. Autonomous vehicles increase comfort for their passengers by removing the need for them to perform driving tasks. Autonomous vehicles provide new mobility opportunities for groups of people that thus far have been partially or entirely excluded from participation in public life due to mobility restrictions.

Trajectory similarity search has been an attractive and challenging topic which spawns various applications. In this work, we study the problem that finds trajectories close to some query locations with timestamps designated by a user. We firstly define the similarity between the query locations and trajectory on road networks. Then, we propose a method to retrieve similar trajectories based on Network Voronoi Diagram. By taking advantage of Network Voronoi Diagram, the proposed method can accelerate the query processing through some pre-computation. Finally, we verify the efficiency of the proposed method by extensive experiments.

Accurate extraction of road networks from high resolution remote sensing images is a problem not satisfactorily solved by existing approaches, especially when the color of road is close to that of background. This paper studies a new road networks extraction from remote sensing images based on the shear transform, the directional segmentation, shape features and a skeletonization algorithm. The proposed method includes the following steps. Firstly, we combine shear transform with directional segmentation to get road regions. Secondly, road shape features filtering are used to extract reliable road segments. Finally, the road centerlines are extracted by a skeletonization algorithm. Road networks are then generated by post-processing. Experimental results show that this method is efficient in road centerlines extraction from remote sensing images.

The p-median problem is often used to locate P service facilities in a geographically distributed population. Important for the performance of such a model is the distance measure. The first aim in this study is to analyze how the optimal location solutions vary, using the p-median model, when the road network is alternated. It is hard to find an exact optimal solution for p-median problems. Therefore, in this study two heuristic solutions are applied, simulating annealing and a classic heuristic. The secondary aim is to compare the optimal location solutions using different algorithms for large p-median problem. The investigation is conducted by the means of a case study in a rural region with a. asymmetrically distributed population, Dalecarlia. The study shows that the use of more accurate road networks gives better solutions for optimal location, regardless what algorithm that is used and regardless how many service facilities that is opt for. It is also shown that the Simulating annealing algorithm not just is much faster than the classic heuristic used here, but also in most cases gives better solutions.

Many existing solutions focus on point-to-point shortest-path queries in road networks. In contrast, only few contributions address the related single-source shortest-path problem, i.e., finding shortest-path distances from a single source s to all other graph vertices. This work extends graph separator methods to handle this specific problem and its one-to-many variant, i.e., calculating the shortest path distances from a single source to a set of targets T ⊆ V. This novel family of so-called GRASP algorithms provides exceptional preprocessing times, making them suitable for dynamic travel time scenarios. GRASP algorithms also efficiently solve range / isochrone queries not handled by previous approaches.

The majority of the road networks in developing countries and large percentages in most developed countries are currently unpaved. This results in the road surface being directly exposed to traffic and the environment with a consequent continual loss of gravel, which needs to be replaced at regular intervals. This has severe environmental and sustainability implications and is totally unacceptable in these respects in the long term. Alternatives to this need to be developed such that the materials are either protected against environmental loss or are treated to an extent that the annual loss is significantly reduced. The optimum solution is to pave all roads with either a bituminous or concrete surfacing such that the material imported into the road is preserved against loss by erosion and abrasion. This is, however, probably not financially viable in most developing countries. The alternative is to treat the materials in some way that will reduce the annual loss. Research has indicated that, firstly by selecting the most appropriate materials and secondly, by improving construction methods, significant reductions in material loss are possible. To supplement this, methods of chemical or physical treatment can be considered to minimize material loss. Essentially, the status quo is no longer sustainable and a paradigm shift in this respect is urgently necessary. The impact of the use of water during the construction and maintenance of unpaved roads should also not be neglected.

Transit Node Routing (TNR) is a fast and exact distance oracle for road networks. We show several new results for TNR. First, we give a surprisingly simple implementation fully based on contraction hierarchies that speeds up preprocessing by an order of magnitude approaching the time for just finding a contraction hierarchy (which alone has two orders of magnitude larger query time). We also develop a very effective purely graph theoretical locality filter without any compromise in query times. Finally, we show that a specialization to the online many-to-one (or one-to-many) shortest path problem.

We present a new dynamic graph structure specifically suited for large-scale transportation networks that provides simultaneously three unique features: compactness, agility and dynamicity. We demonstrate its practicality and superiority by conducting an experimental study for shortest route planning in large-scale European and US road networks with a few dozen millions of nodes and edges. Our approach is the first one that concerns the dynamic maintenance of a large-scale graph with ordered elements using a contiguous memory part, and which allows an arbitrary online reordering of its elements.

Aim at moving objects on road network, we propose a novel indexing named PPFN*-tree to store past trajectories, present positions, and predict near future positions of moving objects. PPFN*-tree is a hybrid indexing structure which consists of a 2D R*-tree managing the road networks, a set of TB*-tree indexing objects’ movement history trajectory along the polylines, and a set of basic HTPR*-tree indexing the position of moving objects after recent update. PPFN*-tree can not only support past trajectory query and present position query, but also support future predictive query. According to the range query time, query in PPFN*-tree can be implemented only in the TB*-tree, or only in the HTPR*-tree, or both of them. Experimental results show that the update performance of the PPFN*-tree is better than that of the PPFI and the RPPF-tree. The query performance of the PPFN*-tree is better than that of the MON-Tree and the PPFI.

In this paper, we consider a new problem in the context of road network databases, named Resource Constrained Best Upgrade Plan computation (BUP, for short). Consider a transportation network (weighted graph) G where a subset of the edges are upgradable, i.e., for each such edge there is a cost, which if spent, the weight of the edge can be reduced to a specific new value. Given a source and a destination in G, and a budget (resource constraint) B, the BUP problem is to identify which upgradable edges should be upgraded so that the shortest path distance between source and destination (in the updated network) is minimized, without exceeding the available budget for the upgrade. In addition to transportation networks, the BUP query arises in other domains too, such as telecommunications. We propose a framework for BUP processing and evaluate it with experiments on large, real road networks.

Location-based services (LBS) have became more and more popular nowadays since people equipped with smart phones. Existing keyword k-nearest neighbor (kNN) search methods focus more on the keywords; therefore, they use direct distance of two points, also known as, Euclidean distance as spatial constraints. However, the nearest point-of-interest (POI) returned by these services may not be the nearest on the road networks. For some services that consider the road networks, they use road expansion methods to solve this problem. The speed limitation for a large road network and index structures for millions POI may be the bottlenecks for these services. To address those problems, we develop a fast keyword kNN search system in road networks, called Saturn. Instead of using road expansion methods, we introduce a grid-based shortest path computation method, a filter-and-verification framework to search fast in road networks, and we also devise an improvement of the grid index to further improve the performance. We conduct extensive experiments on real data sets, and the experimental results show that our method is efficient and scalable to large data sets, significantly outperforming state-of-the-art methods.

Simulating any nontrivial traffic situation requires describing not only acceleration and braking but also lane changes. When modeling traffic flow on entire road networks, additional discrete-choice situations arise such as deciding if it is safe to enter a priority road, or if cruising or stopping is the appropriate driver’s reaction when approaching a traffic light which is about to change to red. This chapter presents a unified utility-based modeling framework for such decisions at the most basic operative level.

A characteristic particle method for the simulation of first order macroscopic traffic models on road networks is presented. The approach is based on the method particleclaw, which solves scalar one dimensional hyperbolic conservation laws exactly, except for a small error right around shocks. The method is generalized to nonlinear network flows, where particle approximations on the edges are suitably coupled together at the network nodes. It is demonstrated in numerical examples that the resulting particle method can approximate traffic jams accurately, while only devoting a few degrees of freedom to each edge of the network.

The current widespread use of GPS navigations and trip planning on web has aroused great interests in fast and scalable path query processing. Recent research has mainly focused on static route optimisation where the traffic network is assumed to be stable. However in most cases, route planning is in presence of frequent updates to the traffic graph due to the dynamic nature of traffic network, and such updates always greatly affect the performance of route planning. Most existing methods, however, cannot effectively support traffic aware route planning. In this paper, a new strategy is proposed to handle this problem. We analysis the traffic condition on the road network and explore spatial-temporal knowledge to guide effective route planning. In particular, a set of effective techniques are used to avoid both unnecessary calculations on huge graph and excessive re-calculations caused by traffic condition updates. A comprehensive experiment is also conducted to evaluate the strategy performances.

Recently, several techniques have been proposed to protect users location privacy for location-based services in the Euclidean space. Applying these techniques directly to the road network environment would lead to privacy leakage and inefficient query processing. In this paper, we propose a query-aware location privacy model based on p-sensitive & k-anonymity for road networks. By cloaking a user’s location into p connected road segments which include at least k users, our model is able to meet privacy requirements, and to minimize the query processing cost. We conducted simulate experiments on our model, the result manifest its privacy resilience and efficient query processing.

We consider the problem of finding routes in road networks that optimize a combination of travel time and additional time-invariant costs. These could be an approximation of energy consumption, distance, tolls, or other penalties. The resulting problem is NP-hard, but if the additional cost is proportional to driving distance we can solve it optimally on the German road network within 2.3 s using a multi-label A* search. A generalization of time-dependent contraction hierarchies to the problem yields approximations with negligible errors using running times below 5 ms which makes the model feasible for high-throughput web services. By introducing tolls we get considerably harder instances, but still we have running times below 41 ms and very small errors.

We present a fast algorithm with preprocessing for computing multiple good alternative routes in road networks. Our approach is based on single via node routing on top of Contraction Hierarchies and achieves superior quality and efficiency compared to previous methods. The algorithm has neglectable memory overhead.

We study an important practical aspect of the route planning problem in real-world road networks --- maneuvers. Informally, maneuvers represent various irregularities of the road network graph such as turn-prohibitions, traffic light delays, round-abouts, forbidden passages and so on. We propose a generalized model which can handle arbitrarily complex (and even negative) maneuvers, and outline how to enhance Dijkstra's algorithm in order to solve route planning queries in this model without prior adjustments of the underlying road network graph.

We study hierarchical hub labelings for computing shortest paths. Our new theoretical insights into the structure of hierarchical labels lead to faster preprocessing algorithms, making the labeling approach practical for a wider class of graphs. We also find smaller labels for road networks, improving the query speed.

Route selection plays a very important role in road networks. It is a major problem for city travelers. This paper proposes a hierarchical community mining system which helps to model the road network in static and introduce a dynamic technique for fast route planning in large road networks. The foundation of our dynamic method is new approach that generalizes and combines fuzzy logic for local pheromone updating of an ant colony system in detection of optimum multi parameter direction between two desired points, origin to destination. The hierarchical community based routing algorithm significantly reduces the search space. We then propose a new Hierarchical community -Fuzzy Ant colony system supports dynamic efficient route computation on large road networks.

Our objective is to reduce the risk of overwork in the refuse collection procedure while keeping efficient routes. On optimum routes in refuse collection, vehicles pass through each road segment only once. When we look upon our road network as a graph, the optimum route is Euler graph. Euler graph consists of several Euler cycles. When Euler cycles are exchanged in Euler graph, these cycles are yet Euler cycles if the exchanged cycles are adjacent. Our idea is to construct the cycle graph, which represents cycles as nodes and connective relationships between adjacent cycles as links, from Euler graph. It is guaranteed that the cycle based on links in the cycle graph does not generate the redundancy. In the computer simulation, we conclude that our method is effectively applicable to many kinds of road networks.

In recent years, the research community has introduced various methods for processing spatio-temporal queries in road networks. In this paper, we present a novel type of spatio-temporal queries, named the continuous min-max distance bounded query (or CM2DBQ for short). Given a moving query object q, a minimal distance dm, and a maximal distance dM, a CM2DBQ retrieves the bounded objects whose road distances to q are within the range [dm, dM] at each time instant. The CM2DBQ is indeed an important query with many real applications. We address the problem of processing the CM2DBQ and propose two algorithms, named the Continuous Within Query-based (CWQ-based) algorithm and the CM2DBQ algorithm, to efficiently determine the bounded objects at each time instant. Extensive experiments using real road network dataset demonstrate the efficiency of the proposed algorithms.

This paper focuses on processing continuous k nearest neighbor queries over objects moving at uncertain speeds (CUkNN) in road networks. We present a novel model to estimate the distances between objects and a query, both of which move at variable speeds in the road network. Based on the proposed distance model, we present a CUkNN query monitoring method to continuously find the objects that could potentially be the k-nearest neighbors (kNN) of the query. We propose an efficient method to calculate the probability of each object being a kNN of a query. The key thing about the method is that the probability of an object being a kNN of query q is shown to be equivalent to the probability of a special line segment being one of the k-nearest lines from q, which greatly simplifies the probability calculation.

We present an algorithm to compute shortest paths on continental road networks with arbitrary metrics (cost functions). The approach supports turn costs, enables real-time queries, and can incorporate a new metric in a few seconds--fast enough to support real-time traffic updates and personalized optimization functions. The amount of metric-specific data is a small fraction of the graph itself, which allows us to maintain several metrics in memory simultaneously.

A new approach to the static route planning problem, based on a multi-staging concept and a scope notion, is presented. The main goal (besides implied efficiency of planning) of our approach is to address--with a solid theoretical foundation--the following two practically motivated aspects: a route comfort and a very limited storage space of a small navigation device, which both do not seem to be among the chief objectives of many other studies. We show how our novel idea can tackle both these seemingly unrelated aspects at once, and may also contribute to other established route planning approaches with which ours can be naturally combined. We provide a theoretical proof that our approach efficiently computes exact optimal routes within this concept, as well as we demonstrate with experimental results on publicly available road networks of the US the good practical performance of the solution.

As a measure for the resemblance of tracks in a network graph, we consider the so-called Freechet-distance based on network distance. For paths P and Q consisting of p and q consecutive edges, an O((p2+q2)logpq) time algorithm measuring the Freechet-distance between P and Q is developed. Then some important variants are investigated, namely weak Freechet distance, discrete Freechet distance , all based on the network distance.

Generating route sketches is a graph redrawing problem, where we are given an initial drawing of a graph G and want to find a new, schematized drawing of G that reduces the drawing complexity while preserving the structural characteristics of the input. The motivation of our work is the visualization of routes in road networks as sketches for driving directions. An important property of a route sketch is that it focuses on road changes and important landmarks rather than exact geography and distances. Typically the start and destination lie in populated areas that are locally reached via a sequence of relatively short road segments. On the other hand, the majority of the route typically consists of long highway segments with no or only few road changes. This property makes it difficult to display driving directions for the whole route in a single traditional map since some areas require much smaller scales than others. The strength of route sketches for this purpose is that they are not drawn to scale but rather use space proportionally to the route complexity.

In the last decade major progress has been made in accelerating shortest path queries in large-scale, time-dependent road networks. Most techniques are heuristically motivated and their performance is experimentally evaluated on real-world data. However, to our knowledge no free time-dependent dataset is available to researchers. This is the first work proposing algorithmic approaches for generating timedependent road networks that are built on top of static road networks in the scenario of systematic delays. Based on an analysis of a commercial, confidential time-dependent dataset we have access to, we develop algorithms that utilize either road categories or coordinates to enrich a given static road network with artificial time-dependent data. Thus, the static road-networks we operate on may originate from manifold sources like commercial, open source or artificial data. In our experimental study we assess the usefulness of our algorithms by comparing global as well as local statistical properties and the shortest-path structure of generated datasets and a commercially used time-dependent dataset. Until now, evaluations of time-dependent routing algorithms were based on artificial data created by ad-hoc random procedure. Our work enables researchers to conduct more reasonable validations of their algorithms than it was possible up to now.

Every human likes choices. But today's fast route planning algorithms usually compute just a single route between source and target. There are beginnings to compute alternative routes, but there is a gap between the intuition of humans what makes a good alternative and mathematical definitions needed for grasping these concepts algorithmically. In this paper we make several steps towards closing this gap: Based on the concept of an alternative graph that can compactly encode many alternatives, we define and motivate several attributes quantifying the quality of the alternative graph. We show that it is already NP-hard to optimize a simple objective function combining two of these attributes and therefore turn to heuristics. The combination of the refined penalty based iterative shortest path routine and the previously proposed Plateau heuristics yields best results. A user study confirms these results.

Skyline queries have gained attention lately for supporting effective retrieval over massive spatial data. While efficient algorithms have been studied for spatial skyline queries using Euclidean distance, or, L2 norm, these algorithms are (1) still quite computationally intensive and (2) unaware of the road constraints. Our goal is to develop a more efficient algorithm for L1 norm, also known as Manhattan distance, which closely reflects road network distance for metro areas with well-connected road networks. Towards this goal, we present a simple and efficient algorithm which, given a set P of data points and a set Q of query points in the plane, returns the set of spatial skyline points in just O(|P| log |P|) time, assuming that |Q| = |P|. This is significantly lower in complexity than the best known method. In addition to efficiency and applicability, our proposed algorithm has another desirable property of independent computation and extensibility to L∞ norm, which naturally invites parallelism and widens applicability. Our extensive empirical results suggest that our algorithm outperforms the state-of-the-art approaches by orders of magnitude.

In Germany, the data of the Open Street Map project has become available as an alternative to proprietary road networks in commercial business geomatics software and their customers are wondering whether the quality may be sufficient. This paper describes an implemented methodology to compare OSM street data with those of Navteq for all populated roads in Germany. As a unique feature, the presented methodology is based on a matching between the street objects of OSM and Navteq and all steps are fully automated so that they can be applied to updated versions of both data sets.

The metric of the current road networks tends intrinsically to favour the efficacy of the routes which have the longer range, what leads to promote urban sprawl and automobile dependence. Indeed this metric ensures to individuals the possibility to travel even further, without necessarily increasing their transportation time in the same proportions. According to this assessment, we introduce a new kind of metric, the “slow metric”, which amounts to invert the current ratios of efficacy between the different types of automobile travels, i.e. to favour the efficacy of the short range travels. This metric is reached thanks to traffic lights, under constraints regarding their location and duration. The calibration of the slow metric (number, duration and location of the traffic lights for different networks structures), its impact on traffic (fluidity versus congestion) and conversely the impact of traffic interactions on the slow metric, are simulated and evaluated with S3 which is an agent-based simulation platform.

We study the problem of finding good alternative routes in road networks. We look for routes that are substantially different from the shortest path, have small stretch, and are locally optimal. We formally define the problem of finding alternative routes with a single via vertex, develop efficient algorithms for it, and evaluate them experimentally. Our algorithms are efficient enough for practical use and compare favorably with previous methods in both speed and solution quality.

Accelerating the computation of quickest paths in road networks has been undergoing a rapid development during the last years. The breakthrough idea for handling road networks with tens of millions of nodes was the concept of shortcuts, i.e., additional arcs that represent long paths in the input. Very recently, this concept has been transferred to time-dependent road networks where travel times on arcs are given by functions. Unfortunately, the concept of shortcuts is very space-consuming in time-dependent road networks since the travel time functions assigned to the shortcuts may become quite complex. In this work, we present how the space overhead induced by time-dependent SHARC, a technique relying on shortcuts as well, can be reduced significantly. We are able to reduce the overhead stemming from SHARC by a factor of up to 11.5 for the price of a loss in query performance of a factor of 4. The methods we present allow a trade-off between space consumption and query performance.

This paper investigates the influence of gradient and payload correction factors used within a CO2 emission model on the solutions to shortest path and travelling salesman problems when applied to freight delivery. Problem instances based on real life examples using the road network of Scotland are studied. Solutions are obtained using a range of metrics and vehicles. The results are compared to determine if the inclusion of gradient and payload as inputs to the emission model have any influence on the final routes taken by vehicles or the order of visiting customers. For the problem instances studied no significant influence was found. However for vehicle routing problems with large differences in payload and hilly road networks further investigation is needed.