Can computer modelling be used in the testing and designing of timetables on a large scale?

[bspahh]

Regulation/recovery strategies and passenger loadings themselves have a circular relationship to the timetable*, as well as being influenced heavily by performance regimes. e.g. delay may be minimised overall by cancelling a train, but the TOC will not do that if that results in a net greater financial penalty, and the relative incentives may vary through the life of the franchise. It's often perverse, but it's reality.

*Good example: Since, May 2018, the 1Txx King's Cross-King's Lynn services have been more commonly known to pick up calls at places like Hitchin during disruption to other services, as there's a bit more natural 'slack' to take them up. Pre-May 2018 you generally wouldn't have done, as it would have messed up the King's Lynn single lines too much.

RailSys is itself interesting work when you get to the analysis part; going through data, picking out trends, drawing conclusions, making recommendations. Even sitting with actual signallers playing through example scenarios!

Modeling can give useful answers, but the skill is in asking the right questions, and judging the reliablilty of the prediction. It is pointless to ask "what is the best timetable?" if you wouldn't then act on it.

From a static timetable, you could calculate the slack in the schedule, so that you can judge when there is time to add in an extra Hitchin stop, or when you can delay the departure of a train https://twitter.com/GeorgeFreemanMP/status/1158656855373221889 as an MP runs down the platform.

With a dynamic model of the network, this could add in live data from temporary speed limits, one-off paths for a freight train, or late running for other trains. These calculations would be pretty quick for just the local area, for a short time window. Predicting the knock on effects across the whole network in 18 hours time would take more time, be less accurate, and perhaps not worth the bother.

Another approach is to have a model which checks for specific scenarios and gives a warning if it finds something that it recognises. This is annoying when its an animated paperclip in Word and you're typing a letter. If its an alert which flags an issue where there is a strong chance of it being a problem, or if there is small chance of something really bad. This can be a black box model, where you don't have to understand the precise meaning of the calculations.

 

[Ianno87]

Modeling can give useful answers, but the skill is in asking the right questions, and judging the reliablilty of the prediction. It is pointless to ask "what is the best timetable?" if you wouldn't then act on it.

From a static timetable, you could calculate the slack in the schedule, so that you can judge when there is time to add in an extra Hitchin stop, or when you can delay the departure of a train https://twitter.com/GeorgeFreemanMP/status/1158656855373221889 as an MP runs down the platform.

With a dynamic model of the network, this could add in live data from temporary speed limits, one-off paths for a freight train, or late running for other trains. These calculations would be pretty quick for just the local area, for a short time window. Predicting the knock on effects across the whole network in 18 hours time would take more time, be less accurate, and perhaps not worth the bother.

Another approach is to have a model which checks for specific scenarios and gives a warning if it finds something that it recognises. This is annoying when its an animated paperclip in Word and you're typing a letter. If its an alert which flags an issue. This could be where there is a strong chance of it being a problem, or if there is small chance of something really bad. This can be a black box model, where you don't have to understand the precise meaning of the calculations.

That's effectively what Traffic Management does - tell you the consequences of a single decision across the next 1-2 hours or so.


But you dont want to do that every time. In many cases, a pre-planned off-the-shelf strategy saves time and effort, especially where there is a standard hour timetable with a predictable consequence.

Micklefield Jn is the standard example - always hold the stopper from Selby to let the TPE goes first....until the TPE is more than (say) 8 minutes late leaving York, in which case send the stopper first as the better outcome overall.

 

[rf_ioliver]

Mod Note: Posts #1 - #55 originally in this thread.

Well one can imagine, with the computing power at our disposal, we could build a model of the entire railway network and then automate timetable generation based on optimisation for various outputs that would be put into the system.
Would take quite a while to build the physical model and get it set up, but I imagine you could generate timetables in a matter of days, given a fast enough computer.

Oh I love this stuff...regrettably timetabling is mathematically hard, meaning you just can't solve it with a computer - well you can, but one of three things will happen: we just don't have enough CPU availability to solve it in a reasonable amount of time, but, even if we could we might hit the problem that we don't have enough memory available, and finally, even if we do have enough CPU and Memory, we might not have enough time. Unfortunately we're not just talking about one or two super computers, but rather trying to find the question to the answer 42 computer capabilities...or bigger. In other words, every time you add an extra variable to the model, the CPU/memory/time requirements increase polynominally, eg: 2-stations, single train = seconds to solve; 2 stations, two trains + crew + passing place + delay recover = minutes, 1000+ stations/trains etc = lifetime of Universe ^ lots and a bit more.

Timetabling isn't that complex a problem to specify, just solving it for reasonable solutions. There's a huge amount of work on optimisation, eg: https://core.ac.uk/download/pdf/18511383.pdf which reduces the problem to SAT and demonstrates it is NP-complete: https://en.wikipedia.org/wiki/NP-completeness . This is cool at a mathematical level, but pretty bad for large, general cases.

There's also a huge body of work on optimising the problem itself; so instead of making the perfect timetable you try and made something that is good enough (for some defintion of "good enough). For example, a trivial solution is to run a single train from, say, Cardiff to Swansea, every day at 9 arriving at 12 - unfortunately that isn't a good solution for everyone else.

