This paper deals with the problem of finding the optimal location and sizing of Energy Storage Systems in DC-electrified railway lines. These devices increment the use of the regenerated energy produced by the trains in the braking phases, as they store the energy to later provide to the catenary the excess of regenerated energy, that otherwise would be lost in the rheostats. However, these infrastructures require a high initial investment that, in some cases, may question their profitability. We propose a multi-method ensemble meta-heuristic to obtain the optimal solution to the problem, with a high level of accuracy. Specifically, the Coral Reefs Optimization with Substrate Layers (CRO-SL) is proposed, an evolutionary-type approach able to run different search procedures within the same population. We will evaluate the performance of the CRO-SL in the problem, and we will show that it performs better than the best known existing meta-heuristics for this problem.