GEOG 160
Mapping Our Changing World

6.9 Routing

PrintPrint

Operations such as mail and package delivery, food and beverage distribution, and emergency medical services need to know not only where their customers are located, but how to deliver products and services to those locations as efficiently as possible. Geographic data products like TIGER/Line Shapefiles are valuable to analysts responsible for prescribing the most efficient delivery routes. The larger and more complex the service areas of such organizations, the more incentive they have to automate their routing procedures.

In its simplest form, routing involves finding the shortest path through a network from an origin to a destination. If the nodes are specified within geographic or plane coordinate systems, the distance between them can be calculated readily. Routing procedures sum the lengths of every plausible sequence of line segments that begins and ends at the specified locations. The sequence of segments associated with the smallest sum represents the shortest route. In addition to geographic distances, modern transportation data can also make use of local speed limits or, where available, current traffic conditions to determine the length of time needed to travel a particular line segment. This allows analysts and users to compare and make compromises between a route of the shortest distance and a route of the shortest travel time.

To enable this kind of analysis and computation, the data must indicate which line segment follows immediately after another line segment. In other words, the procedure needs to know about the connectivity of features. As discussed earlier, connectivity is an example of a topological relationship. If topology is not encoded in the data product, it can be calculated by the GIS software in which the procedure is coded.

Several online travel planning services, including MapQuest.com and Google Maps, provide routing capabilities. Both take origin and destination addresses as input, and produce optimal routes as output. These services are based on vector feature databases in which street segments are attributed with address ranges, as well as with other data that describe the type and conditions of the roads they represent. Recent advances in these services have added routing for pedestrians and bicyclists as well as by mass transit.

Try This: Use a routing tool to help you find your way

Let’s take a practical look at a routing application you might use while on vacation or exploring a new city.

1: Visit Google Maps: maps.google.com/

2: In the search box, enter: The Henley Park Hotel, Massachusetts Avenue Northwest, Washington, DC. The Henley Park Hotel will be marked by the ‘A’ pin.

3: Click it and then click the ‘Directions’ link shown in Figure 6.11:

Google maps screenshot of The Henley Park Hotel, Washington, D.C. marked by an 'A' pin
Figure 6.11: Step 1 - Click the 'A' pin for the Henley Park Hotel, and then click 'Directions.'
Credit: Google Maps.

4: A new textbox will appear on the left of the map. Enter Library of Congress, Independence Avenue Southeast, DC in the empty textbox.

5: ClickGet Directions’ (Figure 6.12):

Google maps screenshot of 'Get Directions' section.
Figure 6.12: Step 2 - Click 'Get Directions' to see a route from the Henley Park Hotel to the Library of Congress.
Credit: Google Maps.

6: Use the buttons indicated in Figure 6.13 to toggle different transpiration options:

Google maps screenshot of buttons used to indicate transportation options.
Figure 6.13: Step 3 - Toggle the different modes of travel to see how the routes between the origin and destination change.
Credit: Google Maps.

Experiment with the different routes and travel modes. Which travel mode takes the shortest route? Which route has more turns? Which travel mode/route is quickest? Note that each mode of travel may also have additional routes that can be toggled (Figure 6.14).

Google maps screenshot showing route options for various modes of travel.
Figure 6.14: Each of the available modes of travel is associated with at least one route.
Credit: Google Maps

Which mode of travel would you choose?

Sometimes routes have more than one destination and several stops must be made during a trip. This is a complex special case of routing called the traveling salesman problem. School bus dispatchers, mail and package delivery service managers, and food and beverage distributors all seek to minimize the transportation costs involved in servicing multiple, dispersed destinations. Choosing the optimal route requires very sophisticated analysis to evaluate all possible routes, keeping in mind speed limits, typical traffic volumes, one-way streets, and other characteristics of the transportation network. As the number of destinations and the costs of travel increase, the high cost of purchasing up-to-date, properly attributed network data becomes easier to justify.