IMAGINARY: The travelling salesman problem

Mathematics exhibition "IMAGINARY: beauty and power of mathematics" is from the 1st of October in Utrecht!

Throughout the school year 2022-2023, the exhibition can be visited and experienced in various cities across the Netherlands. In The Netherlands, the IMAGINARY exhibition is organized by the Dutch Platform for Mathematics, in collaboration with Dutch universities, and supported by partner organizations. The exhibition runs simultaneously in Flanders, where the Flanders Platform for Mathematics is the driving force. 

In the exhibition, you can also see four posters on networks and algorithms! These were made in collaboration with various people. One of these posters is about the Travelling Salesman Problem, a very famous problem in networks theory. This poster was made by Frans de Ruiter from the Dutch company CQM.

The poster can be seen below. Below the poster in English, you can read more details about this modern line of research.   

Poster created by Frans de Ruiter, in collaboration with the Network Pages.

The traveling salesman problem

Suppose you have a delivery service. You have one truck and have to deliver a large number of parcels to different cities in the country every day. Then you run into the following problem: in which order should you visit the cities? In other words, you want to find a tour that starts at the depot where the packages are kept, then visits each of the given cities, and finally returns to the depot. The goal, of course, is to find a tour with minimal travel costs. Here, travel costs can refer to the average time it takes to complete the tour or the total length of the tour.

Computer scientists call this problem the traveling salesman problem or TSP for short. You may think that if we know the cities to visit and the travel costs of the roads they connect, a computer can easily find the shortest tour. But the fact that TSP is so easy to claim is deceptive: using strong algorithms the shortest tour can be approached very accurately and fast, but proving that, given the distances, there cannot be a tour that is even an inch shorter is extremely difficult. The Traveling Salesman Problem has become so popular that it even has its own website, with applications ranging from finding the optimal pub crawl in the UK, to determining the optimal interstellar journey between stars! For example, this poster shows the optimal tour between 57,912 national monuments in the Netherlands!

Can you imagine that the TSP is one of the most challenging problems in theoretical computer science? Do you want to know why? And would you like to read about recent breakthroughs in the TSP? You can view this article for more information on the result shown in the poster, this article to get a taste of the research mathematicians do on the Traveling Salesman Problem, and this website for much more information on this problem. 

NETWORKS

NETWORKS has collaborated with four more scientists to make posters about their research for IMAGINARY. The three other posters concern the following topics:

WHERE AND WHEN?

Where When
Nijmegen, Huygensgebouw September 4 to 24, 2022
Utrecht October 1 to 21, 2022
Enschede November 2022
Eindhoven Februari/March 2023
Groningen, Zernike Campus April 1 to 23, 2023
Amsterdam May 2023
Maastricht June/July 2023

If you want to see the posters, then pick a day and go to the exhibition. If you can't wait until the exhibition comes to your city, you can combine the visit with a day trip to Utrecht! 

Would you like to stay up to date whenever a new post appears on the Network Pages? Then subscribe to our mailing list, follow us on Twitter or on LinkedIn.

Comments are closed