4 ms·

My goodness, a HN topic I can speak on with some level of expertise! I developed and deployed a rail yard scheduling application based on MiniZinc which is bei

My goodness, a HN topic I can speak on with some level of expertise! I developed and deployed a rail yard scheduling application based on MiniZinc which is being used daily in production at several sites by one of the largest rail network operators in Australia. Like others here I had started out with the free coursera courses a couple of years prior and was really taken by the declarative nature of the language. When approached about the yard scheduling problem I thought it seemed like a good fit and was able to quickly generate a proof of concept. I spent the next 2 years iterating on it until it was able to handle all of the real world (and real-time) constraints. The topology: - A yard has many tracks (~40 in our largest case) - A track has many track circuits (this reflects the underyling control system) - ~ 250 track circuits - A circuit can only be occupied by 1 train at a time - A train occupies many track circuits - This yard was a staging point for 2 unloading locations - Each unloading location had many loaders The dynamics: - Trains entered the yard primarily for the purpose of proceeding to the unload and unloading - Most trains required 'provisioning' on certain tracks before or after unloading - Some trains required' shunting', making or breaking a consist into separate peices for repair or reconfiguration - Some trains required manual examination, meaning adjacent tracks must be vacant while the inspection took place - There are many routes trains can take (we pre-calculated these) - There were multiple train operators using the yard - Each operator had soft or hard constraints on where and how they would like their trains to operate - The primary objective function was meeting the agreed unloading time at the port and completing all maintenance and inspections - Secondary objectives were queuing times, route preferences The implementation: - ~50k python codebase - Data read from 4 internal systems for maintenance requirements, schedules, etc - Telemetry from the train control system used to determine train location within the yard - Data was stored in python using attrs, cattrs and roundtripped to JSON - MiniZinc models were compiled on demand, this was a massive help in performance and flexibility - Frontend was a Streamlit app which displayed schedules using Altair/Vega-lite - The core 'solve' method was used in a variety of ways, you could reschedule a single trains, or many trains at once (the ideal), or a heuristic where trains were scheduled in dynamic batches (required for longer +24hr runs) - The frontend exposed a '1 click schedulers' which would bring in all the data and produce a feasible schedule very quickly (<1min) with a heuristic - Once the business was confident in the tool we had it running inside a container on an hourly basis to continually produce optimal schedules based on the latest available data which was the advertised to operators - Used Google OR-Tools as the backend solver which was by far the fastest - Trains were scheduled using 1minute time blocks Reflection: This was an extremely challenging project for a lot of reasons, mainly because I was a 1 man team and trying to learn on a deadline, also this was during covid and I had nothing else to do so it became quite all consuming. I have since thought that if I could do it all again would the approach be different? Of all the parts of the tech stack I enjoyed MiniZinc the most and would happily use it again. Modelling with constraints is not easy but there is a rock solid gaurantee that comes with it that pleases me greatly. As other people have said there is a lack of intermediate or advanced level "real world" tutorials which I completely agree with and am working on in my spare time. I would say that things got a lot easier once I stopped trying to represent the entire model ahead of time in one minizinc file, and instead compiled models as required from the python side based on the data I was dealing with. Python was great for the POC stage and horrendous once it got to a certain size. Alas a rewrite was never in the cards. We dealt with it by using type hints everywhere Streamlit is absolutely not fit for purpose for anything beyond hello-world, at least at the time I was using it. Unfortunately I had no experience in frontends at all and just needed a way to expose the model to end users and display results so we made it work. Altair/Vega-lite is a fantastic charting library which I would readily use again. Being able to produce standalone gantt-style train schedules complete with interaction was a major win for both end users and myself for debugging. I have to duck off but love talking about this stuff, you can reach me at "justin dot rawlings at protonmail dot com" or jmjrawlings on github.

montecarl 3y ago
How can you be sure that your constraint model is correct? When the models are so complex that seems like a real challenge! In your case was it possible to take a proposed solution and verify that it does not have any issues? Are there many other safeguards in place to prevent train collisions or invalid schedules?
- jmjrawlings 3y ago
  Fortunately the colleague who proposed this project was a former train controller with encyclopaedic knowledge of the particular yard and its operations. You find that all of these experienced train controllers can just look at a schedule and instantly tell you if it's viable or not. This was a really important part of development because I had rapid feedback and could prioritise the features that were really important to the people on the ground. The model was in user-acceptance testing phase for almost a year until it was feature complete, had acceptable performance, was verified by the controllers etc. I should clarify that the model was not in charge of actually telling trains where to go. Train Controllers are solely responsible for that and do so using a Train Control System which has rigorous safety measures in place to ensure collisions do not happen. The model was a decision support system for the controllers. It showed them how they could best run the yard given the current state of play and expected arrivals. Controllers were absolutely free to disregard the advice which certainly happened earlier on but as the model got better and better this became less of an issue. I should say the main reason I could 'speak the same language' with the end users in this case is due to the vega-lite schedule visualisation. Every single part of the constraint model (trains, tracks, tasks, track failures, even the objective function) had an analagous visual representation on the diagram which meant controllers both confident the model did what I said it did, and they could also easily point out errors by referring to the diagram. A big feature of this model was that there was essentially 0 abstraction over what was happening in the real world. The model took inputs from all of the exact same systems that train controllers used, and produced results that tied directly back to the track circuits of the train control system. This meant that we could view historical yard performance, current yard state, and future optimised schedule all on the same diagram which was so great for debugging and verification.

montecarl 3y ago

How can you be sure that your constraint model is correct? When the models are so complex that seems like a real challenge! In your case was it possible to take a proposed solution and verify that it does not have any issues? Are there many other safeguards in place to prevent train collisions or invalid schedules?

jmjrawlings 3y ago
Fortunately the colleague who proposed this project was a former train controller with encyclopaedic knowledge of the particular yard and its operations. You find that all of these experienced train controllers can just look at a schedule and instantly tell you if it's viable or not. This was a really important part of development because I had rapid feedback and could prioritise the features that were really important to the people on the ground. The model was in user-acceptance testing phase for almost a year until it was feature complete, had acceptable performance, was verified by the controllers etc. I should clarify that the model was not in charge of actually telling trains where to go. Train Controllers are solely responsible for that and do so using a Train Control System which has rigorous safety measures in place to ensure collisions do not happen. The model was a decision support system for the controllers. It showed them how they could best run the yard given the current state of play and expected arrivals. Controllers were absolutely free to disregard the advice which certainly happened earlier on but as the model got better and better this became less of an issue. I should say the main reason I could 'speak the same language' with the end users in this case is due to the vega-lite schedule visualisation. Every single part of the constraint model (trains, tracks, tasks, track failures, even the objective function) had an analagous visual representation on the diagram which meant controllers both confident the model did what I said it did, and they could also easily point out errors by referring to the diagram. A big feature of this model was that there was essentially 0 abstraction over what was happening in the real world. The model took inputs from all of the exact same systems that train controllers used, and produced results that tied directly back to the track circuits of the train control system. This meant that we could view historical yard performance, current yard state, and future optimised schedule all on the same diagram which was so great for debugging and verification.