A New Binary Encoding Scheme

in Genetic Algorithm for Solving

the Capacitated Vehicle Routing Problem

Stanley Jefferson de A. Lima(B) and Sidnei Alves de Araújo

Informatics and Knowledge Management Graduate Program,

Universidade Nove de Julho – UNINOVE, São Paulo, SP, Brazil
stanleyjefferson@outlook.com, saraujo@uni9.pro.br
http://www.uninove.br

Abstract. In the last decades the Vehicle Routing Problem (VRP) and
its ramifications, including the Capacitated Vehicle Routing Problem
(CVRP), have attracted the attention of researchers mainly because their
presence in many practical situations. Due to the difficulties encountered
in their solutions, such problems are usually solved by means of heuristic
and metaheuristics algorithms, among which is the Genetic Algorithm
(GA). The solution of CVRP using GA requires a solution encoding step,
which demands a special care to avoid high computational cost and to
ensure population diversity that is essential for the convergence of GA
to global optimal or sub-optimal solutions. In this work, we investigated
a new binary encoding scheme employed by GA for solving the CVRP.
Conducted experiments demonstrated that the proposed binary encoding
is able to provide good solutions and is suitable for practical applications
that require low computational cost.

Keywords: Genetic Algorithm · Solution encoding

Chromosome representation · Capacitated Vehicle Routing Problem

1 Introduction
Optimization of the logistics system has become one of the most important
aspects of the supply chain during the last three decades [1]. In this context,
many researchers have invested their efforts in solving various problems in this
segment, among them is the Vehicle Routing Problem (VRP).
In general, the VRP consists in defining the routes that a set of vehicles must
follow to supply the demand of certain customers, respecting the operational
restrictions imposed by the context that they are inserted. The most common
objectives of the VRP are minimize the total distance traveled, improve the
transport time, minimize the number of vehicles needed and reduce the total
cost of the routes [2]. One of the main ramifications of the VRP is the Capac-
itated Vehicle Routing Problem (CVRP), which is considered in this work and
explained in detail in Sect. 2.1.
c Springer International Publishing AG, part of Springer Nature 2018
P. Korošec et al. (Eds.): BIOMA 2018, LNCS 10835, pp. 174–184, 2018.
https://doi.org/10.1007/978-3-319-91641-5_15
 A New Binary Encoding Scheme in GA for Solving the CVRP 175

In the literature there are several proposals to solve the VRP (and its rami-
fications) using different heuristic and meta-heuristics techniques, among which
are: Tabu Search, Genetic Algorithms, Simulated Annealing, Ant Colony Opti-
mization, Particle Swarm Optimization, Variable Neighborhood Search, and
Hybrid Meta-Heuristics [3]. The Genetic Algorithm (GA) stand out by its versa-
tility of construction and the good results that it has been demonstrated in solv-
ing complex problems, including VRP, as can be seen in Lau et al. [4]; Bermudez
et al. [5]; Wang and Lu [6]; Lee and Nazif [2]; Tasan and Gen [7]; Ursani et al.
[8]; Lu and Vincent [9]; Kuo et al. [10]; Vidal et al. [11]; Reiter and Gutjahr [12];
Osaba et al. [13] and Lima et al. [14].
A trivial way of encoding solutions for the VRP using GA is through a three-
dimensional binary matrix in which the rows are associated with the vehicles, the
columns with the costumers and the depth with the visitation order. However,
this encoding scheme demands high computational cost and may be inefficient
in terms of population diversity, which is essential to promote the convergence
to global optimum or sub-optimal solutions. Thus, many studies found in the
literature has shown concern about how to encode VRP solutions.
In this context, and differently from all above mentioned works which explore
improvements in the heuristic and meta-heuristic algorithms, this work is focused
in more efficient ways to encode solutions in GA. Specifically, we are proposing
a new binary encoding scheme in GA for Solving the CVRP, which constitutes
the main contribution of this work.

