Introduction
Road Network Basics
First we’ll introduce some of the graph properties of road networks.
As Directed, Weighted Graphs
A road network can be modeled as a directed graph. Edges (often called arcs) represent roads. Vertices (often called nodes) are intersections where roads meet. The graph is directed, but usually symmetric (most roads allow for two-way travel). Throughout these sections, we’ll assume that we’re dealing with directed, but symmetric graphs.
When we consider the road network of an entire continent, these graphs are very large. The graph representing the road network of the entire USA contains 23 million nodes and 58 million arcs. For Western Europe, the graph has 18 million vertices and 43 million arcs.
Edge Weights
We also apply some cost function on these graphs to give every arc an associated weight. Naturally, between two intersections a road has a certain distance. But distance isn’t necessarily the best indicator of the cost of driving on that road.
Usually, the objective of route-planning is to find the path between a source and a destination with the shortest travel time. To that end, most cost functions take into account both the distance of the arc and the average speed traveled on that road. Dividing distance by speed gives us edge weights defined by travel time.
In this project, we assume edge weights represent travel time and are precomputed as part of the graph input. Other types of cost functions incorporate additional factors (turn restrictions, time of day, vehicle type, etc.) and are discussed further in [6] and [2]. Also, given our choice of cost function, we assume that all edge weights are positive.
A couple other things to note: road networks are almost planar, but consider bridges or tunnels that cross over (or under) other roads. Also, the average degree in road networks is around 2.5 (See [3]).
Defining the problem
To summarize, we have a directed graph G = (V, E), where every edge e in E has a weight representing the time it takes to travel on that road. We can think of our graph having similar structure to the example below, but with millions of vertices and edges.
So given our graph, if we have a source s and a target t in V, how efficiently can we compute the shortest path from s to t?