Natural disasters are phenomenons which strike countries all around the world. Sometimes, either by the intensity of the phenomenon or the vulnerability of the country, help is requested from the rest of the world and relief organizations respond by delivering basic aid to those in need. Humanitarian logistics is a critical factor in managing relief operations and, in general, there is a lack of attention on the development of mathematical models and solution algorithms for strategic and tactical decisions in this area. We acknowledge that in humanitarian logistics traditional cost minimizing measures are not central, and postulate that other performance measures such as time of response, equity of the distribution or reliability and security of the operation routes become more relevant. In this paper several criteria for an aid distribution problem are proposed and a multi-criteria optimization model dealing with all these aspects is developed. This model is the core of a decision support system under development to assist organizations in charge of the distribution of humanitarian aid. Once the proposed criteria and the model are described, an illustrative case study based on the 2010 Haiti catastrophic earthquake is presented, showing the usefulness of the proposal.