Based on the Ambiance_TSP repository from Jeroen Baert's Github. Problem description is taken from his original Ambiance_TSP repository.
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 successfully 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 -> Jeuk (*) -> Doel -> Duffel -> Sinaai -> Vorst -> Niel -> Mere (**) -> Gits -> Boom -> Haacht -> Mal
We name this problem TSP, a Travelling Sam Problem.
(*) There's some discussion regarding "Leut" or "Jeuk" and "Bere" and "Mere". I choose the latter in both cases as they sounded more alike to my hearing.
Using the format described in the TSPLIB 95, by Gerhard Reinelt, all the city's are listed in the files with the tsp extension. This optimization problem is solved using Mixed-Integer Linear Programming. The Python MIP package provided the tools to model and solve this TSP problem.
Install the gurobi software from there website inside a virtualenv, install also the mip packages. For this project the academic license of gurobi is used, as well as python 3.6.7.
Run the following commands to generate a solution:
$ python solver.py belgium-ambiance-24.tsp > output_files/solve_001.txt
$ python parser.py output_files/solve_001.txt belgium-ambiance-24.tsp > output_files/tour_001.txt
In the output_files folder you can find the output from the solver (solve_00*.txt) and the more useful ordered list of the city's (tour_00*.txt).