Find frequent segments of GPS trajectories
With the initial assumption that the trajectories can follow existing routes that a number of all possible sub-trajectories is limited and can be also discreet. I would discretise the map and on all sub-paths compter a frequency analyses:


Create a map of all possible paths such that you overlay all trajectories which gives you the full map.
Dicretise the map by creating paths and path segments defined that each path segment is a path between two closest branching on the particular path, you can also see this task as generating a graph.
Represent each trajectory as sequence of this path segments and compute a frequency characteristic for each segment in the map
You can extend this task with discretization levels such that some short by-passes could be still counted as the main path...