Automated short-term train planning in OSRD
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| 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 | 10.5446/61429 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
FOSDEM 2023349 / 542
2
5
10
14
15
16
22
24
27
29
31
36
43
48
56
63
74
78
83
87
89
95
96
99
104
106
107
117
119
121
122
125
126
128
130
132
134
135
136
141
143
146
148
152
155
157
159
161
165
166
168
170
173
176
180
181
185
191
194
196
197
198
199
206
207
209
210
211
212
216
219
220
227
228
229
231
232
233
236
250
252
256
258
260
263
264
267
271
273
275
276
278
282
286
292
293
298
299
300
302
312
316
321
322
324
339
341
342
343
344
351
352
354
355
356
357
359
369
370
372
373
376
378
379
380
382
383
387
390
394
395
401
405
406
410
411
413
415
416
421
426
430
437
438
440
441
443
444
445
446
448
449
450
451
458
464
468
472
475
476
479
481
493
494
498
499
502
509
513
516
517
520
522
524
525
531
534
535
537
538
541
00:00
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
08:08
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
16:12
System programmingPresentation of a groupDemonPoint (geometry)CodeVideoconferencingView (database)Menu (computing)Game theoryHypermediaLevel (video gaming)CuboidTwitterWave packetComputer animation
16:35
QuadrilateralView (database)Game theoryVideoconferencingMaxima and minimaHypermediaDigital video recorderWave packetCuboidBitCartesian coordinate systemMultiplication signDistanceTwitterComputer animation
17:27
Gamma functionMenu (computing)View (database)Arithmetic meanCommodore VIC-20Execution unitStructural loadGame theoryVideoconferencingCalculusHypermediaDigital video recorderTable (information)Bus (computing)Wave packetComputer animation
17:53
VideoconferencingHypermediaGame theoryDigital video recorderBoom (sailing)Hill differential equationCalculusView (database)Multiplication signBitWave packetSheaf (mathematics)Forcing (mathematics)Computer animation
19:11
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
24:18
Presentation of a groupContext awarenessPresentation of a groupCodecSuite (music)Computer programmingOpen sourceMedical imagingGoodness of fitFreewareAdditionMachine visionDecision theoryDimensional analysisProjective planeType theorySelf-organizationComputer animation
26:34
Computer animationProgram flowchart
Transcript: English(auto-generated)
00:16
Hello everyone, and welcome to this presentation where we talk about automated short-term
00:21
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
00:40
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.
01:01
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.
01:21
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
01:45
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
02:04
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.
02:22
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,
02:44
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
03:03
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.
03:21
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.
03:43
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
04:02
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
04:24
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,
04:45
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
05:03
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.
05:22
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.
05:44
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.
06:00
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
06:22
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
06:44
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.
07:03
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,
07:24
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
07:41
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.
08:02
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.
08:22
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
08:43
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.
09:01
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.
09:23
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
09:45
point through different paths. Okay, so I've talked about the general principle of the solution, and now I'll talk
10:00
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.
10:22
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.
10:43
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.
11:06
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
11:22
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
11:40
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
12:06
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
12:23
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.
12:42
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,
13:02
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
13:22
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.
13:48
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
14:04
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.
14:26
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
14:42
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.
15:02
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.
15:21
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
15:46
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.
16:04
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.
16:23
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
16:44
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.
17:04
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.
17:23
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.
17:53
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,
18:12
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,
18:37
before all those trains that have been added on the first.
18:41
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.
19:04
And we can see the speed of the trains, so it... Anyway, I'll just move on to the questions.
19:27
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?
19:41
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,
20:08
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,
20:25
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.
20:41
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,
21:02
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.
21:46
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.
22:07
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.
22:29
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...
22:41
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.
23:02
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.
23:23
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
23:41
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,
24:00
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.
24:23
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.
24:46
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,
25:06
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.
25:21
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.
25:42
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.
26:09
Thank you. Thank you for this presentation. The presentation has arrived on time.
26:28
We are starting in a few minutes.