Train scheduling algorithm improvement (non-breaking)

[wag]

Hi, this game is awesome

TL;DR

Improvement to the existing algorithm that would increase train throughput without breaking existing train networks.

Why ?

I now have a large base and the bottleneck is train scheduling to bring ressources to bases, despite optimizing the train network as much as I could.

The current train scheduling algorithm is great but I think it might be improved further.
I guess this was already discussed many times but there are my toughts:

The current algorithm is good to define train ordering with some guarantee of no deadlock if possible which is great.
However with a very large map it means a train could be waiting for ages for some other train to release a lock if the other train is at the other end of the map and could itself be waiting.

What ?

I think the current algorithm can be used as a basis to build a train schedule that would make train scheduling much more optimal without breaking existing train networks and preserving properties of the current algorithm:

1. Build the Optimistic train schedule: from the rail model and from a train program/weight/length it's possible to compute very fast the optimistic schedule of the train (as if it's not blocked or slowed down).

The schedule is a simple list of times the train would optimistically take from the previous stop to enter and leave each crossed rail segment for the configured train program.

2. Add a schedule to each rail segment
Starting with the first train to ask (the highest priority train), the algorithm would insert trains in the schedule for a segment, so no more than one train can be scheduled on the segment at a given time.
The rail segment schedule would replace the current rail segment waiting queue. It could be implemented as a simple linked list of time pairs, maybe with a train reference. It could be invisible for the user.

3. When a train wants to go to its next stop, it would ask to be added to the schedule of rail segments on its path.

A newer/lower priority train would have to wait for the next available time in the schedule. This ensures an older/higher priority train would never be slowed down by a lower priority train.
However a lower priority train can be scheduled before a higher priority train if it fits in the schedule.

If rail segments are linked together (with advanced signals), a train can be scheduled only if its schedule fits for all of the linked segments. It is scheduled as soon as possible given the current segment schedules.

Performance
Optimistic train schedule only needs to be computed when the rails, the train or its program change.
Scheduling rail segments should be quite fast and happens incrementally as train add themselves to the schedule.

[mrvn]

Sounds like you want to plan ahead the complete journey from one stop to the next so the train knows ahead of time where it will stop at a signal and for how long for every signal. That means all trains need to be considered along the full path.

Add to this train priorities and you get cascades and loops. A high priority train plans a path. Suddenly a bunch of lower priority trains get their path blocked and need to re-path. Now one of the low priority trains doesn't get to leave the segment it is at because it's path is blocked. But a high priority train is approaching from behind and gets stopped too, freeing segment it would have reserved. Then a bunch other low priority trains can suddenly go ahead causing the first low priority train to be allowed to drive too. That means the high priority train doesn't stop so it claims the segments again stopping the other low priority trains. Now consider that stations with the same name add even more flexibility...

Endless loop.

Train path scheduling is computationally too expensive to do perfectly. Even with preset train schedules (e.g. one coal train leaves the mine once a day at noon) it is too hard to solve perfectly and still hard to approach an optimal solution. Doing that dynamically for every train that paths if impossible.

You should consider designing your rail network differently, maybe even split it. Collect ore from several mines with short trains to a collection point and then load it onto a long train for shipping to the smelter. Use satelite factories to produce intermediate products instead of corssing through your main base, etc...

[wag]

Sounds like you want to plan ahead the complete journey from one stop to the next so the train knows ahead of time where it will stop at a signal and for how long for every signal.

Yes. Trains would only be scheduled from one stop to their next stop, not beyond. The time spent at the stop is unpredictable and coudn't be planned.

That means all trains need to be considered along the full path.

Only trains crossing the same rail segments, just like now.

Add to this train priorities and you get cascades and loops. A high priority train plans a path. Suddenly a bunch of lower priority trains get their path blocked and need to re-path. Now one of the low priority trains doesn't get to leave the segment it is at because it's path is blocked.

Train priority would work just like now: first train to ask have highest priority on a given rail section (maybe this was not clear in my post).
This mean that this case could not happen: for instance a train deciding to leave a stop always have lower priority than existing trains already waiting for the rail sections crossed, so it could not block other trains already on the path.

The proposal actually preserves the current ordering/priority, just allowing trains to go forward earlier - if that's possible without slowing down "previous"/higher priority trains.

Train path scheduling is computationally too expensive to do perfectly. Even with preset train schedules (e.g. one coal train leaves the mine once a day at noon) it is too hard to solve perfectly and still hard to approach an optimal solution. Doing that dynamically for every train that paths if impossible.

This proposal wouldn't make scheduling perfect but would significantly improve it without taking much more computation time.
Also it's not more dynamic than the current algorithm. Scheduling only needs to happen when a train leave a station.

