In this study, we tackle the challenge of discovering moving-together patterns from long-term travel data, including passengers’ origin and destination routes over extended periods. This problem relaxes the requirement for continuous co-location of moving objects, allowing for patterns where passengers might travel together intermittently. This flexibility is especially valuable in transportation systems, where passengers might not always travel side-by-side but still follow similar routes, allowing for more realistic detection of movement patterns in transit systems. These patterns are crucial for understanding traffic behaviors, alerting to congestion, and identifying familiar strangers. The complexity arises from irregular time gaps and the large volume of travel data. We propose two solutions: Move-Exact, which uses a multi-granularity bins structure for the exact grouping of moving objects, and Move-Approx, a fast, approximate approach for real-time pattern identification in large-scale datasets. Extensive evaluation on a large volume of travel data provided by a train service operator in Hong Kong demonstrates that our approaches achieve an average speedup of two orders of magnitude compared to six competitors in detection performance.