I'm not certain, but in my observations, devastation removal appears to be linked to larger population (i guess more people leads to quicker fixing).

Large Armies == more/quicker devastation
Large Population == more/quicker un-devastation