Then there are the algorithms for solving this themselves - and there's even more work there on making these better. While some of these can be parallelised, some can not, so just thowing additional cores at this won't help - there are all sorts of interesting interdependencies here, even in highly parallel cases - and that's before you start actually throwing this at a real problem.

Someone mentioned AI ... well the good news is we already use AI, the bad news is that AI is basically optimised searching algorithms which is the original problem to be solved.

Building the model of the network and trains - actually that's quite easy and probably wouldn't take that much storage. The basic rules about track occupation etc, again fairly easy. Hints and optimisation are given to the software in terms of fixed situations, eg: a train with a given path and other parameters leaves London Euston, every hour towards Glasgow. Other things such as deliberately weakening certain situations, eg: connecting trains might be missed to ease the model and actually allow a solution.

So, basically there does exist an algorithm for rapidly generating timetables in reasonable time (eg: minutes/hours) on a normal computer. The solutions aren't necessarily going to be good and it doesn't scale beyond some simple models.

 

[Horizon22]

I remember a trip to NS in Netherlands and, whilst I was a little lost with some of the detail, some experts were I think essentially explaining that they'd essentially over a decade built a complete online model network of their system. This is whilst I was slightly involved in planning.

As someone who used to work in transport planning the quality of the model is one thing, but the quality of the personnel interpreting the model is also key. You'd have to assess a huge range of competing factors and this will be years of work across a national network. Regional models might be more feasible, but each has interactions with the boundary network. In addition, there are differences between pathing, junction interactions and platform occupancy. The mathematical balance to make this all work requires a lot of skill and expertise.

You can also make something work in principle, but also some timetables are better able to cope with disruption that others. All in all, a huge amount of work.

 

[Camden]

Given the amount of data we produce, I have no doubt that AI and machine learning could create a robust timetable that takes account of all the railway basics, plus a lot more.

For example, combining datasets a computer model could see that there is a school within a stations catchment, understand whether that school is in session on a given day and the hours it operates, further understanding the factors of distance from the station and area demographics to determine whether at certain times of the day, combined with the rolling stock planned to be on use on the line, more time is needed at the station call to avoid falling behind due to an influx of students. Automatically then calculating the impact on conflicting services and making adjustments as necessary.

It would be an extraordinary effort, though, versus retaining and training up human knowledge.

If it doesn't already exist, a better tool might be a whole network simulator into which timetables are loaded, and then run with some basic parameters to see how well traffic flows with all being well. That could easily simulate impact of individual delays, and even compound delays to a certain extent. Judgement calls can be made whether to adjust, or issue advice on how to mitigate risk of delays/how to deal best with delays if they arise.

 

[rf_ioliver]

Given the amount of data we produce, I have no doubt that AI and machine learning could create a robust timetable that takes account of all the railway basics, plus a lot more.

Modelling it is not the issue - that's actually the easy part. The trouble is that the whole problem is mathematically "difficult", regardless of the algorithm chosen ( AI and ML are just more sophisticated searches ). There are some optimisations you can perform to simplify (aka compromises) the process of getting to the result, but to actually obtain a "correct" or even acceptable result for this kind of problem falls into certain mathematical complexity classes which proclude getting to that answer with available computing power, memory and/or time.

Forget AI/machine learning - they're just algorithms that work over that model to produce a result - and in effect what you end up doing is adding another layer of algorithms to an already mathematical intractable problem. Now there are some good/nice/elegant results for some problems, eg: travelling salesman, where a result can be obtained using clever technqiues ( let's say AI in its absolutely broadest sense ) but these models tend to be relatively simple (even if apparently large and complex) and the algorithms build to solve that particular problem.

Wikipedia has a good article on the base problem:: https://en.wikipedia.org/wiki/Travelling_salesman_problem with links to https://en.wikipedia.org/wiki/Tube_Challenge

 

[The Planner]

If it doesn't already exist, a better tool might be a whole network simulator into which timetables are loaded, and then run with some basic parameters to see how well traffic flows with all being well. That could easily simulate impact of individual delays, and even compound delays to a certain extent. Judgement calls can be made whether to adjust, or issue advice on how to mitigate risk of delays/how to deal best with delays if they arise.

Performance modelling tools for timetabling have existed for years and years and have been spoke about in the thread. The most prevalent one is RailSys and has been used for a decade or more within NR, others before it like VISION also. You can input historic delay into it and it will produce simulations on how punctual a timetable will be. It is however still a big task and takes a big chunk of computational power. To do a model of the entire country in one go would be incredibly time consuming and difficult to incorporate as part of the normal timetable process. I've no doubt it will get quicker over time though.

 

[Bald Rick]

Performance modelling tools for timetabling have existed for years and years and have been spoke about in the thread. The most prevalent one is RailSys and has been used for a decade or more within NR, others before it like VISION also. You can input historic delay into it and it will produce simulations on how punctual a timetable will be. It is however still a big task and takes a big chunk of computational power. To do a model of the entire country in one go would be incredibly time consuming and difficult to incorporate as part of the normal timetable process. I've no doubt it will get quicker over time though.

Indeed. I did my first modelling in VISION in 1992...