Design documents

• 1: Signaling
• 2: Conflict detection
• 3: Search for last-minute train slots (STDCM)
• 3.1: Business context
• 3.2: Train slot search module
• 3.2.1: Input format
• 3.2.2: Encoding the solution space
• 3.2.3: Discontinuities and backtracking
• 3.2.4: Conflict avoidance
• 3.2.5: Standard allowance
• 3.2.6: Implementation details
• 3.3: Signaling interface

1 - Signaling

Description

The signaling layer includes all signals, which respond to track occupancy and reservation. Signals can be of different types, and are modularly loaded. Only their behavior towards the state of the infrastructure and the train’s reaction to signaling matters.

Signals are connected to each other by blocks. Blocks define the movements authorized by signaling.

Goals

The signaling system is at the crossroads of many needs:

• it must allow for realistic signaling simulation in a multi-train simulation
• it must allow the conflict detection system to determine which resources are required for the train
• it must allow application users to edit and display signals
• it must allow for visualization of signals on a map

Design requirements:

Static data:

• must enable the front-end to display the signals
• must enable the infrastructure editor to configure signals
• must enable the back-end to simulate signals
• must be close to realistic industry models
• must allow for the modeling of composite signals, which carry several logical signals within a single physical signal

To simulate signaling:

• blocks must be generated for both user convenience and pathfinding
• for each signal, its next compatible signal and protected zones must be deduced
• the minimum necessary information must be provided to the signaling modules for their operation
• using signaling modules without having to instantiate a complete simulation must be enabled
• the design of the signaling module API must allow for signals to be loaded in any order

{
    # unique identifier for the signaling system
    "id": "BAL",
    "version": "1.0",
    # a list of roles the system assumes
    "roles": ["MA", "SPEED_LIMITS"],
    # the schema of the dynamic state of signals of this type
    "signal_state": [
        {"kind": "enum", "field_name": "aspect", values: ["VL", "A", "S", "C"]},
        {"kind": "flag", "field_name": "ralen30"},
        {"kind": "flag", "field_name": "ralen60"},
        {"kind": "flag", "field_name": "ralen_rappel"}
    ],
    # the schema of the settings signals of this type can read
    "signal_settings": [
        {"kind": "flag", "field_name": "Nf", "display_name": "Non-franchissable"},
        {"kind": "flag", "field_name": "has_ralen30", "default": false, "display_name": "Ralen 30"},
        {"kind": "flag", "field_name": "has_rappel30", "default": false, "display_name": "Rappel 30"},
        {"kind": "flag", "field_name": "has_ralen60", "default": false, "display_name": "Ralen 60"},
        {"kind": "flag", "field_name": "has_rappel60", "default": false, "display_name": "Rappel 60"}
    ],

    # these are C-like boolean expressions:
    # true, false, <flag>, <enum> == value, &&, || and ! can be used

    # used to evaluate whether a signal is a block boundary.
    "block_boundary_when": "true",

    # used to evaluate whether a signal is a route boundary.
    "route_boundary_when": "Nf",

    # used for naive conflict detection.
    "constraining_ma_when": "aspect != VL"
}

Assumptions

• Each physical signal can be decomposed into a list of logical signals, all of which are associated with a signaling system.
• Blocks have a type.
• It is possible to determine, given only the signal, its delimiting properties.
• Blocks never cross route boundaries.
• Blocks which are not covered by routes do not exist, or can be ignored.
• At any time, trains only use one signaling system capable of transmitting movement authority.

Design of Signaling Systems

Each signaling system has:

• A unique identifier (a string).
• A set of roles:
  • Transmission of Movement Authority
  • Transmission of speed limits
• Its signal state type, which enables deducing:
  • The graphical representation of the signal
  • How a train would react to the signal
  • If the signal state constrains Movement Authority
• The signal parameter types, names and description, which enable front-end edition of signal parameters.
• The block and route conditions, which enable evaluating whether a signal delimits blocks or routes, given its parameters.

Note that if a signaling system has a dual role of transmitting Movement Authority (MA) and speed limits, not all signals in this system are necessarily tasked with transmitting speed limit information.

