Better STDCM algorithm

[eckter]

We need to discuss and find a better algorithm to compute STDCMs, as the one we currently use has a very poor complexity.

I have a draft of a new algorithm that we can use as a place to start, but there are still some areas where I don't exactly know if and how they can be computed.

General idea

I think the way to go about it is to represent the problem as a graph so that we can run conventional pathfinding algorithms (and possibly reuse the pathfinding code we already have). This also makes it easier to use an algorithm with a heuristic such as A*, which we may need because evaluating the neighbors would be a costly operation.

To do this, we need to define a node, an edge, and how the neighbors are computed. Ideally we would do this with no backtracking.

I assume we have access to a route graph, with RouteEdge and RouteNode.

Classes

class TrainState {
    public final double time;
    public final double speed;
}

/** A node in the STDCM graph.
 * It has a location component (route node) as well as two train states:
 * one for the fastest run time, ensuring we don't reach occupied sections too early,
 * and one for the slowest run time, ensuring we leave sections before they are occupied again.
 * We can have several STDCM nodes for the same route node, but they should not overlap.
 * */
class STDCMNode {
    public final RouteNode routeNode;
    public final TrainState fastestState;
    public final TrainState slowestState
}

/** Edge between two STDCM nodes */
class STDCMEdge {
    public final RouteEdge routeEdge;
    public final Envelope fastestEnvelope;
    public final Envelope slowestEnvelope;
}

Examples

In this example : occupied sections are filled in red, fastest run time is plotted in blue, slowest run time is plotted in green. Each orange line is one pathfinding node. The orange area represents what the train has access to.
This assumes 0 length rolling stock and sight distance for easier plotting, but it can easily be accounted for.

This second example shows why we need both the time and speed for the slowest run time curve : it handles cases where we don't have enough time to slow down

Grey areas, doubts, things to discuss

This makes several assumptions that may not be true or easy to do.

• We assume that any time and speed value in the node interval can be used to start computing the following curve. This is probably false in some edge cases (such as very short intervals or wonky MRSP), but my hope is that we can at least approximate it.
• Evaluating the slowest run time may be tricky in some cases, especially when there is little margin.

[elzinko]

Some questions :

• How many solution do we want for the result ? only one ? or a space of solutions ?
• Did you plan to reduce the infrastructure graph at first, given the fact that we already know the source and destination ? This would lead to better performance and is not related to the algorithm complexity?

[eckter]

How many solution do we want for the result ?

We need a space of solution for intermediate steps, but we only need one actual solution at the end.

Did you plan to reduce the infrastructure graph at first, given the fact that we already know the source and destination ? This would lead to better performance and is not related to the algorithm complexity?

It would help a lot with the current (bruteforce) implementation but not with a method similar to what I described. If we have an A* with a good heuristic, the search space should grow in an almost optimal way.

[elzinko]

Sorry to ask but why trying to compute a space of solution at first ? My understanding is that A* gives you one solution that is not the best but that is easy to compute.

For A* I guess we need to define G and H.

• For G, my best guess would be the previous node value plus the distance between from the previous node and the actual.
  For H (heuristic), what about using a simple kind of distance computation with GPS coordinates between actual node and final node (destination point) ?

[eckter]

My understanding is that A* gives you one solution that is not the best but that is easy to compute.

A* gives the optimal solution if the heuristic is admissible (ie. it doesn't overestimate the remaining distance). It's something to keep in mind but when dealing with distances and coordinates it's rarely a problem.

why trying to compute a space of solution at first ?

I think the best way to approach this kind of problem is to formally define it as a graph search. That way we don't have to handle the pathfinding itself, we can use A*, Dijkstra, or even a breadth-first search if we want to. We "only" have to define how things are linked together, it's a good way to break the problem down into smaller sub-problems.

For G, my best guess would be the previous node value plus the distance between from the previous node and the actual.

What I had in mind was the earliest time for the node as we want the fastest path (and not shortest). But there are other options, I don't think we'll struggle for this part.

For H (heuristic), what about using a simple kind of distance computation with GPS coordinates between actual node and final node (destination point) ?

This gives a good distance, but if G is a time we need H to be a time as well. But it should work, we can consider the time it would take to travel that distance at max speed.

[elzinko]

One more consideration about reducing the space of search. What about finding the already existing path solutions for such request (source / destination) so that we can build a really smaller graph?
Whether we need a solution space or a single solution, this would lead to really better performance, whatever algorithm we use (brute force or any optimized algorithm).
STDCM needs to perform at production step and not at prospective one. When we want a path for a train, do we really want exotic / weird paths ? But computing solution on bigger space this would lead to such solutions. We could filter those solutions afterwards using some business rules, but reducing the space of search before, based on reality would lead to :

• better performances / scallablity
• solutions that better fit to existing solutions
• lower solutions (weird one excluded)

The question would be "how do we search this existing space of solution" ?

[eckter]

One more consideration about reducing the space of search. What about finding the already existing path solutions for such request (source / destination) so that we can build a really smaller graph?

If we define this sub-space as anything at most k meters away from the optimal path, then this is (roughly) what A* already does, except that the k starts at 0 and grows progressively until a path is found. We will have an upper bound but there are better ways to do this.

We can use the shortest (standalone) path do define a better heuristic, but this is an optimization and it's too early for that. This can be changed later on if we make the rest of the algorithm work.

STDCM needs to perform at production step and not at prospective one. When we want a path for a train, do we really want exotic / weird paths ? But computing solution on bigger space this would lead to such solutions. We could filter those solutions afterwards using some business rules

Not necessarily. If we want to add constraints such as a minimum speed or a maximum total time, it would be both simpler and more efficient to define those in the search graph itself. Any "weird" path would be ignored as soon as it can be considered so.

[eckter]

Another difficulty is how to compute the final speed and position curves, the solution we have implemented is lacking and fails in some cases. This is more difficult than what we originally thought. We have the following problems:

1. The departure time shouldn't be fixed, we need to delay it whenever it's an option to reduce the train occupancy
2. The current implementation with engineering allowances is not flexible enough
   1. If we need x seconds of delay by the time we reach the nth route, we try to put all this delay in the n-1th route. This is not always possible and such cases cause 500 errors.
   2. When adding delay in an area, we never change the speed at the end of this area, we force it to resume at the same speed it would have reached with no delay. This is not always possible and we need a way to lift this constraint.

[eckter]

The details, discussions and meeting notes will now be written in the issue #1960.

The algorithm we will likely implement is not like the one I have described above: as it turns out, the assumptions were wrong and even approximations wouldn't work.