Speed up large calculation of intersections
I would use a somewhat different algorithm to accomplish this task, by instead making a dictionary of all trains that go to each stop, sorting those trains by arrival, and then taking all inorder pairs of trains at each stop.

The basic algorithm is like this:

from collections import defaultdict
from itertools import combinations

trains = {...}
departures = {...}

intersections = set()

stations = defaultdict(list)
for t, train in trains.items():
    for s in train:
        stations[s].append(t)

for station in stations.values():
    intersections.update(combinations(sorted(station, key=lambda t: departures[t]), 2))


(This version of the code vastly improved by @Veedrac)