Introduction
Why write about this? The Germans have a lovely word Schadenfreude. It's the masochistic pleasure in witnessing the suffering of others. What better way to cheer up a tough week than read about the self inflicted wounds computer scientists impose on themselves.
History & Context
The Traveling Salesman Problem was defined in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman.
TSP is an intriguing puzzle in mathematics, computer science, combinatorial optimization & graph theory. The Traveling Salesman Problem is recognized as one of the toughest problems in computer science. It's also called one of the most misunderstood problems.
As it currently stands, there is a $1 million dollar prize to solve it, or prove it can't be solved.[1]
Stating the Problem
- A salesman has to travel N number of cities.
- S/he has to visit every city once
- S/he cannot repeat visiting the same city
- The order of the city s/he visits doesn't matter
- S/he must return back to the starting point
What is the best route the salesman can take- rather what is the most efficient route? Efficiency would be measured in terms of efficiency (shortest in duration) & economics of the travel (cheapest in cost).
Why is it so tough?
Upon first gander it would be feasible to want to just consider all possible options, and that is a valid algorithm: brute force. The trouble is efficiency.
If there is a way to break this problem into smaller component problems, the components will be at least as complex as the original one. This is what computer scientists call "NP-hard problems" [2]. "NP Hard" means that the problem does not have an efficient solution. This was also what Richard Karp's paper contended in the 1970s rendering TSP as an unsolvable problem, but since then that position has been debated and TSP called a NP-Problem.
The mystery is whether there is an efficient solution to this?
What is a Beautiful solution?
The cheaper one. Anything that can be solved quickly is termed an efficient algorithm. And it is this elusive beauty that thinkers strive to create.
Some problems cannot be solved by efficient algorithms. The troubling part is not knowing which problems they can and cannot solve.
The most famous- or rather the most lucrative- algorithm is PageRank. The algorithm that started Google Version 1, and consequent world domination. Simply stated a website's ranking should be determined by the number of inbound links it has, and each link also has a certain relevancy weight which affect the overall results. And while Yahoo, MSN and other search giants had 'solved' the problem of internet search, the difference between a working solution and a beautiful solution is the difference between Google-the-omnipotent and Yahoo-the-shitshow.
Different Solutions & Attempts
The easiest solution is brute force. It is also the most expensive solution. And it mainly boils down to- if you have N cities you have (N-1) factorial solutions.
I have not studied any computer science formally. Fortunately for me that means I don't have to understand these complex algorithms that have been attempted to solve this. Here's an animated video instead.
Great visual that compares the Greedy Algorithm, Local Search, and Simulated Annealing Strategies for solving TSP.In 1976, Nicos Christofides, a professor at Imperial College London, wrote an algorithm that generated routes the salesman could take that would be at most 50 percent longer than the shortest route: which many in the CS community believed would lead to an elegant solution that both students and computers would understand.
That record was broken in 2011, when the Stanford-McGill team edged past Christofides’ 50 percent guarantee with 49.99999999999999999999999999999999999999999999999996 percent longer than the true answer.
The branch and bound (B&B) algorithms which can solve this up to 40-60 solutions. Spanning tree is another approach.
Heuristic approaches to the problem result in approximations. Examples: Close-Nodes, Monte Carlo algorithm (randomization), Las Vegas Solution, Genetic algorithm.
... And my personal favorite: Bumble Bees!
Scientists in England decided to track the movements of the humble bumble, Bombus terrestris . Foraging for limited pollen, flying expends a lot of energy which the bees must preserve. They've essentially been living the TSP making trade offs between which flower to visit and the distances to fly.
Yes, that is a satellite glued on an insect. Because at this point why the fuck not.
The first 5 cycles are of the bee just figuring out where the feeders/flowers are, from rounds 5-15 you begin to see some method in the cycles. Post 25 you get the best cycle- efficient enough but not perfect. Unlike human scientists, bees are not anal about the best path, since they have a life and what not. However, their cleverness points to the direction of applying heuristics or approximations to solving the TSP; algorithms that don't find the perfect solution but get as close as they can.
Applications of the TSP
- Keep Mathematicians amused
- Manufacturing a circuit board
- Vehicle routing: Delivery systems, airplane routing, ambulance dispatches
- Information flow on the web & business supply chain
- DNA sequencing
The Heathrow Sequencing Algorithm. Airports do simulations of all possible flight options, carrying out millions of calculations per second. The process is to work backwards from the time the plane has to be up in the air, and work out all the steps
Conclusion
It's not that the TSP doesn't have a solution. The search is constantly one for a more elegant one. A beautiful, inexpensive solution that scientists fervently believe exists. The great thing about this problem is that many people routinely 'solve it' and it seems like the matter is settled. But then someone else finds out a shortcut, or a better optimization- and then the whole process for efficiency is sparked once more. Every tweak is more money, time and lives being saved. And of course that itch. Just knowing that a better solution is out there, that perfection & finality are within grasp is a quest worth chasing.
REFERENCES & FURTHER READING [1] P v NP Millennium Prize Problems, Business Insider, 2014 http://www.businessinsider.com/p-vs-np-millennium-prize-problems-2014-9
[2] Wikipedia entry on the Traveling Salesman Problem: https://simple.wikipedia.org/wiki/Travelling_salesman_problem
[3] "How bumblebees tackle the traveling salesman problem", https://www.sciencedaily.com/releases/2011/06/110628191339.htm?trendmd-shared=0
[4] "Computer Scientists find new shortcuts for Infamous Traveling Salesman Problem" Wired Magazine 2013 http://www.wired.com/2013/01/traveling-salesman-problem/
[5] "The Secret Rules of Modern Living: Algorithms", available for streaming on Netflix USA.