Design documents

• 1: Signaling
• 1.1: Signaling systems
• 1.2: Blocks and signals
• 1.3: Speed limits
• 1.4: Simulation lifecycle
• 2: Conflict detection
• 3: Search for last-minute train slots (STDCM)
• 3.1: Business context
• 3.2: Train slot search module
• 3.2.1: Infrastructure exploration
• 3.2.2: Conflict detection
• 3.2.3: Encoding the solution space
• 3.2.4: Discontinuities and backtracking
• 3.2.5: Conflict avoidance
• 3.2.6: Standard allowance
• 3.2.7: Implementation details
• 4: Timetable v2

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 paths permitted 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
• it must allow for automated import from existing databases

Design requirements:

All 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
• enable using signaling modules without instantiating a complete simulation
• allow for signals to be loaded in any order, in parallel

For speed limits:

• some speed limits have to be enforced depending on the train path’s routes
• speed limits can be configured to have an impact on signaling
• ability to link the reaction of the train to a signal, and a speed limit

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 compute, given a signal alone, its block and route 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.
• Speed limits change depending on which route is in use, and affect how signals behave
• Some speed limits have an impact on signaling, and some do not
• Either a speed limits differentiates per train category, or requires dynamic signaling, but not both

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)

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.
• are there any signals which depend on which route is set, but are not route delimiters? SNCF(Loïc): Yes, see Sémaphore Clignotant
• how do speed limits per train category and dynamic signaling interact? SNCF(Nicolas): There shouldn’t be any speed limit per category signaled by dynamic signaling
• are there any signals which depend on the state of multiple routes? SNCF(Loïc): No

1.1 - Signaling systems

Each signaling system has:

• A unique identifier (a string).
• 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.

{
    # unique identifier for the signaling system
    "id": "BAL",
    "version": "1.0",
    # 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"}
    ],
    # describes static properties of the signal
    "signal_properties": [
        {"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"}
    ],
    # describes dynamic properties of the signal. These can be set on a per-route basis
    "signal_parameters": [
        {"kind": "flag", "field_name": "short_block", "default": false, "display_name": "Short block"},
        {"kind": "flag", "field_name": "rappel30", "default": false, "display_name": "Rappel 30"},
        {"kind": "flag", "field_name": "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. Only properties can be used, not parameters.
    "block_boundary_when": "true",

    # used to evaluate whether a signal is a route boundary. Only properties can be used, not parameters.
    "route_boundary_when": "Nf",

    # A predicate used evaluate whether a signal state can make a train slow down. Used for naive conflict detection.
    "constraining_ma_when": "aspect != VL"
}

1.2 - Blocks and signals

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.

Dependencies

• 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

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.

Announcing speed limits

When a signal announces a speed limit, it needs to be linked with a speed section object. This is meant to enable smooth transitions between the reaction to the announce signal, and the limit itself.

If multiple signals are involved in the announce process, only the one closest to the speed limit has to have this attribute set.

{
    # ...
    "announce_speed_section": "${SPEED_SECTION_ID}"
    # ...
}

Conditional parameters

Some signal parameters vary depending on which route is set. On each signal, an arbitrary number of rules can be added. If the signal is last to announce a speed limit, it must be explicitly mentionned in the rule.

{
    # ...
    "announce_speed_section": "${SPEED_SECTION_ID}",
    "default_parameters": {"short_block": "false"},
    "conditional_parameters": [
        {
            "on_route": "${ROUTE_ID}",
            "announce_speed_section": "${SPEED_SECTION_ID}",
            "parameters": {"rappel30": "true", "short_block": "true"}
        }
    ]
    # ...
}

Signal parameter values are looked up in the following order:

1. per route conditional parameters
2. per signal default parameters (default_parameters)
3. parameter default value, from the signaling system’s .signal_parameters[].default

Serialized format

The serialized / raw 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 properties, as specified in the signaling system description
• a list of default parameters, which can get overriden per-route
• an optional announced speed section, which can get overriden per-route
• 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
• announces speed limit B on all routes except route A, where speed limit C is announced
• on route A, the block is shorter than usual

{
    # 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
            "properties": {"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"]
            "announce_speed_section": "${SPEED_SECTION_B}",
            "default_parameters": {"rappel30": "true", "short_block": "false"},
            "conditional_parameters": [
                {
                    "on_route": "${ROUTE_A}",
                    "announce_speed_section": "${SPEED_SECTION_C}",
                    "parameters": {"short_block": "true"}
                }
            ]
        }
    ]
}

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",
            "properties": {"has_ralen30": "true", "Nf": "true"},
            "next_signaling_systems": ["BAL"]
        },
        {
            "signaling_system": "BAPR",
            "properties": {"Nf": "true", "distant": "false"},
            "next_signaling_systems": ["BAPR"]
        }
    ]
}

