NGE : Origin / Destination matrix as CSV

[louisgreiner]

Description

First part of meta feature about O/D matrix

Implementation of O/D matrix and output as .csv.

https://colab.research.google.com/drive/1Z1r2uU2pgffWxCbG_wt2zoLStZKzWleE#scrollTo=F6vOevK6znee

A proof of concept has been done

(https://colab.research.google.com/drive/1Omx_qt2fnW1kJC6kQrhOgdkTZzmtibid?usp=sharing#scrollTo=EDXs4tO0kmDr) another one but with less results

Benefit hypothesis

See above meta.

Acceptance criteria

Launching the OD Matrix computation

• [ ] A button enables, in the NGE interface, to launch a OD matrix computation (using the icon <sbb-icon svgIcon="five-circles-interconnected-small" class="sbb-icon-fit"></sbb-icon> )

• [ ] The computation is launched for the nodes :
  • [ ] if some nodes are selected via the multiselection tool, the computation is launched for these nodes
  • [ ] Otherwise, the computation is launched for the nodes visible in the current filtering
• [ ] The trainruns which can be used by paths are :
  • [ ] The trainruns which are not filtered via the filter menu (only filters that concern trains, meaning that if a train is not visible only because its nodes were filtered, it can be used)
  • [ ] Warning : the matrix must show the results only for the nodes for which the computation is launched, but the computed paths between two of these nodes can use any node in the NGE (not only those for which the computation is launched). For example, if 2 nodes are not visible, if the trainrun between these two filtered nodes is not filtered via the train filters, it can be used be the path.

Details about the computation of the OD Matrix

• [ ] The computation must, for each pair of nodes (i,j) find an optimal valid path from i to j, using the constraints and objective described in the following points
• [ ] A valid path is :
  • [ ] A series of trainrunSections
  • [ ] One can enter/exit a trainrun only at the nodes where the trainrun stop
  • [ ] A connection (between two different Trainruns) must respect the minimum connection time (in minutes) : if the time between the arrival of the first TrainrunSection and the departure of the second TrainRunSection is lower than the minimum connection time, the frequence of the second Trainrun is added to the duration of the connection until the minimum connection time is respected (to represent the fact that one has to wait for the next train)
• [ ] The frequencies of the Trainruns must be taken into account to check all the possibilities to go from one node to the other
• [ ] The cost (in minutes) of a path used to compute the optimal path is the sum of the following elements:
  • The effective travel time (in minutes, including connection times)
  • A constant penalty for each connection in the path
• [ ] Bonus : The trainruns are used within their time windows (not done in the POC)
• [ ] Compute time is reasonable (< 5sec)

A first POC is available, but does not take into account all these constraints, so if all the above AC are taken into account, this will check the following criteria

• [ ] Limitations of [POC] https://colab.research.google.com/drive/1Z1r2uU2pgffWxCbG_wt2zoLStZKzWleE#scrollTo=iA9_-nzQemhn (https://colab.research.google.com/drive/1Omx_qt2fnW1kJC6kQrhOgdkTZzmtibid?usp=sharing#scrollTo=EDXs4tO0kmDr) have been overcome (see limitations)

Output of the computation

• [ ] Output O/D matrix is downloaded as .csv : "origin_destination_matrix.csv"
• [ ] This csv contains 3 sheets (each sheet is a matrix, with the nodes for which the OD matrix computation was launched as headers for x and y axis) :
  • First sheet "effective_travel_time," : for each pair of nodes (i,j), the cell (i,j) contains the effective travel time (in minutes) of the optimal path from i to j (effective travel time includes connection times)
  • Second sheet "number_of_connections" : for each pair of nodes (i,j), the cell (i,j) contains the number of connections necessary in the optimal path from i to j
  • Third sheet "cost": for each pair of nodes (i,j), the cell (i,j) contains the cost (in minutes) of the optimal path (cost used in the Dijkstra algorithm)

Example (for the NGE given in the implementation plan) :

Implementation plan

Launching the computation

-[ ] The button calls the corresponding function in the service netzgrafik-editor-frontend/src/app/services/analytics/analytics.service.ts

• [] The arguments of the function are :
  • The whole NetzGraf
  • The list of the selected nodes for the computation (see AC to know which nodes to put in that list)
  • The list of authorized trainruns (see AC to know which trainruns to keep in that list)
  • The penalty for a connection (int, for now 5 by default)

Computation itself

Mostly the proof of concept described above.

• [ ] The function must be implemented in the netzgrafik-editor-frontend/src/app/services/analytics/analytics.service.ts service

The idea is to model our problem thanks to a DIRECTED graph, and to run several Dijkstra algorithms on this graph.

• [ ] Modelisation of the problem on the graph :
  • [ ] Vertices : For each Node of the NGE (represented in the POC as a quadruplet (node, departure or arrival, time or global, trainrunSectionId) :
  • [ ] Global Arrival and Departure vertices : If the node is in the list of the filtered nodes that we want to show in the matrix : 2 global vertices for this node (one for Arrival, one for Departure), which are used as input of the Dijkstra algorithm to say that we want a shortest path from (Departure) or to (Arrival) this node. These vertices are red circles in the ppt document. In the POC, these nodes are (node.id, "arrival" or "departure", "global", None)
  • [ ] Timed arrival vertices : Vertices representing the trainrunSections arriving at this node : for each trainrunSection arriving and stopping at this node, one vertex is created for each arrival time within the time window (to take into account the frequency of the corresponding trainrun). These vertices are blue squares in the ppt document. In the POC, these nodes are (node.id, "arrival", time of arrival, section id of the trainrunSection arriving here)
  • [ ] Timed departure vertices : Vertices representing the trainrunSections departing from this node : for each trainrunSection departing from this node and stopping at this node, one vertex is created for each departure time within the time window (to take into account the frequency of the corresponding trainrun). These vertices are blue squares in the ppt document. In the POC, these nodes are (node.id, "departure", time of departure, section id of the trainrunSection departing here)
  • [ ] Edges. In the POC, edges have a source and target node, a time (to represent travel time), a penalty (to say if it is a connection) :
  • [ ] Global vertices edges : For each node in the filtered list (nodes with the 2 Global Arrival and Departure vertices), edges from the Global Departure vertex to all the timed departure vertices, and from all the timed arrival vertices to the Global Arrival Vertex. These edges have a 0 cost, and enable to link paths to the Global vertices which are the inputs of Dijkstra algorithms. The edges are shown in black in the ppt document. The time and penalty are 0 in the POC.
  • [ ] Inner Node edges : For each node in the filtered list (nodes with the 2 Global Arrival and Departure vertices), edges from the Global Departure vertex to the Global Arrival vertex, with cost 0, to show that the shortest path from A to A is 0. These edges are shown in red in the ppt document. The time and penalty are 0 in the POC.
  • [ ] Transition Edges : This represent show the possible connections at nodes (between the same train) and their cost. For each timed arrival vertex, an edge must be present to represent transition with the corresponding outgoing trainrunSection of the same train. So, an edge is present from our timed arrival vertex to the timed departure vertex of this trainrunSection which represents the next trainrunSection of the trainrun. The cost of this edge is the transition time. These edges are shown in matrices in the ppt document. The time is the transition time and the penalty is 0 in the POC.
  • [ ] Connection Edges : This represent show the possible connections at nodes (between two different trains) and their cost. For each timed arrival vertex, an edge must be present to represent the first connection with each of the outgoing trainrunSections. So, for each trainrunSection, an edge is present from our timed arrival vertex to the timed departure vertex of this trainrunSection which represents the first reachable train (taking into account the minimum connection time). The cost of this edge is the connection time, plus the constant connection penalty. These edges are shown in matrices in the ppt document. The cost is the connection time and the penalty is 1 in the POC.
  • [ ] Section Edges : These edges represent the travel time between nodes. For each timed departure vertex (which corresponds to a trainrunSection), an edge goes to the corresponding timed arrival vertex of the next stop of the trainrun (at the other end of the trainRunSection if there is a stop, otherwise one has to "add" the costs of the trainrunSections until the last stop). The cost of this edge is the travel time. The edges are shown in matrices in the ppt document. The cost is the travel time and the penalty is 0 in the POC.

Example of the graph + result on a 4 nodes NGE :

• SVG NGE :

• Json NGE : netzgrafik (6).json

• Graph + shortest paths : https://sncf.sharepoint.com/:p:/r/sites/OSRD644GrpO365/Documents%20partages/PO/NGE/Graphe%20petit%20example.pptx?d=wc5052d73215542f7880e3691cce7d9b5&csf=1&web=1&e=LGNAxh

• [ ] Run one Dijkstra algorithm for each node visible with the filtering (in the POC, the Dijkstra algorithm stops when all the "computation nodes" are visited (the others are not interesting)

• [ ] One has to choose the window on which the graph is represented. In the POC, I chose 2 hours which is the maximum frequency.

Ideas to speed up if the computation is too long on large graphs :

• [ ] Keep track of the shortest distance for each computed node, and if an explorer path has a distance > than the maximum of these distances, stop exploring it (it means that if it is a subpath of a shortest path, it won't be a shortest path to one of our nodes
• [ ] Prevent a path to reach two timed-arrival vertices which represent the same node (because it will mean a circle between stations)

How to read the NGE json :

• nodes : the nodes in NGE
  • id
  • betriebspunkName : What is written in the square in NGE
  • ports : ports where the trainrunsections reach the nodes (used in transitions)
  • transitions : the transitions of trainruns within the node, saying whether the train stops or not:
  • id
  • port1Id : port of the 1st trainrunSection
  • port2Id : port of the 2nd trainrunSection
  • isNonStopTransit : false if there is a stop (so in our case a possible connection), true otherwise
  • connections : connections between trains at this node, we can ignore it
  • connectionTime : minimum time to make a connection at this node
• trainruns : represent train lines
  • id
  • name
  • frequencyId : id of the frequency, in the attribute "frequency" to know how many minutes there are between two trains
  • trainrunTimeCategoryId : id of the trainrunTimeCategory, in the attribut with this name, to know when the train operates
• trainrunSections : represents sections of a trainrun between two nodes (in both directions)
  • id
  • sourceNodeId : one of the nodes is the source, and it is its id
  • sourcePortId : port of the source node where the section goes (useful to link with transitions)
  • targetNodeId
  • targetPortId
  • travelTime : information about travelTime
    • time : travel time
  • sourceDeparture : when the train leaves the source
    • time : minutes of the hour
    • consecutiveTime : number of minutes from the beginning of the first hour (useful make the difference between H05 and (H+1)05
  • targetArrival : when the train arrives at the target
  • targetDeparture : when the train leaves the target
  • sourceArrival : when the train arrives at the source
  • WARNING : these time fields are not necessarily starting at the source, sometimes it starts at the target
  • trainrunId : id of the trainrun
  • specificTrainrunSectionFrequencyId : if the trainrunSectionhas a specific frequency(not taken into account in the POC)
• metadata
  • trainrunFrequencies : frequencies of trainruns
    • id
    • frequency : number of minutes between two trains
  • trainrunTimeCategories : categories of trainruns to know when they operate
    • id
    • dayTimeInterval : moments of the day when the train operates (24h if empty)
      • from : minutes of the day of the beginning of operation interval
      • to : minutes of the day of the end of operation interval
    • weekday : days of the week at which the train operates (Monday is 1)

Output

• [ ] Name of the file : origin_destination_matrix.csv
• [ ] Name of the sheets : effective_travel_time, number_of_connections, cost

Definition of ready

• Data

  • [x] Necessary data are clearly identified and defined (format, precision required, quality expected)
  • for testing purpose, use scenarios from here
  • [x] A contact person is identified to answer our questions about the data
  • @louisgreiner & @maelysLeratRosso for both technical and business matter, @aiAdrian for business matter

• PO

  • [x] Acceptance criteria are clear and understandable
  • [x] The acceptance criteria are validated by users

• Technical

  • [x] Implementation plan is detailed and validated by maintainers

• General

  • [x] WSJF values are filled
  • [x] Validated by the PM

(development task template from OSRD)

[axrolld]

Review comments:

1

using the constraints et objective described in the following points

~et~ and

2

The name of the .csv output file isn't specified. How's the filed supposed to be named ?

3

First sheet : for each pair of nodes (i,j), the cell (i,j) contains the effective travel time of the optimal path from i to j (effective travel time includes connection times)

What's the unit of this travel time ? Seconds ? Minutes ? Or HH:MM:SS ?

Third sheet : for each pair of nodes (i,j), the cell (i,j) contains the cost of the optimal path (cost used in the Dijkstra algorithm)

What's the unit of the cost ?

[shenriotpro]

Review comments:

3

First sheet : for each pair of nodes (i,j), the cell (i,j) contains the effective travel time of the optimal path from i to j (effective travel time includes connection times)

What's the unit of this travel time ? Seconds ? Minutes ? Or HH:MM:SS ?

Third sheet : for each pair of nodes (i,j), the cell (i,j) contains the cost of the optimal path (cost used in the Dijkstra algorithm)

What's the unit of the cost ?

I'd usually recommend seconds, but I believe durations/times are in minutes for NGE.

[louisgreiner]

Review comments:

3

First sheet : for each pair of nodes (i,j), the cell (i,j) contains the effective travel time of the optimal path from i to j (effective travel time includes connection times)

What's the unit of this travel time ? Seconds ? Minutes ? Or HH:MM:SS ?

Time unit is indeed minute for NGE

https://github.com/SchweizerischeBundesbahnen/netzgrafik-editor-frontend/blob/e839ec247fe47fc057944fa6031dfefb7de09a04/src/app/data-structures/technical.data.structures.ts#L101

[shenriotpro]

Example (for the NGE given in the implementation plan) :

Slight typo as C -> D should have 1 connection.

[maelysLeratRosso]

Example (for the NGE given in the implementation plan) :

Slight typo as C -> D should have 1 connection.

Oops, corrected