oul 2004 
A GIS-Assisted Optimal Urban Route Finding Approach Based On Genetic Algorithms 
M. R. Delavar, F. Samadzadegan, P. Pahlavani 
Dept. of Surveying and Geomatics, Faculty of Engineering, University of Tehran, Tehran, Iran - (mdelavar, samadz, 
ppahlavani)@ut.ac.ir 
Commission II, Working Group II/5 
KEY WORDS: GIS, SDSS, Genetic Algorithm, Route Finding, Vehicle Routing Problem 
ABSTRACT: 
Network analysis in geospatial information system (GIS) provides strong decision support for users in searching 
optimal route, finding the nearest facility and determining the service area. Searching optimal path is an important 
advanced analysis function in GIS. In present GIS route finding modules, heuristic algorithms have been used to carry 
out its search strategy. Due to the lack of global sampling in the feasible solution space, these algorithms have 
considerable possibility of being trapped into local optima. This paper addresses the problem of selecting route to a 
given destination on an actual map under a static environment. The proposed solution uses a genetic algorithm (GA). A 
part of an arterial road is regarded as a virus. We generate a population of viruses in addition to a population of routes. 
A customized method based on a genetic algorithm has been proposed and successfully implemented in an area in the 
north-east of Tehran using the optimal combination of viruses. 
1. INTRODUCTION 
Decisions are often evaluated on the basis of quality of the 
processes behind. It is in this context that geospatial 
information system (GIS) and spatial decision support system 
(SDSS) increasingly are being used to generate alternatives to 
aid decision-makers in their deliberations. The intelligent 
transport system (ITS) can carry and gather very useful 
information for delivery to users and perform other useful 
functions to deal with the travel. The 
subsystems that support the decision making to suit changing 
conditions is a logical important step in providing systems with 
improved functionalities. 
Unfortunately, GIS and SDSS typically lack formal 
mechanisms to help decision-makers explore the solution space 
of their problem and thereby challenge their assumptions about 
the number and range of options available. We describe the use 
of a genetic algorithm to generate a range of options available. 
The ability of genetic algorithms to scarch a solution space and 
selectively focus on promising combinations of criteria makes 
them ideally suited to such complex spatial decision problems. 
Routing problems in car navigation systems are search 
problems for finding an optimal route from an origin to a 
destination on a road map within a time limit. In a practical 
System, when traffic congestion changes during driving, the 
route should be re-evaluated before the car reaches the next 
intersection. A representative solution to these search problems 
is the Dijkstra algorithm (DA), (Golden, 1976). As the DA is an 
exact algorithm it always determines the optimal route but 
cannot guarantec that realistic. deadlines will be met. In 
contrast, as genetic algorithms always have solutions in a 
population during a search, they can provide alternative routes 
using other solutions in the shortest time. 
A method has been proposed in this paper for using a genctic 
algorithm to find the casiest-to-drive and quasi-shortest route to 
introduction of 
reach a destination within a given time. It can be used to 
produce and choose candidate routes that guarantee the meeting 
of deadlines and satisfy constraints regarding ease of driving. 
2. SOLVING CONSTRAINT SATISFACTION 
PROBLEMS USING GA 
Genetic algorithm is a computational model simulating the 
process of genetic selection and natural elimination in biologic 
evolution. Pioneering work in this field was conducted by 
Holland in the 1960s (Holland, 1975; Coley, 1992). 
As a high efficient search strategy for global optimization, 
genetic algorithm demonstrates favorable performance on 
solving the combinatorial optimization problems. With 
comparing to traditional search algorithms, genetic algorithm is 
able to automatically acquire and accumulate the necessary 
knowledge about the search space during its search process, and 
self-adaptively control the entire search process through 
random optimization technique. Therefore, it is more likely to 
obtain the global optimal solution without encountering the 
trouble of combinatorial explosion caused by disregarding the 
inherent knowledge within the search space. It has been used to 
solve combinatorial optimization problems and non-linear 
problems with complicated constraints or non-differentiable 
objective functions. It necessitates the application of genetic 
algorithm into GIS route finding algorithms. 
The computation of usual genetic algorithm is an iterative 
process that simulates the process of genetic selection and 
natural elimination in biologic evolution. For each iteration, 
candidate solutions are retained and ranked according to their 
quality. A fitness value is used to screen out unqualified 
solutions. Genetic operators, such as crossover, mutation, 
translocation and inversion, are then performed on those 
qualified solutions to estimate new candidate solutions of the 
next generation. The above process is carried out repeatedly 
until certain convergent condition is met.