Hack 2. Route Planning Online

Many map services offer a route planner. How do they work and why do they fail?

Maps not only assist you in indicating where you are now, but also help you plan where you want to go next. To help you out, most online mapping services such as Map24, Maporama, MapQuest, and Multimap feature a "driving directions" service on their web sites, which is free, online, and always available. These services provide directions in two different ways: they can give you driving instructions to a location you've just searched for on the site, or they can just help you plan a trip from point A to point B.

A typical route-planning session consists of four stages: address input and validation, address geocoding, route calculation, and route representation. The first two stages revolve around locating a given address in geographic space: translating a human-readable address into a machine-readable pair of coordinates. (You can see these principles in action in [Hack #79] .) Instead of worrying about just one address, two addresses must be converted into computer-friendly coordinates. In the third stage, the actual route is calculated. As this stage requires a lot of computer processing, it takes quite a while. In the last stage, the route is represented in a human-readable format as a table of textual instructions and additional information.

1.3.1. Route Calculation

Road-network data that is used for route calculations is a subset of the data offered by commercial mapping data providers such as AND, GDT, NAVTEQ, and TeleAtlas. These data sets not only include representational informationthe road class (to determine line width and line color), the road name, and house number ranges (for labeling)but also navigational information.

To calculate the shortest or quickest route between two points, routing software borrows from graph theory and relies on (a variation of) the Dijkstra or A* algorithm. These algorithms take into account only the connectivity between navigable features and the difficulty (or impedance) factor of each navigable feature. When calculating the shortest route between two points over a network, the length of the navigable features is used as the impedance factor. When calculating the quickest route, the impedance factor incorporates both feature length and travel speed; the length of the navigable features is combined with their travel speeds to approximate the travel time for each feature.

There are various characteristics of each navigable feature that determine the connectivity between them. The primary attribute is network topology. Most mapping data sets are topological data sets: the geometry of the network consists of nodes and lines. Each intersection of lines is a node. However, in the real world, one cannot always turn onto another road even though the lines that represent these roads intersect in the data model (for example, due to turn restrictions). Also, intersecting lines may represent roads that cross at different levelse.g., tunnels, overpasses, and bridges. Finally, there may be one-way streets or barriers at the start or end of roads that may prevent you from accessing the road altogether. All these factors affect the real-world connectivity between the elements of the road network.

The impedance factor determines the cost of traveling across a navigable feature. To calculate the shortest or quickest route between two locations, this impedance factor has to be minimized. Calculating the shortest route is the most objective calculation, as it is only the length of the navigable features that determines the route's impedance factor. To calculate the quickest route, the algorithm takes into account both the length of the navigable features and their travel speed to determine the impedance factor. Assigning an accurate travel speed to a navigable feature largely determines the satisfaction of the end user. A basic approximation can be derived from the speed restrictions for various road classes: you can generally travel faster on a major highway or motorway than on a secondary road. However, road class alone still gives a rough approximation. Since it takes longer to drive one mile on a primary road in town than a primary road in the countryside, it's important to determine whether the navigable feature is located in an urban area or not. A third characteristic of a navigable feature that can be easily extracted from the mapping data to provide some further hint for determining the travel speed is the form of way. This is particularly helpful when it comes to slip roads (exits) or roundabouts (traffic circles). Although these traffic situations are part of a particular road class and are situated in the same area as the connecting navigable features, one typically drives slower in these conditions than on other road segments. All these attributes of navigable features are taken into account in assigning travel speeds to navigable features. The more granular this classification of navigable features is, the better the route calculation and the more satisfied the user.

1.3.2. Driving Instructions

Once the route between the two locations has been calculated, the driving directions are presented on screen. At this stage, the output of the route calculation, a sequential list of navigable features, has to be presented in a human-readable form. Street names and road numbers are the most important information and can be easily extracted from the mapping data sets. You also have to know which turns to take to get from one road into the next. The angles between two connecting features are used to derive the driving instructions for the turn to take:

Further information can be added by taking into account specific traffic situations such as at traffic circles or exits of highway junctions:

• "At the roundabout take the third exit onto"
• "Leave/Join the highway"

To further enhance the driving instructions, landmarks or points of interest can be added (e.g., "Turn left at the `Dog and Duck' onto Oxford Street"). This gives the instructions a more conversational tone, so they don't sound like staccato, computer-generated commands.

1.3.3. Turn Right, Gone Wrong

A company's board meeting had to be postponed, as most of the board members did not arrive in Cardiff on time, because the driving directions did not take into account the Severn Bridge and took them from Bristol around the Severn estuary via Gloucester. A salesman missed out on landing a deal with his blue chip customer as he arrived too late at the meeting to sign the contract. The right turn he had to take according to the directions was not there. On their way to visit their daughter's new house in Kingston, Dorset, her parents found themselves in Kingston, Devon instead.

These ill-advised travelers all followed driving directions from various online mapping services available on the Web today. Although many people successfully rely on these services on a daily basis, things sometimes go wrong. Then, it is neither the person in the passenger seat reading out the instructions that is to blame, nor the online mapping service: their driving directions come with elaborate disclaimers to avoid any liability.

Then what is the source of these problems? Of course, many problems occur at the geocoding stage when entering ambiguous address details that have to be converted to machine-readable coordinates. But focusing on route calculation alone, three groups of problems can be observed in ascending order of severity:

1. Duration of the trip is poorly estimated. Although the route is correct, the calculated duration of the journey is too short or too long.
2. Driving directions take an illogical route. The route deviates strangely from the most direct route.
3. Driving directions take an impossible route or neglect apparent solutions.

The most likely reason for the first problem is the assumption of an average speed for each road class. Most driving direction services do take into account that traffic flow can be severely delayed during rush hours. Furthermore, local knowledge is difficult to incorporate. How would one formalize the driving pattern of a New York City cab driver? When fine-tuning the route calculation, software engineers tend to exaggerate the speeds on major roads while purposely decreasing the average speeds for minor roads. Thus, long distance routes turn out to take much longer than expected, whereas the calculated journey duration for urban routes is generally too short. Although this approach may skew the route calculation towards preferring major roads, the driving directions guide drivers around the town center and instruct them to follow the ring road, although this may not be the shortest route to join the highway on the other side of town.

In addition to the possibility the route calculation is skewed too much toward a preference for major roads, another problem may be that the speed settings of the various road classes may be too similar. In this case, the route calculation generates driving directions that make travelers take many turns, as the resulting differences of the features' impedance factors (interplay of travel speed and feature length) have become almost negligible. Maintaining the distinction between major roads and minor roads, some route-calculation algorithms introduced the concept of a hierarchical network. A hierarchical network typically consists of two or three networks, in which the upper levels are a subset of the lower levels to ensure connectivity. This way, the algorithm can generate driving directions that are more accurately based on the mental hierarchy one has of a road network, instead of relying primarily on travel speeds.

Assuming three hierarchical levels, the route calculation takes into account all navigable features around the start location and the destination. Between the start location and the destination, the route calculation focuses on the major and connecting roads. Thus, the route calculation embeds the mental hierarchy. Furthermore, less navigable features have to be taken into account at higher levels of the hierarchy, so the route can be calculated much faster.

Finally the route calculation may generate routes that are not possible to navigate or may neglect obvious driving routes. These problems point toward issues related to the connectivity in the road network. If the height difference is not modeled in the graph, drivers may be instructed to take a right turn to join a highway from a flyover. Also, recently built roads or new highways may not always be included in the mapping data. First, it takes a while before these changes filter through in the mapping data. Second, once the mapping data has been shipped, it takes a lot of preparation and quality assurance before a new graph can be put into production to calculate routes.

Recently, small-scale mapping data sets covering only the major road network have become available. These data sets have default travel speeds for each navigable feature. This information is typically derived from historical data obtained from GPS-based fleet tracking systems. Also, some route-calculation engines take traffic information feeds to regularly update the speed settings.

1.3.4. See Also

• http://www.maporama.com/
• http://www.mapquest.com/
• http://www.multimap.com/

Edward Mac Gillavry