Travelling Salesman Challenge

Find the best route of visiting all cities, and win a trip around the world!

A competition for teams of 2–3 members

Assignment

Since Kiwi.com has all the worlds' airline schedules in one database, we can find more than just flights from A to B.
Our search engine can also respond to interesting search requests, like from A to anywhere.
We also offer MultiCity requests, like “I want to go from Brno to Palermo, then to Moscow, and back to Brno”.

An example of MultiCity requests (without specifying time intervals).

This may seem strange, but we sell hundreds of these flights per day.
Another surprising fact is that in a number of cases, passengers don't care about the order in which they visit these cities.
Imagine how this can help an elderly Japanese tourist who just wants to visit the five biggest cities in Europe.
Finding flight connections without caring about the order will enable us to combine hotels to create a "Holiday Plan".
If it's such a great market fit, why isn't every flight search engine doing this?

img2

The issue is, skipping the ordering requirement makes the problem hard. It's an 80+ year-old NP-hard problem.

We love hard problems, and we also want to share the joy of this challenge.
That’s why we've decided to work on it with the wider part of the tech and academic community.

We're rewarding you with flight vouchers!

Task

The input data is a graph defined in CSV with data like this:

img3

The task will be to find a cycle with the lowest possible price for the given N cities.
The difference between this and the classic Travelling Salesman problem is that we specify the day when the flight and the price apply.
The more cities your algorithm can generate with a valid cycle, the more points you get. In general, it's simple. But wait for final rules.

Process and evaluation

There will be two phases: development and evaluation. The development phase will take two weeks.

Schedule

t1

Registration deadline. Assigning servers for teams. 

Sunday, March 5

t2

Deadline for accepting solutions

Sunday, March 19

t3

Evaluation and award ceremony

Tuesday, March 28, 8pm

Impact Hub Brno

marker Cyrilská 7, Brno, Czech Republic

Prizes

1st team

Trip around the world
for the whole team!

Kiwi.com party tickets, and a visit to our Brno offices

2nd team

600 EUR in Kiwi.com plane tickets

Kiwi.com party tickets, and a visit to our Brno offices

3rd team

400 EUR in Kiwi.com plane tickets

Kiwi.com party tickets, and a visit to our Brno offices

Register

We will send you more details right away 

FAQ & Contact

 

How do we find out which solution is the best?

More information find on https://github.com/kiwicom/travelling-salesman/tree/master/scoring_system

Who will run my code and where?

Every team gets SSH access to a Linux-based VPS provided by Kiwi.com. You can develop/debug your code there. Once the deadline arrives, we’ll run the code on this server for evaluation purposes. The access will be given on March 6, after the registration deadline.

Resources: 

dev: 10GB RAM, 2 cores
evaluation: 30GB RAM, 4 cores

How long is my algorithm allowed to run?

30 seconds. 

Intellectual property

Everything you create is yours. Kiwi.com does not have the rights to use it outside of the competition.

Is this the classic Travelling Salesman problem?

This is a more realistic, time-dependent variant of it. It means that flights are available only on given days.

  • All flights are immediate, they take no time.
  • On each day you have to board 1 and only 1 flight.

Where can I ask more questions?

After registration, you will be invited to the Slack channel travelling-salesman.slack.com for direct communication with the organisers.

Alternatively, feel free to send an email to jan.bleha@kiwi.com.

What are the details of the world trip for the winning team?

– All team members must agree on the starting day and specify it via email to janbleha@gmail.com at least two months before the planned departure.
– You may specify the maximum length of our vacation, but Kiwi.com reserves the right to decrease this.
– The whole trip must be completed by the end of 2017.
– Only team members can be part of the trip.
– Kiwi.com creates an itinerary and buys tickets for the whole team.
– Kiwi.com books and pays for the team’s accommodation for the duration of the trip.
– Kiwi.com does not provide any land transportation, visas, meals, insurance, or anything else besides the flights and accommodation.
– If all team members agree, this prize may be exchanged for 1,500 EUR in Kiwi.com vouchers for the team. This has to be done before any booking of the trip around the world.