This paper presents an initial study of a Healthcare Facility Location Problem, the Two-Level P-Median Location Problem (TLPMLP). The main goal is to analyze problem instances by studying their associated fitness landscape characteristics, with a focus on ruggedness, neutrality and number of local optima. For each instance, we consider two fitness landscapes defined by the following two functions: the direct neighborhood function ( \(\mathcal {O}(n)\) ) complexity) and the two-step Neighborhood function ( \(\mathcal {O}(n^2)\) complexity). We also conduct a preliminary exploration on the correlation between the fitness landscape characteristics and the solving difficulty by using an exact method (binary linear program) and two straightforward local search methods: a hill-climber and sampled walk. Experiments are conducted on 40 instances from the literature and 27 randomly generated ones. We discuss our results and point out several future research directions on these initial approaches to analyzing TLPMLP.