Evacuation transport network design plays a critical role in the efficiency of emergency response. This research proposes a novel bi-level nonlinear programming model for the pre-flood evacuation transport network design. The model considers both uncertainties of demand and network connectivity reliability. An upper-level model is developed with the minimum total evacuation time and maximum network connectivity reliability, while the lower-level model is a traffic assignment model that describes people's evacuation route choice behavior. For the uncertain network connectivity reliability, an approach to quantify it based on percolation theory is proposed. For the uncertain demand, an approach to transform it into a solvable form based on Robust Optimization (RO) is proposed. Furthermore, the lower-level model introduces the regret-risk utility function as its objective function and proves its applicability. An equilibrium condition is proposed to improve the Logit model based on the regret-risk utility function. For the solution of this model, an Improved Genetic Algorithm combined with Non-dominated Sorting Genetic Algorithm II(IGA-NSGA-II) is designed. Then, the Nguyen-Dupuis network is used to demonstrate that the approach developed in this paper can be used to solve the bi-level nonlinear programming model and to obtain a satisfactory design solution. Further, a parameter sensitivity analysis is shown to study the impact of the risk aversion parameter and regret aversion parameter in the regret-risk utility function. Finally, the Central Coast region of New South Wales, Australia is used as a case study, and the research output will help government authorities to plan and design a pre-flood evacuation transport network, especially to answer the questions of “Where to build potential roads?”, “How much budget is needed?”, “How long does it take to evacuate?”, and “How reliable is the network connectivity?”.