Contingencies are unexpected crises or events that cause a major threat to the safety, security and well-being of a certain population. This research effort builds upon the work on contingency logistics reliability models by Miman (2008) who extended the preliminary work conducted by Thomas (2004) that provides the modeling approach which takes a mission success orientation and focuses on the ability to recover from or prevent a contingency logistics failure. Miman (2008) proposes the sustainability model of a contingency logistics network using the concept of selective maintenance. This problem, once formulated, is a non-convex, non-linear, non-separable, multi-dimensional, discrete knapsack problem. These problems are known to be NP hard. Therefore, one needs to explore heuristic solutions in search of robust and effective solution approaches. He developed a memetic algorithm, GAFTS, and proposed this for identifying the best set of maintenance actions to sustain the contingency logistics network. Besides, he used Physical Programming, a multi criteria optimization procedure, to exploit a network manager’s preference toward the numerous criteria (reliability, cost, time, resource utilization etc...) judiciously. This research effort continues the exploration of heuristic techniques for the sustainability model developed by Miman (2008) and develops a hybrid heuristics technique, EDGASA, incooperating simulating annealing (SA) procedure with genetic algorithm (GA). Comparisons of EDGASA with GA and SA reveal that it outperforms in terms of average reliability, best reliability and worst reliability found at an expense of increased solution time. One of the contributions of this study is a multi-objective modeling approach developed based on utopia distance that aims at minimizing the weighted distance between a solution to the ideal point that could be achieved. The study fills some of the voids in the contingency logistics networks’ solution and modeling and highlights potential studies by applying the hybrid heuristic developed as well as multiobjective modeling approach proposed to other problems.