New Trends and Applications in GIS Based Routing

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.

Typically WFMS operate to support other enterprise solutions one common example would the case of OMS (Outage Management Systems) in a utility company setting OMS systems are designed to utilize spatial networks to predict the location and potential scope of a reported outage. Incoming trouble calls received from a customer care system are utilized by the OMS in conjunction with the spatial network data supplied by the GIS to infer the extent and location of an outage. Dispatchers will assign or dispatch the job to the WFMS for scheduling, routing, and crew (work force) management. (Schultz 2002) It is interesting to note that GIS routing plays a role in both the WFMS and the OMS functionality. Figure 1 illustrates the relationships between these systems.

Figure 1 OMS/GIS/WFMS Interdependence
Other GIS Routing Applications
There are many other types of applications out there, which are exploiting routing technology. Some of these are not necessarily GIS based but are included here for completeness. Some of this applications are simple in that the routing part comprises the bulk of the application and therefore the system is much simpler and self contained, others are more complex and the routing aspect is only one component of a multi tiered / multi component system. Table 1 summarizes various routing applications.

Function	Application	Description
Routing and	Delivery	Use gis routing and scheduling for delivery
Scheduling		applications
Routing	Onboard Navigation	Use gis routing in conjunction with GPS for path finding and navigation
Routing	Pipeline construction	Use GIS based routing with distance and gradient constraints to optimally locate route
Static routing	Meter reading	Can also incorporate wireless communication for ‘drive by’ meter reading. These routes tend to be quite static
Routing	Circuit board layout	Circuit boards do have an inherent spatial component and the most optimal (shortest path)circuit design will be the one that yields the highest number of devices per board
Single path routing	Personal direction finder	Web applications utilize simple single path route solver as a personal direction finder

GIS Based Routing in Simulation and Research
The examples presented so far describe systems and applications that have been implemented and deployed to optimize work, which is done routinely. The solution is optimized for the problem domain and the system operates under certain assumptions pertinent to the application domain. GIS based routing is also being used in research on problems that are not well understood and where it is believed that a constraint based route solver can simplify the models. For example some researchers have modeled complex channel flow (streams, and rivers) using routing algorithms in places where a complete fluid dynamics approach would be to complex. (Beven 1993)

Theory
A review of the theoretical aspects of GIS based routing systems is worthwhile and will help us implement more efficient systems. All routing systems have the following common characteristics:

They problems be described and solved with graph theory
The problems are algorithmic in nature
Their solution will typically involve heuristics and constraints

A brief discussion of these aspects will provide us with a good theoretical framework for understanding the internals of routing solutions.

Graph Theory
Routing applications are modern day implementations of the classic ‘Traveling salesman’ problem which simply stated is ‘ Given a series of cities or stopping points how does the traveling salesman visit all of the cities using the most direct ‘shortest distance’ route possible? What may seem surprising is that this problem is essentially one that can best be described and solved in the domain of Graph Theory. Which is a formal approach for expressing and solving discrete mathematical problems pertaining to efficient searching and traversing weighted nodes on a tree or graph. What maybe even more surprising to some is that routing problems exist which are independent of the geographic or spatial domain and that routing problems in general can be ‘abstracted’ in such a way where there solution can be understood in a more general context. In other words the distance between nodes is just another constraint which the routing algorithm must handle. Graph theory provides a framework through which efficient algorithms for all sorts of problems ranging from path finding to data compression can be built.

Review of Algorithms
The following examples are a sampling of routing algorithms in use today. An algorithm can be defined as A detailed sequence of actions to perform to accomplish some task. An algorithm must reach a result after a finite number of steps. The word algorithm is named after a famed Middle Eastern mathematician Al-Kwarizmi. It is interesting to note that the shortest path ‘traveling salesman’ problem is one that has intrigued finite mathematicians for years and there are today literally hundreds of algorithms, which supposedly solve the problem efficiently. This is not surprising in that in discrete combinatorial mathematics it is possible to find many solutions to a given problem, however some are more efficient than others. The following examples explain routing systems from the perspective of the algorithms behind them.

