Help me find simple railway management system

[Kemme]

Hello guys

Let's assume we have railway system like this below, it consists of 12 stations and each station is connected to the system through single rail track. There are three trains there and each of them has its ow unique route (eg. B->D->L->J->K->J...->B).



Is there any simple algorithm which would allow for smooth traffic of the trains in this system? Is there any neat idea I can implement here so the trains will autonomously move and will never block themselves?

Every idea will be vital! Thanks in advance.

[SL4P]

I know nothing about train schedules, but it looks like an interesting challenge... a (bit) like PID, whereby you have to accommodate the schedule, speeds, stop times and other arbitrary variables on route availability and multiple entities...

The real trick is that the trains *share* tracks (without sidings) and stations - so delays can accumulate easily.
Fun.

[Ian.M]

Scheduled train movements - no train may start moving without a reservation for all the track blocks it needs to complete the movement, each for a time window with an adequate safety margin either side of the time it will be on that track block.  A train already in motion has absolute authority, and the block reservations it needs  aren't released till it clears each block. Adjust train speed to maintain the schedule.    Emergency stop all if the schedule cant be maintained.   Then, its just a matter of generating and queuing new movements according to whatever algorithm you like and resolving conflicts with a random number generator and train priorities that increase each time the movement is delayed that are compared to the priority of conflicting movements to determine the odds of the random number generator giving that train authority, so no train can be halted forever.   

[jeroen79]

You can make it time based.

The routes the trains take are timetables where each intersection has arrival and departure times based on the start time and the time the train needs to move through each section plus any waits.

Then add some ground rules:

1. A train needs some time to move though a section.
2. Only one train at a time on an intersection.
3. No traffic in opposing directions.
4. No passing.
5. Trains can wait on sections and intersections.

These rules will make intersections and sections inaccessible for a certain time.

For example:
If train 1 has section AB at a given period then the other trains will have BA blocked for that same period.

You can now puzzle out a schedule by moving each train's route back and forth in tme and/or by adding delays until there are no conflicts.

[rstofer]

I'm sure graph theory comes into play pretty soon.  Unfortunately, I know nothing about that subject.

However, it also seems like this problem resembles the traditional 'scheduling with constraints' which had been a business problem that has been solved in various ways for decades (5 that I know of).  A section of track (block) is a resource.  A train is a consumer and it wants to consume a certain number of blocks.  Other trains are also consumers and they want to consume blocks as well.  No two consumers can utilize a block at the same time.

There are going to be two generic solutions:  Let the train with the maximum requirement go first - a greedy algorithm.  The other is 'maximum throughput' where more trains with lesser requirements are scheduled to go first.

I have always admired the zero-one optimization approach.  I have had a textbook on that subject for nearly 50 years!  It was my first introduction to scheduling resources for construction.

http://www.orsj.or.jp/~archive/pdf/e_mag/Vol.13_02_078.pdf

This is a special case of 'integer programming'

http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf


Google search 'binary zero one programming scheduling constraints' or 'integer programming'

I see Matlab in one of the replies, I wonder how that works...

[SL4P]

Before getting in too deep, if more than one train can fit within the length of a single rail segment (per direction),
It may be worth adding ‘virtual’ segments within a longer piece of track.
Thus allowing two trains (in the same direction) with prior awareness that one or both trains may have to stop/wait independently of the adjacent segments and trains.

Still a really inteteresting project!
Is there some value in ‘flattening’ the layout - to simplify visualisation of the map & route options?

[GerryBags]

I found a paper by the gloriously named duo of T.J.J. van den Boom and B. De Schutter called "On a model predictive control algorithm for dynamic railway network management".

http://www.dcsc.tudelft.nl/~bdeschutter/pub/rep/07_009.pdf

The mathematics goes over my head within the first two pages, so I can't evaluate it, but it looks like a very difficult wheel to reinvent when everyone from titans of industry to railway modellers have been looking at the problem for a good 200 years. The early railways, particularly small branch lines, used timetable-based calculations that seem fairly straightforward and should work for a simple setup like the one you've illustrated, but once you start with computer control of signalling, switching points and departure times my head explodes.

[rstofer]

Interesting paper!  I'd have to have a lot more interest in the problem to spend the time working through the math.  In the end, it's a lot of sums.  Notice that in section 4 the authors get into mixed integer linear programming which I hinted at above.

These types of problems turn out to be matrix based.  That's great because a) they can be programmed in Fortran and b) I love Fortran.  I can see how Matlab gets involved because deals easily with matrices.  At least from the programmer's point of view.

This type of optimization is included in the field of Operations Research, usually covered in the better MBA programs and a full blown occupation in some industries (notably aerospace).

[Kemme]

Thanks for your input. I think I'll go the brute force way to establish the train-system-train relationships rather than implementing some clever solutions. For such easy system it will be much faster, for me at least. Anyway thanks for help!