International Conference in Distributed Computing & Internet Technology (ICDCIT-2013)

Proceedings published in International Journal of Computer Applications® (IJCA) (0975 – 8887)

A Multi-objective Vehicle Routing Problem using

Dominant Rank Method

Padmabati Chand J. R. Mohanty

School Of Computer Engineering School of Computer Application
KIIT University, Bhubaneswar, India KIIT University, Bhubaneswar, India

ABSTRACT optimization and need of genetic algorithm to solve VRP,

Vehicle Routing Problem (VRP) is a NP-Complete and a multi- section 3 gives problem formulation of VRP, chromosome
objective problem. The problem involves optimizing a fleet of representation, fitness evaluation and genetic operators (SMCM
vehicles that are to serve a number of customers from a central and SEMM), tournament selection and experimental results.
depot. Each vehicle has limited capacity and each customer has
a certain demand. Genetic Algorithm (GA) maintains a
2. BACKGROUND DETAILS
population of solutions by means of a crossover and mutation 2.1 Genetic Algorithm
operators. We propose new methods for genetic operators. The In the GA, each chromosome in the population pool is
proposed method for crossover is Sub Route Mapped Crossover transformed into number of routes [3, 4]. The chromosomes are
Method (SMCM) and for mutation is Sub Route Exchange then subjected to an iterative evolutionary process until a
Mutation Method (SEMM). This paper applies Dominant Rank minimum possible number of route clusters is attained or the
method to get Pareto Optimal Set. The vehicle routing problem termination condition is met [5]. The evolutionary process is
is solved with two objectives i.e. number of vehicles and total carried out as in ordinary GA using genetic operators
cost (distance). The proposed Dominant Rank Method finds (crossover, mutation) and selection operations on chromosomes
optimum solutions effectively. for reproduction. The primary objective of the reproduction
operator is to make duplicates of good solutions and eliminate
General Terms bias solutions in a population, while keeping the population size
Optimization, Customer, Vehicle. constant. This is achieved by performing the following tasks:
Keywords 1. Identify good (usually above average) solutions in a
Vehicle Routing Problem, genetic algorithm, multi-objective population.
optimization, dominant rank method, sub route mapped cross 2. Make multiple copies of good solutions.
over method (SMCM), sub route exchange mutation method
3. Eliminate bad solutions from the population so that
(SEMM).
multiple copies of good solutions can be placed in the
1. INTRODUCTION population.
The vehicle routing problem (VRP) is a well-known NP-hard
optimization problem which is encountered frequently in At every generation stage, we need to select parents for mating
distribution logistics and transportation systems. It is a Multi and reproduction. A problem specific crossover operator that
Constrained Optimization Problem [2, 7]. VRP formulations are ensures solutions generated through genetic evolution is
used in distribution services like post, parcel, and etc. Fisher [1] proposed. Hence both checking of the constraints and repair
describes the problem as the efficient use of a fleet of vehicles, mechanism can be avoided, thus resulting in increased
which must make a number of stops to pick up and deliver efficiency. A cross over operator is applied next to the strings of
passengers or products. The term customer is used to denote the the mating pool. A little thought will indicate that the
stops to pick up and deliver the product. Every customer is reproduction operator cannot create any new solutions in the
assigned exactly one vehicle in a specific order, which is done population. It only makes more copies of good solutions at the
with respect to the capacity in order to minimize the total cost expense of not-so-good solutions. The creation of new solutions
[3]. This paper studies the VRP as a multi-objective is performed by crossover and mutation operators. Like the
optimization problem (MOP), as implemented within a genetic reproduction operator, there exists a number of crossover
algorithm (GA). The VRP is optimized in two objectives: operators in the GA literature, but in almost all crossover
number of vehicles and total distance. So the result of MOP operators, two strings are picked from the mating pool at
technique is not only one solution, it is a set of solutions. This random and some portion of the strings are exchanged between
set is called Pareto Optimal Set, which consists of all the non- the strings to create two new strings. The crossover operator is
dominated solution. Dominant rank method is used to get Pareto mainly responsible for the search aspect of genetic algorithms,
Optimal Set. To improve the computational efficiency of GA, even though the mutation operator is also used for this purpose.
an improved mutation (Sub Route Exchange Mutation Method The bit wise mutation operator changes a 1 to 0 and vice versa,
(SEMM)) and cross over (Sub Route Mapped Crossover with a mutation probability. The need for mutation is to keep
Method (SMCM)) operation is exploited so that more parents' diversity in the population. Working of GA is shown in the
excellent performance can be inherited by off-springs. following algorithm.
The rest of the paper is organized as follows - section 2 gives a
back ground study of genetic algorithm, multi objective

