Our champion has a heart of gold
This week, we announced the winners of our Travelling Salesman Competition. Of nearly 800 contestants, we couldn’t have found a more deserving winner than Petr Lavička.
Years ago, Petr promised his parents that he would take them to some dreamy faraway destination like Hawaii. He has now delivered on that promise.
Petr thought that his parents would never accept such a gift if he’d paid for it with his own money, so instead, he entered them into his team as ‘contestants’ for our competition — without their knowledge.
We’d issued a challenge to the development community to solve an age old np-hard problem. We used real Kiwi.com flight data and they had to find the best route of visiting all cities in a given list. At the toughest level, the teams had to find the best price of visiting 300 cities in one trip.
More than ten years ago, Petr’s parents sold their house in Jihlava — where he grew up — to ensure that he and his brother and sister received the best education. The whole family now lives together near Prague, each with their own flat in the same big house. Petr spends his free time renovating the house, playing ice hockey, studying C++, and going to the gym with his brother and his brother-in-law.
To celebrate the moment that he was announced as our champion, Petr’s mum gave him a hug and he and his brother fist-bumped before he went up to accept his giant cheque. They had travelled here together for the award ceremony. His parents have never flown before, and Petr’s joy at being able to fulfil his promise was clear to see.
To build the winning solution, he took just one day’s holiday from his job at OKSystem where he works as the Software Development Team Lead.
We’d been wondering about this team that was performing so amazingly, and that consisted of members all with the same surname. Our guess was that the developer was hoping to take his children with him on his Trip Around the World. We were close.
The other winning teams were also thoroughly deserving of their success. They all bonded at the Impact Hub Brno where we held the event and at the after party at Malej Velkej.
Our silver medalists
The team in second place was made up of three guys from Slovakia — Juraj Škvarla, Rastislav Kudla, and Tomáš Putnoky.
Juraj and Rastislav travelled from Košice for the event. They’ve known each other since high school and are both keen snowboarders. Juraj is a chemist at APIGENEX sro, and Rastislav and works at The Technical University of Košice with Tomáš.
Jurai’s combined knowledge of chemistry and coding is fascinating. He compared one of their algorithms to the process of tempering steel to increase its strength. He’s also a talented athlete, specialising in decathlons.
Rastislav enjoys adrenalin sports and goes out mountain biking and whitewater rafting when there’s no snow to carve. With their prize, they may go somewhere warm with sunny beaches and palm trees, although Scandinavia also came up as an option.
Our bronze medalists
The team that took third place was a group of guys from Prague who’ve all known each other a long time — Ondřej Jamriška, Jan Keller, and René Kratochvíl.
Two of them attended primary school together and they were all at the same high school. Ondra is currently working in Computer Graphics at the Czech Technical University in Prague, while Jan specialises in visual recognition technologies with Eyedea. They employed brute force a lot more than the other two winning teams and achieved a result very close to that of the team in second place.
The problem
Six months ago, Kiwi.com solved the Travelling Salesman Problem so that we could start offering our more adventurous travellers a completely new and unique way of planning their MultiCity trips. The problem was difficult, and after solving it, we wanted to share the experience with our code.kiwi.com followers and the greater IT community. For the sake of the competition, we removed factors that would just further complicate the solution, such as the desired time of stay in each city.
Take a look at Ondřej Veselý’s recap to see what technologies we used to run this competition.
The winning solution
Out of 293 teams, only 71 made it to SSH and just 49 of them returned results within 30 seconds for all levels — up to the 300 city level.
There was a pattern among the top three teams. They all used C++, and they’d all known each other a long time.
The top two teams had very similar solutions, both using the Simulated Annealing Algorithm. They first got a random permutation and then swapped the cities. Whenever the price was better, they accepted the new state, but they would also consider how far they were from the beginning. This algorithm is superior to the Hill Climbing Algorithm because it uses cooling to get a global optimum, instead of a local one.
The difference between first and second place was a hot topic. Petr managed to get the lowest price because, at the 300 city level, he did 120 million swaps — doubling the speed of the team in second place. Petr’s solution included parallelisation with a different seed of randomisation on each of the four processor cores of the server.
How did Kiwi.com solve this?
We used brute force with a highly tuned C++ implementation. We also only need to search a small number of cities because no one in their right mind would want to visit 300 cities in one trip. We still have to consider other factors such as time of stay in each city, which increases the complexity exponentially.
Thank you to all competitors!
We were greatly encouraged by the positive spirit that you all brought to the competition and the award ceremony. Thanks so much for your participation. Stay tuned because we’ll be running more competitions like this in the near future.
Take a look at some pictures from the event, the results, our slides, and the video footage.
