A genetic algorithm for the Vehicle Routing Problem

Santa Claus has noticed that he cannot compete against Amazon, and so he has raised more reindeers over the year. This allows him to deploy multiple flying carriages with presents simultaneously. He decides to create a Genetic Algorithm to solve the Vehicle Routing Problem (VRP), which would allow him to determine the fastest routes to every chimney in town.

GAs belong to the family of evolutionary metaheuristics, which are based on the "survival of the fittest". Each solution is represented by a chromosome, which consists of a sequence of genes that represent a solution to the problem.

GAs operate upon a population of solutions, which are manipulated over several iterations, which are called generations.

Better solutions are progressively identified, as the algorithm pairs parent chromosomes to produce offspring, or applies random mutations on previously generated chromosomes.

There are 5 main steps to the GA process after we initialise the parameters:

  1. Population generation - where a randomised population of chromosomes (a one-dimensional string of real values) is generated.
  2. Fitness evaluation - where the fitness of all chromosomes in the population is calculated
  3. Parent selection - where certain chromosomes are selected to be carried over to the next generation based on elitism
  4. Crossover - where sections of the best parent chromosomes are combines to create offspring
  5. Mutation - where the chromosomes are tweaked to get a new solution

When the population has converged (where the offspring are not significantly different to the parents), the algorithm can be terminated.

We will be using Distributed Evolutionary Algorithms in Python (DEAP) library.

We generate the randomised problem instance using the make_blob function. We assume that the first coordinate in the set is the reindeer deployment location (where the reindeers take off at the start of the operation, and land at after delivering their presents)

Because the reindeers are still young, they can only carry a certain number of presents (vehicle_payload).

We generate the distance matrix between all chimneys and the depot. The optimal routes will seek to minimise the sum of these values.

As the VRP is quite a complex problem, we will first import the package DEAP and "create" in DEAP the chromosomes 'Individual' and the fitness objective, set as a minimisation by weights=(-1.0,).

We now specify the function that will create our population of chromosomes. Each chromosome will consist of two lists:

  1. The first list consists of the name of the chimneys to visit, and indicates the order at which each chimney is visited.
  2. The second list consists of the reindeers that visits the corresponding chimney of the first index.

For example, the following chromosome [1,6,4,5,2,3],[0,1,0,0,1,1] corresponds to the following route:

  1. Vehicle 0: [1, 4, 5]
  2. Vehicle 1: [6, 2, 3]

And proceed to define the functions that will be used to evaluate the chromosomes.

Now we must define how we carry out crossover. To swap the first list (the list of chimneys) we employ a partially mapped crossover (PMX) technique. To swap the second list (the list of reindeers) we use a simpler two-point crossover operation.

The final step is mutation, which adds some randomisation to the results so we don't lose genetic diversity in our sample. We have two operations: we either swap genes place within the same solution, or we shuffle any of the lists.

Finally, as Santa's reindeers can only hold a maximum payload of vehicle_payload, we must check that all our solutions are feasible. A feasibility check is carried out that moves presents to other available

We register the functions that we have carried out to the DEAP Toolbox. See how for 'population', 'individual', and 'select' we use DEAP-specific functions, but for the remaining ones we use the ones defined in the previous cells.

We can now run the main GA-loop.

Note how we generate the chromosome population using the DEAP function we specified using tb.register, which will repeat the 'tb.indexes' function that we linked to our chromo_create function. Meaning, call chromo_create as many times as specified by num_population.

We finally create the for loop with the remaining stages of the GA.

By now we should have a solution, we plot the convergence plot to view how the GA has performed. If the solution hasn't converged (i.e. the optimal value is still decreasing at the end of the algorithm) try increasing the number of generations!

Let's plot the final route.

Looks like a great solution, Christmas is saved thanks to mathematical optimization!