29
 International Conference in Distributed Computing & Internet Technology (ICDCIT-2013)
Proceedings published in International Journal of Computer Applications® (IJCA) (0975 – 8887)

Genetic Algorithm 3. PROBLEM FORMULATION

Start
Step 1: Randomly initialize the population
3.1 Description of VRP
Step 2: Set maximum generation Vehicle Routing Problem (VRP) has been considered as a
significant segment in logistic handling. Thus, a proper
Step 3: Initialize generation as one
selection of vehicle routes plays a very important part to
Step 4: While (generation <=maximum generation) ameliorate the economic benefits of logistic operations [10]. It
{ is used to design least cost routes from a central depot to a set of
Step 4(a): Evaluate fitness function of each geographically dispersed points (customers, stores, schools,
solution in the population cities, warehouses, etc.) with various demands [7, 8]. We
Step 4(b): Apply selection procedure to present the problem description of the Vehicle Routing Problem
(VRP) as follows.
select set of solutions from population ,for
next generation  A set C = {c1,c2, . . . , cn} of customers, with known
Step 4(c): Apply genetic operators (crossover demands di > 0,where i=2,3,…n
and mutation)  A special node c0, called the depot.
Step 4(d): generation =generation+1  dij is the distance of the arc(i,j). The arc start and end
} in the same depot.
End  A fleet of K(k=1,k=2…k=m) identical vehicles
available in the depot.
2.2 Multi Objective Optimization  Customer should be visited in such a way that vehicle
Multi-objective optimization, also known as multi-criteria capacity constraint (vc) should not violated.
optimization, is the process of simultaneously optimizing two or  Each customer should visit once by one vehicle.
more conflicting objectives subject to certain constraints. If a
multi-objective problem is well formed, there should not be a We have to design routes, in such a way that there should be
single solution that simultaneously minimizes each objective to minimum number of distance and minimum number of vehicle.
its fullest. In each case we are looking for a solution for which Two fitness functions are taken here - first fitness function (F1)
each objective has been optimized to the extent that, if we try to to minimize distance and the second fitness function (F2) to
optimize it any further, then the other objective(s) will suffer as minimize number of vehicles.
a result [6]. Finding such a solution, and quantifying how much
better this solution (compared to other such solutions) is the F = minimum(F1,F2)
goal when setting up and solving a multi-objective optimization F1 = minimum(distance)
problem [3].When solving multi-objective problems our main n 1 n
focus is to calculate fitness value of individual solution and then = d ij
selection means set of solutions for genetic operators. These set i 1 j  i 1
of solutions is called Pareto Optimal Set and fitness of solution
F2=minimum(vehicle)
is called Pareto approximation. It is important to find as many
n 1 n m

  v
Pareto-optimal solutions as possible in a problem. Thus there k
are two goals in a multi-objective optimization. First goal is to =
ij
find a set of solution as close as possible to the Pareto-optimal i 1 j  i 1 k 1
front and the second goal is to find a set of solutions as diverse Where
as possible. i and j are customers in the population.
2.3 Need of Genetic Algorithm to Solve VRP n is the total number of customers in the population(or
population size).
Every good optimization method needs to balance the extent or
exploration on information obtained up until the current m is the total number of vehicles available in the depot.
generation through recombination and mutation operators with vijk indicates number of vehicles (k number of vehicles)
the extent of exploitation through the selection operator. If the required to traverse the arc (i,j).
solutions obtained are exploited too much, premature
convergence is expected. On the other hand, if too much stress The following figure shows a simple graphical model of the
is given on a search, the information obtained thus far has not VRP and its solution. In this figure, fleet of identical vehicles
been used properly. Therefore the solution time may be (number of vehicle four, with each vehicle capacity is 50)
enormous and the search exhibits a similar behavior to that of a available in the depot (d). Number of customers, numbered from
random search. Most classical methods have fixed transition 1 to 10, with demand of each customer is illustrated in the
rules and hence have fixed degrees of exploration and figure. In “Table 1” distance from depot to customer, customer
exploitation. Since these issues can be controlled in a GA by to depot, customer to customer explained. By considering
varying the parameters involved in the genetic operators, GA constraints and objective (minimum distance and minimum
provide an ideal platform for performing a flexible search in number of vehicles), the exact routes explained in “Table 2”.
VRP. Genetic algorithm is widely used to solve optimization Distance of each sub routes, total route distance and total
problems for its characteristic, especially vehicle routing number of vehicles required to traverse each customer
problem [11, 12]. illustrated in “Table 2”. The final route design is explained in
“Figure 2”.