Signal description strings

Signal definitions need to be condensed into a shorter form, just to look up signal icons. In order to store this into MVT map tiles hassle free, it’s condensed down into a single string.

It looks something like that: BAL[Nf=true,ralen30=true]+BAPR[Nf=true,distant=false] It’s built as follows:

• a list of logical signals, sorted by signaling system name, separated by +
• inside each logical signal, signal properties are sorted by name, enclosed in square brackets and separated by ,

Dependencies

For signal state evaluation:

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

1.3 - Speed limits

Description

Railway infrastructure has a surprising variety of speed limits:

• some are known by the driver, and not announced at all
• some are announced by fixed signs regardless of where the train goes
• some are announced by fixed signs, depending on where the train path goes
• some are announced by dynamic signals regardless of where the train goes
• some are announced by dynamic signals, depending on where the train path goes

Data model

{
    # unique speed limit identifier
    "id": "...",

    # A list of routes the speed limit is enforced on. When empty
    # or missing, the speed limit is enforced regardless of the route.
    #
    # /!\ When a speed section is announced by signals, the routes it is
    # announced on are automatically filled in /!\
    "on_routes": ["${ROUTE_A}", "${ROUTE_B}"]
    # "on_routes": null, # not conditional
    # "on_routes": [], # conditional

    # A speed limit in meters per second.
    "speed_limit": 30,

    # A map from train tag to speed limit override. If missing and
    # the speed limit is announced by a signal, this field is deduced
    # from the signal.
    "speed_limit_by_tag": {"freight": 20},

    "track_ranges": [{"track": "${TRACK_SECTION}", "begin": 0, "end": 42, "applicable_directions": "START_TO_STOP"}],
}

Design considerations

Where to put the speed limit value

When a speed limit is announced by dynamic signaling, we may be in a position where speed limit value is duplicated:

• once in the signal itself
• once in the speed limit

There are multiple ways this issue can be dealt with:

✅ Mandatory speed limit value in the speed section

Upsides:

• simpler to implement, works even without train reactions to signals nor additional API

Downsides:

• more work on the side of users
• room for inconsistencies between the speed limit announced by signaling, and the effective speed limit

❌ Deduce the signal constraint from the speed limit

This option was not explored much, as it was deemed awkward to deduce signal parameters from a speed limit value.

❌ Deduce the speed limit from the signal

Make the speed limit value optional, and deduce it from the signal itself. Speed limits per tag also have to be deduced if missing.

Upsides:

• less work for users
• lessens the likelyhood of configuration mismatches

Downsides:

• not all signaling systems work well with this. It may be difficult to deduce the announced speed limit from a signal configuration, such as with TVM.
• speed limits have to be deduced, which increases implementation complexity

How to link announce signals and speed limit area

Speed limit announced by dynamic signaling often start being enforced at a specific location, which is distinct from the signal which announces the speed limit.

To allow for correct train reactions to this kind of limits, a link between the announce signal and the speed limit section has to be made at some point.

❌ Automated matching of signals and speed sections

Was not deemed realistic.

❌ Explicit link from route to speed limit and signals

Was deemed to be awkward, as signaling is currently built over interlocking. Referencing signaling from interlocking creates a circular dependency between the two schemas.

❌ Explicit link from speed limit to signals

Add a list of (route, signal) tuples to speed sections.

Upside:

• a link with the signal can be made with creating the speed section

Downside:

• Creates a dependency loop between speed limits and signaling. Part of the parsing of speed limit has to be deferred.
• Signals parameters also have to be set per route, which is done in the signal. Having per-route options on both sides doubles the work.

