The dynamic routing problem for Overlapped Segment Shared Protection in multi-domain networks has not received a lot of interest so far as it is more difficult than in single-domain network. Difficulties lie in the lack of complete and global knowledge about network topology and bandwidth allocation meanwhile this knowledge is assumed to be easily available in single-domain networks. We propose a two-step routing approach for this problem based on a topology aggregation scheme and link cost estimations: an inter-domain step and an intra-domain step. We propose two different heuristics, GROS and DYPOS for the inter-domain step, and a "Blocking-go-back" feature in order to reduce the blocking rate in the intra-domain step. We compare the performance of the two heuristics, and evaluate their solutions against an optimal single-domain solution. It shows that the proposed heuristics lead to resource efficient solutions that are not far from the optimal one. Moreover, both heuristics require a quite small computational effort and are scalable for multi-domain networks.