30
 International Conference in Distributed Computing & Internet Technology (ICDCIT-2013)
Proceedings published in International Journal of Computer Applications® (IJCA) (0975 – 8887)

3.2 Chromosome Representation and Initial

Population Creation
In our approach, a chromosome has two parts. First part of the
chromosome represents routes. In “Figure 3” total number of
route is 3. A gene in a given chromosome indicates the original
node number assigned to a customer, while the sequence of
genes in the chromosome indicates the order of visitation of
customers. Thus, the chromosome consists of integers, where
new customers are directly represented on a chromosome with
their corresponding index number and each committed customer
is indirectly represented within one of the groups [9]. The
second part of the chromosomes indicates last node number of
each sub route. In the following “Figure 3”, sub routes are there
and the second part of the chromosome (1,7,4) are last node
Fig 1: Customers with Demand numbers of three sub routes.

Table 1. Distance table

Fig 3: Chromosome Representation

3.3 Fitness Evaluation

When dealing with multi-objective problem, fitness assignment
cannot be done directly, as the number of objective function is
more than one. In this paper we consider dominance approaches
to assign fitness of individual solution and we named this
method as dominant rank method. In the following we have
explained two algorithms. First algorithm is dominant rank
method and the second is dominant rank method with GA.

3.3.1 Dominant Rank Algorithm

Start
Step 1: Initialize population
Step 2: Repeat generation until to reach maximum generation
{
Step 2(a): Calculate distance and number of vehicles of each
solution in the population
Step 2(b): Count number of solutions dominated by certain
individual. If j number of solutions dominated by solution i then
fitness of i is j
Step 2(c): Repeat step 2(a) and 2(b) to get dominance
relationship of rest of the solutions in the population
}
Fig 2: Final Route Design End
Table 2. Sub routes with distance and number of vehicles 3.3.2 Dominant Rank Method with GA Algorithm
Start
Sub Routes Distance Vehicle
Step 1: Read problem instance data
d-1-2-d 13 1
Step 2: Set GA parameters
d-4-d 6 1 Step 3: Generate randomly an initial population
d-3-8-7-d 21 1 Step 4: For Generation =1 to Maximum Generation
d-6-5-d 24 1 {
d-9-10-d 25 1 Step 4(a): Evaluate fitness of the individuals of population
Step 4(b): Apply Dominant rank method and select new
Total 89 5
population (Tournament Selection)

31
 International Conference in Distributed Computing & Internet Technology (ICDCIT-2013)
Proceedings published in International Journal of Computer Applications® (IJCA) (0975 – 8887)

Step 4(c): Apply GA operators (crossover (SMCM) and Now second sub route of offspring 1 is, last node number of
mutation (SEMM)) each sub route in chromosome 2, by satisfying all the
Step 4(d): generation =generation+1 constraints. If the constraints are not satisfied then make a new
route. Same procedure follows for offspring 2.
}
End
Offspring 1: 1 7 4 – 2 8 6
3.3.3 Diversity Method
Offspring 2: 2 8 -6 7- 1 5 4
In Pareto approximation, diversity is important because all the
solutions are different. Density information gives us good Delete the visited node number which is second sub route of
metric to increase this diversity. This means probability to select offspring 1 from chromosome 2. Similarly delete the visited
solution decreases the greater density of solutions in its node number which is second sub route of offspring 2 from
neighborhood. So for density information histogram “Figure 4” chromosome 1. So after deletion rest of the nodes in sub routes
method is applied. Histogram is the technique consists of equal are:
dimension grids. According to fitness value different solutions
are located in different grids. Maximum number of solutions in
any particular grid is the density information. Chromosome 1: 3 9
Chromosome 2: 5 - 9 3

