Responding to hurricanes is an exceedingly complex task whose effectiveness can significantly influence the final impact of a hurricane. Despite a lot of progress, recent events and unchecked population growth in hurricane-prone regions make it clear that having appropriate shelter options and shelter evacuation plans is very important. This research proposes a scenario-based shelter location model that identifies a set of shelter locations to maintain over time. These locations are chosen such that they are robust across a range of major hurricane events. This model considers the influence of changing the selection of shelter locations on drivers' route choice behavior and the resulting traffic congestion. The problem is formulated as a two-stage stochastic bilevel programming model where the evacuees' route choice follows dynamic user equilibrium (DUE). Aiming for large-scale realistic applications, a heuristic approach is developed to efficiently solve the formulation. A case study in the state of North Carolina is presented to illustrate the applicability and efficacy of the proposed model formulation and solution approach.