A bi-level programming model for network design of regional emergency logistics was formulated for the network to survive in natural disasters and to meet the needs of emergency supplies. There are two objectives in the upper programming model: a shortest total logistics time and maximum connectivity reliability under emergency. The upper model was solved by transforming it into a single objective model. The lower model was a user equilibrium assignment model with a fixed demand. An improved simulated annealing optimization algorithm was used to solve the whole bi-level programming model. Results of a numerical example indicated that adding the objective function of maximum connectivity reliability under emergency into the upper model decreased the system maximum criticality from 821.55 to 32.66, and total logistics cost by 0.22%, with the same total investment and logistics time.