sbb-train-schedule-optimisation-challenge-starter-kit

This is a starter-kit Repo for the SBB Train Schedule Optimisation Challenge on crowdAI.

In this repo you will find background material, sample files and support scripts that help you to get started with the challenge.

How to get started?

This challenge requires a bit of explanation before you can get started. While the general idea is quite simple, and there are only a grand total of twelve rules that need to be taken into account when producing a timetable, the data models used require an introduction.

We recommend that you proceed through the documentation in the following order:

1. Quick Introduction to the Timetabling Problem First, read the Quick Introduction to the Timetabling Problem. After this, you should be able to relate to the problem and start to get a feeling for the algorithmic difficulties involved.

2. Worked Example Second, it is probably a good idea to go through the Worked Example. In that document, we take a very simple sample problem, produce a solution from the ground up (in the required solution data format) and then verify that we indeed satisfy all twelve timetabling rules.

3. General Outline After the first two, you may proceed with the further documentation (see below), and maybe start to solve the simple instances in parallel with learning the fine details of the data models and the timetabling rules.

4. Instance Description Once you really want to start solving the instances, you should also check out the description of the instances which gives you an idea about the size (and difficulty) of the problem instances. You should start solving the simple instances first. More information on that in the description of the instances.

5. How to Submit ? The what to submit guide walks you through a sample submission.

What do I have to do?

You must try to generate solutions to the nine problem instances in this folder.

Once you have solutions, you can submit them through the Challenge page on crowdAI.

In order to submit, it is not necessary to solve all nine problem instances. You can also submit an arbitrary subset of them. However, each missing solution will incur a penalty of 10'000 points. As soon as you manage to find a solution with an objective value better (i.e. lower) than 10'000, you should therefore include that solution in the submission.

By the way, we provide sample solutions to seven of the nine problem instances. These seven solutions are also available as a sample submission. You may use these solutions to test the submission workflow and verify the data models. You must not use them as a basis for your solver, however, see the according challenge rules.

The goal is to create a submission with as small a score as possible.

What can I find in this Repo?

• In the Documentation folder you find all documentation texts, such as

  • the Quick Introduction mentioned above
  • the Worked Example
  • description of the input data model
  • description of the output data model
  • definition of the twelve 'timetabling', or business rules
  • A description of the nine problem instances that make up the challenge
  • A note on what and how to submit

• The sample_files folder contains some simple sample instances and solution. We use these in the documentation to explain our data models and the grading function.

• The problem_instances folder contains the actual timetabling problem instances that you need to solve for this challenge. Also, you find in a subfolder sample solutions (although not very good ones) to some of the instances and a sample submission.

• The utils folder contains some utilities such as

  • a script to evaluate individual solutions to problem instances without a "formal" submission. This is very helpful when trying to tune your algorithms. There is also an accompanying notebook explaining its use.
  • a script that transforms the routes in a problem instance into directed graphs in the networkx package. You may find this useful when trying to work with the route graph algorithmically in your solver, or just for visualization purposes.

Author

• Julian Jordi julian.jordi@sbb.ch