crowdAI is shutting down - please read our blog post for more information
Optimizing train schedules
By SBB CFF FFS
about 2 years ago
First, thanks for this amazing and very interesting challenge.
I am trying to completely understand the sample scenario by following the documentation. However, regarding routes specification i see one thing that in general confuses me:
o route id 4 is specified with “starting_point”: “C” and “ending_point”: “C” which seems to indicate a cycle.
I understand that the special case where this appears in the end of the path is handled in route_graph.py through list indexing logic and appending “_end” in the end. However, in general, is it safe to assume that for the inputs of the challenge that such cycles will not exist ? After all, if I followed everything correctly the routes graph is supposed to be a DAG, no?
Many thanks in advance for your support :-)
about 2 years ago |
Great question, I can understand your confusion!
Thing is, we use the fields starting_point and ending_point internally basically as geographical reference markers when plotting the timetable in graphical form, something like this. Having the same starting and end point then means that the train spends some time there, but doesn’t actually proceed to the next geographical point. Of course, this typically means it has a stop there.
In calculating the timetable, we never actually use the starting_point and ending_point, it is only afterwards for visualisation.
Now, to actually answer your questions. If you look at route_graph.py, it also doesn’t use starting_poing and ending_point, but rather it uses either the sequence_numbers of the sections (which, by some axiom, we promise to be unique in a route), or the route_alternative_marker if there is one route coming together in a node.
As an example, I copied below the output of the route_graph script which lists the node labels it assigns to the nodes for the sample scenario (see the notebook).
You will notice, they are either built up with sequence_numbers or with route_alternative_markers. The starting_point and end_point are not used. The _end and _start suffixes, by the way, are used when a node does not have incoming or outgoing arcs, so we know it is a source or a sink node just from the label.
Constructing route graph for route 111
Adding Edge from (1_beginning) to (M1) with sequence number 1 -> add arc 1. The starting node doesn’t have an incoming arc, so give it the name of the section plus the suffix _beginning. The end node receives the label of the route_alternative_marker
Adding Edge from (1_beginning) to (M1) with sequence number 1
Adding Edge from (M1) to (4->5) with sequence number 4 -> second arc. It starts at M1 and its end node receives the label 4->5, which means its (unique) incoming arc has sequence number 4 and its (unique) outgoing arc has sequence number 5.
Note that if there was more than one incoming or outoing arc, then we would label the node according to its route_alternative_marker as above.
…and so on…
I hope this clears things up a bit?
Thanks again for the great question!