New Trends and Applications in GIS Based Routing
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 )
