Answers are grounded in this paper and cite their sources.
Dengue control programs must decide which city blocks to spray and how to route a spraying vehicle under tight time constraints. We introduce the City Block Routing Problem (CBRP), a covering-routing variant in which a block is serviced by traversing its perimeter and blocks may overlap at intersections; each serviced block yields a prize, and the goal is to maximize total prize subject to travel and spraying times. We present two mixed-integer linear programming formulations: a path-based model defined on the original street network, where routes are simple, and a walk-based model defined on a metric-closure graph over the street-network, where revisits are permitted. Both formulations are strengthened by valid inequalities. To scale up, we design a Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking (BRKGA-MP-IPR) whose decoder, based on a directed acyclic graph, maps chromosomes to time feasible routes. We compile a reproducible benchmark from dengue notifications (2015–2021) in two Brazilian cities and complement it with 640 synthetic instances derived from OpenStreetMap. Computational results show that the exact models are effective for medium-sized instances, whereas the BRKGA-MP-IPR efficiently generates high-quality solutions for larger networks. The path- and walk-based formulations offer complementary advantages depending on the operational setting.
No takes yet. Share an insight, caveat, or question.
Andrade et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: