The Dutch railway system is subject to maintenance, which is carried out by a group of rail contractors who need parking space to park and prepare trains in between projects. The objective of this study is to minimise the total costs as a result of the distance travelled by maintenance trains and the preservation of the included parking locations in the Dutch railway network. According to the dynamic nature and the NP-hardness of the Facility Location Problem (FLP), a Simulation-Optimisation (Sim-Opt) approach is proposed. This Sim-Opt consists of a Discrete Event Simulation (DES) and Simulated Annealing (SA) optimisation. Two neighbourhood functions are evaluated: a Random Search Algorithm (RSA) and a Utility Level Search Algorithm (ULSA), which takes the utility level of parking locations into consideration. This research shows that DES is a feasible evaluation method for finding possible solutions to the FLP in a Sim-Opt approach. The results of this evaluation show that the ULSA converges sooner than the RSA. Furthermore, the spread in best solutions across all instances is tighter when applying the ULSA. The findings indicate that the ULSA gives more robust solutions when compared to the RSA and makes the SA process more efficient. This research found that the best solutions in terms of overall cost includes on average 22 parking locations, which can reduce the maintenance cost by ~30%. The average increase in travel costs of ~9% does not justify the use of more capacity than the absolute minimum to house all trains.