This paper provides insights to locate a finite number of distribution centers to provide a quick response time for disaster relief incorporating social costs within the modeling framework. We explore theoretical aspects of the problem formulation and propose a model that maximizes coverage of affected regions while minimizing human suffering through the use of a social cost function. Our results show that the social cost function is minimized within the area enclosed by the Voronoi region for a chosen facility. We also propose a heuristic algorithm to solve the problem of locating these facilities in a reasonable amount of time. Since the quality of the solution and the running time depends largely on the initial starting points for the heuristic, we provide recommendations to choose the initial starting points. The proposed approach has the potential to significantly improve the efficiency of distributing critical supplies in disasters by optimizing the response time. © 2010 Springer Science+Business Media, LLC.