Design of blocks

The blocks have several attributes:

• A signaling system that corresponds to that displayed by its first signal.
• A path, which is a list of direction + detector pairs (just like route paths).
• An entry signal, (optional when the block starts from a buffer stop).
• Intermediate signals, if any (only used by systems with distant signals).
• An exit signal, (optional when the block ends at a buffer stop).

The path is expressed from detector to detector so that it can be overlayed with the route graph.

A few remarks:

• There can be multiple blocks with the same path, as long as they have different signaling systems. Trains only use a block at a time, and ignore others.
• Blocks do not have a state: one can rely on the dynamic state of the zones that make it up.
• Blocks are used to figure out which signals protect which zones in a given context.

Design of signals

Physical signal are made up of one or more logical signals, which are displayed as a single unit on the field. During simulation, logical signals are treated as separate signals.

Each logical signal is associated with a signaling system, which defines if the signal transmits Movement Authority, speed limits, or both.

Logical signals have one or more drivers. Signal drivers are responsible for computing signal state. Any given signal driver only works for a given pair of signaling systems, where the first one is displayed by the signal, and the second is the one displayed by the next signal.

When a logical signal has an empty driver list, its content is deduced from neighboring signals.

For example, a BAL signal that is both a departure of the TVM block and a departure of the BAL block, it will have two drivers: BAL-BAL and BAL-TVM.

Raw signal format

The raw signal format is the user-editable description of a physical signal.

Raw signals have a list of logical signals, which are independently simulated units sharing a common physical display. Each logical signal has:

• a signaling system
• user-editable settings, as specified in the signaling system description
• a list of allowed next signaling systems, which are used to load drivers

For example, this signal encodes a BAL signal which starts both a BAL and a TVM block:

{
    # signals must have location data.
    # this data is omitted as its format is irrelevant to how signals behave

    "logical_signals": [
        {
            # the signaling system shown by the signal
            "signaling_system": "BAL",
            # the settings for this signal, as defined in the signaling system manifest
            "settings": {"has_ralen30": "true", "Nf": "true"},
            # this signal can react to BAL or TVM signals
            # if the list is empty, the signal is assumed to be compatible with all following signaling systems
            "next_signaling_systems": ["BAL", "TVM"]
        }
    ]
}

For example, this signal encodes a BAL signal which starts a BAL block, and shares its physical display / support with a BAPR signal starting a BAPR block:

{
    # signals must have location data.
    # this data is omitted as its format is irrelevant to how signals behave

    "logical_signals": [
        {
            "signaling_system": "BAL",
            "settings": {"has_ralen30": "true", "Nf": "true"},
            "next_signaling_systems": ["BAL"]
        },
        {
            "signaling_system": "BAPR",
            "settings": {"Nf": "true", "distant": "false"},
            "next_signaling_systems": ["BAPR"]
        }
    ]
}

Such signal descriptions can be condensed down into a simplified description string, for the specific use-case of representing / generating signal icons: BAL[Nf=true,ralen30=true]+BAPR[Nf=true,distant=false]

Loading Signal Parameters

The first step of loading the signal is to characterize the signal in the signaling system. This step produces an object that describes the signal.

During the loading of the signal:

• the signaling system corresponding to the provided name is identified
• the signal parameters are loaded and validated according to the signaling system spec
• the signal’s block and route delimiting properties are evaluated

Loading the Signal

Once signal parameters are loaded, drivers can be loaded. For each driver:

• The driver implementation is identified from the (signaling_system, next_signaling_system) pair.
• It is verified that the signaling system outgoing from the driver corresponds to the one of the signal.
• It is verified that there is no existing driver for the incoming signaling system of the driver.

This step produces a Map<SignalingSystem, SignalDriver>, where the signaling system is the one incoming to the signal. It then becomes possible to construct the loaded signal.

Constructing Blocks

• The framework creates blocks between signals following the routes present in the infrastructure, and the block properties of the signals.
• Checks are made on the created block graph: it must always be possible to choose a block for each signal and each state of the infrastructure.

