This paper presents a robust vertex p-center model for locating Urgent Relief Distribution Centers (URDCs) on a set of given candidate sites, as well as assigning relief stations in affected areas to those URDCs. Particularly addressed in the model are uncertain travel times that are represented using intervals (or ranges), instead of probability distributions. The objective is to locate p URDCs so as to minimize the maximum travel time between URDCs and affected areas under the worst-case scenario. A key problem property that can facilitate the determination of the worst-case scenario, among an infinite number of possible scenarios, is analyzed. Since the problem is NP-hard, a simulated annealing (SA)-based heuristic is developed, to find robust solutions. Numerical results show that the proposed heuristic is effective and efficient in obtaining robust solutions. Finally, the model and its algorithm are applied to a real case with the data .from the 921 Chi-Chi Earthquake disaster.