If you still want to keep the same frequency even there are setup violations, probably, you could redesign your circuit in the path where it has setup violations.
I think Hold timing the router should be able to solve. However for setup time violations you should add pipeline in timing critical paths. If you really have function which cannot split with a pipeline, writing your RTL in boolean equation (of-course the optimised ones) does help many times.