❌ Inlining speed limit definitions into signals

Introduces a new type of speed limit, which are announced by signals. These speed limits are directly defined within signal definitions.

{
    # ...
    "conditional_parameters": [
        {
            "on_route": "${ROUTE_ID}",
            "speed_section": {
                "speed_limit": 42,
                "begin": {"track": "a", "offset": 10},
                "end": {"track": "b", "offset": 15},
            },
            "parameters": {"rappel30": "true", "short_block": "true"}
        }
    ]
    # ...
}

Upsides:

• straightforward infrastructure edition experience for speed sections announced by a single signal

Downsides:

• creates two separate kinds of speed limits:
  • can cause code duplication
  • could make later changes of the data model trickier
  • it’s unclear whether the criterion used to make this partition is appropriate
• speed sections created directly inside signals can only be announced by a single signal, which could be an issue for speed sections which apply to very large areas, and are announced by multiple signals (such as one for each direction)
• the cost of reversing this decision could be fairly high

✅ Explicit link from signal to speed section

{
    # ...
    "conditional_parameters": [
        {
            "on_route": "${ROUTE_ID}",
            "announced_speed_section": "${SPEED_SECTION_ID}",
            "parameters": {"rappel30": "true", "short_block": "true"}
        }
    ]
    # ...
}

Upsides:

• single unified way of declaring speed limits
• very close to the current implementation

Downsides:

• adds a level of indirection between the signal and the speed section
• the edition front-end has to be smart enough to create / search speed sections from the signal edition menu

Speed limits by route

Some speed limits only apply so some routes. This relationship needs to be modeled:

1. speed limits could have a list of routes they apply on
2. routes could have a list of speed limits they enforce
3. the routes a speed limit apply on could be deduced from its announce signals, plus an explicit list of routes per speed section

We took option 3.

1.4 - Simulation lifecycle

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 properties and 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.

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
}

fun signal(maView: MAView?): 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

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 - Infrastructure exploration

The first thing we need to define is how we move through the infrastructure, without dealing with conflicts yet.

We need a way to define and enumerate the different possible paths and explore the infrastructure graph, with several constraints:

1. The path must be compatible with the given rolling stock (loading gauge / electrification / signaling system)
2. At any point, we need to access path properties from its start up to the considered point. This includes block and route lists.
3. We sometimes need to know where the train will go after the point currently being evaluated, for proper conflict detection

To do this, we have defined the class InfraExplorer. It uses blocks (sections from signal to signal) as a main subdivision. It has 3 sections: the current block, predecessors, and a “lookahead”.

In this example, the green arrows are the predecessor blocks. What happens there is considered to be immutable.

The red arrow is the current block. This is where we run train and signaling simulations, and where we deal with conflicts.

The blue arrows are part of the lookahead. This section hasn’t been simulated yet, its only purpose is to know in advance where the train will go next. In this example, it would tell us that the bottom right signal can be ignored entirely. The top path is the path being currently evaluated. The bottom section of the path will be evaluated in a different and already instanciated InfraExplorer

The InfraExplorer is manipulated with two main functions (the accessors have been removed here for clarity):

interface InfraExplorer {
    /**
     * Clone the current object and extend the lookahead by one route, for each route starting at
     * the current end of the lookahead section. The current instance is not modified.
     */
    fun cloneAndExtendLookahead(): Collection<InfraExplorer>

    /**
     * Move the current block by one, following the lookahead section. Can only be called when the
     * lookahead isn't empty.
     */
    fun moveForward(): InfraExplorer
}

cloneAndExtendLookahead() is the method that actually enumerates the different paths, returning clones for each possibility. It’s called when we need a more precise lookahead to properly identify conflicts, or when it’s empty and we need to move forward.

A variation of this class can also keep track of the train simulation and time information (called InfraExplorerWithEnvelope). This is the version that is actually used to explore the infrastructure.

3.2.2 - Conflict detection

Once we know what paths we can use, we need to know when they can actually be used.

The documentation of the conflict detection module explains how it’s done internally. Generally speaking, a train is in conflict when it has to slow down because of a signal. In our case, that means the solution would not be valid, we need to arrive later (or earlier) to see the signal when it’s not restrictive anymore.

The complex part is that we need to do the conflict detection incrementally Which means that:

1. When running simulations up to t=x, we need to know all of the conflicts that happen before x, even if they’re indirectly caused by a signal seen at t > x down the path.
2. We need to know the conflicts and resource uses right as they start even if their end time can’t be defined yet.

For that to be possible, we need to know where the train will go after the section that is being simulated (see infra exploration: we need some elements in the lookahead section).

To handle it, the conflict detection module returns an error when more lookahead is required. When it happens we extend it by cloning the infra explorer objets.

3.2.3 - 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.4 - 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.5 - 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.

Post-processing

We used to compute the engineering allowances during the graph exploration, but that process was far too expensive. We used to run binary searches on full simulations, which would sometimes go back for a long distance in the path.

What we actually need is to know whether an engineering allowance is possible without causing any conflict. We can use heuristics here, as long as we’re on the conservative side: we can’t say that it’s possible if it isn’t, but missing solutions with extremely tight allowances isn’t a bad thing in our use cases.

But this change means that, once the solution is found, we can’t simply concatenate the simulation results. We need to run a full simulation, with actual engineering allowances, that avoid any conflict. This step has been merged with the one described on the standard allowance page, which is now run even when no standard allowance have been set.

3.2.6 - 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.

During the exploration

The main implication of the standard allowance is during the graph exploration, when we identify conflicts. It means that we need to scale down the speeds. We still need to compute the maximum speed simulations (as they define the extra time), but when identifying at which time we see a given signal, all speeds and times are scaled.

This process is not exact. It doesn’t properly account for the way the allowance is applied (especially for MARECO). But at this point we don’t need exact times, we just need to identify whether a solution would exist at this approximate time.

Post-processing

The process to find the actual train simulation is as follows:

1. We define points at which the time is fixed, initialized at first with the time of each train stop. This is an input of the simulation and indirectly calls the standard allowance.
2. If there are conflict, we try to remove the first one.
3. We add a fixed time point at the location where that conflict happened. We use the time considered during the exploration (with linear scaling) as reference time.
4. This process is repeated iteratively until no conflict is found.

3.2.7 - 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.

4 - Timetable v2

Design decisions

Some major changes were made between our first version of the timetable and the new one:

• Isolate the timetable table. It can be used in a scenario or in other contexts
• Have a soft reference from train schedule to rolling stock (to be able to create a train schedule with unknown rolling stock)
• Consider path and simulation output as cache (that don’t require to be stored in DB)
• We can compute pathfinding without having to store data
• All input needed to compute a path is stored in the train schedule (we can recompute it if needed)
• All input needed to run a simulation is stored in the train schedule (we can recompute it if needed)

Train schedule v2

Requirements

• front: easy to keep consistent during edition
• front: intermediate invalid states than can be reached during edition have to be encodable
• front: when deleting a waypoint that is referenced by margins, the position of the deleted waypoint within the path must be preserved until the situation is resolved
• import: path waypoint locations can be specified using UIC operational point codes
• import: support fixed scheduled arrival times at stops and arbitrary points
• import edition: train schedules must be self-contained: they cannot be described using the result of pathfinding or simulations

Design decisions

Path waypoints have an identity

At some point in the design process, the question was raised of whether to reference location of stops and margin transitions by name, or by value. That is, should stops hold the index of the waypoint where the stop occurs, or a description of the location where the stop occurs?

It was decided to add identifiers to path waypoints, and to reference those identifiers where referencing a path location is needed. This has multiple upsides:

• you can’t reference a location outside of the path
• when changing a waypoint’s location, for example from one station’s platform to another, no additional maintenant work is needed to keep the path consistent
• if a path goes to the same place multiple times, the identifier reference makes it clear which path location is referenced
• it makes keeping data consistent while editing easier, as all locations are kept in a single place

Invalid train schedules and soft deletes

If an user deletes a waypoint, what happens? Is it the front-end’s responsibility to only save valid schedules, or can invalid schedules be represented in the data model? We decided that it wasn’t just the front-end’s responsibility, as we want to be able to model inconsistent states, until the user comes back to fix it.

