This paper proposes a solution for the automation and optimized orchestration of maintenance operations in IP/MPLS transport networks by capitalizing on the standardized graceful restart mechanisms. The operator is only responsible for setting maintenance targets and constraints, and then assessing progress reports. In this context, the maintenance planning issue is formulated as a Constraint Satisfaction Optimization Problem (CSOP). In order to provide effective solutions to this problem, two different algorithmic approaches are described and evaluated: a glutton heuristic and an evolutionary method. The experimentation results show that the combination of these two methods allows to significantly reduce the convergence time towards an optimized solution.