New Trends and Applications in GIS Based Routing

Printer Friendly Format

Page 3 of 3
| Previous |

New Trends and Applications in GIS Based Routing

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