How do we route Santa?

Some things seem very simple, supposing I ask you to visit 10 friends in the shortest possible distance.

This is quite an easy problem for us to solve simply by looking at a map. But in how many different orders can you arrange the 10 visits?
The number of possible ways in which we can visit our 10 friends is calculated as ... = (10x9x8x7x5x4x3x2x1)/2*10.
So there are 181,440 different orders we can visit our friends in!


Santa on a PC

For a simple problem such as visiting 10 friends we can easily solve the problem by looking at a map and using some common sense.

Q: What if Santa has to visit 50 houses?...

A: There would be 3041409320171337804361260816606476884437764156896051200000000000 possible routes that he can take....! If we have to visit more than a few houses it becomes impossible to check all of the possible routes, even using a computer would take a very long time.

Q: How can we solve a complex problem like this quickly?...

A: We can solve this problem using a simple computer program known as an Evolutionary Algorithm.

It works like this..


OurEvolutionary Algorithm is written in a programming language called Java, it's running on a computer at Edinburgh Napier University. If you refresh this page it will show the latest state of the algorithm.

Step 1.
The Evolutionary Algorithm has a group of posible sleigh trips, this group is known as the population. When the algorithm starts, each member of the population has the deliveries in a random order, but we can still calculate the length of each tour.

Click here to see the lengths of the tours in the latest population

77386.06
77382.61
77382.61
77382.61
77382.61
77382.62
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.80
77382.61
77382.61
77382.61
77382.61
77382.61
77382.73
77382.61
77382.61
77409.14
77382.61
77382.61
77382.61
77382.61
77382.61
77780.09
77382.61
77382.61
77414.58
77382.61
77382.61
77382.61
77382.75
77382.61
77387.68
77382.61
77382.61
77382.61
77382.61
77382.61
77382.62
77382.61
79005.43
77382.61
77382.73
77382.62
77382.61
77382.61
77382.61
77382.61
77382.75
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77383.40
77382.75
77382.61
85802.09
77382.82
77382.61
77383.56
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77393.79
77382.61
77383.17
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.62
77382.61
77382.61
77398.45
77382.62
77382.61

The average length of the sliegh ride in the population is 77487.98260551885
Sometimes all of the tours will have the same length, this happens when a short tour has been found, but will change when new houses are added.