2 Theorectical Background
2.1 Capacitated Vehicle Routing Problem (CVRP)
The CVRP is one of the most basic version of VRP. In this problem all customers
have their demands previously defined which must be attend entirely by a fleet
of homogeneous vehicles, all of them running from only distribution center. In
the CVRP, just the vehicle capacity restriction is imposed [15], that is, the sum
of the demand of all customers belonging to a route does not exceed the capacity
of vehicle used to execute that route. Figure 1 illustrates an example of CVRP,
which involves two vehicles for meeting the demands of eighteen geographically
dispersed customers.
Let be G = (V, E) a graph in which V = 0 . . . n is the set of vertices that
represent the customers and E the set of edges, representing the paths connecting
the customers to each other and to the distribution center. Each edge (vi , vj) has
associated a cost Cij of the path between the costumers represented by vertices
i and j. When Cij = Cji , the problem is known as symmetrical, otherwise the
problem is identified as asymmetrical. A set of K identical vehicles with capacity
cv is allocated to the distribution center. For each customer v is associated a
demand dv , and for the distribution center is defined d0 = 0.
In summary, the CVRP consists of finding a set of routes, where each route
is traveled by a vehicle, with the objective to minimize the total cost of the
routes (T C), respecting the following restrictions: (1) each route must start and
176 S. J. de A. Lima and S. A. de Araújo

Fig. 1. Example of routing with the vehicles starting from a distribution center.

finish at the distribution center; (2) each customer must be visited just only time
and (3) the sum of the customers’ demands included in a route cannot exceed
the vehicle’s capacity. According to Vieira [3] the CVRP can be mathematically
formulated as follows:
nc
 nc
 K

Minimize T C = Cij xijk (1)
i=0 j=0,j=i k=1

K 
 nc
Subject to x0jk ≤ K (2)
k=1 j=1

nc
 nc

x0jk = xj0k = 1, k = 1, . . . , K (3)
j=1 j=1

K 
 nc
xijk = 1, i = 1, . . . , nc (4)
k=1 j=0

nc
 nc

xijk − xijk = 0, k = 1, . . . , Ki = 1, . . . , nc (5)
j=0 j=0

K 

xijk ≤ |S| − v(S), ∀S ⊆ V /{0}, |S| ≥ 2 (6)
k=1 i∈S j∈S

nc
 
di xijk ≤ cv, k = 1, . . . , K (7)
i=1 i=0,j=i

xijk ∈ {0, 1}, i = 1, . . . , nc, j = 1, . . . , nc, k = 1, . . . , K (8)

where: di is the demand of customer i; k: vehicle; K: set of vehicles; S: set
of customers; nc: Number of customers; v(S): Minimum number of vehicles to
attend S; cv: Capacity of vehicles; cij : cost of the path from customer i to
 A New Binary Encoding Scheme in GA for Solving the CVRP 177

customer j; T C: total cost of the routes; xijk : path from customer i to customer
j with vehicle k.
The Eq. 2 ensures that K vehicles will be used, while the Eq. 3 guarantees that
each route has its beginning and ending at the distribution center. Equation 4
defines that customers must be attended exactly one time and the Eq. 5 keeps
the flow ensuring that a vehicle arrives at a customer and out of it, preventing
that the route ends prematurely. The Eq. 6 prevents the formulation of routes
that do not include the distribution center. In this restriction, v(S) represents
the minimum number of vehicles required to attend a set of customers S. To
ensure that the number of vehicles used to attend the customers of set S is
not less than v(S), the restriction 6 establishes, indirectly, that the capacity of
the vehicle is not exceeded. However, to let this explicit, the Eq. 7 is used to
formulate the capacity restriction.
Finally, the Eq. 9 is used to evaluate the solutions generated by GA. It reflects
the value of the objective function (OF ) or fitness and involves the number of
vehicles used in the solution, violated restrictions (Eqs. 2 to 7) and the total cost
of routes (Eq. 1).

OF = T C + KWv + nrWr (9)

