Listing all possible train routes
Based on your comments, I'm assuming that if the problem asked to find all paths between $A$ and $B$ on a directed graph, you'd have no problem.  So the only hurdle is how to deal with the extra route information.
Here's an outline of the most obvious approach that I can see:


Convert the given set of routes to an adjacency matrix. Since each edge $(A,B)$ belongs to some route $R$, store that route in the corresponding entry for $(A,B)$ in the matrix.
Run your algorithm to find all paths between your start and goal nodes.
Convert the output of your algorithm to the desired form by collapsing all consecutive edges that belong to the same route into one edge.