Speed Limits

Speed limits are represented as ranges on routes. They start their life as ranges on track sections, and are lifted to ranges on routes as follows:

• Directional speed limits by track are elevated to routes. The same speed limit can be on multiple routes.
• For each speed limit, the route graph is traversed in reverse searching for signals capable of handling the limit:
  • Only speed limits not preceded by another limit with identical properties are considered.
  • Each signal must signal its interest in a speed limit: Not concerned, Concerned but to be announced by another signal, or Concerned and terminal.
• For each speed limit planned along the train’s path, the signals in the announcement chain are added to the list of those to be simulated for the train.

enum SpeedLimitHandling {
    /** This signal isn't supposed to announce this limit */
    Ignore,
    /** This signal should announce this limit, but cannot */
    Error,
    /** This signal can announce this limit, and is part of an ongoing chain */
    Chain,
    /** This signal can announce this limit, and ends the chain */
    EndChain,
}

fn handles_speed_limit(
   self: SignalSettings,
   speed_limit: SpeedLimit,
   distance_mm: u64,
) -> SpeedLimitHandling;

fn handles_speed_limit_chain(
   self: SignalSettings,
   speed_limit: SpeedLimit,
   chain_signal: Signal,
   distance_mm: u64,
) -> SpeedLimitHandling;

Block validation

The validation process helps to report invalid configurations in terms of signaling and blockage. The validation cases we want to support are:

• The signaling system may want to validate, knowing if the block starts / ends on a buffer:
  • the length of the block
  • the spacing between the block signals, first signal excluded
• Each signal in the block may have specific information if it is a transition signal. Therefore, all signal drivers participate in the validation.

In practice, there are two separate mechanisms to address these two needs:

• The signaling system module is responsible for validating signaling within blocks.
• Signal drivers take care of validating transitions between blocks.

extern fn report_warning(/* TODO */);
extern fn report_error(/* TODO */);

struct Block {
   startsAtBufferStop: bool,
   stopsAtBufferStop: bool,
   signalTypes: Vec<SignalingSystemId>,
   signalSettings: Vec<SignalSettings>,
   signalPositions: Vec<Distance>,
   length: Distance,
}

/// Runs in the signaling system module
fn check_block(
   block: Block,
);


/// Runs in the signal driver module
fn check_signal(
   signal: SignalSettings,
   block: Block, // The partial block downstream of the signal - no signal can see backward
);

Signal lifecycle

Before a train startup:

• the path a of the train can be expressed is given, both as routes and blocks
• the signal queue a train will encounter is established

During the simulation:

• along a train movement, the track occupation before it are synthesized
• when a train observes a signal, its state is evaluated

Signal state evaluation

Signals are modeled as an evaluation function, taking a view of the world and returning the signal state

enum ZoneStatus {
   /** The zone is clear to be used by the train */
   CLEAR,
   /** The zone is occupied by another train, but otherwise clear to use */
   OCCUPIED,
   /** The zone is incompatible. There may be another train as well */
   INCOMPATIBLE,
}

interface MAView {
    /** Combined status of the zones protected by the current signal */
    val protectedZoneStatus: ZoneStatus
    val nextSignalState: SignalState
    val nextSignalSettings: SignalSettings
}

interface DirectSpeedLimit {
    /** Distance between the signal and the speed limit */
    val distance: Distance
    val speed: Speed
}

interface IndirectSpeedLimit {
    val distanceToNextSignal: Distance
    val nextSignalState: SignalState
    val nextSignalSettings: SignalSettings
}

interface SpeedLimitView {
    /** A list of speed limits directly downstream of the signal */
    val directSpeedLimits: List<DirectSpeedLimit>
    /** A list of speed limits which need to be announced in a signal chain */
    val indirectSpeedLimits: List<IndirectSpeedLimit>
}

fun signal(maView: MAView?, limitView: SpeedLimitView?): SignalState {
    // ...
}

The view should allow access to the following data:

• a synthetized view of zones downstream until the end of the train’s MA
• the block chain
• the state of downstream signals which belong to the current block chain