where: Wv is the weight assigned to the number of vehicles used in the solution;
nr is the number of violated restrictions and Wr is the weight given to the
violated restrictions.

2.2 Genetic Algorithm (GA)

The GA is an evolutionary computational technique that simulates the mech-

anisms of natural selection, genetics and evolution. In the last decades it has
been employed in several applications to solve complex optimization problems.
Its bias is how much better an individual adapts to its environment, the greater
their chances of surviving and generating offspring [16]. A GA individual rep-
resents a solution to the problem being solved. Each individual is defined as a
chromosome, consisting of genes, which represent variables of the problem, and
each position of a gene is defined as an allele.
In GA, the crossover operation consists in recombination of genes from
selected individuals, responsible to reproduce descendants more adapted to the
next generation. After a certain number of generations, it is common to occur
the loss of population diversity, which results in the premature stopping of the
GA leading to local optimum solutions. To avoid this problem, the mutation is
applied at a given rate of individuals (usually by randomly changing the alleles),
aiming to change the characteristic of the genes [17].
Other concepts associated with GAs are:

• Genotype: is related to the population in the computation space, in which

the solutions are represented to be easily understood and manipulated by
computers [18,19].
178 S. J. de A. Lima and S. A. de Araújo

• Phenotype: is related to the population in the real world solution space, in

which the solutions are represented to be interpreted in real world situations
[18,19].
• Encoding and Decoding: in the most cases, the phenotype and genotype
spaces are different. Encoding is an operation that transforms a solution from
the phenotype to genotype space, while decoding is responsible by transform-
ing a solution from the genotype to the phenotype space. The main encoding
schemes are: Binary, Value (integer, float, string, etc.), Permutation and Tree
[19,20]. Since these operations are carried out repeatedly during the fitness
value calculation (evaluation) in a GA, as illustrated in Fig. 2, they need to
be simple and fast.

Fig. 2. Encoding/decoding operations.

Based on the above explanation, it is observed that the encoding solution

scheme is an important step in the development of GA, since it is directly related
to the quality of the solutions found, as well as the computational time spent to
find them.

2.3 Some Recent Encoding Schemes Used in GA for Solving the

VRP and Its Ramifications

As observed in the recent literature, the most commonly used schemes for VRP
solution encoding are permutation and value (integer). Such representations can
be found, for example, in the works of Lu and Vincent [9], Lau et al. [4], Lee
and Nazif [2], Bermudez et al. [5] and Lima et al. [14].
Lu and Vincent [9] proposed a simple mixed encoding scheme (permuta-
tion and integer), illustrated in Fig. 3, which encapsulates a main chromosome
(permutation of costumers) and a ‘subchromosome’ formed by integer values
representing the number of customers on each route.

Fig. 3. Encoding scheme proposed by Lu and Vincent [9].

 A New Binary Encoding Scheme in GA for Solving the CVRP 179

Lau et al. [4] adopted an encoding scheme similar to that presented in [9], for
the Multidepot VRP, in which the subchromosome (first chromosome positions)
represents the number of costumers that each vehicle must attend, as well as the
depot each vehicle will depart to make deliveries (see Fig. 4).

Fig. 4. Encoding scheme proposed by Lau et al. [4].

It is important to note that in these cases additional mechanisms must be

used for route separation and also to bypass the problem of generating non-
feasible solutions after applying the crossover and mutation operators. However,
this latter mechanism is not clearly described in the above mentioned works.
Recently, Lima et al. [14] proposed a short binary encoding scheme for CVRP
in which the chromosome represents the set of customers that must be attended
by each vehicle, as can be seen in Fig. 5, while the sequence for visiting the
customers is solved by the Nearest Neighbor algorithm.

Fig. 5. Binary encoding scheme proposed by Lima et al. [14].

In this encoding scheme the alleles with value of 1 indicate the customers
that will be attended by a vehicle, that is represented by each line of the binary
matrix.

3 Materials and Methods

In the development of proposed encoding scheme, the programming language
C/C++ and GAlib library [21] were used. The GAlib is a free library widely
180 S. J. de A. Lima and S. A. de Araújo

