However, the DP approach limits the size of the road networks that can be solved within a 24-hour time limit. This fact motivated the development of a heuristic (IGRCP) that we develop for our problem. We run extensive computational experiments to analyze the difficulty of solving instances of the NRCSRP depending on the values of three distinct parameters. Two of the parameters are beyond the control of the decision maker: the number of nodes or population centres in a network and the level of network damage caused by the disaster, which is denoted by parameter α and determines the number of edges requiring repair. The third parameter, β, is the maximum tolerable percentage by which a path connecting each demand node i to the depot is allowed to increase in order to be considered accessible. This parameter can be controlled by the decision maker and depends on the specifics of each setting.