Signaling view path

The path along which the MAView and SpeedLimitView live is best expressed using blocks:

• blocks can be added to extend the view along the path of a train
• the view can be reduced by removing blocks, as the train passes by signals

Simulation outside the train path

Everything mentionned so far was designed to simulate signals between a train the end of its movement authority, as all others signals have no influence over the behavior of trains (they cannot be seen, or are disregarded by drivers).

Nevertheless, one may want to simulate and display the state of all signals at a given point in time, regardless of which signals are in use.

Simulation rules are as follows:

• if a signal starts blocks which have differing paths, it is simulated as if it were at the end of a route
• if a signal starts blocks which all start the same path, it is simulated in the same view as the next signals in this path

Dependencies

For the block graph generation:

• route graph. For each route:
  • waypoints: List<DiDetector>
  • signals: OrderedMap<Position, UnloadedSignal>
  • speed_limits: RangeMap<Position, SpeedLimit>, including the logic for train category limits
• signaling systems
• drivers

For evaluation:

• train path in blocks
• portion of the path to evaluate
• drivers
• state of the zones in the section to evaluate

Operations

• Instantiating a view creates a framework for observing signals
• Planning the path signals to the view the blocks that the train will traverse
• Observing a signal subscribe to the state of a signal (through the view)
• Passing a signal signals that a signal has been passed by the train (through the view)

Appendices

Research Questions

• Are there any blocks that overlap the end of a route? SNCF(Loïc): No.
• Are there any signals which rely on the state of the one after next signal? SNCF(Loïc): No.
• Are there signals that change behavior based on the active block in front of them? SNCF(Loïc): Yes, for slowdowns.
• Are there signals that are the start of blocks of different types? SNCF(Loïc): Yes.
• Can the behavior of a signal depend on which block is active after the end of the current block? SNCF(Loïc): Yes, with slowdowns or blinking yellow.
• Do some signaling systems need additional information in the blocks? SNCF(Loïc): Kind of, there are slowdowns, but it’s not specifically carried by the block.
• Is it nominal for a train to have multiple active signaling systems at the same time? SNCF(Loïc): No.
• When and by whom are the blocks generated?
• What data is necessary for generating the blocks?

2 - Conflict detection

Conflict detection is the process of looking for timetable conflicts. A timetable conflict is any predictable condition which disrupts planned operations. Planned operations can be disrupted if a train is slowed down, prevented from proceeding, or delayed.

One of the core features of OSRD is the ability to automatically detect some conflicts:

• spacing conflicts: insufficient spacing between trains sharing the same path
• routing conflicts: insufficient spacing between trains with intersecting paths

Some other kinds of conflicts may be detected later on:

• maintenance conflicts: planned maintenance disrupts the path of a train
• power delivery conflicts: combined power delivery requirements exceeds capacity

Conflict detection relies on interlocking and signaling modeling and simulation to:

1. figure out what each actor requires to perform its duty undisturbed
2. detect conflicting requirements

Design constraints

The primary design goals are as follows:

• enable threading new train paths into an existing timetable (see STDCM)
• produce conflicts which can be linked back to a root cause
• operate in way that can be visualized and interpreted
• scale to real world timetables: millions of yearly trains, tens of thousands of daily trains

In addition to these goals, the following constraints apply:

• it must be possible to thread new train paths into timetables with existing conflicts
• it must not cause false-negatives: if no conflicts are detected, a multi-train simulation of the same timetable must not yield any slowdowns
• it cannot rely on data we do not have
• it has to enable later support of mobile block systems
• it has to rely on existing signaling and interlocking simulation
• it has to enable detecting conflicts regardless of the signaling system in use
• it has to support transitions between signaling systems
• it has to support conflicts between different signaling systems

Conflict modeling

Actors are objects which cause resources to be used:

• train paths (or someone / something on the behalf of the train)
• maintenance work

Actors need resources to be available to proceed, such as:

• zones, which have one state per way to traverse it
• switches, which have one state per position
• station platforms, which could be used to prevent two large trains from occupying both sides of a tiny platform

