Ambiance_TSP

Ambiance_TSP copied to clipboard

Ambiance_TSP

A Traveling Salesman problem based on the song Ambiance, Ambiance by Sam Gooris. (And some other songs.)

Problem description

In 1999, Belgian songsmith Sam Gooris rocked the charts with his dance hit Ambiance, Ambiance.

During the March 2019 edition of the Nerdland Science Podcast (listen at 39:08), whilst discussing the news that amoeba had been succesfully used in problem-solving, we looked at the lyrics of this song. In his anthem, Mr. Gooris eloquently describes how he visits several Belgian villages and cities in order to engage in rhyming party-related activities. However, the order in which he visits these locations is far from optimal. Bart Van Peer posed the question: What if Mr. Gooris could rearrange his travel itinerary (and, subsequently, his lyrics) to allow for an optimal usage of his time and mileage?

This is a classic example of a Traveling Salesman problem, a well-known problem in Computer Sciences which is NP-hard, which means that the worst-case running time of any problem-solving technique will increase superpolynomially with the number of cities. In this instance, Mr. Gooris visits 24 locations in the following order, derived from the lyrics:

Mal -> Ghent -> Leest -> Peer -> As -> Tielt -> Lot -> Puurs -> Lint -> Heist -> Reet -> Bree -> Schriek -> Geel -> Leut -> Doel -> Duffel -> Sinaai -> Vorst -> Niel -> Bere* -> Gits -> Boom -> Haacht -> Mal

We name this problem TSP, a Travelling Sam Problem.

Solution strategy

With n being the number of locations, there are (n-1)!/2 possible solutions, which in this case results in 1.2926008e+22 . We solve this problem by using the constraint optimization solver from Google's ORtools. The method we use is based on this article.

We use the latitude and longitute of the center (as per Google Maps) of every location in the list, stored together with the location name and the planned activity of Mr. Gooris (not needed to solve the problem, but funny) in the CSV file ambiance.csv. We use the Euclidean (straight line) distance between these (lat, long) coordinates in the distance matrix.

Solution

Within an execution limit of 30 seconds, the solver returns the following optimized path for Mr. Gooris, resulting in more than 1000kms off the original path. No additional refinements were found when gradually increasing execution limits (On a 3.6 Ghz Intel Xeon processor).

Mal -> As -> Leut -> Bree -> Peer -> Geel -> Schriek -> Haacht -> Duffel -> Lint -> Reet -> Leest -> Boom -> Niel -> Puurs -> Doel -> Sinaai -> Heist -> Gits -> Bere -> Tielt -> Ghent -> Lot -> Vorst ->  Mal

The village of Mal is chosen as a startpoint here, but the solution is a closed loop, so it doesn't matter where Mr. Gooris chooses to start.

*Bere or Mere? Leut or Jeuk?

• We originally interpeted the village of Bere as slang for the city of Meulebeke, because the village of Bere in Botswana would be uncharacteristic. Now, several listeners have informed us that they - after careful listening of the song - don't hear Bere, but Mere, which could be slang for the city of Erpe-Mere.
• The same goes for the part about leuk in, where we heard Leut, but several listeners informed us that Jeuk is also a village, and would fit better into the rhyming scheme.

The jury's still out on which interpretation is correct, but we have included an alternative list of locations in ambiance_alt.csv, and ran the solver again, resulting in the following (slightly altered) optimized path:

Mal -> As -> Bree -> Peer -> Geel -> Schriek -> Haacht -> Duffel -> Lint -> Reet -> Leest -> Boom -> Niel -> Puurs -> Doel -> Sinaai -> Heist -> Gits -> Tielt -> Ghent -> Mere -> Lot -> Vorst -> Jeuk ->  Mal

As you can see, introducing the locations of Mere and Jeuk to the solution changes the path slightly between Ghent and Mal.

Extra: Let's try another song!

To put the algorithm through a more thorough test, we also tested with the song Vlaand'renland by Nerdland jingle producer and well-known rockabilly Johnny Trash. In this song, ca. 100 locations are mentioned. The data for this song is in johnny_trash.csv. Mr. Trash does not specify any activities he undertakes at these locations, but it's safe to assume the default is heavy drinking.

The script came up with the following solution:

Installation

The script requires Python 3.6 or newer and depends on the , csv, numpy and ortools packages, which you can install using your favorite package manager, for example: pip install csv numpy ortools.

Visualisation

A quick and dirty Google Maps example to plot the results is included in src\util\plotmap.html. You can use the command solve_tsp.py --gmapjs ambiance.csvto output the result as copy-pastable JavaScript coordinates. Please note that in order to use this rudimentary visualizer, you'll have to generate and specify your Google Maps API key (see Google Dev Console) in the source code.

See also:

A lot of people took up the challenge to solve this TSP

• Github user soniCaH has developed a method which uses the Google Maps API to get the actual paths, and solves the problem in Excel: Traveling-Sam-Gooris-Problem.
• Martin Fiers made nice write-up on tackling the problem using Python and genetic algorithms: notebook
• Koos Fransen attacked the problem using ArcGIS - tweet link
• Q-Music DJ Maarten Vancoillie suggested we added Sam's hometown of Brasschaat to the tour - tweet link
• Thanks to the following people for also sending in solutions: Keith Meyerscough, Christophe Scholliers, Ward Van Driessche, Wies Vanden Kieboom, Jelle Victoor, Barbara Verdonck