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

crowdAI is shutting down - please read our blog post for more information

Train Schedule Optimisation Challenge

Optimizing train schedules


Completed
209
Submissions
444
Participants
29677
Views

What tools did you use?

Posted by rockper about 1 year ago

I used Julia. JuMP (Julia Mathematical Programming) makes the modelling quite straightforward. Many solvers can be added as packages, instead of having to install each solver separately. (http://www.juliaopt.org/)

2

Posted by secret_squirrel  about 1 year ago |  Quote

We used AMPL to formulate the problem and Gurobi to solve it. AMPL provides solvers interfacing with it as long as you purchase their licenses. In order to parse the input json, create the AMPL files and the output json we used Lua

1

Posted by twonests  about 1 year ago |  Quote

I wrote a python simulator that you can find here: https://github.com/deuxnids/sbb_challenge.

The simulator is enhanced with a Q-table. State is the position of the train on the network (section_id) + occupancy of the following x sections ahead of the train. Action is the section that the train will enter when leaving the node.

With this simple logic it can happen that 2 trains are mutually blocked. The simulator decide which train should go back and save this information in an “avoidance table”, aka when train_x is on link_x1, train_y should not enter link_y3…

Can not wait to know more about how you guys did solve these problems. Congratulations to the winners!!

1

Posted by Palstek  about 1 year ago |  Quote

I programmed it all in python without any fancy external modules and without any parallelization implemented (because you know, python sucks at being parallelized). It’s a pretty simple iterative approach with some backtracking mechanisms and stuff.

Close call but I guess it was not good enough to win me anything :(

1

Posted by jordiju  about 1 year ago |  Quote

Great topic, thanks @rockper for starting it!

Posted by jordiju  about 1 year ago |  Quote

Close call but I guess it was not good enough to win me anything :(

I wouldn’t say that ;) If your solution is, as you mentioned, still reasonably generic, it might be a very interesting heuristic solver to add to our solver pool.

Posted by Must  about 1 year ago |  Quote

I used python to decompose the global problem into a routing and a scheduling problems, each formulated as MIP and solved by Gurobi. For the routing problem, the main idea was to balance the number of occupations on each resource, so as to avoid congestion on the most used ones. The scheduling part was quite straightforward, with some care to reduce at most the number of disjunctive constraints expressing the order of trains on sections / ressources.

This approach was overall quite fast, with each instance solved between < 1s for the easiest ones and 5mn for instance 5. Probably a better use of the allowed 15mn computation time would have lead to better results, but I didn’t have enough time work on it. Maybe next time…

1

Posted by LeoB  about 1 year ago |  Quote

Congratulations too all of you! I’m impressed (especially with the ones that solved the problem without a solver)!

I ended up with a pipeline controlled by a R program. Along the way the program did the following steps:

  1. Read the Source files and simplifies it
  2. Build the graph for each route
  3. Find the shortest path for each route (wrt the objective function)
  4. Output the problem as a Minizinc problem to a file (reduce some statements that can never be true along the way)
  5. Call Minizinc to compile the file to Flatzinc (for speed reasons without any optimization)
  6. Call the Google OR-Tools Flatzinc-Solver
  7. Read the result from the Flatzinc-Solver and create the JSON result file

Step 2 and 3 where parallelized in R. In Step 6 I run the Solver in parallel. All in all, I ended with around 450 Lines of R code.

1

Posted by jordiju  about 1 year ago |  Quote

I ended up with a pipeline controlled by a R program. Along the way the program did the following steps:

  1. Read the Source files and simplifies it
  2. Build the graph for each route
  3. Find the shortest path for each route (wrt the objective function)
  4. Output the problem as a Minizinc problem to a file (reduce some statements that can never be true along the way)
  5. Call Minizinc to compile the file to Flatzinc (for speed reasons without any optimization)
  6. Call the Google OR-Tools Flatzinc-Solver
  7. Read the result from the Flatzinc-Solver and create the JSON result file

Impressively short and nice use of standard tools! Wouldn’t have believed the flatzinc solver can solve all but instance 09, and most of them very well. Nice!

Posted by Roman Chernenko  about 1 year ago |  Quote

We (me and my teammate johngull) used pure C++ for solving the problem. No additional libraries were used for solving the problem (except the library for JSON parsing).

The algorithm based on the greedy approach. It takes a list of trains in some order and tried to push it one-by-one with the minimal possible score for each. As an initial order, we sorted train by entry earliest on the first station and in topological order by connections (so train that has an outcoming connection to another train, was handled first). On next iterations, we reordered all trains trying to get the better score. We have a few strategies on how to make reordering, one is fully deterministic and some are based on trains score and some random influence. But all strategies have important restrictions - doesn’t break the topological order of trains connections.

After that, we implemented a new starting sort order based on the train’s pairwise scores. So first we solved a lot of small task with each possible pair of two trains ignoring connections. And when we have these pair scores, we construct the initial train’s sort order minimizing the sum of all used pairs. This approach significantly improved the total score and calculation time.

Unfortunately, this approach not worked with task 9, because it has a lot of bi-connections (train A has a connection with train B and vice versa). So in this case impossible to make a topological sort of connections. So when we have seen the first submissions of this task last Monday, we concentrated on solving it and we have a first successful submission on Tuesday.

In this solution, we grouped all trains that have cyclic connections. So in result, we can make a topological sort of groups. Many groups had one train and were handled same as in the first approach. For complicated groups with cycles, we implemented another solver which iteratively tries to guess the arriving time of all trains to transfer stations and use it as a real one. On each iteration, this guess is improved and just with few iterations we got the correct solution for the whole group. Important note, we also added restriction to use sections with different resources on transfer station for trains with bi-connections.

Unfortunately, we haven’t time to fine-tune the solution, while we saw a lot of areas for improvement.

2

Posted by jordiju  about 1 year ago |  Quote

I used python to decompose the global problem into a routing and a scheduling problems, each formulated as MIP and solved by Gurobi. For the routing problem, the main idea was to balance the number of occupations on each resource, so as to avoid congestion on the most used ones. The scheduling part was quite straightforward, with some care to reduce at most the number of disjunctive constraints expressing the order of trains on sections / ressources.

Very interesting, thanks! We also use MILP internally and have always been thinking about decomposing routing and scheduling, but never implemented it. It has drawbacks of course, but fore some instances it’s probably the only way to prevent explosion of the MILP model. Would love to have a look how you choose the routes.

Posted by iquadrat  about 1 year ago |  Quote

My solver is written in Java without any additional libraries. It first builds a data structure with all the potential conflicts where two trains might use the same resource at the same time. It then iteratively picks the worst conflict (according to some simple heuristic) and decides greedily a resolution to the conflict (which train gets the resource at the conflict time) using a second heuristic. For most problems this was enough to find a solution. For the more complex ones, it needs to do some backtracking. Connections are handled in a similar way, iteratively narrowing down the arrival / departure time window.

2

Posted by Alejo  about 1 year ago |  Quote

My solver is written in Java without any additional libraries. It first builds a data structure with all the potential conflicts where two trains might use the same resource at the same time. It then iteratively picks the worst conflict (according to some simple heuristic) and decides greedily a resolution to the conflict (which train gets the resource at the conflict time) using a second heuristic. For most problems this was enough to find a solution. For the more complex ones, it needs to do some backtracking. Connections are handled in a similar way, iteratively narrowing down the arrival / departure time window.

Wow, very impressive!

1

Posted by ms123  about 1 year ago |  Quote

I converted the problem into a maximization problem by giving a profit of 10000 to each train and subtracting the penalty of the schedule. Using this, I made a (randomized) greedy heuristic, which iteratively takes trains, schedules them, and kicks other trains out, when they block the current train. This procedure usually gives feasible solutions for all instances, however with about at least 50 penalty. Thus, I restart this heuristic a few times to generate a bunch of useful routes and put them in a set-covering/partitioning MIP (solved using CPLEX). Finally, I repeatedly solve this MIP and heuristically generate more tours based on the solution of the MIP (e.g., I randomly fix 70% of the trains and look for compatible schedules for the remaining ones). I guess there are still many avenues of improvements for this approach, the biggest issue was the size of the resulting MIP.

1

Posted by jordiju  about 1 year ago |  Quote

Hi all

We have received several questions from interested participants that would like to have a look at the code for the most successful solutions.

Even though we have received access to the code of the leading submitters, we would not want to blindly redistribute it. Instead, if you are one of the leading submitters (say inside the top 10, these approaches all look very promising to me), you might consider publishing your code on a public repo, as user @twonests has done above.

As this would be outside the challenge, you may of course pick a licence of your choice for this repo (or none at all, in which case you retain exclusive copyright).

Apart from participants of this challenge, this might very well arouse interest from other parties as well. For example, we have contact with a couple of research groups at universities that I imagine would be very interested to learn about the many new ideas that have been explored by you guys.

If you decide to proceed, it would be great if you could post the link to your repo also in this thread.

Posted by secret_squirrel  about 1 year ago |  Quote

You can find our code here: https://gitlab.epfl.ch/buetuen/sbb_challenge

1

Posted by Aspaara & Friends  about 1 year ago |  Quote

At the core, our algorithm first determines a path for each train and then greedily schedules all train sections in chronological order, respecting all hard constraints (all business rules except #101). Pre-processing is done to enforce some of the necessary conditions, such as the order of trains giving each other connections that cannot overtake each other.

On all but the simplest instances, this approach leads to situations with trains blocking each other. To avoid such blocks, affected trains are stopped early. Once some blocks have been avoided in an iterative fashion, the algorithm can find an initial feasible solution. After a feasible solution has been found, it is iteratively improved by favoring trains with delays.

In order to find a good first feasible solution, the paths for the trains are chosen according to different criteria, the simplest being shortest paths in terms of the number of sections. The approach is randomized and different methods are tried in decreasing order of likelihood of success.

The search for better solutions is parallelized and done in two phases: First a shallow search to find good starting solutions, and then a more in-depth search on the most promising starting solutions.

Our algorithm is written in Python with only few dependencies (none directly related to optimization).

Posted by LeoB  about 1 year ago |  Quote

My code is now published in my own repository: https://github.com/leobuettiker/sbb-challenge-2018

Posted by iquadrat  about 1 year ago |  Quote

The code for my solution is now available at: https://github.com/iquadrat/sbb-train-scheduler

Posted by DanielLSM  about 1 year ago |  Quote

Do you guys know when the code of the winner will be open sourced?

Posted by jordiju  about 1 year ago |  Quote

Do you guys know when the code of the winner will be open sourced?

It is. Quite literally in the very post above yours you will find the link to @iquadrat’s repo. Also many other solvers have been published here.

Posted by Hubi  about 1 year ago |  Quote

@iquadrat Since you have been the only one of the Top 3 to post your code (so far…), I took some time to look at it - very impressive! I haven’t figured out all the details, yet ;-)

Could you give me some hints to understand in more detail how your code works? - I tried to solve the instances without setting any parameters manually. What do your outputs “Unsolvable problem” (instance 4) and “unsolveable” (instance 5) mean? Is there some fancy method involved that finds out instance 4 or 5 are not solvable with objective 0, or is it just some resource conflict? - How can I get good solutions for instances 4 and 5? If I do it without manually setting the parameters, I get the exceptions written above. Is there some easy way to see which parameters would work for all the instances?

Thanks! Hubert

Posted by iquadrat  about 1 year ago |  Quote

Could you give me some hints to understand in more detail how your code works?

The code first computes a time window for each train where it is allowed to run to be within the rules based on the earliest/latest time restrictions given. So, it gets an earliest/latest time for each segment of each graph where a train can possibly run. From this it creates a map for each resource which records at which time a train might run and computes an “occupation density” over time for each resource. This also gives a list of all possible conflicts between two trains on a resource.

The code then iteratively takes the “worst” conflict (which is based on the density mentioned before), shrinks the time window of the involved trains (based on a second heuristic) and updates all the maps. It does this until either there are no more conflicts left or it finds that for a certain resource and time window there is no possible solution – at which point it backtracks.

  • I tried to solve the instances without setting any parameters manually. What do your outputs “Unsolvable problem” (instance 4) and “unsolveable” (instance 5) mean? Is there some fancy method involved that finds out instance 4 or 5 are not solvable with objective 0, or is it just some resource conflict?
  • How can I get good solutions for instances 4 and 5? If I do it without manually setting the parameters, I get the exceptions written above. Is there some easy way to see which parameters would work for all the instances?

See the readme for the parameters. You need to give the solver an upper param on the penalty score. By default this is 0 which works for all problems except 4 and 5. 4 you can solve by choosing penalty bound 0.1, problem 5 needs a bit more tuning, there is the example for the best solution I found on the readme.

Posted by Hubi  about 1 year ago |  Quote

Thanks for your answer!

One more question: How do you chose the path for each train?

It does this until either there are no more conflicts left or it finds that for a certain resource and time window there is no possible solution – at which point it backtracks.

So do I understand it right: “Unsolvable problem” (instance 4) and “unsolveable” (instance 5) here just means your heuristic(s) couldn’t solve some resource conflicts? Or does it mean there can not exist any solution with objective 0 for these instances?

See the readme for the parameters. You need to give the solver an upper param on the penalty score. By default this is 0 which works for all problems except 4 and 5. 4 you can solve by choosing penalty bound 0.1, problem 5 needs a bit more tuning, there is the example for the best solution I found on the readme.

Did you have kind of a search algorithm for the best parameters, or have you been lucky in guessing good ones?

Best, Hubi