Actor emit resource requirements, which:

• describe the need of an actor for a resource, for a given time span
• describe what the resource is needed for
• detail how the resource is used, such as switch position, zone entry and exit

Resource requirements can turn out to be either satisfied or conflicting with other requirements, depending on compatibility rules.

Compatibility rules differ by requirement purpose and resource type. For example:

• spacing requirements are exclusive: simultaneous requirements for the same resource are conflicting
• zone and switch requirements are shareable: simultaneous requirements are satisfied if the resource configuration is identical

For conflict detection to work, resource requirements have to be at least as extensive as what’s required to guarantee that a train path will not be disturbed.

Routing conflicts

Context

For trains to proceed safely along their planned path:

• switches have to be moved in the appropriate position
• level crossings have to activate
• risks of collision with other trains have to be mitigated

In practice, the path of trains is partitioned into routes, which when set, ensure a train can safely follow the route.

Routes have the following lifestyle:

• As a train approaches the start of one of its routes, it is called by an operator. If all resources required to safely use the route are available, switches and level crossings start to move. If a resources is not available, e.g. because another train has reserved a section of track, this process is delayed until all conditions are met.
• Once all resources are configured and reserved, the route is set and ready to be followed. Before that point, the entry of the route was protected by signaling, which prevented the train from moving past the entry point.
• As the train moves along the route, it is destroyed. When the tail of the trail releases key detectors along the route, resources before this detector are released, and can this be reserved by other routes.

For a train to proceed through a route unimpeded, the following things have to happen:

• The route has to be set before the train arrives, and before it is slowed down by signaling.
• The route has to be called, so that is it set in time.
• All resources required for the route to start setting at call time have to be available.

Generating requirements

struct RouteRequirement {
    route: RouteId,
    set_deadline: Time,
    zone_requirements: Vec<RouteZoneRequirement>,
}

struct RouteZoneRequirement {
    zone: ZoneId,
    entry_det: DirDetectorId,
    exit_det: DirDetectorId,
    release_time: Time,
    switches: Map<SwitchId, SwitchConfigId>,
}

Routing requirements are generated by the following algorithm:

• Compute the set deadline using signaling simulation. The set deadline is the point in time at which the train would be slowed down if the route were not set.
• For each zone in each route, simulate when it would be released, and thus not required anymore.

Requirement compatibility rules

Requirement compatibility is evaluated for all RouteZoneRequirements, grouped by zone. Requirements A and B, ordered such that A.set_deadline <= B.set_deadline, are compatible if and only if either:

• their active time span does not overlap, such that A.release_time <= (B.set_deadline - activation_time), where the activation time is the delay required to reconfigure from A.switches to B.switches.
• (A.entry_det, A.exit_det, A.switches) == (B.entry_det, B.exit_det, B.switches)

Spacing conflicts

Context

Even if interlocking mitigates some of the risks associated with operating trains, a major one is left out: head to tail collisions, caused by insufficient spacing.

This responsibility is handled by signaling, which conveys both interlocking and spacing constraints.

Signaling helps trains slow down until the end of their movement authority, which is either:

• behind the tail of the next train
• at the end of the last route set for this train

Spacing requirements are emitted for zones which if occupied, would cause a slowdown, and zones occupied by the train

Generating requirements

struct SpacingRequirement {
    zone: ZoneId,
    begin_time: Time,
    end_time: Time,
}

Every time the driver sees a signal, generate updated spacing requirements by calculating which zones, if occupied, would trigger a slowdown:

• start by assuming the zone just after the head of the train is occupied
• until the train is not slowed down, move the occupied section one zone further away from the train

Requirement compatibility rules

Requirement compatibility is evaluated for all SpacingRequirements, grouped by zone.

Requirements A and B are compatible if and only if their [begin_time, end_time] ranges do not overlap.

Incremental requirement generation

Routing requirements

sequenceDiagram
    participant client as Client
    participant gen as Routing resource generator
    client ->> gen: initial path + train movement
    loop
        gen ->> client: prefix path extension needed
        client ->> gen: extra prefix path + train movement
    end
    gen ->> client: resource requirements