One key observation was that don’t want to loose the ability to locate within the path waypoints that were deleted, until all references are gone. How is the front-end supposed to display margin bounds or stops for a waypoint that’s gone, if it’s not there anymore?

We thus decided to add a deleted soft-delete flag to waypoints. When this flag is set, the back-end run simulations on the path, but still allows saving it. Once all references to a deleted waypoint are gone, it can be removed from the path. The backend can deny train schedules with stale deleted waypoints.

Separating path and stops

This decision was hard to make, as there are little factors influencing this decision. Two observations led us to this decision:

• when deleting a waypoint, the end user may want to preserve the associated stop. Making the separation clear in the data model helps with implementing this behavior correctly, if deemed relevant
• bundling stops into the path makes it harder to describe what fields path waypoints should have, and what should have a separate object and reference. It was decided that keeping path a simple list of Location, with no strings attached, made things a little clearer.

No more engineering margins?

In the legacy model, we had engineering margins. These margins had the property of being able to overlap. It was also possible to choose the distribution algorithm for each margin individually.

We asked users to comment on the difference and the usefulness of retaining these margins with scheduled points. The answer is that there is no fundamental difference, and that the additional flexibility offered by engineering margins makes no pratical sense (overlap and choice of distribution…).

Arrival times are durations since departure time

• this allows shifting the departure time without having to change arrival times
• we don’t have to parse dates and compute date differences within a single trip

We also discussed whether to use seconds or ISO 8601 durations. In the end, ISO 8601 was choosen, despite the simplicity of seconds:

• it preserves the user’s choice unit for specifying duration
• it interfaces nicely with the ISO 8601 departure time
• it does not suffer from potential integer-float serialization related precision loss

Invalid and outdated train schedules

Reasons for a train schedule to be invalid:

• Inconsitent train schedule (contains deleted waypoint)
• Rolling stock not found
• Path waypoint not found
• The path cannot be found

Reasons for a train schedule to be outdated:

• The train path changed
• The train running time changed

What we can do about outdated trains:

1. Nothing, they’re updated without notification
2. We can notify the user that a train schedule is outdated:
   • Nothing can be done except acknoledge the change
   • We can not check what changed between the old and new version
   • We can not know the cause of this change (RS, Infra, Algorithms…)

Note: The outdated status is a nice to have feature (it won’t be implemented right now).

Creation fields

These fields are required at creation time, but cannot be changed afterwards. They are returned when the train schedule is queried.

timetable_id: 42

Modifiable fields

train_name: "ABC3615"
rolling_stock_name: R2D2

# labels are metadata. They're only used for display filtering
labels: ["tchou-tchou", "choo-choo"]

# used to select speed limits for simulation
speed_limit_tag: "MA100"

# the start time is an ISO 8601 datetime with timezone. it is not always the
# same at the departure time, as there may be a stop at the starting point
start_time: "2023-12-21T08:51:11.914897+00:00"

path:
 - {id: a, uic: 87210} # Any operational point matching the given uic
 - {id: b, track: foo, offset: 1000} # 10m on track foo
 - {id: c, deleted: true, trigram: ABC} # Any operational point matching the trigram ABC
 - {id: d, operational_point: X} # A specified operational point

# the algorithm used for distributing margins and scheduled times
constraint_distribution: MARECO # or LINEAR

# all durations and times are specified using ISO 8601
# we don't supports months and years duration since it's ambiguous
# times are defined as time elapsed since start. Even if the attribute is omitted,
# a scheduled point at the starting point is infered to have departure=start_time
# the "locked" flag is ignored by the backend.
# To force a stop signal, you can use the "arrival_on_stop_signal" flag.
schedule:
 - {at: a, stop_for: PT5M, locked: true} # infered arrival to be equal to start_time
 - {at: b, arrival: PT10M, stop_for: PT5M}
 - {at: c, stop_for: PT5M}
 - {at: d, arrival: PT50M, locked: true, arrival_on_stop_signal: true}

