Access to healthcare is a requirement for human well-being that is partly dependent upon safe infrastructure. One of the UN Sustainable Development Goals regarding healthcare is to achieve universal healthcare coverage, which includes access to qual- ity essential health-care services. In many developing nations, roads are often vulner- able to floods. Floods can cause roads (especially roads with a dirt or gravel surface type) to become inaccessible for a long period of time. This inaccessibility can cause many inhabitants to lose access to a healthcare facility within a crucial traveling time span. Upgrading flood prone roads on which many households are dependent in or- der to access a healthcare facility, could reduce this threat to healthcare accessibility for many inhabitants. This research aims to use optimization techniques to reduce the impact floods can have on healthcare accessibility, and apply a case study to the country Timor-Leste. We formulate an optimization model that maximises the num- ber of households that can access a healthcare facility within a 5 kilometer traveling distance via a flood resilient route, given a specific budget. Alongside this formula- tion, we provide a (simple) flood and costs model for the road as well as di↵erent heuristics to find (near-)optimal solutions. Our research includes multiple tests to de- termine which heuristic works best and which parameters and other settings increase the computational performance of these heuristics for Timor-Leste. The heuristic that performs the best is a dynamic greedy heuristic. This algorithm is able to generate an optimal solution for all possible budgets within 4 hours.