Loading
Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more

Train Schedule Optimisation Challenge

Optimizing train schedules


Completed
209
Submissions
419
Participants
23914
Views

Overview

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.

dark-evening-light-trails-434415.jpg

Evaluation

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.

Rules

The following rules have to be observed by all participants:

  • participants are allowed at most 5 submissions per day
  • when evaluation individual solutions directly via the REST-API, a limit of one REST-call per minute shall be observed
  • In order to be eligible for prizes
    • a participant must release their solution unter the MIT License and make it available to the organizers. We encourage all participants to open-source their code!
    • the solutions must be found by the participants’ solver in no more than 15 minutes per problem instance. The resource limits are: 32 CPU cores, 256 GB of RAM. You may use GPUs if desired. If you want to use more exotic hardware, please get in touch with us and we will let you know if your desired setup would still qualify for the awards.
      Before awarding prizes, the organizers reserve the right to verify these limits by running your solver on the crowdAI cluster
    • The results achieved by the solver must be reproducible. If there are randomized portions of your approach, be sure to include seeds to make the runs repeatable.
    • The solver must be generic enough that it is able to handle problem instances that are similar to the nine published problem instances. Custom tuning of the solver to the nine published instances is allowed, but must be within reasonable limits. For example, (hyper)parameter-tuning of an algorithm based on the nine instances is ok. Reading in solutions, or partial solutions, to the problem instances as part of the “algorithm” is not ok.
  • Sample solutions by Admins and Organizers can serve as baselines/benchmarks. However, your solutions must not be based on those. Your solutions must be produced from the problem instances by your code.
  • It is in principle allowed to use commercial solving engines (such as e.g. CPLEX/Gurobi for a Mixed Integer Approach) to attack the problem. However, please contact us if you intend to do that, so we can confirm that the product is accepted for this challenge.
  • In case of conflicts, the decision of the Organizers will be final and binding.
  • Organizers reserve the right to make changes to the rules and timeline.
  • Violation of the rules or other unfair activity may result in disqualification.

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.

train.png

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:

Contact Us

For Challenge-related questions (technical and/or content questions)

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