An ongoing cluster randomized trial aims to investigate the efficacy of Targeted Indoor Residual Spraying (TIRS) in the prevention of symptomatic dengue, chikungunya, and Zika in children in Merida, Mexico. This study utilizes covariate-constrained randomization to screen for selections of 50 out of the 133 available clusters placed into two arms that are balanced across four specified covariates and geographic sector. We prioritized allocations that maximized the average minimum pairwise distance between clusters in order to reduce contamination. As some selected clusters may be subsequently found unsuitable in the field, we desired a strategy to substitute new clusters while maintaining balance. We developed an algorithm that successfully produced many allocations that allowed for many rerandomizations, all of which balanced specified covariates. Substitutions were made as needed. Validity of the design—as indicated by the lack of pairs of clusters that always or never appear in the same treatment arm—was confirmed at each stage. Simulations show that there are limitations to validity in other settings where the numbers of clusters available and selected are reduced.