Hello, everyone, and welcome to this presentation where we talk about automated short-term
train planning, what it means, and how we handle it in OSRD.
So what is the problem?
I would say a train wants to go from station 4 to station bar.
We could easily just find a path, but the problem is there's many trains that have already
been scheduled, and we need to find a path that doesn't just work havoc on a timetable.
We can be completely realistic in our simulation, we assume everything is on time.
We know where every train is going to be located at any time.
So there's a few rules we have to follow to make our blue train go to station bar.
We can't add a train that will be delayed by other trains.
So in those examples, I use a signal system pretty simple where signal is red if there's
a train behind it, and the signal is yellow, meaning slow down, if the next signal is red.
What I mean here is that our train cannot ever see a yellow signal, meaning slow down.
We can add delay before it reaches a signal, but once the blue train sees a yellow signal,
it's game over, the solution isn't valid.
The opposite is of course true.
We cannot cause delay on other scheduled trains, meaning by being here, our blue train cannot
cause another train to see a yellow signal, or red, of course.
This means that we need to handle all the weird behaviours of the signal systems which
can become pretty chaotic quite quickly.
So in these examples, there's one track with signals going both ways, and what happens here
actually is that the signals change around the train, but what really matters is on the
white, the other train cannot actually enter the main track at all, even if it's really
far away, because otherwise it goes face-to-face, and so the last signal would be red, the signal
behind that would be yellow, and as soon as we see it, it's over.
There's some other weird behaviours, sometimes we even have to know in advance where we will
go next to know if we would be delayed.
So in this example, if the train continues straight forward, it would see a green signal,
but if it would turn to the white to the other train, it would see a yellow signal before
we even reach the point where we need to take a decision.
This may seem pretty minor here, but in some signal systems, we need to know, like, kilometres
in advance.
But there are some things we can do.
The train can take detours to avoid busy areas, and we can also sometimes not go at maximum
speed, like if we need to fit between two trains that would go slower than our train,
we can just slow down.
What this means is that this is actually not a good thing for us, because we can't just
find the shortest path and then find the departure time we need to actually consider all the
possibilities that we have.
So that's the problem, and in OSRD, we are currently working on a solution to this problem,
so OSRD, meaning open source railway designer, is a tool, open source tool, that can be used
to edit railway infrastructure and all kinds of simulations on them.
Keep in mind that on these specific features, we've come a long way, but it's still very
much a work in progress, so not everything is properly handled for now, and we're still
currently working on it.
So how do we deal with this?
The main problem is that the solution space has a lot of dimensions, there's of course
position, because we do need to find a path that goes from origin to destination, there's
also time, because the constraints caused by other trains depends only on certain time
interval when the other train is here, and the tricky one is speed, because unlike cars
and bikes and most means of transportation, a train cannot just speed up really fast,
it can take dozens of kilometers to just speed up or slow down.
So if we find, for example, a solution that does reach our destination avoiding all other
trains, but where we reach a destination that says 300 kilometers per hour, this is not
a good solution, it's not even a good approximation of a solution, so we do need to keep track
of the speed that can be reached by the train.
So the way we do that is that we represent the such space as a graph that considers all
those dimensions as well as all the constraints, because once we do have a graph like that,
we can just find a path, and at this step it becomes pretty simple.
So the main challenge is defining the problem itself as a graph.
So in this case, a node would have a position, a time, and a speed to consider those three
dimensions, and must not add defined implicitly.
To get the speed and times, we want train simulations, which we already know how to
do in other parts of the project, so we consider everything we need to, like slope, curves,
rolling stock, data, and everything we need to.
So I have a small, yes, but we actually compute the speed to get the position and the time.
So I have a small graphical representation to explain really what I mean by that when
we add time to our solution, so let's say we start from a simple graph that represents
the physical infrastructure, in this case that would be, for example, track sections,
and what we do is in a way we duplicate all nodes of the graph at different times, meaning
that the point A always represents a specific point in space, but there's a different node
for A at t equals zero, and another node for A at t equals one, and so on.
And then we link them in a way that actually reflects the travel time, so meaning that
we start at A at t equals zero, and we can reach C at certain time after.
And yeah, we can, for example, go from A to F at the same time, because we can't just
teleport there.
And so this graph is constructed as we explore it, it would be too expensive to just build
a whole graph on the whole country at first, so it's all implicitly defined at first,
but then we actually want simulations when we move forward in the graph.
It's also discretized in time, but only when we evaluate visited locations.
What I mean by that is that when we want simulations, we actually keep a full track of the time
at full accuracy, but once we reach a point that has already been visited, if we've visited
it at, like, too close in time, we consider that it's already visited.
Once we have that graph, we just run an A star on the resulting, yeah, on that graph.
So A star means we have two functions to define, we have a cost function and an optimization
heuristic, in this case, the cost function would be the travel time of the train from
start to the current point, and the optimization heuristic is based on geographical data.
And because our heuristic doesn't overestimate the remaining cost, we are guaranteed to find
the optimal solution, so we will find the path that takes the least amount of time.
But I've talked about how we add time to the graph, but I haven't really talked about speed
yet.
So the default behavior is that we always go at full speed unless we need to.
By full speed, I mean not just the maximum allowed speed, like the train speed up as
much as it can and always stays at maximum speed.
So in this slide, we have a space time chart, so we have time on the horizontal axis and
distance on a given path on the vertical axis, and there's an area that is unavailable, meaning
there's another train, for example, in this specific area at a given time.
And I've shown the edges, the hours represent edges of the graph.
So in this case, we can just, if we speed up as much as we can, we can go before that
other train, but we also could go after that train, which would lead to different solutions.
So in this case, we actually create several edges that are all considered as valid paths.
In a way, you can see it as a decision tree, except we can actually reach the same point
through different paths.
Okay, so that matters.
So I've talked about the general principle of the solution.
Now I'll talk about a few problems we faced and how we handled them, a problem out of
them concerned speed, because it's actually a pain to manage.
So as I said, we want simulation to get the speed of the train, but we do that only one
edge at a time when we explore the graph.
What that means is that we don't know what comes after.
So when we reach our destination, we only know that when we explore the graph, the edge
that contains that destination, but that doesn't always leave enough distance to properly break.
So in this example, we have speed plotted with a distance, and we start in the first
stage by going at full speed, and then we see that we need to stop there.
We start breaking, and there's a discontinuity.
This is not a valid solution.
So in the next slide, it's mostly the same situation, but represented differently.
Here we have edges of the graph, where in red we have edges where we speed up, and in
blue where we try to slow down, and we have the same discontinuity here.
To stop at the end of section 4, we need to enter that section at 10 km per hour, but
because we've been speeding up, we had 50 km per hour.
So the way we do this, we handle this case, is that we go back in the graph, we backtrack
to backpropagate the constraints.
So we see that there's a discontinuity there, and what we actually do is that we go over
the previous section, and we create a new graph edge, but this time slowing down, and
we know that we need to enter the last section at 10 km per hour, so we create an edge where
we end at 10 km per hour.
We notice that to do that, we need to enter that section at 20 km per hour, which is still
not the same as the previous edge, so we keep going, and we continue creating new edges going
over the previous section until we have something that looks like that.
We have a valid path that actually stops there.
The two different paths still exist in the graph because if we go another direction or
something like that, we can still find paths that would take the top path.
Then there's another problem, I've talked about adding delay previously to go after
another train, but I haven't explained how we do that.
So as long as we can, we shift the departure time, meaning that the train for example needs
to leave not just at 10 am, but between 10 and 12 or something like that.
So if we notice that the train which the final station, like 15 minutes too early and the
other train is already still there, we just make the new train leave 15 minutes later
and this fixes the problem.
But it is not always possible, like in this example, if we try to shift the departure
time to avoid the problems on section 3, we would cause new problems on section 1.
So we actually need to add delay between two specific points of the path without affecting
the rest and the way we handle this is actually the same way as the other problem, meaning
that we go back, we backtrack on the graph to propagate the delay.
So we actually have the old edges that go at maximum speed, but we have new edges going
from section 1 to 3 that has what we call an engineering allowance.
I can't go too much into details in how it's computed, but basically the idea is that we
can do precisely what we need to.
We add delay between two points of the path by slowing the train down without affecting
the rest of the path.
So this edge is here, isn't changed, this one is actually the same, but this one is
slowed down.
So we're ending the end of the presentation.
So to conclude what we can do, we can find paths that avoid delay on any train, the one
we add and any other, we can take details, we can slow down, we can have all kinds of
way to avoid any scheduled train.
There are some features that haven't really talked about because I didn't have the time,
but for example, the user can input allowance parameter, which means that the train generally
go a bit slower than they can at fastest so that they can catch up their delay if they
are being delayed.
And as far as performances go, it takes up to about five seconds, so it's not instant,
but not really a problem for now, this is good enough.
And there are some features that we still need to work on.
For example, the signaling systems, for now we only support the simplest signaling systems.
The reason for that is because we are currently refactoring the signaling engine in OSRD,
which is actually really amazing and we would have loved to talk about it today, but it's
almost finished and when it is done, we need to plug the two systems together.
There are some features a bit more minor, like for now, the user can set the departure
time and leave the overall time unspecified, we also need to do the opposite, meaning we
need to arrive at a given time and we don't know when we leave.
And we also need the user to be able to say we want to stop there, there and there on
the path.
So I've been faster than I thought, so what I'm going to do is that I'll show a small
video demonstration of the project, this is a few months old, but it shows generally
what we do, what we can do with this tool.
So we are on the Brittany region of France and we add the trains that go from Laurent
to Brest.
We just set the schedule, we have several trains going there, which we can see here.
I won't go too much into details in what the boxes are, but generally it's like if this
box overlaps, a train is slowed down.
So now we ask for a last minute train that starts from Rennes to Brest and we do find
the path.
So I'll explain a bit, I do have time, I do have time.
What we see here, horizontal axis is a time, vertical axis is distance and previous trains
we already added are toward the end of the path, so we see them at the top and the new
train goes over the whole path.
Okay now we add some other trains, no we don't add other trains, we move one of the trains
so that it blocks one, actually the path we took at first.
So if we ask for another train, what we'll see is that it will be shifted to avoid the
previous one.
And we notice that it leaves around 7.20, something like that.
So what we'll do is that we'll add another train, this time going to Kibron called Tirebouchon.
And we'll make it leave around that time.
We add a few of them.
And what we see here is that the train started before, before all those trains that have been
added on the first, actually I'll explain a bit more, the trains we have added diverged
here, like from here they move away from the path we used to Kibron.
But so we only see them up to here and the train we add starts before then it slows down
to enter in this section here.
And we can see the speed of the trains, so it, anyway, anyway, yeah, I'll move on to
the questions.
I have also kind of links, a website for the project, a link, an email, what kind of stuff.
Yes.
Does this kind of solution is used to create schedules in advance?
It's not used to create the schedules, actually, it's used once the schedule is set, yeah.
Like last minute, you need to add a train on a given date.
There's a given date where the, it's something I wanted to talk about, I didn't really have
time in this presentation, so there's a train railway manager offers some paths for trains
and at a given time, those paths are assigned to trains, like train operators who want their
trains on those paths.
And once this is set, there's still room for more trains, and this is what we do here,
we find the room for new trains, yes.
Five seconds response time, yes, for how many nodes and trains?
Not a lot of trains, we don't have the tools yet to import a whole, what we call SR, and
not sure what things, like the whole set of trains on a line, yeah, there's, generally
we test with a few trains, like the kind of things that I showed, and pass over a few
hundred kilometers, and we do know that it doesn't scale that well with a number of trains
and we'll work on that kind of questions when we have something actually working and
finished.
You go, for example, to a fridge somewhere in the country that can have some stuff that
I actually didn't really hear your question that well.
Sorry.
If I got it right, like you asked about the troubles
we can find along the way, mostly we assume
at these steps that everything is on time
and works as expected.
There's, when people like work on the tracks or something like that
we know in advance that it's unavailable.
Yeah.
It's not real time.
Not real time. Yeah, it's not real time.
It's actually not exactly last minute.
It's generally a few days before the train's actually won.
So yeah, it's a fair assumption to just...
Yeah.
There was one question on the chat
that this problem might be a good candidate
for an artificial intelligence plan or so.
I have to consider that.
And please repeat the question.
Someone asked on the chat if artificial intelligence
has been considered for this problem.
We do have considered them in the project in general
but not specifically in this context.
I personally don't think it would tell that much.
I mean, it would be a good heuristic to know
which path to evaluate before another
and not to still find a good path towards the end.
We do need to explore all the kinds of solutions.
The place where we thought about using artificial intelligence
is a decision like which train goes before one another.
The context where we really thought about this is not in this case
but like when trains are actually running late
which one do we favor over one over the other.
I think it would be a good heuristic in this case
but not really that important.
There was another question.
What are the biggest remaining challenges to be solved?
Definitely the signaling interface,
plugging the things together because as I showed in this slide,
this problem, this is a pain.
We do have some leads, like some intuitions
that we could do things in some way
but I won't go too much into details
because we don't know if that's true
and the solution we are thinking about is valid or not.
But we'll work on that in the next few months anyway.
I'm working in an international organization
that is handling aviation through the place
so same kind of problems but with additional dimension.
And I'm asking how have you managed
or your organization has managed to say
we will do that open source
and we will have this type of solution available for others.
So I guess you are working for SNCF
to get some money from SNCF and make open source.
How have you got agreement on that?
So the question is how we managed
to make the project open source in SNCF.
So I'm not actually the one taking those decisions
or even negotiating them.
But the general idea I think,
I mean that's my vision of it,
is that we don't have any competition
or something like that.
We won the infrastructure for France
and I think no one else will.
So maybe the other countries nearby
have the same kind of problem
and maybe they could use our solution
and maybe contribute to that solution to these tools
and generally it makes more sense
to contribute than to compete in this context.
Thank you.
Yeah, cool. Thank you for this question.
So the presentation has arrived on time.
We are starting in a few minutes with the next slide.
Thank you.