The Nature of Geographic Information

11. Delivering Products and Services

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. Although shortest path algorithms were originally implemented in raster frameworks, transportation networks are now typically represented with vector feature data, like TIGER/Line Shapefiles. Street segments are represented as digital line segments each formed by two points, a "start" node and an "end" node. 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 begin and end at the specified locations. The sequence of segments associated with the smallest sum represents the shortest route.

To compare various possible sequences of segments, 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.

Screenshot of MapQuest 1998
Figure 4.12.1 Input form for an early version of the MapQuest routing utility.
© 1998 MapQuest.com, Inc. All rights reserved.

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.

Screenshot of MapQuest options window
Figure 4.12.2 An early interface to MapQuest's routing options. Different algorithms are required to calculate shortest and fastest routes. Specific attributes must be encoded in the database to provide the options to avoid limited access highways, toll roads, and ferry lanes.
© 1998 MapQuest.com, Inc. All rights reserved.

The shortest route is not always the best. In the context of emergency medical services, for example, the fastest route is preferred, even if it entails longer distances than others. To determine fastest routes, additional attribute data must be encoded, such as speed limits, traffic volumes, one way streets, and other characteristics.

Screenshot of MapQuest maps
Figure 4.12.3 MapQuest routing solution.
© 1998 MapQuest.com, Inc. All rights reserved.

Then there are routing problems that involve multiple destinations--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. 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.

Try This!

The Georgia Institute of Technology publishes an extensive collection of resources about the Traveling Salesman Problem. Go to this site: http://www.gatech.edu/ and type traveling salesman in the Search slot.

Penn State logo
This textbook is used as a resource in Penn State's Online Geospatial Education online degree and certificate programs. If this topic is interesting to you and you want to learn more about online GIS and GEOINT education at Penn State, check out our Geospatial Education Program Office.