The multi-stop station location problem (MSLP) is motivated by infrastructure planning for range-limited transportation services such as electric intercity buses. We study this foundational infrastructure-siting and routing problem in which a fixed set of ordered trips must be made feasible under vehicle-range limits by installing shared stations and, if necessary, allowing detours between consecutive planned stops. We present an arc-based mixed-integer linear program (MILP) and two pattern-based reformulations, one based on complete trip paths and one based on trip segment paths. The latter yields shortest path pricing problems, and both are combined in a nested approach. For the pattern-based reformulations, we develop branch-price-and-cut algorithms with a problem-specific primal heuristic, branching strategies, and, for the segment-based formulation, additional cutting planes. On synthetic benchmarks derived from TSPLIB, the pattern-based approaches are more scalable than the compact MILP, and the nested approach performs best overall, solving 82.4% of all instances to optimality within the time limit. On a GTFS-based intercity bus instance with 1644 nodes and 2408 trips, the nested approach proves optimality in 40.06 hours. These results show that exact methods can solve the MSLP beyond toy instances on public-data transportation networks.