After an initial path is given, the requirement generator can ask for more prefix path (before the start of the route). The client responds with:

• the extra prefix path
• the movement of the train over time on the given prefix path

If the initial path has multiple routes, the last route is the one resource requirements are emitted for.

Spacing requirements

sequenceDiagram
    participant client as Client
    participant gen as Spacing resource generator
    client ->> gen: initial path + train movement
    loop
        gen ->> client: postfix path extension needed
        client ->> gen: extra postfix path
    end
    gen ->> client: resource requirements

After an initial path is given, the requirement generator can ask for more postfix path (before the start of the route).

Visualizing requirements

Full-page requirements diagram

3 - Search for last-minute train slots (STDCM)

OSRD can be used to find a slot for a train in an already established timetable, without causing conflicts with other trains.

The acronym STDCM (Short Term Digital Capacity Management) is used to describe this concept in general.

3.1 - Business context

Some definitions:

Capacity

Capacity, in this context, is the ability to reserve infrastructure elements to allow the passage of a train.

Capacity is expressed in both space and time: the reservation of an element can block a specific zone that becomes inaccessible to other trains, and this reservation lasts for a given time interval.

It can be displayed on a chart, with the time on the horizontal axis and the distance traveled on the vertical axis.

Example of a space-time chart displaying the passage of a train.

The colors here represent aspects of the signals, but display a consumption of the capacity as well: when these blocks overlap for two trains, they conflict.

There is a conflict between two trains when they reserve the same object at the same time, in incompatible configurations.

Example of a space-time graph with a conflict: the second train is faster than the first one, they are in conflict at the end of the path, when the rectangles overlap.

When simulating this timetable, the second train would be slowed down by the yellow signals, caused by the presence of the first train.

Train slots

A train slot corresponds to a capacity reservation for the passage of a train. It is fixed in space and time: the departure time and the path taken are known. On the space-time charts in this page, a train slot corresponds to the set of blocks displayed for a train.

Note: in English-speaking countries, these are often simply called “train paths”. But in this context, this name would be ambiguous with the physical path taken by the train.

The usual procedure is for the infrastructure manager (e.g. SNCF Réseau) to offers train slots for sale to railway companies (e.g. SNCF Voyageurs).

At a given date before the scheduled day of operation, all the train paths are allocated. But there may be enough capacity to fit more trains. Trains can fit between scheduled slots, when they are sufficiently far apart or have not found a buyer.

The remaining capacity after the allocation of train paths is called residual capacity. This section explains how OSRD looks for train slots in this residual capacity.

3.2 - Train slot search module

This module handles the search for solutions.

To reduce the problem to its simplest form and for easy and efficient testing, inputs and outputs are strongly simplified and abstracted.

To summarize its behavior: the solution space is described as a graph that encodes locations, time, and speed. A pathfinding is run on this graph to find a solution.

This graph could, in a way, be seen as a decision tree, but different paths can lead to the same node.

3.2.1 - Input format

This module takes several parameters to find a path:

• A graph describing the physical infrastructure
• Unavailable sections in time intervals
• Origin and destination point(s)
• Departure time interval
• Maximum run time
• Simulation parameters (rolling stock, time step, allowances, …)

Among those, the first 3 require more explanations.

Infrastructure graph

Today, the input graph is the SignalingRoutes graph. But it can be any graph that represents the physical infrastructures and the paths that can be used.

The only constraints are: the edges must have a length, and it must be possible to compute running time on parts of an edge.

Unavailable sections

This input encodes the areas that are unavailable because of capacity constraints.

Every edge has a set of “occupancy block”. A block is made of these elements:

• Start offset
• End offset
• Start time
• End time

Offsets are relative to the start of the edge. Each block means that the head of the train cannot be located in the edge segment during the given interval.

These blocks include the grid margin. If the solution needs to have an x seconds margin before the train passage, every block ends x seconds later.

To give an example, with the following schedule, a 42m long train, and 10m sight distance:

