The long and winding road

Last week, I received an email telling me a recent online purchase was out for delivery. There was a real-time tracking option - I clicked the link to check on progress. I was encouraged to see my driver was only a few streets away, which impressed me since I'd only bought the item the night before.?

Four hours passed before the doorbell finally rang. I'd updated delivery tracking many times, watching the dot on my screen move in what seemed like a random pattern from one drop-off point to another.?

It's life Jim, but not as we know it

I was reminded of the travelling salesperson problem and inspired by similar work by others (thanks, to Peter den Haan , Micha? Jankowski , Michael Baczyk and Peter Brookes-Smith ). We have also created a Quantum Computing solution for this challenge for anyone that's interested. This may be handy since the number of possible routes gets large very quickly as the number of locations increase.

My version uses Python to create a genetic algorithm to optimise delivery journeys. The application works in real-time, providing a view of the best current route. A simple chart also shows how the total journey distance (mostly) decreases over time.?

The screenshots above show a route at specific generations. Note how the journey chart flattens out over time. Mutation continues but has less effect in later generations as diversity in the route population decreases. Showing diversity in some way may be something to think about for a future version. The diagram below illustrates what happens for each generation of routes.

1: The process starts by generating a specified number of random routes.

2: For fitness, I've just used the reciprocal of the total route distance which means shorter routes are fitter.

3: A specified number of parents are chosen based on their relative fitness.

4: The next generation is created using the parents that were chosen in the previous step. In genetics, crossover means that children take a mixture of genes from their parents - for this adventure, elements of parent routes are combined.

5: Now and again, a route mutates, the amount is configurable by specifying the probability that mutation will occur. Mutation provides an element of exploration in the exploration-exploitation trade off.

For this example, the application runs until it is stopped.

Interesting measurements

The application sidebar updates progress as each frame is drawn. Here you can see the number of locations, the initial (random) journey distance and the current distance (amongst other things). The application has a configuration file that allows the hyperparameters to be set.

The mutation rate can be changed as the application is running to show how this affects the algorithm.

The buttons allow you to run the application again using the same locations or to generate new locations. The number of locations is defined in the configuration file along with other application settings. A selected subset is shown here.

    # Environment details
    TICKS_PER_SECOND = 40
    LOCATION_RADIUS = 12
    
    # The bars representing total route distance over time
    DRAW_BAR_INTERVAL = 4
    BAR_WIDTH = 12
    BAR_COLOR = (130, 205, 207)
    
    LOCATION_COUNT = 48
    
    # Hyperparameters       
    FITTEST_ROUTES_COUNT =22
    POPULATION_SIZE = 110
    MUTATION_RATE = 0.003        

Final thoughts

These kinds of algorithms can help with a number of real-world challenges especially in the areas of optimisation and search/sort. There are other ways to address this problem, I chose this after working on a similar strategy for an evolution simulation I recently created.

If anyone would like to discuss this more, see it running (it's strangely soothing) or get access to the code then please let me know. If you're interested in Quantum Computing - some of my colleagues are mentioned above.