B. Dykstra’s shortest path algorithm
Perhaps the best well-known solution to this problem was the one proposed by E.J. Dysktra and which is generally referred to as the Dysktra shortest path algorithm. The algorithm finds the solution for finding the shortest distance between a point on a graph and another destination point on the graph. A side effect of the solution is that it also finds the shortest paths to all points on the graph. The graph must include all vertices or segments and there can only be one vertex between any two edges (nodes). The following exposition of the algorithm is from (Grimaldi 1999).

The basic mode of operation is:

Initialize d and pi,
Set S to empty,
While there are still vertices in V-S,

Sort the vertices in V-S according to the current best estimate of their distance from the source,
Add u, the closest vertex in V-S, to S,
Relax all the vertices still in V-S connected to u

Relaxation:
The relaxation process updates the costs of all the vertices, v, connected to a vertex, u, if we could improve the best estimate of the shortest path to v by including (u,v) in the path to v.

The relaxation procedure proceeds as follows:

initialise_single_source( Graph g, Node s )
for each vertex v in Vertices( g )
g.d[v] := infinity
g.pi[v] := nil
g.d[s] := 0;

This sets up the graph so that each node has no predecessor (pi[v] = nil) and the estimates of the cost (distance) of each node from the source (d[v]) are infinite, except for the source node itself (d[s] = 0). The relaxation procedure checks whether the current best estimate of the shortest distance to v (d[v]) can be improved by going through u (i.e. by making u the predecessor of v):

relax( Node u, Node v, double w[][] )
if d[v] > d[u] + w[u,v] then
d[v] := d[u] + w[u,v]
pi[v] := u

The algorithm itself is now:

shortest_paths( Graph g, Node s )
initialise_single_source( g, s )
S := { 0 } /* Make S empty */
Q := Vertices( g ) /* Put the vertices in a PQ */
while not Empty(Q)
u := ExtractCheapest( Q );
AddNode( S, u ); /* Add u to S */
for each vertex v in Adjacent( u )
relax( u, v, w )

The Simulated Annealing Algorithm
More recently researchers have found that efficient algorithms can be found when one looks at natural processes for inspiration. It seems that in the natural world efficient analogues exist for every imaginable process. A case in point is the SA (Simulated Annealing) algorithm At first glance the SA algorithm seems far removed and incompatible with the problem routing or shortest path. The algorithm gets its name from the phenomena in physical chemistry known as annealing which is the process of crystalline reorganization that a metal undergoes as it slowly cools. Initially the molten metal is in a highly disordered state characterized by a high energy (entropy), as the metal slowly cools and the atoms begin to arrange themselves in ordered crystalline lattices the overall energy declines. The SA algorithm begins with an initial configuration with energy E₀. Each subsequent iteration involves performing a small random perturbation to the current configuration i (with associated energy E_i), then the energy, E_j, of the resulting configuration j is calculated. If the change in energy E'' = E_j - E_i <= 0, the configuration j is accepted with probability 1 and becomes the current configuration of the next iteration. If E'' > 0, then configuration j_i is accepted. Hence the current configuration j corresponds to the overall routing solution, which yields the lowest energy value E_j (Bucci 2001).

Genetic Algorithms
Another novel approach in routing algorithm research exploits the concept of genetic algorithms (GA). GA mimics evolutionary biology and the idea of natural selection. The GA uses the concept of solution states encoded as binary-valued strings where a bit is analogous to a gene and the string is analogous to a chromosome. Although complete elaboration of a genetic based routing algorithm is beyond the scope of this paper, the following outline from (Goldberg 1989) presents a basic methodology :

A set (i.e., population) of candidate solution states (i.e., chromosomes) is randomly generated and evaluated.
A fitness function is used to evaluate each of the solutions in the population.
The chromosomes encoding the better solutions are broken apart and recombined through the use of genetic operators such as cross-over, mutation, and recombination to form new solutions (i.e., offspring) which are generally better or more fit than the previous iteration (i.e., generation)
The process is repeated until an acceptable solution is found within specific time constraints.

