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.

Published 25 Jan 2020

A weekly sketch by email

Learn something new in a sketch each Sunday

Get the book!
Big Ideas Little Pictures

Prefer to listen?
Try the podcast

Sketchplanations is ad-free
thanks to supporters like you.See more on Patreon

Keep exploring

Kitchen table survival skills

Solstice

The business flywheel

Learn the Kano model

Leading from Any Chair

Notice when you're happy: advice from Kurt Vonnegut's Uncle Alex to stop and say "If this isn't nice, I don't know what is."

Notice when you're happy: If this isn’t nice, I don’t know what is

Kitchen table survival skills are survival skills you can put into practice from your kitchen table. I humbly submit my set of tried and tested (and at times learned from bitter experience) non-glamorous, but effective, kitchen table survival skills: Checking the weather There's not always a choice, but having a good handle on the weather (know your clouds) can mean the difference between a nice day out and a disaster. Sensible route planning As Alistair Humphrey's writes in his book Local, "Unfolding a map is the ritual that launches all good journeys." There's art and science in route planning—considering the needs and abilities of your party, the terrain, the effect of the weather or altitude, availability of water, interest and views, access, timing, trail condition and more. So many varied aspects go into it. When planning a family hike now, we weigh up a very different set of factors than we did for two fit twenty-somethings happy to endure a little hardship. Telling someone where you're going If you're going to the wilderness, go with somebody if you can, and leave your intended plan with friends or family back home. If you're not back when expected, at least you'll have someone looking out for you, and a rescue party will know where to start looking. Hiring a guide OK, so it doesn't seem like a survival skill exactly, but going with a local guide will work wonders for your survival. You might not need one for a walk in the local woods, but if you fancy hiking on a glacier or venturing down a river, and it's not something you do too often, then hiring a guide will be the best survival decision you make. Reading up on your route Sure, you can head out and figure it out when you're out there, but mountains, and wilderness generally, are capricious places. There's so much a good hiking book, or a recent trip report can teach you before you set out. Is a river crossable? Is there still snow on a pass? Are the mosquitoes out in force? How long is it likely to take? How much up and down will there be? Where can you camp? And on and on. Taking the right gear Whenever I've been on semi-serious expeditions, I've been very impressed with the kit lists provided by our guides. Every item is carefully chosen—like, say, bringing the 10 essentials—and lists are refined and revisited after each trip. It's rarely exciting assembling your kit and running through lists, but if it means you remembered spare batteries, the water filter, mosquito repellent, or a fire lighter it may prove your saving grace in the wild. More mundane perhaps, but still helpful, is packing your gear in the right places and order in which you'll use it. You're much more likely to stop and put on sun lotion or a warm hat if it isn't stuffed under your sleeping bag in the depths of your backpack. Staying within your limits When we're tired, it's easy to make poor decisions. The best defence I know for this is to plan trips within your limits so you aren't trying to find a camp spot in the dark, feeling too tired to filter the water, or too tired to keep track of where you're going. After a long day, it's easy to start skipping the things that keep us safe, like putting on an extra layer or stopping for water. A guide once told me, "don't be too lazy to be comfortable." Keeping track of time A small, but very useful practice, I've adopted is having a good awareness of time on your excursions. Plan in advance and estimate how long different sections may take. Making a mental note of when you set off from the trailhead or from a rest stop gives you a sense of your progress, lets you know what it might take to get back if you need to, and teaches you how far you might get ahead of you. If your pace is changing, you'll have a good idea of how strong everyone is still feeling. Knowing when the sun rises and sets and how much daylight you have left means you're less likely to find yourselves in the dark without a headlamp. I'm sure you might have more to add to the list. This set came from reflecting on our survival skills before a brilliant chat with Brendan Leonard of the excellent Semi-rad about all things Ultra on the Sketchplanations podcast (episode out in Autumn 2024). Growing up in the 80s, for me survival skills were things Crocodile Dundee had, or perhaps MacGyver. More recently, Bear Grylls would demonstrate making a shelter in the jungle, starting fires, or catching salmon to survive in the wild. However, I realised that my survival skills were much less glamorous, but still rather effective, and most of them are used before I head out on a trip. In other words, my survival skills are ones that mean (touch wood) I don't get into a scrape that need the traditional survival skills most of us think of. As with so much in life, it's often the unglamorous stuff that makes the difference, like showing up every day, replicating before innovating, writing a rubbish first draft, or re-writing. I hope this set may keep your expeditions Type I or Type II fun, rather than Type III. Also see: The fun scale The 10 essentials Why camp 50yd from water The automation paradox Don't make important decisions on an empty stomach Glacial erratic Microadventure Perhaps you were really expecting something about a kitchen table: how to set a table…Kitchen table survival skills are survival skills you can put into practice from your kitchen table. I humbly submit my set of tried and tested (and at times learned from bitter experience) non-glamorous, but effective, kitchen table survival skills: Checking the weather There's not always a choice, but having a good handle on the weather (know your clouds) can mean the difference between a nice day out and a disaster. Sensible route planning As Alistair Humphrey's writes in his book Local, "Unfolding a map is the ritual that launches all good journeys." There's art and science in route planning—considering the needs and abilities of your party, the terrain, the effect of the weather or altitude, availability of water, interest and views, access, timing, trail condition and more. So many varied aspects go into it. When planning a family hike now, we weigh up a very different set of factors than we did for two fit twenty-somethings happy to endure a little hardship. Telling someone where you're going If you're going to the wilderness, go with somebody if you can, and leave your intended plan with friends or family back home. If you're not back when expected, at least you'll have someone looking out for you, and a rescue party will know where to start looking. Hiring a guide OK, so it doesn't seem like a survival skill exactly, but going with a local guide will work wonders for your survival. You might not need one for a walk in the local woods, but if you fancy hiking on a glacier or venturing down a river, and it's not something you do too often, then hiring a guide will be the best survival decision you make. Reading up on your route Sure, you can head out and figure it out when you're out there, but mountains, and wilderness generally, are capricious places. There's so much a good hiking book, or a recent trip report can teach you before you set out. Is a river crossable? Is there still snow on a pass? Are the mosquitoes out in force? How long is it likely to take? How much up and down will there be? Where can you camp? And on and on. Taking the right gear Whenever I've been on semi-serious expeditions, I've been very impressed with the kit lists provided by our guides. Every item is carefully chosen—like, say, bringing the 10 essentials—and lists are refined and revisited after each trip. It's rarely exciting assembling your kit and running through lists, but if it means you remembered spare batteries, the water filter, mosquito repellent, or a fire lighter it may prove your saving grace in the wild. More mundane perhaps, but still helpful, is packing your gear in the right places and order in which you'll use it. You're much more likely to stop and put on sun lotion or a warm hat if it isn't stuffed under your sleeping bag in the depths of your backpack. Staying within your limits When we're tired, it's easy to make poor decisions. The best defence I know for this is to plan trips within your limits so you aren't trying to find a camp spot in the dark, feeling too tired to filter the water, or too tired to keep track of where you're going. After a long day, it's easy to start skipping the things that keep us safe, like putting on an extra layer or stopping for water. A guide once told me, "don't be too lazy to be comfortable." Keeping track of time A small, but very useful practice, I've adopted is having a good awareness of time on your excursions. Plan in advance and estimate how long different sections may take. Making a mental note of when you set off from the trailhead or from a rest stop gives you a sense of your progress, lets you know what it might take to get back if you need to, and teaches you how far you might get ahead of you. If your pace is changing, you'll have a good idea of how strong everyone is still feeling. Knowing when the sun rises and sets and how much daylight you have left means you're less likely to find yourselves in the dark without a headlamp. I'm sure you might have more to add to the list. This set came from reflecting on our survival skills before a brilliant chat with Brendan Leonard of the excellent Semi-rad about all things Ultra on the Sketchplanations podcast (episode out in Autumn 2024). Growing up in the 80s, for me survival skills were things Crocodile Dundee had, or perhaps MacGyver. More recently, Bear Grylls would demonstrate making a shelter in the jungle, starting fires, or catching salmon to survive in the wild. However, I realised that my survival skills were much less glamorous, but still rather effective, and most of them are used before I head out on a trip. In other words, my survival skills are ones that mean (touch wood) I don't get into a scrape that need the traditional survival skills most of us think of. As with so much in life, it's often the unglamorous stuff that makes the difference, like showing up every day, replicating before innovating, writing a rubbish first draft, or re-writing. I hope this set may keep your expeditions Type I or Type II fun, rather than Type III. Also see: The fun scale The 10 essentials Why camp 50yd from water The automation paradox Don't make important decisions on an empty stomach Glacial erratic Microadventure Perhaps you were really expecting something about a kitchen table: how to set a table

Newer

RRandom

Older