4 2004 
  
1g Out 
ontain 
d into 
orced, 
urrent 
and/or 
ns and 
on the 
For 
traffic 
ct the 
rected 
ils are 
on= | 
until 
  
ficant 
search 
enting 
onally 
tation 
ithout 
of the 
genes 
m. À 
es of 
which 
route 
A and 
route, 
ase of 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B2. Istanbul 2004 
Penalties for violations are defined for each constraint. An 
amenity can be calculated from a penalty if the route violates 
constraints. 
We regard the route with the lowest number of penalties as the 
best one for drivers. 
4.3. Population initialization 
In general, there are two issues to be considered for population 
initialization of GA: the initial population size and the 
procedure to initialize population (Goldberg, 1989; Hue, 1997). 
It was felt that the population size needed to increase 
exponentially with the complexity of the problem (ie, the 
length of the chromosome) in order to generate good solutions. 
Recent studies have shown, however, that satisfactory results 
can be obtained with a much smaller population size. To 
summarize, a large population is quite useful, but it demands 
excessive costs in terms of both memory and time (Goldberg, 
1989; Harik, 1999). As would be expected, deciding adequate 
population size is crucial for efficiency. 
Secondly, there are two ways to generate the initial population: 
heuristic initialization and random initialization (Hue, 1997). 
In this method, we select viruses within the rectangle on the 
map with a diagonal that links the origin and the destination 
and we name them ‘main-viruses’. 
To generate the initial population, a virus is randomly selected 
from the population of viruses. Next, both the routes from the 
origin to the virus and the route from the virus to the destination 
are generated by using an RTA* algorithm (Korf, 1990). 
Finally, the route that combines these two routes with the virus 
becomes an individual. This procedure is repeated for all of the 
main viruses. 
4.4. Selection and crossover 
The selection (reproduction) operator is intended to improve the 
average quality of the population by giving the high-quality 
chromosomes a better chance to get copied into the next 
generation (Goldberg, 1989; Hue, 1997). 
Crossover examines the current solutions in order to find better 
ones (Goldberg, 1989; Hue, 1997). Physically, crossover in the 
routing problems plays the role of exchanging each partial route 
of the two chosen chromosomes in such a manner that the 
offspring produced by the crossover will only be one route. 
This dictates selection of one-point crossover as a good 
candidate scheme for the proposed GA. One partial route 
connects the source node to an intermediate node and the other 
partial route connects the intermediate node to the destination 
node. But the mechanism of the crossover is not the same as 
that of the conventional one-point crossover. 
In the proposed scheme, we use the minimal generation gap 
(MGG) model (Satoh et al, 1996; Ono et al., 1999) for 
alternation of generations. In this model, two routes are 
replaced by crossover with each new generation and so two 
evaluations of fitness are required between generations. 
Mutation is not used in this method (Figure 2). 
  
Selection for 
Reproduction 
Randomly 
  
Generation of 
Children by 
Crossover 
    
Selection for 
Survival 
Elite + Roulette 
  
  
Figure 2. Minimal Generation Gap (MGG) model 
Here are the directions for the process. 
e Take two individuals at random from the 
population for use as parents. 
e Apply simple crossover to the parents to produce 
offspring, where the crossover site is at an 
intersection which they have in common. If there 
is no such common intersection, then go to the 
previous step. 
* [rom the parents and their children, we select 
the best individual (elite route) and the random 
one using the roulette wheel technique. With 
them the original parents are replaced. 
In this model, original parents are two individuals, and 
replacing individuals are also two. Then we leave the elite 
individual for progress in solving a problem, and leave a 
random individual for maintaining diversity of population. It 
should also be noted that this model only uses fitness values of 
each individual. It makes the computational load of the 
operation light. 
5. EXPERIMENTS 
To evaluate the performance of the outlined method, we 
performed experiments using actual road maps of Tehran at a 
scale of 1:2000 provided by Miaad Andisheh Saz, Research and 
Development Company, in Iran. 
Table 1 shows the characteristics of the maps used in the 
following experiments, where the nodes correspond to the 
intersections and Table 2 shows the experimental results 
achieved from the map. In addition, each result given bellow 
was performed on AMD Athlon(tm) XP 1600+ (1.40 GHz), 
(Figures 3 and 4). 
Table 1. Characteristics of the map used 
  
Number of viruses 
Number of links Number of nodes 
  
Map 121 
  
  
3993 3071 
  
  
07