Contact Graph Routing (CGR) is the state-of-the-art deterministic routing approach for scheduled space Delay-tolerant Networks (DTN). Indeed, CGR outlined the Schedule-Aware Bundle Routing (SABR) recommended standard from the Consultative Committee for Space Data Systems (CCSDS). The core approach exploits the predictability of space node mobility patterns and link availability, which is imprinted in time-varying graphs fed to Dijkstra and Yen's algorithms for route computation (pathfinding). This paper addresses the scalability issues CGR faces when computing routes over large-scale contact plans spanning several nodes and long-term planning horizons. After an in-depth analysis of the main CGR computation limitations, we propose multipath-tracking and tree-caching embedded in the Shortest-Path tree routing for Space Networks (SPSN) routing scheme. Simulation results show that SPSN's route computation time does not increase with increasing contact plan horizon while slightly improving on CGR's delivery rate.