New Trends and Applications in GIS Based Routing
Tadeo H. Schultz
KEMA Consulting 101 Inverness Drive East, Suite 130
Englewood CO 80112 USA
Phone (303) 708-9355 ext 119, Fax (303) 708-9356
E-mail: tschultz@kemaconsulting.com
Abstract
GIS based routing solutions have proven to be one of the most popular and cost effective GIS
applications of recent years. Typically these systems will find a least cost path among a series of nodes
on a linear network against a series of constraints. As evidence of their popularity, is the abundance of
web based direction finders, personal navigation and routing systems and the use of routing components
in a wide variety of critical business applications such as work force management. Allocation and
optimization components, which are used to solve problems such as scheduling, can typically be found
as part of larger GIS based routing applications. Another powerful and popular combination is the
integration of GPS and vehicle tracking technology with routing components.
This paper reviews the various styles of routing solutions currently in vogue as well as the
technology behind them. Traditional approaches such as the Dykstra algorithm, which is typically used
to solve the classic ‘traveling salesman’ (least cost path) problem, are contrasted against some of the
newer developments such as the adaptive swarm-based distributed method. In addition new novel GIS
routing applications are presented, and guidelines for integrating GIS based routing components with
other systems are given.
Introduction
The ability possessed by contemporary GIS systems to determine the optimal, least cost path
amongst a series of alternate paths has been widely utilized in a variety of applications ranging from
vehicle routing and scheduling, to navigation and emergency dispatching. This paper presents the basic
theoretical underpinning of these geospatial functions and examples of their practical usage,
implementation and limitations. In addition newer methods, and applications are also discussed and
their relevance to current GIS systems is revealed.
The appeal inherent in these applications and the underlying technology is largely due to the
universality of the problem, which they attempt to solve. A large part of our daily activity and
commerce involves selecting the most optimal route. Regardless of whether our domain is scheduling
our weekend activities or scheduling the daily service calls in a telco or utility, the problem is one that
involves a spatial component. Destination points are scattered across a geographic area connected via a
linear network. In addition a temporal component such as a delivery time as well as other constraints,
may further define the problem. It has been stated that the development of maps and the concept of
abstracting the physical world down to a chart, ranks close to printing as one of man’s important
achievements. They helped to foster the subsequent eras of commerce, exploration and discovery. GIS
has added the power of digital computing infusing digital maps with a dynamic interactive capability,
giving the user access to a virtual world where he can pick from a multitude of alternate scenarios. This
is what GIS routing applications can contribute.
Applications
Application and problem domains, which concern themselves with routing, optimization, scheduling and
logistics and which also have a spatial or geographic component are candidates for GIS routing
solutions. The following discussion presents a few examples illustrating the various and distinct ways in
which this technology has been applied.
GIS based routing and scheduling in WFMS and OMS
Routing and dispatching, tasks central to all Work Force Management Systems (WFMS) are essentially
GIS problems: how to most efficiently allocate personnel across a geographic area to meet demand
(tasks). GIS technology can be used to accurately locate the tasks and personnel and to then calculate the
optimal least costs paths between tasks and personnel. The derivation of the paths along a topologically
consistent spatial network (i.e. roads) can take into account such impedance gradients as travel speed
and distance as well as other user specified constraints.
GIS based routing applications can solve the complex routing and scheduling problems, inherent in
WFMS which involve matching crews to work orders given a series of constraints, such as travel time,
distance, appointment time, as well as other user defined constraints. The routing system relies on valid
street network datasets as well as geocoding functions, (the ability to translate a street address into a
geographic coordinate location in order to designate service points.) The system will then calculate
optimal (least cost/shortest path) routes and then schedule and assign crews to routes. The results are
then typically presented in either formatted maps or reports or as part of the systems graphical display. Figure 1 shows a typical route report with the enumerated service points.
Figure 1 Service Route Map
These systems allow organizations to efficiently manage their workload by optimally matching the
work force (crews) to the load (jobs). In order to do this optimally the systems utilize constraint
based algorithms that take into account such factors as crew and job locations provided by a GIS or
GPS, skills and materials needed for the job, and other scheduling constraints. The implementation
of these solutions may vary widely depending on the number of constraints that the routing engine
must handle. More importantly mobile enabled WMS take advantage of mobile computing
equipment and sophisticated wireless communications to maintain constant voice and data links with
the dispatch centers. Typically organizations that have implemented wireless data links between
their mobile units and enterprise WFMS/OMS systems-servers are able to take advantage of a
streamlined dynamic routing solution that is called upon on an ‘as needed’ basis throughout the work
day. On the other hand, companies that must deal with a large number of operating constraints as
part of their business model will tend to implement solutions that must process all available jobs and
constraint values upfront prior to the commencement of the work day. These static routes are the
result of large batch runs, which may process hundreds perhaps thousands of service requests for
each batch operation.
