Route restoration is considered to be a task of foremost priority in disaster relief. In this paper, we propose a robust optimization approach for post-disaster route restoration under uncertain restoration times. We present a novel decision rule based on restoration time ordering that yields optimal restoration sequencing and propose conditions for complexity reduction in the model and prove probability bounds on the satisfaction of these conditions. We implement our models in a realistic study of the 2015 Gorkha earthquake in Nepal.