[McDuff]

Would using the LTN mod help your scheduling? https://mods.factorio.com/mods/Optera/L ... ainNetwork

[mrvn]

@McDuff: No, he is talking about train paths and not the train schedules them self.

@wag: Ok, that totally did not come across in your proposal. So train priorities are simply FIFO and not some new property of trains.

Let me make an example to make sure I understand what you want to change:

Current
Train A leaves a station and gets a path. It follows the path stopping at signals if they happen to be red.
Later train B leaves a station and gets in the way of Train A. Train A has to stop and wait for train B to clear a section.

wag's alorithm
Train A leaves a station, gets path and time+duration for every segment along the path. At this point it knows when it needs to break, when to wait, when to accelerate and when it will arrive.
Later train B leaves a station, gets a path and now it has to fit into segments in such a way that it doesn't overlap any of the times reserved for train A. Train A will still arrive at the expected time while train B has to wait for train A to clear a conflicting segment. Train B has to wait for A even though it arrives first at the signal because it can't clear the segment before train A is supposed to enter it.

Is that correct?

Assuming it is some thoughts:

1) The first train to leave a station (after some idle time) will get a path with no stops.
2) Each station knows when a train will arrive so stations with the same name could be better balanced.
3) Planing a path the train knows when it can enter a segment and when it must leave it. It could optimize it's speed in each segment to minimize the time required. Instead of going full speed till the breaking point hits a red signal the train could go slower so the breaking point hits the red sign just when it turns green. Break early in section X and accellerate late in section X so as to minimize the time spend in the next segment. And so on.

Question: Does a train use fuel while breaking? Or while coasting along on momentum?

4) Disabling a station, manually controlling signals, building or destroying a rail would still cause a ton of path schedules to become invalid, if not all. Finding a path with time and duration for every segment can mean a lot of try&error because while you find a suitable gap in one segments schedule you might notice 100 segments later that you can't clear a segment and aren't allowed to wait in the segment(s) before that long enough to take the next free slot.

[wag]

Ok, that totally did not come across in your proposal. So train priorities are simply FIFO and not some new property of trains.

Yes. I tried to re-write the post to make it more clear.

wag's alorithm
Train A leaves a station, gets path and time+duration for every segment along the path. At this point it knows when it needs to break, when to wait, when to accelerate and when it will arrive.
Later train B leaves a station, gets a path and now it has to fit into segments in such a way that it doesn't overlap any of the times reserved for train A. Train A will still arrive at the expected time while train B has to wait for train A to clear a conflicting segment. Train B has to wait for A even though it arrives first at the signal because it can't clear the segment before train A is supposed to enter it.

Is that correct?

Yes !

Assuming it is some thoughts:

1) The first train to leave a station (after some idle time) will get a path with no stops.
2) Each station knows when a train will arrive so stations with the same name could be better balanced.
3) Planing a path the train knows when it can enter a segment and when it must leave it. It could optimize it's speed in each segment to minimize the time required. Instead of going full speed till the breaking point hits a red signal the train could go slower so the breaking point hits the red sign just when it turns green. Break early in section X and accellerate late in section X so as to minimize the time spend in the next segment. And so on.

Question: Does a train use fuel while breaking? Or while coasting along on momentum?

4) Disabling a station, manually controlling signals, building or destroying a rail would still cause a ton of path schedules to become invalid, if not all.

Yes just like now

Finding a path with time and duration for every segment can mean a lot of try&error because while you find a suitable gap in one segments schedule you might notice 100 segments later that you can't clear a segment and aren't allowed to wait in the segment(s) before that long enough to take the next free slot.

Yes but that would only happen one train at a time, once in a while when a train go for the next stop. Also the algorithm is bounded by the number of train scheduled on the segments.

[mrvn]

4) Disabling a station, manually controlling signals, building or destroying a rail would still cause a ton of path schedules to become invalid, if not all.

Yes just like now

Finding a path with time and duration for every segment can mean a lot of try&error because while you find a suitable gap in one segments schedule you might notice 100 segments later that you can't clear a segment and aren't allowed to wait in the segment(s) before that long enough to take the next free slot.

Yes but that would only happen one train at a time, once in a while when a train go for the next stop. Also the algorithm is bounded by the number of train scheduled on the segments.

No, when a station is disabled, a signal turned red by circuits, a rail added that connects segments, a rail removed that splits segments, a signal added or removed then potentially all trains need to repath. That means right that tick all trains need to find new paths. That already happens but with your idea I fear the cost would increase too much. But one would have to try it on a large train setup to be sure.