Insert sequentially rest of the node number in offspring 1 from

chromosome 2. If constraints are not satisfied then make new
sub routes. Same method follows for offspring 2. So the final
routes are:

Offspring 1: 1 7 4 – 2 8 6 – 5 9 3
Offspring 2: 2 8 -6 7 3- 1 5 4 – 9

Fig 4: Histogram Method

3.4 Cross Over (Sub Route Mapped

Crossover Method (SMCM))
Initial experiments using standard crossover operators such as
Partially-Mapped-Crossover (PMX) and uniform order
crossover (UOC) yielded non-competitive solutions [10].
Hence, a problem-specific crossover operator is utilized that
generates feasible route schedules [9]. Our proposed crossover
technique explained in “Figure 5”. According to the figure, two
Fig 5: Sub Route Mapped Crossover Method
parents A and B are selected from the population. We have
considered two chromosomes and in each chromosome there are 3.5 Mutation (Sub Route Exchange
9 customers. Number of sub routes in chromosome 1 is 3 and in
chromosome 2 is 4.
Mutation Method (SEMM))
In this method two sub routes selected randomly, then last node
Chromosome 1: 3 9 1- 2 5 7-8 6 4 number of each sub routes exchanged, by satisfying all the
Chromosome 2: 1 5 2-9 3 8-6-4 7 conditions [2]. The following figure explain mutation step wise.

The last node number of each sub route of chromosome 1 is the Step 1: The following chromosome are taken for mutation
first sub route in offspring 1 i.e, 1 7 4, by satisfying all the where 1 7 4 are last node numbers of each sub routes.
constraints. If the constraints are not satisfied then make a new
route. Similarly the last node number of each sub route of
chromosome 2 is the first sub route of offspring 2 i.e. 2,8,6,7 by
satisfying all the constraints. Since constraints are not satisfied
so here one sub route is 2 8 and another is 6 7.
Step 2: Suppose randomly two sub routes are selected i.e. 2 5 7
Offspring 1: 1 7 4 and 3 9 1. Then exchange last node number of each sub routes.
Offspring 2: 2 8 -6 7

Delete the visited node number which is in offspring 1 from

chromosome 2. Similarly delete the visited node number which
is in offspring 2 from chromosome 1. After deletion rest of the
nodes in sub routes are:
Step 3: After exchanging, the new chromosome is:
Chromosome 1: 3 9 1-5 -4
Chromosome 2: 5 2-9 3 8-6

32
 International Conference in Distributed Computing & Internet Technology (ICDCIT-2013)
Proceedings published in International Journal of Computer Applications® (IJCA) (0975 – 8887)

Table 3. Experimental results

Solomon data set Vehicle Distance

c101 13 1467.43
Fig 6: Sub Route Exchange Mutation Method
c105 9 1456.23
3.6 Tournament Selection c201 3 773.21
At every generation stage, we need to select parents for mating
and reproduction [2]. Tournament selection is used to perform r201 6 1724.43
fitness-based selection of individuals for further evolutionary
rc101 15 1987.12
reproduction [4]. In the tournament selection, tournaments are
played between two solutions and the better solutions is chosen rc201 4 2453.10
and placed in the mating pool. Two other solutions are picked
again and another slot in the mating pool is filled with the better
solution. If carried out systematically, each solution can be
made to participate in exactly two tournaments. The best
solution in a population will win both times, thereby making
two copies of it in the new population. Using similar argument,
the worst solution will lose in both tournaments and will be
eliminated from the population. In this way any solution in a
population will have zero, one or two copies in the new
population. It has been shown by Goldberg and Deb in
literature that the tournament selection has better or equivalent
convergence and computational time complexity properties
when compared to any other reproduction operator [5].
Tournament selection operator is that just by changing the
comparison operator, the minimization and maximization
problems can be handled easily and VRP is a minimize
optimization problem.

3.7 Experimental Results

