Abstract It has been proved that, in networks with co-existing delay sensitive and delay tolerant traffic flows, the overall network utility can be significantly improved by putting off (or storing) delay tolerant flows until off-peak hours. In our previous work, we proposed Time-Shifted Multilayer Graph (TS-MLG), a routing framework for Store-and-Forward (SnF) optical circuit switched (OCS) networks. With TS-MLG, the scheduling of delay tolerant traffic flows can be determined through a single routing computation. TS-MLG has been shown to be useful in SnF OCS networks of medium size, but the computing time required per traffic flow increases quickly as the network size increases and the number of active requests grows. To control the computational complexity, the number of layers used in routing must be limited, resulting in degradation of network performance. Although the delay caused by computing the end-to-end spatial/temporal path is negligible compared to the overall end-to-end transmission delay, it decides the scalability of the control plane. This prevents TS-MLG from being used in large-scale networks. In this paper, we aim to increase the scalability of the TS-MLG, by taking into account the graph sparsity. Instead of running Dijkstra Algorithm on adjacency matrices, we propose to use adjacency list to represent the graph, and Breadth-First Search Algorithm to compute shortest paths. This reduces the computational complexity from O(N2 × L2) to O(N × L + E), in which N is the number of network nodes, L is the number of layers used in routing and E is the number of edges, with a slightly increased overhead in graph update. We verify the effectiveness of the proposed algorithm by performing a large number of computations on the same hardware platform. In a network containing 30 nodes, and when the number of layers is limited to 20, the average time needed to complete 1000 routing computations with the proposed solution is 1.597 s, while that for the original one is 244 s. The proposed solution effectively scales up TS-MLG and make it suitable for large-scale networks.