The travelling salesman problem

You have to drop off 2 things after school, get to the shops and back home — which route should you take? You drive an Amazon delivery van and you have 145 parcels to deliver across London — what’s the most efficient route?

It’s pretty clear that for situations like the first one, with fewer stops, assuming you know travel distances or travel times, you could figure out the best route by trying out the different combinations until you hit on the shortest. The trouble is as you keep adding extra stops it doesn’t get just a little bit harder — instead the difficulty continues to increase along with the time it will take to find an answer.

Figuring out the shortest route to visit all the stops and return back home is known as the travelling salesman problem. It’s a problem formulated over 150 years ago that still has relevance and interest today whether it’s for delivering parcels, stocking shelves or soldering transistors.