margins:
  # This example encodes the following margins:
  #   a --- 5% --- b --- 3% --- d

  # /!\ all schedule points with either an arrival or departure time must also be
  # margin boundaries. departure and arrival waypoints are implicit boundaries. /!\
  # boundaries delimit margin sections. A list of N boundaries yields N + 1 sections.
  boundaries: [b]

  # the following units are supported:
  #  - none is a special value which indicates no margin. It's the default
  #  - % means added percentage of the base simulation time
  #  - min/km means minutes per kilometers
  values: ["5%", "3%"]

# train speed at simulation start, in meters per second.
# must be zero if the train starts at a stop
initial_speed: 2.5

power_restrictions:
 - {from: b, to: c, value: "M1C1"}

comfort: AIR_CONDITIONING # or HEATING, default STANDARD

options:
  # Should we use electrical profiles to select rolling stock speed effort curves
  use_electrical_profiles: true

Combining margins and schedule

Margins and scheduled points are two ways to add time constraints to a train’s schedule. Therefore, there most be a clear set of rules to figure out how these two interfaces interact.

The end goal is to make the target schedule and margins consistent with each other. This is achieved by:

• computing what the schedule would look like if only margins were applied
• compare that to the target schedule
• correct the margin schedule so that it matches the target schedule

The path is partitionned as follows:

• known time sections span between locations where the arrival time is known. If there are N such locations, there are N - 1 known time sections. In these sections, margins need to be adjusted to match the target schedule.
• If the arrival time at destination is unknown, the section from the last known arrival time point and the destination is called the relaxed time section has no bound. Margins can be applied directly.

As margins cannot span known time section boundaries, each known time section can be further subdivided into margin sections. Margins cover the entire path.

The end goal is to find the target arrival time at the end of each margin section. This needs to be done while preserving consistency with the input schedule.

The final schedule is computed as follows:

• A base simulation is computed, without any time constraint (other than stops). It’s used to compute provisional margin values.
• Make a provisional time table, which ignores target arrival times but includes provisional margin values.
• For each known time section, compute the adjustment required to make the provisional schedule match the target schedule.
• Distribute this difference into the known time section’s margin sections, proportionally to margin section running time. After distributing the adjustment into margin sections, the final schedule should be compatible with the target schedule.

Error handling

Some errors may happen while building the timetable:

• if a known time section’s required adjustment is negative, a warning must be raised, as margins will have to be lowered
• if a margin section’s final running time is tighter than the base simulation, it cannot be achieved, and a warning should be raised

Other errors can happen at runtime:

• target margin values can be too low, as transitions from high density margin to low margin section force the train to loose time after it has exited to high density margin section.
• target margin values can also be too high, as the train may not have time to slow down enough, or drive so slow as to be unacceptable.

During simulation, if a target arrival time cannot be achieved, the rest of the schedule still stands.

Endpoints

Timetable

POST /v2/timetable
GET /v2/timetable/ # Paginated list timetable
PUT /v2/timetable/ID
DELETE /v2/timetable/ID
GET /v2/timetable/ID # Timetable with list of train schedule ids attached to it

Train Schedule

POST /v2/train_schedule # A batch creation
GET /v2/train_schedule/ID
PUT /v2/train_schedule/ID # Update a specific train schedule
DELETE /v2/train_schedule # A batch deletion

Path

POST /v2/infra/ID/pathfinding/topo # Not required now can be move later
POST /v2/infra/ID/pathfinding/blocks
# takes a pathfinding result and a list of properties to extract
POST /v2/infra/ID/path_properties?props[]=slopes&props[]=gradients&props[]=electrifications&props[]=geometry&props[]=operational_points
GET /v2/train_schedule/ID/path?infra_id=42 # Retrieve the path from a train schedule

Simulation results

# Retrieve the list of conflict of the timetable (invalid trains are ignored)
GET /v2/timetable/ID/conflicts?infra=N
# Retrieve the space, speed and time curve of a given train
GET /v2/train_schedule/ID/simulation?infa=N
# Retrieves simulation information for a given train list. Useful for finding out whether pathfinding/simulation was successful.
GET /v2/train_schedule/simulations_sumary?infa=N&ids[]=X&ids[]=Y
# Projects the space time curves and paths of a number of train schedules onto a given path
POST /v2/train_schedule/project_path?infra=N&ids[]=X&ids[]=Y