if you are using special routing rules or constraints, you can make them softer. for instance, if clock is always 2W2S, you can make it 1W2S or something.
if the problem is related to a specific cell (think something like AOI22, lots of pins), you can replace it for simpler cells and run OPT followed by route again.
if you have max tran, max load, max fanout rules that are too strict, you can make them less strict but still within allowed values. OPT+route should take care of it for you.
if the problem is related to floorplanning that was too tight to begin with, then you likely need to rethink the design.