12. Delivering Products and Services

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 files 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 files. Street segments are represented as digital line segments each formed by two points, a "from" node and a "to" 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 begins and ends 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 requires data about the connectivity of features. As discussed earlier, connectivity is an example of a topological relationship. Such data are included in TIGER/Line files, and in comparable proprietary products.

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.

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.

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.