used for solving combinatorial optimization problems. For evaluating the pro-
posal, experiments were performed and the results obtained were compared with
the best results found in the literature for a set of instances extracted from
Christofides and TSPLIB libraries, with up to 30 customers.
In the experiments we employed a desktop computer with the following con-
figurations: Intel Celeron 1.40 GHz processor; 4 GB of RAM; Windows 7 Ulti-
mate 32-bits operating system.
The following parameters (empirically defined) were employed by imple-
mented GA:

• Population Size = 1200;

• Number of Generations (used as stop criterion) = 5000;
• Population rate of replacement = 0.8;
• Elitism rate = 0.2;
• Crossover rate = 0.8;
• Selection Method = Roulette;
• Mutation rate = 0.01;
• Type of Mutation = Flip Bit.

4 Proposed Binary Encoding Scheme

The encoding scheme proposed in this work consists of a binary matrix of M =

nc ∗ 2 − 1 columns by K rows. The example shown in Fig. 6 illustrates the
solution encoding of a CVPR instance that involves nc = 7 costumers and K = 2
vehicles (as depicted in Fig. 1). The first nc columns of each row indicate the
costumers to be served by a vehicle, while the last nc − 1 columns consist of
a vector that indicates the permutations to be made in a matrix of integers
(Fig. 7), called permutation matrix, representing the order that the costumers
will be visited by the K vehicles.

Fig. 6. Proposed binary encoding scheme for CVPR.

The permutation matrix (that can be understood as a seed) containing nc

columns and K rows, shown in Fig. 7, is unique and must be generated before
the execution of GA using random permutations or some heuristic algorithm.
Thus, when it is combined with a GA chromosome (indicating the costumers to
be visited and how the visitation order will be permuted), a solution for CVRP
is generated, as shown in Fig. 8.
 A New Binary Encoding Scheme in GA for Solving the CVRP 181

Fig. 7. Permutation matrix (seed).

Fig. 8. Combining a permutation matrix with a chromosome to generate a solution for

CVRP.

In summary, combining a unique seed with the GA chromosomes a set of

different solutions for the CVRP is generated, each one providing the set of
customers to be visited by each vehicle as well as the order they will be visited.
It is valid to mention that the encoding scheme described here was inspired
by the work of Grassi [22], who proposed a similar way to represent solutions
to the Job-shop Scheduling Problem (FJSP), and is very different from those
employed in the VRP solution found in the literature, including the schemes
described in Sect. 2.3.

5 Experimental Results
To evaluate the proposed encoding scheme we executed the GA ten times for
each instance. Then, the results obtained were compared with the best solutions
found in the literature. To this end, we considered the optimal solutions presented
by Reinelt and Wenger [23] and by Ralphs et al. [24], respectively, for instances
extracted from Christofides and TSPLIB.
The quality of obtained solutions was evaluated by a measure known as GAP,
which is widely used in the literature to express how far the result obtained for
a problem is from the best result reported in the literature for that problem. In
our case, GAP = (OF − OFBest )/OFBest , being OF the best value of objec-
tive function (Eq. 9) obtained in the 10 executions of GA and OFBest the best
182 S. J. de A. Lima and S. A. de Araújo

solution found in the literature. In addition, we present in Table 1 results con-

sidering the population initiated in a random way (GA) and including in it a
feasible solution generated by Gillet & Miller heuristic (GA+GM).

Table 1. Experimental results of proposed scheme.

Instance OFBest GA GAP% GA+GM GAP% Time (s)