Swarm Based Algorithms
Swarm intelligent behaviour as seen in insect colonies where an overall intelligent, optimizing behaviour arises out of the simple actions of local autonomous agents (individual ants) offers the most unique model for the development of cooperative, agent based adaptive algorithms. The routing / shortest path problem is ideally suited for this approach because it is one which ant colonies will routinely solve as a result of their swarm based cooperative habits. A natural communication feedback system exists between the ants and their environment known as stigmergy, which is defined as communication through the environment.

Scout or lead Ants release pheromones trails in response to favorable environmental conditions encountered (low slope, no obstacles, good travel time, etc)
Neighboring ants can detect and follow the pheromone trail releasing their own in a positive feedback loop
As more ants pick up the pheromone scent and follow it, the pheromone trail becomes stronger as the new ants reinforce it.
Eventually the entire colony moves optimally as if it where guided.
The guidance comes in the form of localized, adaptive behaviour by individual agents, which are quickly communicated, to other members of the colony.

To illustrate how this could be implemented, the following is from a system known as AntNet (Di Caro and Dorigo 1998). Only the stigmergy – feedback aspects of the algorithm are presented.

Each network node launches forward ants (agents) to all destinations in regular time intervals.

Figure 2: Forward and Backward Propagating Ant Agents
Swarm based algorithms have proven to be effective in solving problems in communications network management such as dynamic routing and load balancing It is important to note that modern communications networks are very much analogous to a hive in that routers and switches can provide feedback about local conditions (bandwidth, hop counts, etc) What is most interesting here from the vantage point of GIS is that research is currently underway to apply these types of algorithms in the area of air and ground traffic control. It is envisioned that as traffic densities increase and as the deployment of onboard GPS with computing and communications capabilities continues to increase swarm based adaptive solutions to traffic control problems will become both a reality and a necessity.

Conclusions
This paper has shown to us some of the various solutions and options available in the realm of GIS based routing applications. A review theory behind routing algorithm has also been presented, as well as the current research initiative in the field. From the vantage point of the integrator who is in the process of either selecting or implementing an enterprise solution this information presented serves the purpose of exposing the reader to the variety of options that are available and possible.

Application
development has become more streamlined in recent years with the advent of component based object technologies. It is now possible to acquire constraint based routing engines in a component object form. Such components encapsulate years of research and provide the integrator-developer with the capability to implement efficient solutions to complex logistical problems.

References
Beven, K.J. & Kirkby, M.J. (Eds.) Channel Network Hydrology.., John Wiley & Sons, Chichester. 1993,319 pp.

Bonabeau, E., Dorigo, M., and Théraulaz, G., Swarm intelligence: from natural to artificial systems, Oxford University Press, 1999.

Bucci, Mark, Optimization with Simulated Annealing, C/C++ Users Journal, Vol. 19, No. 11, Nov 2001, pp10-27.

Di Caro, G., and Dorigo, M., AntNet: distributed stigmergetic control for communications networks", Journal of Artificial Intelligence Research, vol. 9, pp. 317-365, 1998.

Gambardella, L.M., and Dorigo, M., Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem, Proc. Twelfth International Conference on Machine Learning, Tahoe City, CA, pp. 252-260, 1995.

Goldberg, D., E., Genetic Algorithms in Searching Optimization and Machine Learning, Addison Wesley, 1989.

Grimaldi, R., Discrete and Combinatorial Mathematics: An Applied Introduction. Addison Wesley, 1999, 896pp

Gunton, N., SOAP: Simplifying Distributed Development, Dr. Dobb’s Journal, #328, September 2001, pp 89-95.

. Laarhoven, P.J.M and. Aaarts, E.H.L, Simulated Annealing: Theory and Application, Reidel Publishing, 1987, 200 pp.

MDSI, Wireless Empowerment and Single Source Simplicity, April 2001,11pp Motorola, 1995, Wireless Data Communications: An Overview, 16 pp.

Oida, K., and. Sekido, M., An agent-based routing system for QoS guarantees, Proc. IEEE

International Conference on Systems, Man, and Cybernetics, Oct. 12-15, pp. 833-838, 1999