Sketchplanations

Get my new weekly sketch in your inbox

Join over 30,000 people learning something new in a moment each Sunday.

The travelling salesman problem illustration showing a bewildered salesman contemplating the many options he could take to visit all the places the need across America

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.

You’re welcome to use and share this image and text for non-commercial purposes with attribution. Go wild!
See licence

Buy Me A Coffee