INTRODUCTION
Vehicle Routing Problem (VRP) is often faced by distribution and logistictransportation
companies. Usually many companies use classical deterministic VRP models
on their routing that do not capture an important aspect of real life
problems. In real life problems, the parameters (demand, time, city location,
etc.) are often stochastic or random. It is appropriate to model the stochasticity
of real world situation by using VRP with Stochastic Demands (VRPSD) model
to produce better routes and reduce cost. In VRPSD, the customer demands
are unknown until the vehicle arrives at customer locations but it is
assumed to follow a specific probability distribution according to the
past customer demands behaviour. One of the applications is in the case
of a solid waste collection problem where it is impossible to know the
exact amount of garbage to be collected at the time when the route is
planned.
In stochastic environment, due to its randomness in customers` demands,
a vehicle capacity may be exceeded during service. A route failure is
said to occur if the demand exceeds capacity and a recourse action needs
to be taken. Assuming that enough capacity is available at the depot,
the vehicle may return to the depot, replenish its load and then resume
service at the point where failure occurred. Therefore the vehicle will
always be able to satisfy all demands and the length of the corresponding
tour becomes a random quantity. In the literature, VRPSD has been studied
under two distinct approaches. The recourse action could be the vehicle
resumes service along the planned route, namely a priori approach, or
visiting the remaining customers possibly in an order that differs from
the planned sequence that is called reoptimization approach. There are
two common recourse policies for a priori optimization. The first is the
simple recourse policy (Gendreau et al., 1995; Chepuri and HomemdeMello,
2005), a vehicle returns to the depot to restock when its capacity becomes
attained or exceeded. In the second approach (Bertsimas et al.,
1995; Yang et al., 2000; Bianchi et al., 2004), preventive
restocking is planned at strategic points preferably when the vehicle
is near to the depot and its capacity is almost empty, along the scheduled
route instead of waiting for route failure to occur. On the other hand,
two most recent computational studies in reoptimization approach are
done by Secomandi (2001, 2003).
Stochastic VRPs are considerably more intricate and very time consuming
than the deterministic one. It requires the development of new ideas and
algorithm that can solve problem in realistic time and reasonable solution
quality. The class of VRPs being addressed is a difficult one, since its
elements are usually NPhard problems. They are generally solved by heuristic
methods (Secomandi, 2003). Beside the work of Bianchi et al. (2004),
the work on the application of GA in VRPSD is very lacking in the literature,
although as known for many years, GA has been successfully used in a wide
variety of problem domains including VRP. In majority of GA implementation,
the operator settings are remaining static during the GA run. However,
some existing works found were showed that varying GA settings during
the GA application can lead to improvement of GA performance. Herrera
and Lozano (1996) have reviewed many aspects of the adaptation of GA parameters
settings such as mutation probability (pm), crossover probability (pc)
and population size (N).
The awareness of the importance of mutation is growing within the evolutionary
algorithm community and interest is increasing in a closer consideration
of its features (De Falco et al., 2002). Mutation operator may
be considered to be an important element in GA for solving the premature
convergence problem, since, it serves to create random diversity in the
population. If the lack of population diversity takes place too early,
a premature stagnation of the search is caused. Under these circumstances,
the search is likely to be trapped in a local optimum before the global
optimum is found. Most approaches adapt pm along with other GA parameters
(Lee and Takagi, 1993; Srinivas and Patnaik, 1994; Sugisaka and Fan, 2001;
MeiYi et al., 2004; Xing et al., 2007) and so, the specific
effects of the adaptation of pm alone were not studied. Lee and Takagi
(1993) presented experimental study which was aimed at isolating the effects
of the adaptation by Fuzzy Logic Controllers of N, pc and pm. It showed
that the adaptation of pm contributes most to high performance.
A timedependency of pm was first suggested by Holland (1992) although
he did not give a detailed choice of the parameter for the timedependent
reduction of pm. The idea of sustaining genetic diversity through mutation
is then developed by measuring the Hamming distance between the two parents
during reproduction. One of it was done by Herrera and Lozano (1996) using
the adaptive control of pm by Fuzzy Logic Controllers. Reeves (1995) used
adaptive mutation rate allowing high mutation rate and slowly decreased
as long as a reasonably diverse population exists. Liu and Feng (2004)
presented a modified GA based on tuning of pm by the value of individual
fitness. The modified GA implements mutation first, after that crossover.
This study contributes mainly on presenting an adaptive GA based on diversity
measures for a priori VRPSD. We also proposed a new adaptive mutation
probability based on Lr distance measure. The performance of several adaptive
mutation probability types on VRPSD was also studied for the first time.
In this study, the VRPSD recourse action is under restocking policy.
VEHICLE ROUTING PROBLEM WITH STOCHASTIC DEMANDS
The VRPSD is defined on a complete graph:
Where:
V 
= 
{0, 1,. .., n} is a set of nodes with node 0 denotes the depot
and nodes 1, 2, ..., n correspond to the customers, 
A 
= 
{(i, j) : i, j ∈ V, i ≠ j} is the set of arcs joining the
nodes,and a nonnegative matrix 
C 
= 
{c_{ij} : i, j ∈ V, i ≠ j} denotes the travel costs
(distances) between node i and j. 
The cost matrix C is symmetric and satisfies the triangular inequality.
Customers have stochastic demands ξ_{i}, i = 1,..., n which
follows known probability distributions p_{ik} = pr ob(ξ_{i}
= k), k = 0, 1, 2, ..., K. Assume further that customers` demands are
independent. Actual demand of each customer is only known when the vehicle
arrives at the customer location. A feasible solution to the VRPSD is
a permutation of the customers s = (s(1), s(2),. .., s(n)) starting at
the depot (that is, s(1) = 0) and it is called a priori tour. Let 0 →1
→2 ... j →j+1 ... →n be a particular vehicle route. Upon
the service completion at customer j, suppose the vehicle has a remaining
load q (or the residual capacity of the vehicle after having serviced
customer j) and let f_{j}(q) denote the total expected cost from
node j onward. If S_{j} represents the set of all possible loads
that a vehicle can have after service completion at customer j, then,
f_{j}(q) for q ∈ S_{j} satisfies:
Where:
with the boundary condition:
In Eq. 24,
represents the expected cost of going directly to the next node, whereas
represents the expected cost of the restocking action. Equation
24 are used to recursively determine the objective value of the planned
vehicle route and the optimal sequence of decisions after customers are
served (Bianchi et al., 2004). In principle, this procedure leads
to a dynamic programming since each time a customer demand is revealed,
a decision has to be taken as to where the vehicle should proceed.
The expected costtogo in case of restocking, is constant in q,
since in case of restocking the vehicle will have full capacity Q before
serving the next customer, whatever the current capacity q is. On the
other hand,
is a monotonically nonincreasing function in q, for every fixed customer
j. Therefore there is a capacity threshold value h_{j} such that,
if the vehicle has more than this value of residual goods, then the best
policy is to proceed to the next planned customer, otherwise it is better
to go back to the depot for replenish (Yang et al., 2000).
DATA
VRPSD application is considered in the solid waste collection problem
of residential area in Malaysia. The problem of optimization of waste
collection can be described as follows. The solid waste is located in
box or containers along the streets and they must be all collected by
a fleet of vehicles whose capacity can not be exceeded. Each vehicle can
service several such sites before going to dumpsite to unload. Each vehicle
starts from the depot, visits a number of stops and ends at the depot.
When a vehicle is full, it needs to go to the closest available dumpsite
to empty its load and then resume their visit. Each vehicle can make multiple
disposal trips per day.
Based on experiments reported in Gendreau et al. (1995), three
factors seem to impact the difficulty of a given VRP instances: number
of customers` n, number of vehicles m and filling coefficient f. In a
stochastic environment, the filling coefficient can be defined as:
where, E(ξ_{i}) is the expected demand of customer i and
Q denotes the vehicle capacity. This is the measure of the total amount
of expected demand relative to vehicle capacity and can be approximately
interpreted as the expected number of loads per vehicle needed to serve
all customers. In this experiment, the value of f is 1.1.
A set of data are randomly generated to simulate this problem of waste
collection. n nodes are generated in the [0,100]^{2} square according
to a continuous uniform distribution. Nodes are first assigned to a specific
three demand range in equal probabilities. Three ranges of demand present
low, medium and high solid waste weight. The value of each demand is then
generated in the appropriate range according to a discrete uniform distribution.
The sample size of number of nodes and associates demand ranges are described:
• 
Small sample size: n = 10 and n = 15, Demand range: (1, 3),
(2, 4), (3, 5) 
• 
Larger sample size: n = 20, n = 30 and n = 50, Demand range:
(1, 5), (6, 10), (11, 15) 
THE PROPOSED GENETIC ALGORITHM
The important details of the Genetic Algorithm are outline below.
Step 0: 
(Define): Define operator settings of GA suitable with the
problem which is VRPSD. 
Step 1: 
(Initialize): Create an initial population P of N chromosomes
that consists of constructive heuristics solutions and randomly mutation
of it where all individuals are distinct or clones are forbidden. 
Step 2: 
(Fitness): Evaluate the fitness f(C_{i}) of each
chromosome C_{i} in the population. The fitness is the function
of VRPSD objective function. 
Step 3: 
(Selection): Apply Roulette Wheel Selection. This gives the
set of Mating Population M with size N. 
Step 4: 
(Crossover): Pair all the chromosomes in M at random forming
N/2 pairs. Apply crossover with probability pc to each pair and form
N chromosomes of offspring, if random number ≥ pc then offspring
is the exact copy of parents. 
Step 5: 
(Mutation): With a mutation probability pm mutate the offspring. 
Step 6: 
(Replace): Evaluate fitness of parents and new offspring.
Choose the best N chromosomes. Replace the old population with newly
generated population. 
Step 7: 
(Test): If the stopping criterion is met then stop and return
to the best solution in current population, else go to step 2. 

Fig. 1: 
Illustration of order representation 
Chromosome representation: In developing the algorithm, the permutation
representation or the path representation or order representation is used
since the typical approach using binary strings will simply make coding
more difficult. Order representation is perhaps the most natural and useful
representation of a VRP tour, where customers are listed in the order
in which they are visited. A chromosome represents a route and a gene
represents a customer and the values of genes are called alleles. The
search space for this representation is the set of permutations of the
customers; every chromosome is a string of numbers that represent a position
in a sequence. Order representation can be described as shown in Fig.
1.
Initialization: Usually, the initial population of candidate solutions
is generated randomly across the search space. However, other information
can be easily incorporated to yield better results. The inclusion of good
heuristic in initial solution is stated as Prins (2004) by using Clarke
and Wright, Mole and Jameson and Gillett and Miller heuristics for solving
distanceconstrained VRP (DVRP) instances. In this study, Nearest Neighbour
(NN) and Farthest Insertion (FI) is included to the initial solution and
the rest are the mutation results of NN and FI. The population is an array
P of N (population size) chromosomes. Each chromosome P_{k} is
initialized as a permutation of customers. Clones (identical solutions)
are forbidden in P to ensure a better dispersal of solutions and to diminish
the risk of premature convergence.
The population size is one of the important factors affecting the performance
of genetic algorithm. Small population size might lead to premature convergence.
On the other hand, large population size leads to unnecessary expenditure
of valuable computational time. Prins (2004) stated that population size
< 25 or > 50 will give moderate degradation of the average solution
and found that population size equal to 30 performs best.
Evaluation: Once the population is initialized or an offspring
population is created, the fitness values of candidate solutions are evaluated.
The fitness value is the function of VRPSD objective function. The lower
the VRPSD objective function means the higher the fitness of solution.
Roulette Wheel Selection with elitism: This research employs the
combination of two types of GA selection techniques, namely roulette wheel
and elitism. The roulette wheel selection works by selecting the chromosome
by looking at their proportional fitness rank. This is where the evolution
concept survival of the fittest comes into plays. Some researchers found
that this technique will lead to only the best chromosome been selected
in the population. It because the fittest chromosome rank is bigger compared
to the less fit chromosome and in probability of course chromosome with
the highest rate will have a big chance to be selected, while the elitism
technique is a simple selection operator, which reserved the best found
chromosome in the current population to rebirth for the next generation.
Mitchell (1996) said that elitism could increase rapidly the performance
of genetic algorithm, because it prevents losing the bestfound solution.
When creating a new generation using the reproduction operator, we could
have a chance of losing the bestfound chromosome in the current population.
This is where elitism plays their role in preventing the lost of this
chromosome. In this example, after the calculation for each selection
chromosome probability has been done, the elitism operator will automatically
reserved the chromosome that produce the lowest expected cost.
Order Crossover (OX): Oliver et al. (1987) applied Partially
Match Crossover (PMX), Cycle Crossover (CX) and Order Crossover (OX) to
the 30city problem of Hopfield and Tank. They found that the best tour
generated with OX was 11% shorter than the best PMX tour and 15% shorter
than the best CX tour. In a later study by Starkweather et al.
(1991), six different crossover operators were tested on the problem of
Hopfield and Tank. Thirty different runs were performed with each operator.
In this experiment, OX found the optimum 25 times (out of 30), while PMX
found the optimum only once and CX never found the optimum.
Thus in this study, OX was employed in the generation of offspring. OX
was first proposed by Oliver et al. (1987). This crossover operator
extends the modified crossover of Davis (1991) by allowing two cut points
to be randomly chosen on the parent chromosomes. In order to create an
offspring, the string between the two cut points in the first parent is
first copied to the offspring. Then, the remaining positions are filled
by considering the sequence of cities in the second parent, starting after
the second cut point (when the end of the chromosome is reached, the sequence
continues at position 1). The pc is set to be 0.6 as used by Jerald et
al. (2006).
Mutation: Mutation alters one or more genes (positions) of a selected
chromosome (solution) to reintroduce lost genetic material and introduce
some extra variability into the population. The role of mutation in GAs
has been that of restoring lost or unexplored genetic material into the
population to prevent premature convergence of the GA sub optimal solutions
(Laoufi, 2006; Zuhaimy and Irhamah, 2007). As opposed to the classical
mutation operator, which introduces small perturbations into the chromosome,
the permutation operators for the VRP and or TSP often greatly modify
the original tour. In this study, we implement swap mutation.
The choice of probability of mutation is known to critically affect the behaviour
and performance of the GA. Increasing the value of pc and pm promote exploration
at the expense of exploitation. The moderately large values of pc promote the
extensive recombination of schemata, while small values of pm are necessary
to prevent the disruption of the solutions. Several schemes of mutation probability
is used including fixed mutation probability and adaptive ones. In fixed mutation
probability, the mutation probability remains the same from generation to the
next generation. Small values of pm (0.001 until 0.05) that commonly employed
in GA practice were implemented (Davis, 1991).
Stopping criterion: In using the optimization algorithms, the
goal is to search for the global optimum and it should be found. However,
in general it is not clear when the goal is achieved especially in our
application in the real world situation. Therefore, it is sometimes not
that easy to decide when execution of an optimization algorithm should
be terminated. There are many different mechanisms can be used for the
detection of an appropriate time for ending an optimization run and one
of the commonly used mechanism is the setting of a maximum number of generation.
The GA procedure is repeated until the maximum number of generation set
in the algorithm (which may be adjusted).
ADAPTIVE MUTATION PROBABILITY
Adaptation of operator probabilities is an attempt to make the Genetic
Algorithm a more effective optimizer. In this study, we compare the performance
of several schemes of adaptive mutation probability as follows:
Mutation probability is random numbers in the range of [pm_{min},
pm_{max}]: Mutation probability is dynamically changed in
the range of [0.001, 0.05] during the generations.
Adaptive mutation probability based on PDM: Lee and Takagi (1993)
propose two Phenotypic Diversity Measure (PDM) performance measures:
PDM_{1} and PDM_{2} belong to the interval [0, 1]. If
they are near to 1, convergence has been reached, whereas if they are
near to 0, the population shows a high level of diversity.
Adaptive mutation probability based on Euclidean distance: Herrera
and Lozano (1996) proposed Genotypic Diversity Measure (GDM) based on
Euclidean distances of the chromosomes in the population from the best
one. The GDM is denoted by ED.
where, , ,
d_{min} = min{d(C_{best}, C_{i})}C_{i}
is chromosome in population with Euclidean distance .
The range of ED is [0, 1]. If ED is low, most chromosomes in the population
are concentrated around the best chromosome and so convergence is achieved.
Lee and Takagi (1993) and Herrera and Lozano (1996) were proposed the
use of Fuzzy Logic Controller to dynamically control the mutation probability.
But in this study we rather use simple linear formula of pm = PDM_{1}
or pm = PDM_{2 }and pm = 1ED. These formula are used since the
value of PDM_{1}, PDM_{2} and ED are in the range of [0,
1] as the mutation probability. The nearer to the convergence is shown
by higher PDM_{1}, higher PDM_{2} (nearer to 1) and lower
ED (nearer to 0) that each requires higher pm, higher pm and lower pm,
respectively. But since we attempt to compare performance of algorithms,
we have considered that these techniques should handle the same range
of possible pm values in the range of [0.001, 0.1]. So, a transformation
was made from the interval considered by these techniques into [0.001,
0.1]. Beside the above measures, we also propose new adaptive mutation
probability as below.
Adaptive mutation probability based on Lr distance: Another diversity
measure is provided which is based on Lr distance that usually used to
measure dissimilarity between two objects. Formula is proposed by Herrera
and Lozano (1996) by substituting the ED with LD where Lr distance between
two objects is. Then pm = 1LD.
RESULTS AND DISCUSSION
Table 1 shows the result obtained based on performance:
average of the best fitness function found at the end of each run. We
executed all the algorithms for 10 times and 50 iterations for each run.
Regarding to the GA versions under fixed pm values, we may underline
fact that the best performance measures for each problem set are reached
with different pm values:
For n = 10 
: 
pm = 0.01 
For n = 15 
: 
pm = 0.05 
For n = 20 
: 
pm = 0.1 
For n = 50 
: 
pm = 0.001 
whereas, for n = 30, the result of all fixed pm values are the same.
Now, considering the performance between fixed versus adaptive mutation
probability, we may observe that adaptive algorithms leads in better solution
quality rather than fixed parameter, since for each problem set, it returns
results that better than all fixed pm values, or the same as the ones
of the most successful GAs with fixed pm settings (the case of n = 15
and n = 50). The adaptive scheme plays a role in improving solution quality
and possibly directing search to unknown regions to avoid being trapped
in local optimum. By using the adaptive GA, the amount of time to spend
in finding appropriate mutation probability values of GA can be reduced.
From the results it can also be deduced that different AGAs are better
suited to different problem sets. Compare to other adaptive schemes, PDM_{1}
showed superiority since it can find best performance measure for 2 (two)
problem set, while if we compare it to fixed pm, the lowest values of
VRPSD objective function from PDM_{1} were still lower than that
can be resulted from all fixed pm setting, or the same with fixed pm results
like in the case of n = 15. The proposed LD measure was proven to yield
best performance measure among other diversity measure on the problem
set n = 15, its performance was also quite good on the n = 20, 30 and
50 but performs worst in n = 10.
Table 1: 
Performance of fixed parameter vs adaptive GA 


Fig. 2: 
Search process of several AGAs in n = 20 
The illustration of search process of
several adaptive GAs on problem set n = 20 is shown in Fig.
2. It is observed that PDM_{2} was better than the others
and had nearly the same convergence with PDM_{1} and LD after
40 iterations.
CONCLUSIONS
A Genetic Algorithm (GA) approach as a solution to the VRP with Stochastic
demands under restocking policy was designed and presented. The GA does
exhibit a very good performance when suitable combinations of operator
parameters were used. The amount of time required to examine several combinations
of parameters especially in mutation probability can be reduced significantly
by using the proposed adaptive mutation probability scheme. When compared
with the solution generated using fixed pm values, the adaptive GA does
produce a better solution quality. On the other hand, based on the different
performances of the various AGAs, it was found that different adaptation
mechanisms are better suited to different problems. Future work should
be directed towards the development of other adaptive scheme that allows
for the integration of these diversity measures with the fitness of every
individual.
ACKNOWLEDGMENTS
The research is supported by IRPA Grant Vote No. 74285 from Ministry
of Science, Technology and Innovation (MOSTI), Malaysia. The authors would
like to thank MOSTI, Research Management Centre (RMC) and Universiti Teknologi
Malaysia. The authors also wish to thank lecturers and friends for many
helpful ideas and discussion. We also wish to thank Perniagaan Zawiyah
Sdn. Bhd. Johor Bahru, Malaysia for providing necessary data in this study.