What may also help is to partition the design into key blocks - ones where there are many internal routes, but a lower number of routes between that block and the rest of the design. What you can then do is add logiclock regions into the design to constrain partitions to certain areas. This can help timing in some cases (brings logic with critical paths closer together), but also can help with routing congestion by avoiding the logic being scattered around in a way which means there is lots of competition for resources.
On a design I'm working on, it is pretty much impossible to get it to route and meet timing without logiclock regions.