### 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!

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

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

### 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

### 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

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