This section describes computational experiments carried out to
investigate the performance of the proposed GA. By our given Fig 7: Initial Population for Instance c105
fitness function, it minimizes both number of vehicles and travel
costs without bias. All the programs are implemented in mat
lab. The program was run on an Intel Pentium IV 1.6 MHz PC
with 512 MB memory. We have applied histogram method for
selection of number of solutions. Then we applied tournament
selection, where tournament size is two and genetic operators
like for crossover SMCM and for mutation SEMM. The
probability of cross over is 0.8 and probability of mutation rate
is 0.2. In this program we used Solomon’s benchmark data set.
The following figures illustrate the progress of the genetic
algorithm. “Table 3" represents experimental results. In “Table
3” we are taken different solomon’s data set. Basically the
keywords in the data set represent how the customers are
located. c represents customers located in clustered manner, r
means customers are in random wise, rc means customers are in
random and clustered manner. So c101, c105 and rc101
represents hundred different customers are located in clustered
and random clustered manner. c201, r201, rc201 represents two Fig 8: Result for Instance c105
hundred different customers located in clustered, random and
random clustered manner. “Figure 7” represents initial
population of the instance c105, “Figure 8” represents network
topology for the instance c105 and Pareto optimal front
explained for the instance c105 in “Figure 9”.

Fig 9: Pareto Optimal Front for Instance c105

33
 International Conference in Distributed Computing & Internet Technology (ICDCIT-2013)
Proceedings published in International Journal of Computer Applications® (IJCA) (0975 – 8887)

4. CONCLUSION [6] Goldberg, D.E. 1998 Genetic Algorithm in Search,

Optimization, and Machine Learning. Addison-Wesley,
In this paper we have presented a GA based approach for the
Reading, Massachusetts.
VRP. The approach was tested using problem instances reported
in the literature, derived from publicly available Solomon’s [7] Tan. K. C., Chew. Y.H. 2006. A Hybrid Multi objective
benchmark data for VRP. To get Pareto Optimal Set, Dominant Evolutionary Algorithm for Solving Vehicle Routing
rank method is used. Here two new methods are proposed for Problem with Time Windows. Computational Optimization
genetic operators - One method for cross over SMCM and and Applications, Springer Science, Vol. 34, pp.115–151.
another for mutation SEMM. The experimental results revealed
that GA is able to determine the optimum route for the vehicles [8] Chand, P., Mohanty, J.R. 2011. Multi Objective Genetic
while maintaining their constraints of capacity. Our future work Approach for Solving Vehicle Routing Problem with Time
is the comparison of VRP with GA and other classical Window. In proceeding of trends in Computer Science,
optimization methods. Engineering and Information Technology, LNCCIS
(CCSEIT), Vol.204, pp.336-343.
5. REFERENCES [9] Chand, P., Mohanty, J.R. 2011. Multi Objective Genetic
[1] Fisher, M.1995 Vehicle routing. Handbooks of Operations Approach for Solving Vehicle Routing Problem. In
Research and Management Science, vol. 8. Elsevier , pp. 1- Proceeding 4th International Conference on Computer
33. Science and Information Technology (ICCSIT), in press.
[2] Ombuki, B., Ross, J., Hanshar, F.2006. Multi-Objective [10] Mohammed, M.A., Ahmad, M.S., Mostafa, S.A. 2012.
Genetic Algorithms for Vehicle Routing Problem with Using Genetic Algorithm in implementing Capacitated
Time Windows. Journal of Applied Intelligence, Springer Vehicle Routing Problem. In Proceeding of International
Science, Vol. 24, pp.17-30. Conference On Computer & Information
Science(ICCIS),Vol.1, pp.257-262.
[3] Haupt, R.L., Haupt, H.S. 2004 Practical Genetic
Algorithms. 2nd Edition, A John Wiley & Sons, Inc., [11] Zongyan, X., Haihua, L.,Wang, Y. 2011. An Improved
Publication. Genetic Algorithm for Vehicle Routing Problem. In
Proceeding of International Conference on Computational
[4] Deb, K.2001 Multi- Objective Optimization Using
and Information Sciences (ICCIS), pp.1132-1125.
Evolutionary Algorithm. John Wiley & Sons, Ltd.
[12] Jiajiao, Q.,Yong, Z., Jianlin, M., Lixia, F. 2011. A new
[5] Goldberg, D.E., Deb, K. 1991 A comparative analysis of
coding method for genetic algorithm in vehicle routing
selection schemes used in genetic algorithm. In G.J.E.
problem. In Proceeding International Conference on
Raslins(Ed.), Foundations of genetic algorithms, pp.69-93.
Cyber Technology in Automation, Control, and Intelligent
Systems (CYBER), pp.201-204.

34