Step 2.
We need to create some new shorter sleigh rides. We select some of the shortest sleigh rides in our population andthey become the parents of our next generation of sleigh rides. To create a child sleigh ride we copy either a whole tour from one parent, or make a new tour by adding togther the tour from two parents. We then make a random change (swap around some of the deliveries in the child (this is known as a mutation)

Click here to see the new children and their parents

Child, 83982.68Parents ,p1,77382.61,p2,77382.61 Mutation Swap Mutate
Child, 79933.94 Parent p1,77382.61 Mutation Swap Mutate
Child, 77388.23 Parent p1,77382.61 Mutation adj Swap Mutate
Child, 77383.66 Parent p1,77382.61 Mutation NN Simple Mutate
Child, 77382.61 Parent p1,77382.61 Mutation NN Simple Mutate
Child, 77574.53 Parent p1,77382.61 Mutation NN Simple Mutate
Child, 80811.71 Parent p1,77382.61 Mutation Simple Mutate
Child, 77930.93 Parent p1,77382.61 Mutation Simple Mutate
Child, 77804.69 Parent p1,77382.62 Mutation 2 opt Mutate
Child, 77451.32 Parent p1,77382.61 Mutation NN Simple Mutate
Child, 77392.69 Parent p1,77382.61 Mutation adj Swap Mutate
Child, 77946.88 Parent p1,77382.61 Mutation 2 opt Mutate
Child, 77461.73 Parent p1,77382.61 Mutation adj Swap Mutate
Child, 84165.87 Parent p1,77382.61 Mutation 2 opt Mutate
Child, 82420.61 Parent p1,77382.61 Mutation 2 opt Mutate
Child, 77532.13 Parent p1,77382.61 Mutation adj Swap Mutate
Child, 88136.43 Parent p1,77382.61 Mutation 2 opt Mutate
Child, 78077.07 Parent p1,77393.79 Mutation Swap Mutate
Child, 77519.11Parents ,p1,77382.61,p2,77382.61 Mutation NN Simple Mutate
Child, 79049.03 Parent p1,77382.61 Mutation NN Simple Mutate
Child, 77508.46 Parent p1,77382.61 Mutation Simple Mutate
Child, 96076.56Parents ,p1,77382.61,p2,77382.61 Mutation Swap Mutate
Child, 83376.76Parents ,p1,77382.61,p2,77382.61 Mutation 2 opt Mutate
Child, 80078.41 Parent p1,77382.61 Mutation Swap Mutate
Child, 96027.96 Parent p1,77382.61 Mutation Swap Mutate
Child, 103675.83 Parent p1,77382.61 Mutation Swap Mutate
Child, 98143.40 Parent p1,77382.61 Mutation Simple Mutate
Child, 77382.61Parents ,p1,77382.61,p2,77382.61 Mutation NN Simple Mutate
Child, 77551.85Parents ,p1,77382.61,p2,77382.61 Mutation Swap Mutate
Child, 77895.70Parents ,p1,77382.61,p2,77382.61 Mutation adj Swap Mutate
Child, 77687.34 Parent p1,77382.61 Mutation NN Simple Mutate
Child, 78614.07 Parent p1,77382.61 Mutation 2 opt Mutate
Child, 78061.57 Parent p1,77382.61 Mutation 2 opt Mutate
Child, 103390.41 Parent p1,77382.61 Mutation Swap Mutate
Child, 77382.61 Parent p1,77382.61 Mutation NN Simple Mutate
Child, 78138.53 Parent p1,77382.61 Mutation adj Swap Mutate
Child, 80417.10 Parent p1,77382.61 Mutation 2 opt Mutate
Child, 77892.31 Parent p1,77382.61 Mutation Swap Mutate
Child, 77648.16 Parent p1,77382.61 Mutation NN Simple Mutate
Child, 77387.55 Parent p1,77382.61 Mutation adj Swap Mutate
Child, 77939.58 Parent p1,77382.61 Mutation 2 opt Mutate
Child, 77554.94 Parent p1,77382.61 Mutation Simple Mutate
Child, 90484.20 Parent p1,77382.61 Mutation Simple Mutate
Child, 80073.56 Parent p1,77382.61 Mutation adj Swap Mutate
Child, 77393.00Parents ,p1,77382.61,p2,77382.61 Mutation adj Swap Mutate
Child, 77382.76 Parent p1,77382.75 Mutation NN Simple Mutate
Child, 77392.69Parents ,p1,77382.61,p2,77382.61 Mutation adj Swap Mutate
Child, 79685.81 Parent p1,77382.61 Mutation 2 opt Mutate
Child, 78778.96 Parent p1,77382.61 Mutation Simple Mutate
Child, 91894.19Parents ,p1,77382.61,p2,77382.61 Mutation Simple Mutate

You can see that some of the children have one parent and some have two. Sometimes the child will have a shorter ride lengththan the parents, do any of the new children in the box above have a shorter length than their parents?

Step 3.
We would like to add some our new children into our population, to replace the longer tours. For each child we select a random member of the population, if the ride length of the population is longer, then the child replaces that member.

Click here to see the replacement

Child 78614.07 Replaces 79005.43
Child 77382.61 Replaces 77409.14
Child 77387.55 Replaces 85802.09

Sometimes, there may be no members of the population replaced, as none of the children have short enough rides. The length of the child will be less than than the member of the population that it is replacing

Step 4.
We have now added the children into the population

Click here to see the improved population

77386.06
77382.61
77382.61
77382.61
77382.61
77382.62
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.80
77382.61
77382.61
77382.61
77382.61
77382.61
77382.73
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77780.09
77382.61
77382.61
77414.58
77382.61
77382.61
77382.61
77382.75
77382.61
77387.68
77382.61
77382.61
77382.61
77382.61
77382.61
77382.62
77382.61
78614.07
77382.61
77382.73
77382.62
77382.61
77382.61
77382.61
77382.61
77382.75
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77383.40
77382.75
77382.61
77387.55
77382.82
77382.61
77383.56
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77393.79
77382.61
77383.17
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.61
77382.62
77382.61
77382.61
77398.45
77382.62
77382.61

The averge length of a tour in the popultion is now 77399.6583193497 is that less than in step 1? If some some shorter children have been created and added then distance will be less, but sometimes no shorter routes will be found.

Check to see if any new deliveries have been added and then go back to step 2