Round 1: Completed

Train Schedule Optimisation Challenge

Hidden

Optimizing train schedules

SBB CFF FFS

32.8k

164

209

SBB Swiss Federal Railways manages one of the most densely-used mixed-traffic railway networks in the world. Every day we transport over 1.2 million people and carry 210’000 ton-kilometers of freight on more than 10’000 trains, all while achieving world-leading punctuality metrics.

While average utilisation of our infrastructure (measured in average number of trains per kilometer of track) is already second-to-none, traffic is expected to increase even further. There are also financial incentives to use the available infrastructure to its maximum. However, before trains can run, they must first be accepted into the timetable.

Generating a railway timetable is known to be an NP-hard problem. While scheduling few trains is easy, complications quickly explode with increasing number of trains. The most important factors contributing to complexity are interdepencies between trains (such as connections) and the inability of trains to overtake one another on the same track.

Our goal with this challenge is to solicit ingenious ways to tackle the timetable generation/optimization problem. Do you see a suitable algorithm? A promising AI-approach? A powerful heuristic? We can’t wait to see it in action!

We provide you with a set of sample problem instances consisting of a list of trains to be scheduled, their commercial requirements to be respected and a set of routes they can take through the network. Your challenge is to come up with a timetable for these problem instances.

Evaluation criteria

Each train in a problem instance will define a latest desired arrival times at its stops. It will also define its importance, relative to other trains.

The evaluation criterion for each individual solution will be the weighted sum of all delays. The delay is zero if all trains are scheduled such that they arrive at each of their stops no later than desired. There is also the possibility that some routes for a train are more desirable than others, in which case a solution incurs additional “routing penalty” if an undesired route is chosen.

The overall evaluation criterion will be the sum of each individual problem instance. Missing or invalid solutions are penalized with a large constant, so that it is generally better to find valid solutions to as many instances as possible, even if these solutions have large delays/routing penalties.

If you would like to know the precise formulation, head over to our Starter Kit, in particular the formal definition of the objective function. Be advised that that definition is rather technical. It is important to understand the meaning behind it.

Resources

This Challenge is a little bit special in that to provide solutions, you need to understand a few things about the data format of the problem instances and the solutions, as well as the rules that a solution must adhere to.

We have put together a Starter Kit that contains the necessary documentation in, hopefully, easily understandable form, works through some step-by-step examples and provides some utility scripts that help you get startet. Please head over to the Starter Kit, where the README should guide you through the content available there.

In case of questions about the material, please do not hesitate to contact us.

Here are some interesting blog posts:

Can You Make Swiss Trains Even More Punctual?

Contact Us

Gitter Channel : crowdAI/sbb-challenges
Technical Issues : https://github.com/crowdAI/train-schedule-optimisation-challenge-starter-kit/issues
Discussion Forum : https://www.crowdai.org/challenges/train-schedule-optimisation-challenge/topics

We strongly encourage you to use the public channels mentioned above for communications between the participants and the organizers. In extreme cases, if there are any queries or comments that you would like to make using a private communication channel, then you can send us an email at :

For Press inquiries

Please contact SBB Media Relations at press@sbb.ch

Prizes

The top three submissions will be awarded the following cash prizes (in Swiss Francs):

CHF 7’000.- for first prize
CHF 5’000.- for second prize
CHF 3’500.- for third prize

In addition, we allow for the possibility of awarding several travel grants to the Applied Machine Learning Days 2019 in Lausanne, Switzerland. Participants with promising solutions may be invited to present their solutions in person.

Note that the travel grants are not automatically awarded to the top-rated submissions. It may be possible that a submission does not score very highly because, for example, only half of the problem instances could be solved. However, the approach used demonstrates an original and promising idea that SBB would like to expand upon. In this case, SBB would reserve the right to award a travel grant to such a submission.

In case more than one submission receives the same score, the tie will be broken as follows 1. preference to the submission which requires less total computation time 2. preference to the submission which requires less computing resources 3. if neither of these can be adequately measured or distinguished, the organizers break the ties or decide to award joint prizes.