• The occupancy of the block 1 from t=0 to t=300 makes it unavailable in its entirety during this time
• The last 10 meters of block 1 are unavailable from t=300 to t=360, because the signal at the start of block 2 must be green when the conductor sees it. It is possible to consider that this unavailability block starts at t=130 (when the next signal isn’t green), as blocks can overlap.
• The occupancy of block 2 from t=130 to t=360 makes it unavailable during this time. It is also unavailable from t=0, as the presence of a train in this block would cause a warning on block 1.
• The first 42 meters of block 3 are unavailable from t=0 to t=360, because the tail of the train must have left the block 2 at this time.
• The rest of block 3 is unavailable in its entirety from t=280 to t=360

3.2.2 - Encoding the solution space

General principle

The problem is still a pathfinding problem in a given graph. Once the problem is encoded as a graph search, it is possible to reuse our existing tools for this purpose.

We consider the product graph of position, time, and speed. This means that every graph element contains these 3 variables (among other things)

Every graph edge is computed using running-time calculation to get speed and positions as functions of time.

Graphical representation

Space is encoded with a graph that contains the physical infrastructure.

It is then “duplicated” at different times.

The nodes are then linked together in a way that reflects travel time.

Notes

• The graph is constructed on the fly as it is explored.
• It is discretized in time, to evaluate which nodes have already been visited. We keep full accuracy of time values, but two nodes at the same place and close times are considered identical.
• Every edge is computed with a running time computation.
• Speed isn’t discretized or considered to check visited nodes, it’s only used to compute time.
• By default, the train always goes as fast as it can (while still following standard allowances). It only slows down when necessary.

Example

For example, with the following infrastructure, using the track graph:

Exploring the solution graph can give the following result:

3.2.3 - Discontinuities and backtracking

The discontinuity problem

When a new graph edge is visited, a simulation is run to evaluate its speed. But it is not possible to see beyond the current edge. This makes it difficult to compute braking curves, because they can span over several edges.

This example illustrates the problem: by default the first edge is explored by going at maximum speed. The destination is only visible once the second edge is visited, which doesn’t leave enough distance to stop.

Solution : backtracking

To solve this problem, when an edge is generated with a discontinuity in the speed envelopes, the algorithm goes back over the previous edges to create new ones that include the decelerations.

To give a simplified example, on a path of 4 edges where the train can accelerate or decelerate by 10km/h per edge:

For the train to stop at the end of route 4, it must be at most at 10km/h at the end of edge 3. A new edge is then created on edge 3, which ends at 10km/h. A deceleration is computed backwards from the end of the edge back to the start, until the original curve is met (or the start of the edge).

In this example, the discontinuity has only been moved to the transition between edges 2 and 3. The process is then repeated on edge 2, which gives the following result:

Old edges are still present in the graph as they can lead to other solutions.

3.2.4 - Conflict avoidance

While exploring the graph, it is possible to end up in locations that would generate conflicts. They can be avoided by adding delay.

Shifting the departure time

The departure time is defined as an interval in the module parameters: the train can leave at a given time, or up to x seconds later. Whenever possible, delay should be added by shifting the departure time.

for example : a train can leave between 10:00 et 11:00. Leaving at 10:00 would cause a conflict, the train actually needs to enter the destination station 15 minutes later. Making the train leave at 10:15 solves the problem.

In OSRD, this feature is handled by keeping track, for every edge, of the maximum duration by which we can delay the departure time. As long as this value is enough, conflicts are avoided this way.

This time shift is a value stored in every edge of the path. Once a path is found, the value is summed over the whole path. This is added to the departure time.

For example :

• a train leaves between 10:00 and 11:00. The initial maximum time shift is 1:00.
• At some point, an edge becomes unavailable 20 minutes after the train passage. The value is now at 20 for any edge accessed from here.
• The departure time is then delayed by 5 minutes to avoid a conflict. The maximum time shift value is now at 15 minutes.
• This process is applied until the destination is found, or until no more delay can be added this way.

Engineering allowances

Once the maximum delay is at 0, the delay needs to be added between two points of the path.

