The rational design of interventions is critical to controlling communicable diseases, especially in urban environments. In the case of the Chagas disease vector Triatoma infestans, successful control is stymied by the return of the insect after the effectiveness of the insecticide wanes. Here, we adapt a genetic algorithm, originally developed for the travelling salesman problem, to improve the spatio-temporal design of insecticide campaigns against T. infestans, in a complex urban environment. We find a strategy that reduces the expected instances of vector return 34-fold compared with the current strategy of sequential insecticide application to spatially contiguous communities. The relative success of alternative control strategies depends upon the duration of the effectiveness of the insecticide, and it shows chaotic fluctuations in response to unforeseen delays in a control campaign. We use simplified models to analyse the outcomes of qualitatively different spatio-temporal strategies. Our results provide a detailed procedure to improve control efforts for an urban Chagas disease vector, as well as general guidelines for improving the design of interventions against other disease agents in complex environments.