Improve STDCM heuristic

[eckter]

BH

• STDCM performance improvements

This would be the most significant performance improvement (and I don't think it will ever be completely "done"). It's not planned to be done soon, but it's important to keep track on the roadmap. It's also a way to keep track of informal discussions that don't leave any written resource.

Context

STDCM uses an A* algorithm, which uses an heuristic to sort the considered paths. When visiting a location, we know the time it takes to get there, and we estimate the time it takes to reach the destination. Summing the two values give a weight, the lowest weight is evaluated first.

In this context, both the cost functions and the heuristic are time. We are looking for the fastest path.

To ensure that we find the optimal solution, the heuristic must not be pessimistic, it should never give a value higher than the actual time it would take to reach the destination. We can have a tolerance for a few seconds difference (like considering points on different tracks as one), but it can't have different units or an arbitrary weight.

Note: the user can input several waypoints, we look for a path that goes through all of them in order. Because we run a single A*, the cost includes the time it takes to reach the previous waypoints, and the remaining ones need to be included in the heuristic.

It's also a way to cut off paths that can't be fast enough. There is a maximum running time parameter, the heuristic is used to evaluate it and drop the paths that don't fit the criteria. We've talked a lot IRL about methods to avoid exploring "bad" paths using preprocessing - this is the correct way to do it. Excluding paths in a binary way is to be avoided: this method can ignore invalid paths in the same way but also improves the speed at which a solution is found (if one exists).

Current situation

The heuristic is based on geographic distance. We simply take the distance between the current point and the next waypoint. Because we need a time, we consider the time it would take at the train's maximum speed.

This is significantly underestimating the remaining time, and we can make a lot of significant improvements. It is currently mostly stateless, but we can pre-compute a lot of useful info at preprocessing (or even when loading an infra).

Possible solution

This is a draft. I don't know how well this plan would work out in practice.

I think we should run some preprocessing at the start of the request that would give some static information at the start of every block.

One way to do this is to explore the infra, starting at the destination point. We can compute the actual shortest distance it takes to reach it.

We need a time though, and I don't think we can afford actual simulations. We can use the train max speed, but I would also try to integrate the MRSP. Another possibility to explore would be to run simulations using an extremely coarse time step (but the heuristic may become pessimistic).

Waypoints need to be kept in mind. The data we compute for each block needs to be "for a given number of passed waypoints" as well.

We don't need to explore the whole infrastructure, especially not for every waypoint count.

[eckter]

As noted by @multun: when pre-computing the distance until destination, we shouldn't explore the infra in every direction starting at the destination. We should rather compute it for an ellipsoid around the start and destination, in a way that's similar to an A* traversal that doesn't stop when reaching the destination.