The idea is the same as the one used to fix speed discontinuities: new edges are created, replacing the previous ones. The new edges have an engineering allowance, to add the delay where it is possible.

computing an engineering allowance is a feature of the running-time calculation module. It adds a given delay between two points of a path, without affecting the speeds on the rest of the path.

3.2.5 - Standard allowance

The STDCM module must be usable with standard allowances. The user can set an allowance value, expressed either as a function of the running time or the travelled distance. This time must be added to the running time, so that it arrives later compared to its fastest possible running time.

For example: the user can set a margin of 5 minutes per 100km. On a 42km long path that would take 10 minutes at best, the train should arrive 12 minutes and 6 seconds after leaving.

This can cause problems to detect conflicts, as an allowance would move the end of the train slot to a later time. The allowance must be considered when we compute conflicts as the graph is explored.

The allowance must also follow the MARECO model: the extra time isn’t added evenly over the whole path, it is computed in a way that requires knowing the whole path. This is done to optimize the energy used by the train.

Linear margin expressed as a function of time

As a first step, the problem is solved with a linear margin, i.e. added evenly over the whole path. The speed is simply modified by a constant factor.

The envelopes. computed during the graph traversal are not modified, they are always at maximum speed. But they are paired with a speed factor, which is used to compute running time and to evaluate conflicts.

The final envelope, with the allowance, is only computed once a path is found.

Linear margin expressed as a function of distance

The principle is generally the same, but with an extra difficulty: the speed factor isn’t constant over the path. When a train goes faster, it travels more distance in the same time, which increases the allowance time and the speed factor.

Because the train speed changes over the path, the speed factor changes from one edge to another. This causes irregular speed curves.

MARECO Allowances

This is exclusively a post-processing step, because it isn’t possible to compute the MARECO envelope without knowing the full train path. When looking for a path, linear allowances are used.

This means that conflicts may appear at this step. To avoid them, the following procedure is applied:

1. A mareco allowance is applied over the whole path.
2. If there are conflict, the first one is considered.
3. The mareco allowance is split in two intervals. The point where the first conflict appeared is set to be at the same time as the envelope with a linear allowance, removing the conflict at this point.
4. This process is repeated iteratively until no conflict is found.

3.2.6 - Implementation details

This page is about implementation details. It isn’t necessary to understand general principles, but it helps before reading the code.

STDCMEdgeBuilder

This refers to this class in the project.

This class is used to make it easier to create instances of STDCMEdge, the graph edges. Those contain many attributes, most of which can be determined from the context (e.g. the previous node). The STDCMEdgeBuilder class makes some parameters optional and automatically computes others.

Once instantiated and parametrized, an STDCMEdgeBuilder has two methods:

• Collection<STDCMEdge> makeAllEdges() can be used to create all the possible edges in the given context for a given route. If there are several “openings” between occupancy blocks, one edge is instantiated for each opening. Every conflict, their avoidance, and their related attributes are handled here.

• STDCMEdge findEdgeSameNextOccupancy(double timeNextOccupancy): This method is used to get the specific edges that uses a certain opening (when it exists), identified here with the time of the next occupancy block. It is called whenever a new edge must be re-created to replace an old one. It calls the previous method.

Pathfinding

The methods mentioned here are defined in this class.

Cost function

The function used to define pathfinding cost sets which path is used over another. The result is always the one that minimizes this cost (as long as the heuristic is admissible).

Here, two parameters are used: total run time and departure time. The latter has a very small weight compared to the former, so that the fastest path is found. More details are explained in the documentation of those methods.

Heuristics

The algorithm used to find a path is an A*, with a heuristic based on geographical coordinates.

However, the coordinates of generated infrastructures are arbitrary and don’t reflect the track distance. It means that, for the generated infrastructures, the path may not always be the shortest one.

It would be possible to use this heuristic to determine whether the current node can lead to a path that doesn’t take longer than the maximum allowed total run time. But for the same reason, adding this feature would break any STDCM test on generated infras. More details in this issue.

3.3 - Signaling interface

WIP

There’s a draft of what we intend to do on the French page, but it’s still a work in progress. The implementation hasn’t been started.