Due to the fundamental role of transportation infrastructure in the functioning of societies, the speed and cost of restoring it following a disruptive event are of utmost importance. Restoring damaged infrastructure using existing prioritization rules is time-efficient but seldom optimal. However, determination of the optimal restoration program from combinations of various interventions in time is computationally intensive and time-consuming. This paper introduces a novel approach to identify near optimal restoration programs that reduce the time between the occurrence of the disruptive event and the time the restoration work starts, using a double-stage optimization model. Moreover, the efficiency of commonly used heuristic algorithms is investigated in the proposed model, which minimizes the overall costs from the time the disruptive event occurs to the time the restoration work is complete. The results of the case study suggest that simulated annealing and particle swarm optimization are efficient algorithms for this model. DOI: 10.1061/(ASCE)IS.1943-555X.0000700. This work is made available under the terms of the Creative Commons Attribution 4.0 International license, https://creativecommons.org/licenses/by/4.0/.