As one of the outcomes of climate change, humanity faces more and more natural disasters. Storms and floods are among the most frequent disasters occurring in different parts of the world. Disaster Operations Management (DOM), which aims to save lives and eliminate or reduce the impacts of disasters, consists of mitigation, preparedness, response, and recovery phases. This study considers the Shelter Location Optimization and Relief Supply Management (SLORSM) problem, one of the essential problems under the preparedness phase of DOM for cyclones, storms and floods. The problem consists of selecting shelters to be opened among predetermined alternatives and distributing the relief supplies to these shelters. In addition, it addresses when to open the selected shelters and when and how much relief supplies are to be shipped to each shelter based on the estimated scenarios of the route and severity of the cyclone, storm and flood. This study aims to formulate and develop solution methods for this problem. Accordingly, a Mixed Integer Programming (MIP) formulation for this optimization problem followed by a decomposition-based heuristic algorithm are proposed to solve this complex combinatorial problem. Furthermore, an extensive computational study is conducted to test the performance of the proposed MIP model and heuristic algorithm. To this end, real data of the Sultanate of Oman was solved as a case study. The heuristic model performed well and was able to solve the complete model with good quality results in a reasonable time which meet the requirement during the emergency situation. The detailed analyses of the obtained results provide insights for the decision-makers and researchers for future research direction.