Routing on city blocks: A case study for dengue control

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.

Authors

Institutions

Publication Details

Journal
Transportation Research Part E Logistics and Transportation Review
Published
2026-11-18
DOI
https://doi.org/10.1016/j.tre.2026.105402
Primary Topic
Vehicle Routing Optimization Methods
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Routing on city blocks: A case study for dengue control

Laura Silva de Assis, Rafael Kendy Arakaki, Matheus Diógenes Andrade, Fábio Luiz Usberti et al.
Transportation Research Part E Logistics and Transportation Review
Vehicle Routing Optimization Methods
article

Routing on city blocks: A case study for dengue control

Laura Silva de Assis, Rafael Kendy Arakaki, Matheus Diógenes Andrade, Fábio Luiz Usberti, Carlos Victor Dantas Araújo, Emrah Demir
article en

Abstract

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.

Transportation Research Part E Logistics and Transportation ReviewVol. 218
Federal Center for Technological Education Celso Suckow da Fonseca (BR), Khalifa University of Science and Technology (AE), Universidade Estadual de Campinas (UNICAMP) (BR)
Conselho Nacional de Desenvolvimento Científico e Tecnológico
Sustainable cities and communities, Industry, innovation and infrastructure
Vehicle Routing Optimization Methods
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon