By Diana U
Imagine that you are a travelling salesman. Let’s say that you have to visit three different cities to find buyers for your product. You want to find the fastest route to visit all three cities and then return to your home town without visiting the same city twice. Find the most efficient route, and you might be home in time for the weekend!
Now, you might be thinking, “all I need to do is try out every possible combination and pick the one with the shortest total distance.” At first, that seems like a solid plan. It’s only three cities, right? That means there are only, what, six different routes you could take? Easy enough to calculate.
But how about we add some more cities to visit? Let’s say you need to visit ten cities. Well, there are now over 360,000 possibilities if we’re looking for one way routes. Would you like to test out each of these routes to see which one is the shortest?
I sure wouldn’t.
Is there a way to solve this problem? How can we find the shortest route without inputting endless numbers into a calculator?
Thankfully, there’s no need to resort to manual calculations. This is because the travelling salesman problem is something made for an algorithm to solve. At least, that’s what people were hoping for.
Can it be Solved?
Though the explanation of the problem is simple enough, it is quite difficult to solve. The more cities you add, the more complex it gets. As mentioned earlier, 10 cities would give you hundreds of thousands of possibilities. However, 15 cities would give you billions.
There are also more detailed versions of this problem, including gas prices and different modes of transportation. In these versions, you not only want to find the quickest route, you need to figure out the most efficient one.
Despite these details, multiple possible solutions have already been named. The fact that the Clay Mathematics Institute listed this problem as one of the seven Millennium Problems is certainly a motivator for mathematicians and computer scientists to take their hand at finding one great algorithm to resolve the case of the salesman. “Find a solution to any of the listed problems and be rewarded with $1,000,000!”
Some Solutions
Brute-Force
So the first idea to figure out the solution is to just try every combination and then pick the best choice. People call it the “Brute-Force Approach“. With this method, you are pretty much doing what we did above. Though this is really the best way to figure out the number one route, it takes a long time. It’s true, computers are quick, but most are definitely not fast or strong enough to run billions of possibilities in a few hours, let alone minutes.
Branch and Bound
The next possible solution is the “Branch and Bound Method”. In this approach, the name of the game is to break down this big problem into a bunch of smaller sub-sections and go from there. With this, you end up filtering out less optimal paths when the program decides that there is a section that cannot be improved upon. Really, you could probably write a separate article about the Branch and Bound Method. It has a unique way of working and there are a lot more details to it than what I’ve just mentioned. A key fact is that it’s faster than the previous method.
Nearest Neighbour
The last method doesn’t always find the best solution, but rather it finds something close enough. “The Nearest Neighbour Method” could be the simplest idea for a solution– or something near enough. The main idea here is that you don’t need to run a program a bunch of times. All you do is find the closest city and go there. Then from your new city, find the next closest city, and so on and so on. This won’t exactly find the top solution, but it can find some of the better ones.
Special Solutions
In addition to these popular methods, groups of researchers have had their hand at creating their own methods. One that caught my eye was a “Biogeography-Based Optimization Algorithm” that uses the migration strategy of animals to solve the travelling salesman problem.
Why is this important again?
The travelling salesman problem might seem like just a fun thing to try and solve in your free time, but there are real world benefits if a flawless algorithm is created. If it turns out that there truly is an algorithm that works perfectly for this problem we’ll be able to apply it to other situations. Not only is it useful for planning delivery and transportation routes, but you can even apply it to microchip and network design and genome sequencing.
So who knows? Maybe after learning more about it you could be the one to find a general solution to the travelling salesman problem! One million dollars is waiting for you…
Leave a Reply