Refactoring Shortest travel times journey chain using OD Matrix algorithm

[louisgreiner]

Description

Note

The "Shortest travel times journey chain" is also refered as "Analytics" feature (which is actually the name used in the application).

The current "Analytics" feature:

• uses a separate, slower, and unreliable algorithm,
• produces different results than the OD Matrix,
• loses its rendered results when the user pans/zooms the network - the rendering integration is poor - just quick & dirty implemented.

The "Analytics" feature should be refactored to display to travel times and the connections given by the OD Matrix algorithm. Unify the “Analytics” shortest‑path feature with the OD Matrix algorithm so both features use the same computation logic, produce identical travel‑time results, and behave consistently in the UI. The current code should be totally replaced by this, to use a single algorithm for the both features.

The next version of Netzgrafik "Analytics" will only support interactions based on clicking a node.

The following screenshots have been made using this network: analytics.json. When clicking on the "Analytics" button, the view changes, highlighting the departure minutes:

Then we can click on any node (here on node A), and this shows the shortest path to other nodes. Using this shortest path, (1) represents the number of connections to this node and (2) represents the travel time to this node.

However, when we look at the Origin-Destination Matrix for the same network, the results are not the same. For instance, if we click on node F:

The OD Matrix does not output the same result (⚠️ make sure to click on "Temps de parcours", to observe only the travel times, and not the "cost", which is travel time + connections * penality)

As we have a better trust on the OD Matrix algorithm, we need both features to use the same algorithm, then displaying the same results. The goal is then to refactor the OD Matrix algorithm, to be able to use it elsewhere and generate the shortest path from the clicked node to all other nodes (and not from all nodes to all nodes, which is currently what the OD Matrix algorithm doing).

Mock-ups

The rendering should not be affected by this refactoring, except that the color of the nodes after computation should be based on the travel time, using the same color scale as the OD Matrix does.

Acceptance Criteria

• The OD Matrix feature works the same and display the same results as before the refactoring
• The "Analytics" feature works the same as before and display the same results as the OD Matrix feature, without taking connection penality into account
  • Clicking on a node compute "one‑to‑all shortest paths computation"
    • In the nodes, the "Total travel time" and "Connections" are displayed:
      • "Connections" (number of transfers): displayed on the left side of the node as #n
      • "Total travel time" (travel time without any penalty): displayed on the right side of the node, formatted as hh:mm.
    • The nodes then are colored, using the same color scale as the OD Matrix does, based on the "Total travel time" value
  • The trainrun sections part of the computed shortest paths are highlighted (as it is already the case with old "Analytics" feature)
  • The transitions part of the computed shortest paths are highlighted (as it is already the case with old "Analytics" feature)
• "Analytics" feature should take active filters into account (as it is already the case for OD Matrix feature)
• Once the "Analytics" is activated and a result is there, it remains visible until another node is clicked, or "Analytics" is explicitly deactivated
• "Analytics" only supports interactions based on clicking a node
• Paning and zooming don't affect the results rendering
• Exports (.png and .svg) allow rendered results to be exported

Implementation Plan

• Refactor the OD Matrix algorithm service to make it possible to generate the shortest path from a node to all other nodes (and not from all nodes to all other nodes) and make it available from a service.
  • The OD Matrix service should act like an interface that offers:
    • all‑to‑all shortest‑path computation (existing behavior)
    • one‑to‑all computation (a single row of the matrix)
    • ⚠️ the core algoritm should not be modified, just the endpoints
  • src/app/services/analytics/origin-destination/components/origin-destination.service.ts
• Remove all the existing "Analytics" algorithm code, and use the above service instead
  • src/app/services/analytics/analytics.service.ts
• Populate the "Analytics" rendered values with the OD Matrix algorithm service
• Update the tests (or create new ones) to test the unified algorithm and both endpoints

Tests

Definition of Ready

• PO/UX-UI

  • Mock-ups are complete and validated
  • ACs are clear and have been reviewed by another refiner

• Technical

  • Implementation plan has been written and validated by another maintainer

• General

  • Validated by Adrian

Outscope TODOs

This will need to create another issue:

• Extended UI
  • such as checkboxes or switches, for the "value" fields and "color" parameter
• Prepare Analytics component for future extension (difficult to imagine from that)

[aiAdrian]

Unified Origin–Destination (OD) Matrix Algorithm for Analytics

Goal

Unify the “Analytics” shortest‑path feature with the OD Matrix algorithm so both features use the same computation logic, produce identical travel‑time results, and behave consistently in the UI.