Eil7 114 114 0.00% 114 0.00% 30
Eil13 290 316 8.97% 308 6.21% 50
Eil22 375 472 25.87% 376 0.27% 100
Eil23 875 1025 17.14% 903 3.20% 110
Eil30 545 840 54.13% 750 37.61% 150
P-n16-k8 450 520 15.56% 462 2.67% 60
P-n19-k2 212 284 33.96% 255 20.28% 70
P-n20-k2 216 270 25.00% 255 18.06% 80
P-n21-k2 211 249 18.01% 229 8.53% 90
P-n22-k2 216 338 56.48% 268 24.07% 100
P-n22-k8 590 722 22.37% 618 4.75% 100
P-n23-k8 529 675 27.60% 574 8.51% 110
E-n13-k4 247 306 26.89% 302 22.27% 50
E-n22-k4 375 462 23.20% 390 4.00% 100
E-n23-k3 569 892 56.77% 690 21.27% 110
E-n30-k3 534 880 64.76% 687 28.65% 150
Average GAP% − − 29.6% − 13.14% −

As shown in Table 1, the proposed scheme provided good performance regard-

ing the quality of the solutions. Considering the results of GA+GM, the GAP in
most cases (except for instances “Eil30” and “E-n30-k3”) did not exceed 25%,
being that for 56% of tested instances the GAP was less than 10%. Still ana-
lyzing the GAP, the average value did not exceed 14%, highlighting the good
performance of our proposed approach.
With respect to computational cost, as can be seen in Table 1, the process-
ing time ranges from 30 s for the smallest instance (“Eil7”) to 150 s for larger
instances (“Eil30” and “E-n30-k3”). In addition, the results showed that the use
of Gillett & Miller heuristic to generate a feasible solution in the initial popula-
tion helps the GA to converge quickly to promising points in the search space,
generating solutions with good quality. It should be noted that the average time
spent in the execution of the Gillett & Miller algorithm was on average 1.7 s,
which shows that it does not compromise the computational cost of GA.
Despite the good results obtained by our approach, many improvements can
still be made in the proposed encoding scheme, such as: the use of more than one
 A New Binary Encoding Scheme in GA for Solving the CVRP 183

seed (matrix of permutation), the use of local search operators (k-opt, OR-opt,
k-Point Move and Cross-Exchange) and also by incorporating some local search
algorithm to refine the solutions generated by GA.

6 Conclusions
In this work we presented a new binary encoding scheme for GA to solve
the CVRP. From the computational experiments carried out with instances of
Christofides and TSPLIB, it was possible to conclude that the proposed scheme
provided good results considering the computational cost and the quality of solu-
tions. In addition, it was found that the chromosome representation is suitable
to met the specific characteristics of the CVRP, besides it is simple to interpret
and adapt. The experiments also pointed out that the use of Gillett & Miller
heuristic helped the convergence of GA to promising points in the search space.
In future works some improvements in the proposed scheme will be investigated,
such as: (i) the use of Clarke and Wright heuristic to generate feasible solutions
to be injected into the initial population of the GA; (ii) the use of local search
operators (k-opt, OR-opt, k-Point Move and Cross-Exchange), aiming to gen-
erate different solutions from the same seed; (iii) incorporate some local search
algorithm to refine the solutions generated by GA and (iv) apply the proposed
scheme in a large number of instances found in the literature, in order to evaluate
the applicability of our approach in real scenarios.

Acknowledgements. The authors would like to thank UNINOVE, FAPESP–São

