We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Automated short-term train planning in OSRD

00:00

Formal Metadata

Title
Automated short-term train planning in OSRD
Title of Series
Number of Parts
542
Author
License
CC Attribution 2.0 Belgium:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
You're a railway infrastructure manager. A train operator calls up, and would like to fit a new train in the existing schedule. It should leave at 10am, and it's 8am. How do you make sure this new train won't cause any traffic jams? We discuss what is short-term train planning, what are the challenges involved, and how it's done in OSRD.
14
15
43
87
Thumbnail
26:29
146
Thumbnail
18:05
199
207
Thumbnail
22:17
264
278
Thumbnail
30:52
293
Thumbnail
15:53
341
Thumbnail
31:01
354
359
410
AutomationWorkstation <Musikinstrument>Wave packetSystem programmingDean numberSimulationSolution setDimensional analysisSpacetimeGraph (mathematics)Representation (politics)Function (mathematics)TrailVertex (graph theory)Mathematical optimizationCoordinate systemPower (physics)Phase transitionCASE <Informatik>ApproximationPosition operatorCategory of beingConstraint (mathematics)Keilförmige AnordnungMultiplication signWave packetMessage passingDimensional analysisComputer programmingDecision theorySpacetimeTheory of everythingComputer simulationPhysical systemTrailArithmetic meanWorkstation <Musikinstrument>Arithmetic progressionCausalityGame theorySummierbarkeitGraph (mathematics)Representation (politics)Functional (mathematics)MereologyUniform resource locatorOpen sourceGroup actionPoint (geometry)Graph (mathematics)WordMathematicsBounded variationTwitterControl flowNetwork topologyCore dumpLatent heatTerm (mathematics)Observational studyProjective planePhysicalismPrisoner's dilemmaDirection (geometry)NeuroinformatikData storage deviceDifferent (Kate Ryan album)Cost curvePresentation of a groupRule of inferenceMathematical optimizationSheaf (mathematics)Derivation (linguistics)HeuristicComputer animation
Graph (mathematics)Function (mathematics)Mathematical optimizationCoordinate systemDefault (computer science)Maxima and minimaDistanceSimulationSheaf (mathematics)OpticsMereologyParameter (computer programming)outputSystem programmingGraph (mathematics)Multiplication signWave packetPoint (geometry)Power (physics)Group actionState of matterPresentation of a groupEstimationPressureProjective planePhysical systemVideoconferencingSheaf (mathematics)CASE <Informatik>Keilförmige AnordnungSimulationSpacetimeInternetworkingAreaCausalityLink (knot theory)Cartesian coordinate systemOptimization problemWorkstation <Musikinstrument>Network topologyDecision theory2 (number)Observational studyMathematical singularityBitVideo gameTwitterDistanceArithmetic meanComputer programmingPlanningService (economics)Latent heatMaxima and minimaMathematicsArrow of timeDefault (computer science)Mathematical optimizationoutputHeuristicDirection (geometry)Different (Kate Ryan album)Constraint (mathematics)Computer animation
System programmingPresentation of a groupDemonPoint (geometry)CodeVideoconferencingView (database)Menu (computing)Game theoryHypermediaLevel (video gaming)CuboidTwitterWave packetComputer animation
QuadrilateralView (database)Game theoryVideoconferencingMaxima and minimaHypermediaDigital video recorderWave packetCuboidBitCartesian coordinate systemMultiplication signDistanceTwitterComputer animation
Gamma functionMenu (computing)View (database)Arithmetic meanCommodore VIC-20Execution unitStructural loadGame theoryVideoconferencingCalculusHypermediaDigital video recorderTable (information)Bus (computing)Wave packetComputer animation
VideoconferencingHypermediaGame theoryDigital video recorderBoom (sailing)Hill differential equationCalculusView (database)Multiplication signBitWave packetSheaf (mathematics)Forcing (mathematics)Computer animation
Computer iconHypermediaView (database)VideoconferencingCurve fittingArithmetic meanSign (mathematics)SummierbarkeitCodeZoom lensConvex hullSystem programmingLink (knot theory)InformationEmailWebsiteMultiplication signVideo gameTwitterMereologyInformation securityWave packetMeasurementBit rateOrder (biology)QuicksortNumberLink (knot theory)TorusDecision theoryMessage passingInterface (computing)CASE <Informatik>Context awarenessScheduling (computing)Data management2 (number)TheoryHeuristicDependent and independent variablesArtificial neural networkTrailMultiplication tableRoutingPlanningSet (mathematics)Projective planeScaling (geometry)Line (geometry)EmailComputer animationLecture/Conference
Presentation of a groupContext awarenessPresentation of a groupCodecSuite (music)Computer programmingOpen sourceMedical imagingGoodness of fitFreewareAdditionMachine visionDecision theoryDimensional analysisProjective planeType theorySelf-organizationComputer animation
Computer animationProgram flowchart
Transcript: English(auto-generated)
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? Let's say a train wants to go from station FU 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 wreak havoc
on a timetable. We can't 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 the trains that would be delayed by other trains. So in those examples, I use a signal system, pretty simple, where a 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 is invalid. 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 behaviors 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.
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 behavior. So 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 kilometers
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 an open source tool that can be used to edit railway infrastructure and run 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 paths that go from origin to
destination. There's also time, because the constraints caused by other trains depend only on certain time intervals 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 would do a solution that says 300 km 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 search 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. 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 have 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, the rolling stock, data, and everything we need to.
So I have a small… Question. Is the speed derivable from the position and time? 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 a certain time after.
And we can, for example, go from A to F at the same time because we can't just teleport there. So this graph is constructed as we explore it, it would be too expensive to just build the whole graph on the whole country at first, so it's all implicitly defined at first,
but then we actually run simulations when we move forward in the graph. It's also discretized in time, but only when we evaluate visited location. What I mean by that is that when we run 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 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. The optimization heuristic is based on the 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 arrows 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 of the train, but we also could go after the 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 I've talked about the general principle of the solution, and now I'll talk
about a few problems we faced on how we handle them, some of them concern speed, because it's actually a pain to manage. So as I said, we run 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 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 kmph, but because
we've been speeding up, we're at 50 kmph. 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 kmph, so we create an edge where we end at 10 kmph. We notice that to do that, we need to enter that section at 20 kmph, 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. And 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 when we can, as soon 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 reached 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 this 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, to add 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 these edges here isn't changed, this one is actually the same, but this one is slowed down.
So we're nearing 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 detours, we can slow down, we can have all kinds of ways to avoid any
scheduled train. There are some features I haven't really talked about because I didn't have the time, but for example the user can input allowance per meter, which means that the train generally goes 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. 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 arrival 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.
OK, so I've been faster than I thought. So what I'm going to do is 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 in the Brittany region of France and we add a train that goes from Lorient 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 on what the boxes are, but generally it's like
is this box overlap or a train is slow 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 in a bit.
I do have time, I do have time. What we see here, horizontal axis is the time, vertical axis is distance, and previous trains we already added are towards the end of the path, so we see them at the top, and the new train goes over the whole path.
OK, 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 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 Quiberon, called Terbouchon,
and we'll make it leave a bit 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 diverge here, like from here they move away from the path we used to Quiberon, 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, I'll just move on to the questions.
I have also all kinds of links, a website for the project, GitHub link, an email. Yes? Does this kind of solution use to create schedules in advance?
It's not used to create the schedules, actually. It's used once the schedule is set. Like in the last minute? Yes. You need to add a train? Yes, that's it. There's a given date, something I wanted to talk about but 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 run 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 room for new trains. Yes? Five seconds response time? How many routes for how many nodes and trains? Not a lot of trains.
We don't have the tools yet to import a whole, what do you call it, SR. I'm not sure what the English... Like the whole set of trains on the line. 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 once we have something actually working and finished. We don't have a code yet.
Why is the problem you have in local constraints, like especially in London, where you share data to train all the train workers? 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 this step that everything is on time and works as expected. When people work on the tracks or something like that, we know in advance that it's unavailable.
It's not real time, it's actually not exactly last minute, it's generally a few days before the train is actually one, so it's a fair assumption to just...
Theoretical time table. Yeah, theoretical time table. 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. Please repeat the question.
Oh, yeah. Someone asked on the chat if artificial intelligence have 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 help that much. I mean, it would be a good heuristic to know which path to evaluate before another, but if we want to still find a good path towards the end, we do need to explore all the kind 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 train are actually running late, which one do we favor over one over the other. I think it could 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, if the solutions we are thinking about are valid or not. But we will work on that in the next few months anyway.
I'm working in an international organization, but handling aviation through planes, 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. So you had 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 want 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. Thank you for this presentation. The presentation has arrived on time.
We are starting in a few minutes.