In this paper, a service restoration method is proposed. From a recently algorithm called MEAN-MH, that combines Multi-objective Evolutionary Algorithms with the tree encoding named Node-Depth Encoding and an Alarming Heuristic in order to find adequate restoration plans for distribution systems, we proposed a modification that include a search for a feasible optimal solution. In cases where this optimal solution was not found the best solution is used as a initial configuration to MEAN-MH. The case study uses a real large-scale distribution system with size from 3,860 buses and 632 switches to 30,880 buses and 5,166 switches, requiring running time less than 37 seconds for all the test cases. The proposed methodology requires no network simplification (as modeling a set of loads in a unique load point or using a relatively small set of switches instead of all switches) in order to generate adequate restoration plans for those distribution systems. Moreover, the results show that the service restoration plans is significantly improved in comparison with MEAN-MH.