---

Problem

The current Analytics feature:

• uses a separate, slower, and unreliable algorithm,
• produces different results than the OD Matrix,
• loses its rendered results when the user pans/zooms the network - the rendering integration is poor - just quick & dirty implemented.

This creates inconsistent UX and doubles maintenance effort.

The next version of Netzgrafik Analytics will only support interactions based on clicking a node. The current proof‑of‑value implementation — which is still available — will be removed and completely reworked. As a result, all other interaction types will be discontinued.

We will restart with a simple but high‑quality foundation. The existing version has limited quality, but it successfully demonstrated what is possible. That proof‑of‑value phase was a success, and now the focus shifts toward stability, robustness, and a high‑quality user experience.

---

Solution Overview

Refactor the OD Matrix algorithm so it supports:

• all‑to‑all shortest‑path computation (existing behavior),
• one‑to‑all computation (a single row of the matrix).

Replace the entire Analytics algorithm with this unified OD Matrix service.

Acceptance Criteria

• compute shortest paths from the clicked node using the OD Matrix logic,
• Make switchable which cost will be used. Default: Total cost like O/D Matrix
• Render same color as set in the O/D matrix (switchable) - Default: Total cost
• Render (hightlight) the used trainrunSection for the shortest path
• Render (hightlight) the use transistions for the shortest path
• Display the number of "changes* and travel time (not the cost!!) in the node
• Use active filter - use only visible objects for the computation, rendering
• OD Matrix continues to work exactly as before (all‑to‑all, CSV export, matrix view).
• Analytics uses the OD Matrix algorithm and shows the same travel times and paths as the corresponding OD Matrix row.
• Once the analyicts is activate and a result is there it remain visible until: another node is clicked, or Analytics is explicitly deactivated.
• Rendering is stable: results remain visible during pan/zoom.
• Tests updated to reflect the unified algorithm.
• The rendered analytics results can be exported to svg/png

Acceptance Criteria (extended)

• No UI elements other than rendering (svg) are implemented as part of this feature; UI work will be delivered in a separate feature request.
• The implementation must be fully prepared for the upcoming larger Analytics feature.
• The solution must be highly flexible and generalised, enabling future extensions without major refactoring.
• The internal architecture should follow best practices to ensure the logic can be reused for additional analytical visualisations and data layers.
• The code must be structured so that future UI components can consume the results without modification of the core algorithm.
• The implementation must be maintainable, testable, and aligned with long‑term product evolution.

---

Implementation plan

• Refactor the algorithm integration (use O/D Matrix)
• Refactor (replace or make new rendering) - remove all rendering artefact only use for analyitcs, then start implementing the rendering and integration. We need temporal storage (flags, data, etc. ) on trainrunSection, transition and node objects
• Rendering: Node - color layer , two text fields
• Interaction: Node - analytics on -> click start computation
• Rendering TrainrunSection & transistion -> highlight when in the shortest path
• Interaction: None

Out-of-scope

• We don't need to start with a trainrunseciton time click the shortestpath calculation. This can be removed in this 1st appraoch. Might we will reimplement this later on or we might as well skipt this
• Any UI elements, such as sidebar, boxes switches. We just start with default settings - but be aware that this will be added later on

[louisgreiner]

I updated the core of the issue, to integrate your suggestions @aiAdrian. I still have some considerations.

Questions:

• Value and Color parameters: can we postpone to a next version?
  • How do we make the "value" parameter accessible by the user?
    • Total travel time (connection penality = 0) or Total cost (connection penality = 5 (default))
  • How do we make the "color" parameter accessible by the user?
    • Based on Total travel time or Total cost
• "Display the number of "changes* and travel time (not the cost!!) in the node", then I don't understand the above points about switching to a cost or not

My suggestions:

• Keep "value" parameter to "Total travel time" as a v1
• Keep "color" parameter to "Total travel time" as a v1

[louisgreiner]

If you agree with all that, this feature will be presented in the next OSRD PIP (no guarantee that this will be retained, as well for the other features we present, we'll know on the 11th February latest).

[aiAdrian]

I fully agree with this approach. We will display the number of transfers on the left side of the node as #, and on the right side we will show the effective travel time (i.e., travel time without any penalty), formatted as hh:mm.

The node color will be encoded based on the travel time, using the same color scale as the O/D Matrix default settings. Everything should remain very simple for the first version. The only important requirement is that in the future the color scale must be adjustable, and both text fields on the node must remain flexible so they can be reused for additional analytics later on.