Case Studies - Vehicle Routing

Client: ESRI

Client Business Need: ESRI required development of a nationwide door-to-door routing technology able to calculate precise shortest and quickest routes between arbitrary street addresses and display comprehensive and accurate driving directions. Moreover, the solution was required to employ compressed data structures to fit the U.S. nationwide streets network of over 30 million streets with geometry, street names, and all indexes on a single CD. It was also required that the route and driving directions take only a few seconds to calculate.

In addition to simple door-to-door routing, the solution was required to be able to solve the Traveling Salesman Problem (TSP), which is optimizing the order of stops to minimize travel time or distance. Restrictions like time to spend at the specific stop had to be considered as well as start/end time for travel for a given day.

Technical Response:

In order to satisfy the data storage requirement, a highly compressed data structure for storage of the network topology with attributes was invented, which allows storing the complete streets network consisting of over 30 million links in less than 250 MB.

A complex multi-tier network model was designed to be able to account for various transportation restrictions including one-way streets, prohibited turns, bridges and tunnels. It also supports dynamic factors like road closures/accidents (network barriers), driving speed settings per each road class and road preference/avoidance flag.

The algorithm of path computation was optimized for performance on huge transportation networks like nationwide streets network. It uses several heuristic methods to be able to quickly calculate accurate routes no matter if it is a route between two neighborhoods or between the west coast and east coast.

Significant effort was spent on analysis of the source transportation network coming from major data vendors and improvement of network connectivity to make it usable for routing purposes. Sophisticated network analysis tools were designed and developed to aid in locating and fixing errors in source data.

Routing technology is implemented using C++ and COM technologies, which allows for easy integration in various applications. It also runs on multiple platforms including Windows NT and Unix servers, Windows 2000/XP desktop computers, and PocketPC mobile devices.

Client Result: Development of this leading-edge routing technology allowed ESRI to include door-to-door nationwide routing capability in a wide range of their product lines including server, desktop and mobile applications. It also can be successfully used in logistics applications as well as a backend for Location Based Services (LBS) applications.