A Traveling Salesman problem based on the song Ambiance, Ambiance by Sam Gooris. (And some other songs.)
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 26 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
Note that we have interpeted the village of Bere as slang for the city of Meulebeke (because the village of Bere in Botswana would be uncharacteristic), and suppose that Mr. Gooris will start and end his party tour in the same location. We name this problem TSP, a Travelling Sam Problem.
With n being the number of locations, there are (n-1)!/2 possible solutions, which in this case results in 7.755605e+24. 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.
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.
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:
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.
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.
- Convert from Latitude/Longitude to actual kilometers using earth curvature, for more detailed stats
- Use the Google Maps (or similar) API to fetch actual paths and their lengths between each location. (Like here).
- Figure out the exact location where Mr. Gooris would like to engage in party-related activities for added accuracy
- Attack the problem using a different technique, like genetic algorithms programming (Like here).