search

OpenRailAssociation / osrd

An open source web application for railway infrastructure design, capacity analysis, timetabling and simulation
https://osrd.fr
457 stars 43 forks source link

[META] New STDCM implementation #1960

Closed eckter closed 1 year ago

eckter commented 2 years ago

Optional / to do once the rest is stable:

Cleanup:

Current known bugs:

eckter commented 2 years ago

For now, the plan to implement this is as follows:

The problem is split into two parts:

  1. We encode the state of the infra in a simplified and abstracted way: we only consider a graph of signaling routes, and the availability of route sections is encoded as blocks. This step is likely to be modified once we have a proper signaling engine, but those changes will not affect the other steps.
  2. We run the pathfinding and compute a simulation on the path. Depending on the exact implementation, the pathfinding and simulation can be two different steps, but for now they are done at the same time.

We intend on implementing step 2 iteratively: at first we will only find the simplest paths, where the train always goes as fast as possible. We will then add ways to avoid occupied blocks, by shifting the departure time, adding braking sections, and eventually engineering allowances.

We will still use a greedy algorithm, which means we may miss some possible solutions. As far as we know, the only methods that would find all possible paths would have a time and space complexity we can't afford.

eckter commented 2 years ago

Now that we have an implementation of the most simple version where the train does not slow down, we can list the things that we will need to improve or change.

  1. We need to improve the way we handle visited edges/nodes. Right now we only visit each route once and then consider it "visited". We will need to consider the same route at different time/speed as different edges, but if we do it naively the graph becomes too "dense" and doesn't scale properly. We also have a problem with infinite loops. We will probably need to test for something that isn't plain equality to determine if an edge has already been visited.
  2. When computing the envelope for a given route, we only "see" the tracks on that route. This is a problem because we need access to the tracks before the route starts, at least as far as the length of the train. This is needed to have accurate MRSP and declivities. This is a difficult problem to solve and only causes mild inaccuracies, I suggest we give this a low priority.
  3. When when assemble all the edges to compute the final envelope, we need to add braking curves. This is needed both for the last stop and when there are MRSP drops right at/after a route transition. This can cause a shift between the path we explore and the actual path, which may end up crossing over an occupied block. I don't have a solution to offer for this problem for now, except maybe adding margins. We must keep it in mind when we'll try to delay the departure time until the curve almost crosses an occupied block.
  4. In the pathfinding, we should consider that the cost of an edge is a duration (and change the heuristic accordingly). This would ensure we find the shortest path in terms of time and not distance. But the use of edge locations makes this a bit difficult.

Things that need to be done:

  1. Delay the departure time to avoid occupied blocks. This can be done by keeping the maximum delay we can add at every point of the graph, but we should be very careful about the missing braking curves. We will need some changes in the API service, as the departure time isn't an output.
  2. Add braking curves to add delays to avoid occupied blocks. There are many ways to do this with varying performance costs, I suggest we start by limiting ourselves to changing the envelope where the conflict happens.
  3. If we add the delay as late as possible, the resulting curve will not "look" good. Ideally we should distribute the delay on sections that are as large as possible. We can add an extra post-processing step to turn delays into engineering allowances, whenever possible.

Things to keep in mind, to be done eventually with no real pressure:

  1. Find a way to compute the problem from stop to start (with start time unspecified and end time specified). This should reuse as much code as possible.
  2. There are a lot of small optimizations that can be done, the computing time isn't unreasonably long but it could be better
eckter commented 1 year ago

To add delays in places where we can't delay the departure time, we have several options. Ideally we should be able to output a valid train schedule that can be reproduced in a standalone simulation. To do this, the only real options we have to add delay are engineering allowances and extra stops.

To use either of those, we need to handle backtracking: #2168. And #2006 would make things easier.

Once we can backtrack, the method becomes quite straightforward. When we need to add delay, we first try to delay the departure time (which we can already do). If this fails, we try an engineering allowance, creating a new edge spanning over all of the allowance range. If this fails as well, we try to add a stop. If everything fails, we are at a dead-end.

eckter commented 1 year ago

Outdated: see https://github.com/DGEXSolutions/osrd/issues/3998