This paper proposes a logistics model for delivery of prioritized items in disaster relief operations. It considers multi-items, multi-vehicles, multi-periods, soft time windows, and a split delivery strategy scenario, and is formulated as a multi-objective integer programming model. To effectively solve this model we limit the number of available tours. Two heuristic approaches are introduced for this purpose. The first approach is based on a genetic algorithm, while the second approach is developed by decomposing the original problem. We compare these two approaches via a computational study. The multi-objective problem is converted to a single-objective problem by the weighted sum method. A case study is presented to illustrate the potential applicability of our model. Also, presented is a comparison of our model with that proposed in a recent paper by Balcik et al. [6]. The results show that our proposed model outperforms theirs in terms of delivering prioritized items over several time periods.