By glenn cich & Robin Pauwels
I bet everybody knows the fantastic song “Ambiance, Ambiance” by Sam Goris, right? You don’t know the song? Ok, then before you continue reading, i’ve added the link of the song here below so that also you can be musically inspired by our legendary Flemisch singer. Enjoy!
I know, you either love it, or you hate it! But let’s get down to the real business of where this article is actually about.
Traveling salesman problem wrapped in a song
In his song, Sam describes a large number of activities taking place in different cities all across the Flemish region. Jeroen Beart had the idea to dissect this song to see if Sam was taking the most optimal route to visit the cities. It turned out very quickly that this route was far from optimal. You may also know this type of problem as the Traveling Salesman problem.
What we acutally want to do, is to find the shortest route between all the cities making sure that Sam visits every city only one time and ends up again in the city where he started his journey. Given that this problem is called NP-hard, there is no efficient algorithm yet to fix this problem with a 100% optimal score.
Thankfully, there are certain heuristics available to approach this problem in a most optimal way possible. The big issue here, is the lack of sufficient compute power to solve this kind of problems in a short period of time. The rising trends arround Quantum Computing technologie could be the missing link to provide us with enough compute capacity to create fast and efficient solutions. But that’s something we will cover in another blog!
The route
According to Sam’s song, he follows the following route:
Mal -> Gent -> Leest -> Peer -> As -> Tielt -> Lot -> Puurs -> Lint -> Heist -> Reet -> Bree -> Schriek -> Geel -> Leut -> Doel -> Duffel -> Sinaai -> Vorst -> Niel -> Mere -> Gits -> Boom -> Haacht -> Mal
Let us dissect this for a moment. As you can see in the following image, Sam would have to travel 1 861 478 meters, or 1 861 km to visit all the cities.
This is going to cost Sam quite some fuel, but also time which he can better use for his concerts in the cities.
Let’s suppose that Sam uses approximately 6,5l diesel per 100km. A liter diesel costs about 1,5 Euro. The CO2 emission is about 2 640 grams CO2/liter diesel. Now let’s do the math to get an overview of his current route:
Number of km: 1 861 km
Number of Liter: 121 l
Total/€: € 181,5
Total/CO2: 319 440 gram CO2
So everytime Sam does this trip, he spends € 181,5 and has a CO2 emission of 319 440 gram. Hmm, we know you’ve earned a lot of money with this song Sam, but I think we have to find a way to lower your cost and your CO2 emission.
Let’s see if we can find a better way to plan his trip!
OptaPlanner to the rescue!
To find a better alternative for this problem, we’ve used 3 open-source tools:
- OpenStreetMap for the map data
- GraphHopper to calculate the routes
- OptaPlanner to tackle the TSP problem
Using OptaPlanner, we’ve turned this problem in a software model and created a tool that provides a solution much more durable than the one Sam describes in his song. And the calculations only took a couple of seconds! Pretty awesome, right?
Following figure shows the new and more durable route Sam can now follow:
We have reduced the total travel distance to 638,331 km! Let’s do the math again to see what impact this has on the total cost and CO2 emissions:
Number of km: 638,331 km
Number of Liter: 41,5 l
Total/€: € 62,25
Total/CO2: 109 560 gram CO2
Wow, using the OptaPlanner technology, we were able to save costs and decrease CO2 emissions by 65,7%!
Maybe Sam can think about rewriting his song to use this more eco-friendly alternative…
Curious how we did it? Check out the code here: https://bitbucket.org/xploregroup/infofarm-sam-gooris-routeplanner/src/master/.