Solution Techniques

Genetic Algorithms

Genetic Algorithms are very likely to be the most widely known type of metaheuristic algorithms. Genetic Algorithms are computer procedures that employ the mechanics of natural selection and natural genetics to evolve solutions to problems. The basic concepts were developed by [Holland 1975], while the practicality of using the GA to solve complex problems was demonstrated in [De Jong 1975] and [Goldberg 1989]. A GA evolves a population of individuals encoded as chromosomes by creating new generations of offspring through an iterative process until some convergence criteria are met. Such criteria might, for instance, refer to a maximum number of generations, the convergence to a homogeneous population composed of similar individuals, or getting an optimal solution. The best chromosome generated is then decoded, providing the corresponding solution.

Genetic algorithms work with a population of candidate solutions instead of just a single solution, so they perform a multi-way search simultaneously. Each individual represents a potential solution for the problem. In the original GAs of Holland, each solution may be represented as a string of bits, where the interpretation of the meaning of the string is problem specific.

The creation of a new generation of individuals involves three major steps or phases:

The selection phase consists of randomly choosing two parent individuals from the population for mating purposes. The probability of selecting a population member is generally proportional to its fitness in order to emphasize genetic quality while maintaining genetic diversity. Here, fitness refers to a measure of profit, utility or goodness to be maximized while exploring the solution space.
The recombination or reproduction process makes use of genes of selected parents to produce offspring that will form the next generation.
The mutation consists of randomly modifying some gene(s) of a single individual at a time to further explore the solution space and ensure, or preserve, genetic diversity. The occurrence of mutation is generally associated with a low probability.

A new generation is created by repeating the selection, reproduction and mutation processes until all chromosomes in the new population replace those from the old one. A proper balance between genetic quality and diversity is therefore required within the population in order to support an efficient search. In the figure below we can see the pseudocode of a simple GA.

Pseudocode of a simple genetic algorithm — Pseudocode of a simple GA.

For solving the VRP with GAs, it is usual to represent each individual by just one chromosome, which is a chain of integers, each of them representing a customer or a vehicle, so that each vehicle identifier represents in the chromosome a separator between two different routes, and a string of customer identifiers represents the sequence of deliveries that a vehicle must cover during its route. In the figure below we can see a representation of a possible solution for the VRP with 10 customers and 4 vehicles. Each route begins and ends at the depot (which is assigned the number 0). If we find in a solution two vehicle identifiers not separated by any customer identifier, we understand that the route is empty and, therefore, it will not be necessary to use all the vehicles available.

Chromosome representation of a VRP solution with 10 customers and 4 vehicles — Schema of the chromosome of a GA for solving the VRP.

A typical fitness function used for solving the VRP with a GA is $fitness function f$ , where

$f =$ $fitness function definition$ .

Both the overcapacity and overtime functions return the amount of capacity and time over the maximum allowed value. If none of the restrictions are violated, f returns the total distance traveled. Otherwise both capacity and time are weighted with values $α$ and $β$ . The best solutions may have values close to $f*$ , while the solutions that break any restriction will see their fitness value penalized.