A well-designed hospital facility layout planning process will enable improvements in operational efficiency, health outcomes, and patients’ medical experience. Older hospital facility layouts are likely to be based only on their designer’s experience, extant legal regulations, and other historical constraints. In this paper, we propose a solution to a multi-floor hospital facility layout problem in a hospital in Shanghai, China, based on a double-row model in which all departments are arranged into two rows on each floor. In this model, some fixed facilities are also taken into consideration. Two objectives, namely minimizing the total movement distance of patients and maximizing the total closeness rating score, are considered. An NSGA-II (nondominated sorting genetic algorithm II) algorithm with an adaptive local search operator has been developed to search for Pareto-optimal solutions. Experimental results show that our algorithm is able to solve model requirements successfully, the local search operator performs well, and the obtained results outperform the present layout in both the objectives.