The travelling salesman problem is about finding the shortest route between a number of places, visiting each place only once before returning to the starting position. In the attached video, we show the result of a simple algorithm that uses one of many available optimisation approaches to find the shortest route between the central points of all countries. The shortest route can mean shortest by distance or travelling time, or the most cost-effective (or any other measurable quantity or combinations thereof that should be minimised). For a small number of places one wants to visit, it is still relatively easy to calculate all possible round-trips and rank them to find the shortest/best one. However, with a growing number of “cities” on the itinerary, the problem gets very hard to solve indeed. For example given 10 places to visit, there are already a staggering 10! = 3,628,800 number of possible routes. Trying to solve these kind of problems exactly for a large number of position would take much too long even with good computers. Therefore, approximations to solving the travelling salesman problem have been worked out.

Finding good approaches to address this problem are important in many areas: logistics - the efficient and timely delivery of goods - is an obvious one. When drilling holes in circuit boards, which requires the drilling of many, many thousands of holes, having an efficient ways of doing so can save a company time and money. On a more personal level, you can also use solutions to the travelling salesman problem to optimise your Christmas shopping route. The “Christkind” must have a particularly neat solution at hand, given that it manages to visit every single household in Austria in just a single night.

About the authors

Anna Köferle studied Molecular and Cellular Biochemistry at the University of Oxford and then completed a PhD at University College London. She is interested in gene regulation, epigenetics and everything to do with the gene editing tool “CRISPR”. Since starting as a researcher at Ludwig-Maximilians-Universität in Munich two years ago, she has also developed some interest in topics relating to neurobiology.

As an architect Ralf Bliem has a special interest in generative planing processes and modular design. He studied architecture at the UT Vienna and TU Berlin, also he worked at renowned architecture offices in Berlin and Vienna. Ralf is a co-founder of Biotop and at the moment he works with Biotop on the modular design of labs and some more interesting tasks.

Further Reading

10 Lines Of Coding (as shown in video): https://ericphanson.com/blog/2016/the-traveling-salesman-and-10-lines-of-python/