It is an essential but difficult problem to provide effective and efficient medical or relief services to people in areas impacted by various anthropogenic and natural disasters. This study proposes a mathematical programming model to determine the locations of temporary medical relief shelters, as well as provide the required medical supplies from medical deployment centers effectively and efficiently under a limited relief budget. The severities and geographical locations of patients are considered in the problem. A mixed integer programming formulation has been proposed. The proposed model is hard to solve using a commercially available solver in a reasonable amount of time, especially for the problems of larger sizes. Hence, a greedy algorithm is proposed to solve the problem to generate good solutions in comparison with the solution obtained by LINGO. The computational results demonstrate the effectiveness and efficiency of the proposed methodology. Computational results under different scenarios are provided as well to demonstrate the validity of the proposed algorithm for various situations. © 2018 Elsevier Ltd