Paulo Research Foundation by financial support (#2017/05188-9) and CNPq–Brazilian
National Research Council for the scholarship granted to S. A. Araújo (#311971/2015-6).

References
1. Dalfard, V.M., Kaveh, M., Nosratian, N.E.: Two meta-heuristic algorithms for two-
echelon location-routing problem with vehicle fleet capacity and maximum route
length constraints. Neural Comput. Appl. 23(7–8), 2341–2349 (2013)
2. Nazif, H., Lee, L.S.: Optimised crossover genetic algorithm for capacitated vehicle
routing problem. Appl. Math. Model. 36(5), 2110–2117 (2012)
3. Vieira, H.P.: Metaheuristic to solve vehicles routing problems with time windows
(2013)
4. Lau, H.C., Chan, T., Tsui, W., Pang, W.: Application of genetic algorithms to
solve the multidepot vehicle routing problem. IEEE Trans. Autom. Sci. Eng. 7(2),
383–392 (2010)
5. Bermudez, C., Graglia, P., Stark, N., Salto, C., Alfonso, H.: Comparison of recombi-
nation operators in panmictic and cellular GAs to solve a vehicle routing problem.
Intel. Artif. Rev. Iberoam. de Intel. Artif. 14(46), 34–44 (2010)
6. Wang, C.H., Lu, J.Z.: An effective evolutionary algorithm for the practical capac-
itated vehicle routing problems. J. Intell. Manuf. 21(4), 363–375 (2010)
7. Tasan, A.S., Gen, M.: A genetic algorithm based approach to vehicle routing prob-
lem with simultaneous pick-up and deliveries. Comput. Ind. Eng. 62(3), 755–761
(2012)
184 S. J. de A. Lima and S. A. de Araújo

8. Ursani, Z., Essam, D., Cornforth, D., Stocker, R.: Localized genetic algorithm for
vehicle routing problem with time windows. Appl. Soft Comput. 11(8), 5375–5390
(2011)
9. Lu, C.C., Vincent, F.Y.: Data envelopment analysis for evaluating the efficiency of
genetic algorithms on solving the vehicle routing problem with soft time windows.
Comput. Ind. Eng. 63(2), 520–529 (2012)
10. Kuo, R., Zulvia, F.E., Suryadi, K.: Hybrid particle swarm optimization with genetic
algorithm for solving capacitated vehicle routing problem with fuzzy demand – a
case study on garbage collection system. Appl. Math. Comput. 219(5), 2574–2588
(2012)
11. Vidal, T., Crainic, T.G., Gendreau, M., Lahrichi, N., Rei, W.: A hybrid genetic
algorithm for multidepot and periodic vehicle routing problems. Oper. Res. 60(3),
611–624 (2012)
12. Reiter, P., Gutjahr, W.J.: Exact hybrid algorithms for solving a bi-objective vehicle
routing problem. Cent. Eur. J. Oper. Res. 20(1), 19–43 (2012)
13. Osaba, E., Diaz, F., Onieva, E.: Golden ball: a novel meta-heuristic to solve com-
binatorial optimization problems based on soccer concepts. Appl. Intell. 41(1),
145–166 (2014)
14. Lima, S.J.A., Araújo, S.A., Schimit, P.H.: A hybrid approach based on genetic
algorithm and nearest neighbor heuristic for solving the capacitated vehicle routing
problem. Acta Scientiarum Technology (2018)
15. Laporte, G.: The vehicle routing problem: an overview of exact and approximate
algorithms. Eur. J. Oper. Res. 59(3), 345–358 (1992)
16. Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learn-
ing. Addison-Wesley, Reading (1989)
17. Banzhaf, W., Nordin, P., Keller, R.E., Francone, F.D.: Genetic Programming: An
Introduction, vol. 1. Morgan Kaufmann, San Francisco (1998)
18. Brooker, R.: Concepts of Genetics. McGraw-Hill Higher Education, New York
(2012)
19. Kumar, R.: Novel encoding scheme in genetic algorithms for better fitness. Int. J.
Eng. Adv. Technol. 1(6), 214–219 (2012)
20. Kumar, A.: Encoding schemes in genetic algorithm. Int. J. Adv. Res. IT Eng. 2(3),
1–7 (2013)
21. Wall, M.: GAlib: a C++ library of genetic algorithm components (1996)
22. Grassi, F.: Optimization by genetic algorithms of the sequencing of production
orders in job shop environments. Master’s Dissertation, Industrial Engineering Post
Graduation Program, Universidade Nove de Julho (UNINOVE) (2014)
23. Reinelt, G., Wenger, K.M.: Maximally violated mod-p cuts for the capacitated
vehicle-routing problem. INFORMS J. Comput. 18(4), 466–479 (2006)
24. Ralphs, T., Pulleyblank, W., Trotter Jr., L.: On capacitated vehicle routing. Prob-
lem, Mathematical Programming (1998)