Question: How does Motis CSA handle splitting and joining trains?

[McToel]

I am working on a new routing engine for https://bahnvorhersage.de/ that is able to perform a search for alternatives connections if a connection not work, so that a passanger can plan for journeys with reliable alternatives.

Currently I'm trying to figure out how i might handle splitting an joining trains in my CSA implementation. If I understand correctly, motis implements a CSA that can handle these types of trains. Could you give me some details on how motis is handeling this or where I can find it in the code?

[felixguendling]

Hey! 😄 👋

We call the following services "rule services":

• merge + split ("Flügelung" / "Vereinigung")
• through services ("Durchbindung" / GTFS block_id)

In our approach, we need to consider both of them together to provide correct results (regarding Pareto-optimality).

Let's consider the following services, rules and their connection. Services are the nodes at the bottom, rules the top nodes where MS indicates "merge/split" and T indicates through-services.

Note that those rules apply to specific days. For simplicity, I assume that all rules active on the same days and no service is "cut". This means there's no case where another service outside the timetable period would be required to have all trains of the rule operating and no rule service participant is missing a matching partner.

Let's assume the trains visit the following stations:

From this network, we can derive something we call expanded services: these expanded services represent all ways a rider could travel and are used only for routing purposes. So when it comes to generating departure tables, or plot trains on a map, won't have duplicates.

For our example, the set of expanded services looks like this:

These services allow for all travel options a traveler would have considering that a interchange between two merged trains is not counted as a real interchange. The same is true for the change between services for through trains. Those expanded services can be collected using a repeated depth search from nodes with in-degree of zero.

Code that handles rule services:

• https://github.com/motis-project/motis/blob/master/base/loader/src/hrd/model/rules_graph.cc
• https://github.com/motis-project/motis/blob/master/base/loader/src/hrd/parser/merge_split_rules_parser.cc
• https://github.com/motis-project/motis/blob/master/base/loader/src/hrd/parser/through_services_parser.cc
• https://github.com/motis-project/motis/blob/master/base/loader/src/hrd/builder/rule_service_builder.cc
• https://github.com/motis-project/motis/blob/master/base/loader/src/rule_route_builder.cc
• https://github.com/motis-project/motis/blob/master/base/loader/src/rule_service_graph_builder.cc

If you want to handle this topic correctly (in terms of preserving Pareto-optimality), it escalates quickly. Especially the part that I omitted before (generating rule service constructs with uniform traffic days) can be tricky. The basic idea is that you iterate through the first graph (with MS and T nodes) and intersect bitfields until all bits are zero or there's no further service (graph traversal with early termination if bitfields became zero). Each time the component that was traversed is cut out of the graph (bits set to zero) and written as rule service construct with uniform traffic days).

Feel free to ask more questions.

[felixguendling]

Ah.. and to answer your actual question: the CSA algorithm stays the same, just the connections array, etc. are derived from those expanded trips instead of the raw trips from the source timetable.

The new core (nigiri) currently does not expand merge/split trains in the loading procedure. But this (or another solution with similar effect for the search results) will probably be implemented this year.