AbstractAfter disasters, such as in the aftermath of a major earthquake, the road network can be blocked by debris from collapsed buildings, impacting accessibility to the affected population. In addition, people move and assemble in various points of the city. In this context, road network accessibility becomes an important issue for logistics operations responsible for the relief and the distribution of supplies to the affected population. We propose metaheuristics for the multi‐period Work‐troops Scheduling Problem (WSP), extending a contribution from the literature. The WSP is an NP‐hard problem. This study brings several contributions to the WSP such as a dedicated local search and two metaheuristics: a Greedy Randomized Adaptive Search procedure and an Iterated Local Search. Results are performed on theoretical instances, and on a realistic instance of Port‐au‐Prince city in Haïti after the 2010 earthquake, where the problem has 16,660 vertices and 19,866 routes representing the urban network, and more than 500 blocked roads. The method developed improved the results from the literature and the results indicate its robustness. Moreover, the best‐known results for the case of the Haïti instances are presented in this study.