Optimization Models, Statistical and DSS Tools for Prevention and Combat of Dengue Disease

1. Introduction

The objective of this study is to illustrate how operational research techniques can be used in the organization and resolution of logistic operations for combat of dengue in Sobral, Fortaleza and Rio de Janeiro, middle and large-sized Brazilian cities located in the states of Ceará and Rio de Janeiro, Brazil.

Considering that the activities to combat dengue are similar to those used to combat other zoonoses, we have the expectation and the insight that this methodology has a much larger scope, be it for diseases that are similar to dengue or for other countries with economical and social development similar to Brazil.

In this study, we basically describe the utilization of a selected set of operational research methodologies used in planning the activities of combat and control of dengue in middle and large-sized Brazilian cities, supported by a complex information system. The objective is to speed up the process of information coming from the field concerning the growth of the disease, and improve in quality and effectiveness the decision making by the municipality health managers.

Some of the logistical models related to districting here are well known and have been regularly used in applications associated with various economic and health care sectors, (Bourjolly et al 1981), (Mehotra et al 1998), (Bozkaya et al 2003), (Blais et al 2003), (Zhong et al 2007). The innovative character of the current study is the articulation of these techniques, using others to support them, for solving a public health problem, therefore consisting of an application of great social and economical importance in a sector where the use of such tools has not generally yet received much attention in developing countries.

The study is organized in the following sequence. In Section 2, we describe the characteristics of the dengue disease, the standard control procedures and its presence in the world, with a special focus on Brazil. In Section 3, we present the operational plan in the cities of Sobral, Fortaleza and Rio de Janeiro, for the activities of control and combat of the disease. Concurrently, we make an initial description of the information system proposed to support such information, which is basically grounded on geoprocessing combined with database systems for the Web and the acquisition of remote data. In Section 4, we present briefly a set of logistic optimization models considering the planning of the sanitary agents’ services to combat dengue, as well as some formulations of mathematical programming models, related solution methodologies used by the state-of-the-art heuristics and their respective counterparts in the information system. In Section 5, we consider the prevention aspects by using statistical tools for forecasting the disease and tracking the Aedes by spatial clustering techniques (natural group detection). In section 6, we do a discussion of our Web base Spatial Decision Support System and consider its applicability nationwide. Finally, Section 7 sets out the preliminary conclusions.

2. General considerations on dengue

The fast demographical changes resulting from non-planned migration from rural to urban areas and from the population growth in the urban areas with low infrastructure lead to an increased incidence of the disease transmission and the dissemination of pathologies in areas that have not yet been affected. However, in respect to the emergence of diseases transmitted by mosquitoes, even a population that lives in a risk area may register low infection rates, if preventive measures are taken, such as: operations for closing ditches, the placement of nets in cisterns and water-tanks, the use of repellents and, whenever possible, educational and vaccination campaigns.

The migration process facilitates the introduction and the dissemination of new infection agents, with no previous immunity measures. On the other hand, isolated populations might not have access to a constant treatment, increasing, thus, the morbidity/mortality rates associated to a certain specific disease, (Keating 2001).

The temperature increase associated with the pluviometric precipitations also favor, in a meaningful way the introduction and the dissemination of pathologies that are harmful to people’s health. Temperature changes affect the birth of disease transmitting mosquitoes (vectors) as well as the epidemic potential, since it alters the reproduction rate or the quantity of bites in humans, it transfers the geographical boundaries of the vector or its distribution, it alters the extrinsic incubation of the pathogen and it increases or decreases the vector-pathogen-host interaction, affecting, therefore, the susceptibility of the host. Rainfall increase leads to an increase of reproduction sites and, consequently, to an increased number of mosquitoes. With an increased number of female mosquitoes there is also an increased chance that a mosquito may acquire a pathogen and transmit it to a second susceptible host, (Keating 2001), (Wu et al 2007).

In Figure 1 we see three successive curves, in blue, green (vert) and red. They refer to events in Regional II - Fortaleza, concerning to the period January-October 1995; being considered:

1. the accumulated percentage of the rainfall (varying from 0 to 100%);

2. the accumulated percentage of the number of larvae (focus); and

3. the accumulated percentage of human cases.

Then if we fix some percentage p, let be:

1. t ₁ = t ₁ (p) the time for the rain may reach that value p;

2. t ₂ = t ₂ (p) an analogue time for the focus;

3. t ₃ = t ₃ (p) an analogue time for the human cases.

Let also α(p) = α = t ₂ – t ₁ that is the time elapsed in sort that the percent of focus reaches the same value of the rainfall; and β(p) = β = t ₃ – t ₂ for the percent of focus reaching the same value of the percent of cases. Thus α and β are “waiting times”. In general, as in the figure, we have that t ₁< t ₂< t ₃. We can also consider γ(p) = γ = α + β = t ₃ – t ₁ .

We argue that the increasing of α, β and γ is the result of a good prevention and/or combat process of dengue (Negreiros et al 2006). Unhappily we do not have all the data necessary to observe the occurrences in other years. But we can test to see what is occurring with γ from 1998 just to 2005, that is, considering the two curves, for the rainfall and the cases, Figure 2.

Figure 1.

Accumulated Percentages of the Rainfall, Number of Focus (Focus) and Cases (from 0% to 100%) per day in Regional II – Fortaleza/BR, along the period January-October 2005. Graph produced by Webdengue, Data source: FUNCEME and SMS/PMF-CVS.

With respect to the Figure 2 the following considerations are pertinent:

1. 1998, also 1999 and 2005 are “typical years”, since the “lags” or “waiting-times” were present along all the epidemic year (in general taken from January to October);

2. In the years 2000 and 2002 the “lags” were viewed only later, that is, with p ≥ 50% approximately;

3. In the year 2004 there were practically inexistent “lags” or “waiting times”, and also within 2001.

We must interrogate if with these two years the combat to dengue was neglected or developed in a wrong way. For the year 2003 the data are incomplete but it is still possible to verify the “lag” between rain and the number of human cases for the same period of that year.

Similar graphics were obtained with respect to intervals of five days, or “pêntadas”, but showing exactly the same behavior. In fact, references found in other articles in this direction are somewhat limited in nature, restricting themselves to one or two annual epidemics periods and considering trivial correlation techniques. But a technique also recommended, and found in DePradine & Lovell (2004), refers to the determination of cross-correlations.

An issue in terms of climatic influence refers to the possible effect of ENSO (El Niño/LaNiña-Southern Oscillation). Some items surveyed are not clear enough because they suggest that an El Niño episode would itself be a trigger for dengue, malaria, etc. This is not true in a strict manner because the impacts of ENSO vary widely geographically and are modulated by several other interconnections and also by epidemiologic factors.

For instance, in the septentrional northeastern Brazil, and particularly in Ceará, a strong El Niño points with very high probability to scarce rainfall and hence to a limited cases of dengue cases along the rain months, unless the appearance of new or very older (as DEN-1) viruses strains. Otherwise, with “neutral years” in northern of northeastern-Brazil, are more common or usual “extreme” occurrences, this is, with very scarce or with very high rainfall from February to June, as referred in Xavier (2005) and Xavier et al (2007).

Dengue fever and/or hemorrhagic dengue fever are systems of endemic diseases that occur in many tropical and subtropical regions, highly influenced by the environmental conditions, by climatic instability and demographic changes, in areas that conceal the vectors of the primary mosquitoes: Aedes aegypti and Aedes albopictus. As far as morbidity and mortality are concerned, dengue fever, hemorrhagic dengue fever (HDF) and the the dengue shock syndrome (DSS) are considered to be the most important viral diseases transmitted by arthropods.

Figure 2.

Rainfall & Cases of Dengue accumulated (0 to 100%) in the period 1998-2005 by intervals of ten days = “decêndios” = dc, Fortaleza-Ceará, Xavier et al (2008)

The World Health Organization (WHO) estimates that approximately two-thirds of the world population live in areas that are infected by the vectors of dengue, mainly, Aedes aegypti and Aedes albopictus. These populations are running the risk of contracting one of the four varieties of dengue serotypes that currently circulate in the world. An outbreak of dengue fever or of hemorrhagic dengue fever may affect between 70-80% of the population, drastically reducing the productive capability of an urban environment or of a rural economic sector. Figure 3 shows a picture of the disease dissemination in the world, presenting a detailed division of the areas at risk by dengue fever and by hemorrhagic dengue fever, for the year 2008.

The global impact of dengue has drastically increased in the last decades, and today it is classified as an infectious disease that emerges and re-emerges. Nowadays, dengue fever and hemorrhagic dengue fever (HDF) occur in more than 100 countries, with more than 2.5 billion people at risk annually, and it is estimated that there are 20 million cases of dengue infection, resulting in approximately 24,000 deaths. It’s important to emphasize that the most of the cases refer to children. The WHO considers that it’s necessary to make a global coordinated effort to bring the resources of modern science to bear on the control of ten major tropical diseases in the world, (TDR, 2004). Most recently, their position turn to: To foster an effective global research effort on infectious diseases of poverty in which disease endemic countries play a pivotal role, (TDR, 2007).

Figure 3.

Countries at risk of dengue fever, as occurred until in November 2008 (TDR, 2009).

Dengue appears as the second major important tropical disease worldwide where malaria comes in the first position. Considering the number of people who are infected annually by viral dengue, with more than 500,000 hospitalizations per year, there is a growth tendency, as the control measures of the dengue mosquito either fail or are not effectively implemented or regulated from a global scale point of view. For the eradication of dengue to succeed, the target populations must be quickly identified, so that large scale educational and biological control programs can be implemented immediately (WHO 1999), (KEATING 2001), (TDR 2004/2007/2009).

Alarmed with the resurgent situation of the disease, the WHO estimated that the number of individuals infected with viral dengue might exceed 100 million annual cases around the year 2001. The sub-notification of human cases is a real problem in the major third world countries (those last years’ estimative of 5 to 7 sub-notifications per 1 correct). The real situation is actually far worse most recently.

Understanding the relationships between human behavior, environment and the disease systems, is crucial to reduce the morbidity and mortality rates associated to the epidemic and endemic dengue transmission. In order to avoid the introduction of the dengue fever in new areas and to reduce the re-incidence of epidemic dengue in endemic areas, studies must be carried out so as to identify the correlation between climatic varieties, demographic changes and the increase of the incidence of dengue, to have better forecasts of the disease growth based on more appropriate models, and to define logistical criteria for attack operations through agents and vehicles, that may facilitate and guarantee, in a broad manner, the coverage of the affected regions. All this is necessary in order to define an organization of how, when and where to control the efforts that will be implemented. Since effective dengue vaccines are not foreseen for the immediate future, the government, health insurance companies and researchers must continue their efforts to understand the transmission dynamics associated with dengue.

The number of dengue cases in Fortaleza 2001-2006 (a), Sobral 2006 (b), Brazilian Regions (c-d) and Brazil from 1989-2010 (e), can be seen in Figure 4. The rapid growth and the resurgent behavior of the disease in Fortaleza, Sobral, Rio de Janeiro and Brazilian regions is one of the major worries of the health authorities.

Today, Brazil spends approximately US$ 1.0 billion dollars annually with the prevention and combat of dengue. From that volume, approximately 80% is used to maintain the infrastructure of direct prevention in the real estate units and the rest is spent in management and education. Despite that, it is estimated that US$ 5.5 billion dollars are lost annually due to local epidemic situations like the one that occurred in 2002, (SVS, 2004-2007).

3. The computational framework for dengue management

Dengue is endemic in Brazil, but it often appears in epidemic outbreaks, as we have seen in the previous section. The control of dengue requires managing a huge volume of information on the presence of breeding sites, the presence of the vector in the different real estate unit breeding sites, the occurrence of human cases, the realization of interventions in the larva and adult forms of the vector, and on educational interventions to reduce and eliminate breeding sites. These information changes in time and space. The actual decision making as to when and where to intervene is based on computational systems with outdated technologies that take into account only a small part of that information, such as: occurrence of human cases for urgent interventions and presence of the vector for medium term interventions.

In the city of Sobral, in the state of Ceará, the work to combat dengue is being developed by the Center for the Control of Zoonoses as in Regional II for the city of Fortaleza. The information on vector focuses, collected by approximately 200 sanitary agents is registered daily in Sobral and 300 agents for Regional II in Fortaleza.

By mastering and making use of Information technologies combined with Geoprocessing and Database Systems for the Web and Remote Data Collection, we identify the possibility to dispose the information gathering (through databases) available directly on the field, through palmtops or pocket PCs (Hand-Held), or turning available a network of equipment, through which the print forms are transcribed directly into the network by the sanitary agents themselves, who are trained to do that. The database manager treats the relevant information, which is immediately published on the web, in such a way that the health officials can follow what happens in terms of the expansion of the focuses and cases, with a dynamic vision of their evolution in time. Such an accompanying process is done through a Manager system, installed on the desktop of the center of Zoonoses or through the Webdengue system, available on an Internet website (http://www.webdengue.com).

The framework is thus made up of a set of five computational systems: Webdengue, Manager, Geographvs, a geographical editor to keep actual major urban occupation information, “Hand-Held” Agent and “Hand-Held” Supervisor, that exchange information so as to provide the managing person the necessary resources for making decisions on “what to do” in case of an endemic or epidemic situation of such disease.

Figure 4.

Disaese evolution in number of cases: (a) Fortaleza, Jan/2001-Sep/2006; (b) Sobral, Jan-Dec/2006; (c) Brazilian Northeast and Southeast regions; (d) Brazilian North, Midwest and South regions; (e) dengue re-emerging in Brazil. (*) Source: Ministry of Health (SVS/MS).

The system Webdengue is basically used to increase the speed of information gathering on the evolution of the disease through human cases, and to cross that information in regard to focuses within a certain period of time. This procedure usually takes about 15-30 days, and may take much longer. When the information comes from the web by the medical and laboratories staff, it comes within seconds. Furthermore, decision-making support tools based on optimization models have been included – the Manager System –, as a differential so as to help supervisors of zoonoses centers to optimize the coverage of sanitary agents, besides scheduling the services, and other resources.

Since it is necessary to disseminate the information about the presence of focuses from “real estate unit to real estate unit” in Sobral or by block in Fortaleza, our work extends itself as advantageous in the sense of the georeference of the residences, the businesses and others, resulting in direct gains to both the municipal and the health administration (via the system Geographvs).

As for the “Hand-helds”, the systems for palms or pockets, “Hand-Held” Agent and Supervisor, speed up the process of writing down the field data and the consolidation of the results, pending visits, as well as sporadic surveys of habits, personnel pets survey, educational level and behavior of the citizens who live in the urban regions.

Once they are integrated, the systems can quickly present to the officials the table of the evolution of the diseases, and they can also help analyze other aspects that are not directly related to the diseases. The national information systems on such diseases (SINAN

SINAN - Sistema de Informação de Agravos de Notificação (Aggravation of Notification Information System)

, National System for Accompanying the Cases of Dengue and FAD

FAD – Sistema de Notificação de Febre Amarela e Dengue (Yellow Fever and Dengue Notification System)

, National System for Accompanying the Focuses of Yellow Fever and Dengue) are automatically fed by the system. Therefore the exact place, period and day of the presence of the Aedes aegypti mosquito is stored in a space-temporal georeferenced database.

Figure 5 presents our framework. It is possible to notice the modeling concept of the information management to appreciate the technological content added for minimizing the temporal distances in processing the information and making pertinent decisions on prevention and combat.

Figure 5.

The proposed computational Framework for the management of dengue

Thus, once the information is available at the necessary speed and precision level (now possibly right after each agent’s working day), statistical models for a climatic tracing × forecast of case occurrence, clustering of focuses and cases in significant sizes, as well as infection models were also developed to better estimate the expansionist influences and to indicate the inhibitors for the epidemic advance in a Decision-Making Support process. Such tools are timely and useful to health officials, providing them with a contextual and temporal vision of the expansion of the disease.

This technology was evaluated in Regional II - Fortaleza/CE, with the support of CVS

CVS – Célula de Vigilância Sanitária

/PMF

PMF – Prefeitura Municipal de Fortaleza

^, to the control of strategic points (real estates with control of every 15 days: tire-repair places, buildings in construction, old-car deposits, cemeteries, etc.), having reached excellent results, with “zero focus” in 20 of its 21 boroughs, or more precisely, from 5443 visits in special real estate units done by 13 agents during June to November 2005 only one focus with Aedes remained in a build in construction. Also in Sobral, the framework was partially developed, where we built the city thematic maps, and evaluate some results considering the evolution of focus that were investigated for the years of 2004 and 2005. In Figure 6, we show the thematic maps used in the software for managing the evolution of the disease in different cities (Sobral, Fortaleza and Rio de Janeiro).

Figure 6.

Areas where the computational framework was prepared to run, Sobral and Fortaleza in the state of Ceará, and Rio de Janeiro in the state of Rio de Janeiro, Brazil.

4. Combinatorial models for the logistic of prevention and combat

As it can be identified in the above-described researches on dengue, the prevention logistics in place is characterized by the extended use of spraying vehicles and sanitary agents within the regions affected by the mosquito, generally with an inefficient planning which does not take the process of servicing into consideration from the Operational Research point of view. The use of spraying vehicles as a preventive measure is adopted in Brazil; nevertheless, as we have seen, its effectiveness is questioned in some places.

In 1999, we witnessed both phases of preparation for the massive combat of dengue, namely, planning for attacking the infection sectors and the infrastructure of the spraying-vehicle system. We observed that the organization of the system uses, in a precarious manner, a set of computational modules that register thematic maps, distributed according to the need for action. The distribution of the agents and of the vehicles does not optimize the efforts, but it demonstrates a lot of good will in attacking the problem, (Negreiros, 1996).

The spraying vehicles task can be in fact largely improved by better designing their itineraries, in creating service areas according to risk sectors, or in minimizing the effort undertaken to meet the itineraries of the vehicle, considering its work periodicity.

As for the sanitary agents, practical experience demonstrates that they account for a significant portion of the operational cost and the effectiveness of the combat process. Groups of agents are formed to act in a certain area and, during the visiting cycle, which often consist of 35-45 working days (3 to 4 months cycle), for the focal agent, the entire city must be covered, real estate unit by real estate unit. Work distribution among agents is done superficially, although the managers keep a record of all blocks and places that are difficult to reach by manually drawn maps. SVS indicators are relevant for the teams in respect to coverage of real estate units, and those real estate unit pending (real estate units that have not been visited because they are closed or because the occupant, for any reason, didn’t allow the agent to visit it) must be covered within the cycle, since this is a major indicator for work quality within a period.

The work of the agents is our greatest preliminary concern. The task of assigning them and distributing them among the real estate units is acknowledged as being a difficult task for the Manager of the Center. Next, we report three models that are pertinent to the distribution of the daily service load of the sanitary agent, and one model related to the assignment of the spraying vehicles to service areas.

4.1. The planning process for the sanitary agents’ task

For planning the coverage of the sanitary agents task, districting models were used by extending clustering methods as in classical districting approaches, (Garfinkel & Nemhauser, 1970), (Blais et al, 2003), (Zhong et al 2007). The clustering methods can be treated in the following way:

Let S be the set of real estate units or city blocks to be visited, S = { s ₁ ,..., s _m }, where s _j ∈ R², j =1,...,m. The objective of this first model is to partition S into no empty q disjointed subsets S _i, i = 1,..., q, [1], in such a way as to divide the operations of planning and control of the activities to combat dengue,

$$\begin{array}{l}S={\displaystyle \underset{i=1}{\overset{q}{\cup }}{S}_i},\\ S_i{\displaystyle \cap S_k=\varnothing ,}\\ i=1,\mathrm{...},q,k\ne i\end{array}$$ E1

It is, therefore, a classical clustering problem treated by several publications in the bibliography, for example (Hartingan 75), (Spath 85), (Hansen & Jaumard, 1997), (Kaufmann & Rousseauw, 1990) and more recently (Everitt et al 2001), (Theodorides and Koutrambas, 2003).

Each subset S _i can be represented by its centroid or center of gravity,

$$x_i=\frac{1}{\left|S_i\right|}{\displaystyle \sum _{j\in S_i}{S}_j}$$ E2

where | S _i | is the cardinality of subset S _i, i = 1,..., q.

The most traditional formulation of the clustering problem can be represented by the following optimization problem, (Min-sum Clustering)

$$\text{minimize}{\displaystyle \sum _{i=1}^q}{\displaystyle \sum _{j\in S_i}^{}\parallel }{s}_j-x_i{\parallel }^2$$ E3

such that X = { x₁,..., x_q } and x_i ∈ R², i = 1,..., q.

The problem [3] above is known as the clustering one, according to the criterion of the minimum sum of squares. This problem is often presented in the following alternative format,

$$\underset{x}{\text{minimize}}{\displaystyle \sum _{j=1}^m{d}_j^2}(x)$$ E4

such that $d_j(x)={\min }_i\parallel s_j-x_i\parallel$

It is thus a non-linear problem, with a set of constraints that are intrinsically non-differentiable. Within the scope of the project, a new method was developed for the solution that turns it into the solution of a sequence of problems that are completely differentiable, (Xavier, 2005), the so-called Hyperbolic Smoothing Method (HSM), which found out high quality solutions for the clustering over the set of blocks’ centroid of the city of Sobral.

Figure 7 shows the result for a set of 11 distinct groups from 13280 city blocks (Sobral), (Xavier, 2005).

Other clustering methods exist, between the exact and heuristic ones, the most used are the heuristics as: Forgy, k-Means, j-Means, c-Means, and many other variations, (Forgy 1965), (Hansen & Mladenovic, 2001), (Theodoridis & Koutroumbas, 2003), (Negreiros & Palhano, 2006). To have an idea about the performance of the HSM, table 1 shows the clustering results obtained for different number of groups (q=8,..,11), over the Sobral instance. In the table, we have:

f_HSC, is the cost of the objective function for the HSM ;

f_j-means, is the cost obtained by the j-means method, (Hansen & Mladenovic, 2001);

Time_HSC, is the time (in seconds) for the HSM;

Time_j-means, is the time (in seconds) for the j-means method.

$$E=\frac{100\left(f_{j-means}\right)}{f_{j-means}}$$ , is the gap to the method j-means, and

Figure 7.

Result from a clustering of 13260 centroides of blocks, of the city of Sobral/CE, after applying the HSM.

$$Ratio=\frac{Tim{e}_{HSC}}{Tim{e}_{j-means}}$$ , is the computational time between the HSM and j-means, in a PC-Atlhon 0.5GHz, 0.5Gb RAM.

The results on Table 1 reveal the superior quality of the HSM in consideration to one of the state of the art OR methodologies reported, (Xavier, 2010), (Xavier & Xavier, 2011).

Q		TimeHSC (s)		Timej-means (s)	E	Ratio
8	0.40663x1010	95.55	0.40674 x10^10	2220.61	-0.03	0.0430
9	0.35783 x10^10	78.11	0.38988 x10^10	18.08	-8.22	4.3202
10	0.31477 x10^10	127.89	0.56343 x10^10	2259.02	-44.13	0.0566
11	0.27637 x10^10	107.08	0.27637 x10^10	26142.94	0.00	0.0041

Table 1.

Results for the instance of the city of Sobral/CE

Among the alternative approaches directly related to covering planning problem of sanitary agents, two are directly extracted from solutions to clustering problems with capacity constraints: traps placement and coverage division of city by group of agents.

4.1.1. Traps placement

The increase of Aedes aegypti mosquitoes on the urban space constitutes an important hole for the dengue propagation. The permanent estimation of mosquito population densities is fundamental information for prevention of the disease.

Different types of traps were developed by Brazilian biologists, which are used in the context of prevention the Aedes aegypti expansion. There are traps whose types are to capture the adult mosquito (female) - Mosquitrap, others to capture grubs and eggs (Ovitraps) and others the female mosquito, and its grubs and eggs, Figure 8.

Figure 8.

Different types of traps developed by Brazilian biologists, Mosquitrap (left) – to capture adult female, by Álvaro Eiras and Mosquitérica (right) – to capture grubs and eggs, by Maulori Cabral.

The use of traps for capturing dengue vectors is a universal strategy for such proposes, therefore the traps placement problem appears, once the cost of some of these apparatus are related to the number installed in square area of the field. Three major approaches that may appear: the first can define the placement of the traps considering its coverage in a given radius throughout the blocks of the boroughs, and one wishes to cover all the area by using the least number of traps; a second approach consider the placement of the traps by introducing the spatial distribution (position) of the buildings and it is desired to obtain the least number of sets of buildings where in each set the trap will be located at the center of the group; and finally a third approach the placement of the traps must be positioned in one building of each set of buildings defined.

To equate the first strategy it was adopted a formulation considering a plane region covering by equal circles, since the mosquitoes have a limited circular range, (Xavier & Oliveira, 2005), (Brito & Xavier, 2006).

Let S be a finite region in a plane. A set of q circles, C _i, i=1,…,q, constitutes a covering of S, if each point in S belongs to at least one circle. The core focus of the adopted approach is the smoothing of the min-max-min problem engendered by the modeling of the covering problem.

Let x _i , i=1,…,q be the centers of the circles. The set of these centers coordinates is represented by X ⊂ R ^2q. Given a point s∈S, we initially calculate the distance from s to the center in X that is the nearest. This is given by:

$$d\left(s,x\right)=\underset{x_i\in X}{\min }{\Vert s-x_i\Vert }_2$$ E5

A measurement of the quality of a covering of domain S by the q circles is, of course, provided by the largest distance d(s,X), which corresponds exactly to the most critical covering of a point. The optimal position of the centers must provide the best-quality covering for the region S, that is, it must minimize the most critical covering. If X ^* denotes an optimal placement, then we have the problem:

$$X^{*}=\underset{X\in {\Re }^{2q}}{\arg \min }\underset{s\in S}{\max }\underset{x_i\in X}{\min }{\Vert s-x_i\Vert }_2$$ E6

In order to solve the above problem numerically, we first discretize the domain S into a finite set of m points, s _j , j=1,…,m thus obtaining the following model (TPP1): (TPP1) minimize z subject to

$$\begin{array}{l}{z}_j=\underset{i=1,\mathrm{...},q}{\min }{\Vert s_j-x_i\Vert }_2,\\ j=1,\mathrm{...},m,\end{array}$$ E7

$$z\ge z_j,j=1,\mathrm{...},m$$ E8

Let φ(y) denote max(0,y). By using a ε perturbation, it is derived the problem (TPP2): (TPP2) minimize z subject to

$$\begin{array}{l}{\displaystyle \sum _{i=1}^q\phi }\left(z_j-{\Vert s_j-x_i\Vert }_2\right)\ge \epsilon ,\\ j=1,\mathrm{...},m,\end{array}$$ E9

$$z\ge z_j,j=1,\mathrm{...},m$$ E10

For overcoming the extremely rigid non-differentiable structure, the function φ(y) is replaced by the hyperbolic function $$\varphi$$ (y,τ)=(y+(y²+τ²)^1/2)/2 approximation, which can be replaced in the model (TPP2) by (TPP3) as: (TPP3) minimize z subject to

$${\displaystyle \sum _{i=1}^q\varphi }\left(z_j-{\Vert s_j-x_i\Vert }_2,\tau \right)\ge \epsilon ,j=1,\mathrm{...},m$$ E11

$$z\ge z_j,j=1,\mathrm{...},m$$ E12

The solution to the equivalent covering problem (TPP3) is obtained by resolving an infinite sequence of the last problems obtained by a gradual decreasing of both parameters ε andτ. Figure 9a shows the process of placing the traps for a coverage of approximately 150m in the boroughs of Dionísio Torres (64 traps) and Praia de Iracema (64 traps) and it indicates the shortest expanses for this type of trap placement.

Figure 9a.

Placement of traps for the boroughs of Dionísio Torres (64 traps) – above, and Praia de Iracema (64 traps) – below, by using the hyperbolic smoothing technique.

The trap placement problem can also be solved by min-sum-of-square clustering problem (second strategy), if the placement must be introduced in the center of sets of buildings, for a defined maximum number of traps. In this case it is an input the position of the real estate units which are the items to be clustered. As third strategy one can use the classical Euclidean p-medians problem to precede the coverage. In this case, the median will be the place (building/real estate) where the trap must be located. The classical p-median model can be stated as follows, (Daskin, 1995). Consider:

Sets:

$$V\text{ - is the set of real estate unit, ||V|| }=n$$ E13

$$J\text{ - is the set centers, 1}\le \text{ ||}J\left|\right|\le p\text{;}$$ E14

$$p-\text{ is the number of medians or centers}\text{.}$$ E15

Parameter:

$$d_{ij}-\text{ is the distance between real estate }i\text{and }j\text{ in the euclidean space }{\Re }^2;$$ E16

Variables:

$$x_j-\text{ is the vertex center of median }j\text{;}$$ E17

$$y_{ij}=\{{}_{\text{0, otherwise;}}^{\text{1, if a real estate unit }i\text{ is assingned to median }j,}$$ E18

$$(p-\text{Median})\text{ minimize}{\displaystyle \sum _i{\displaystyle \sum _j{d}_{ij}{y}_{ij}}}$$ E19

$$\text{subject to}{\displaystyle \sum _j{y}_{ij}=1}\forall i\in V$$ E20

$${\displaystyle \sum _j{x}_j=p}$$ E21

$$y_{ij}\le x_j\forall i\in V,\forall j\in V$$ E22

$$y_{ij}\in \left\{0,1\right\}\forall i\in V,\forall j\in V$$ E23

$$x_j\in \left\{0,1\right\}\forall j\in V$$ E24

In the classic p-median model, [13] defines the minimum cost to assign medians of real estate’s to their real estates, [14] indicates the assignment of only one median to a real estate, [15] defines the number of medians to be assigned, [16] indicates that if an assignment of a real estate to its related median is used it must be at most equal to the fixed median, [17] and [18] indicates the used binary variables, (Daskin, 1995).

Figures 9b and 9c show the two techniques (clustering in Figure 9b, and p-median for Figure 9c) employed for the same set of points for the city of Fortaleza in the boroughs of Dionísio Torres and São João do Tauape, both considering an area of a large number or real estates. A set of methods from Xavier (2008) for the min-sum-clustering and also for the p-median as described in Daskin (1995), Taillard (2003) and others could be used to solve instances of that size within 15 seconds in a PC.

Figure 9b.

Placement of traps in a borough of Dionisio Torres described by its limits and the spatial distribution of the 3947 real estate units (top), by using a min-sum-of-square clustering method (middle, Error=14,707,808.02) or an Euclidean p-median method (bottom, Error: 16,444,592.42) for placing 64 traps each.

4.1.2. Coverage division of the city by the groups of agents with capacity constraints

Such a vision must be done in such a manner that each partition be covered by the same group throughout the visiting cycle. Here there is a problem of Constrained Clustering, which can be solved by means of the Capacitated Centred Clustering Problem. The division of work among the agents will be done according to the quantity of real estate units per agent per cycle, and also taking into account a lower and an upper limit of service within the area (18-22 real estate units per agent per day, groups with 4 agents, and a calendar with 42 working days in the cycle, for example, would thus mean regions with 3024-3696 real estate units for this cycle). Figure 9 shows a solution to the problem – the process of distributing the area coverage among the agents is done with an adaptation of the technique proposed by Negreiros & Palhano (2006), which is already incorporated into the Manager system.

Sets:

$$I\text{ - is the set of real estate unit, ||I|| }=n$$ E25

$$J\text{ - is the set of possible clusters, 1}\le \text{ ||}J\left|\right|\le n\text{;}$$ E26

$$F-\text{ is the fixed cost to open a cluster}\text{.}$$ E27

Figure 9c.

Placement of traps in a borough Sao Joao do Tauape described by its limits and the spatial distribution of the 6950 real estate units (top), by using a min-sum-of-square clustering method (middle) or an Euclidean p-median method (bottom) for placing 64 traps each.

Parameters:

$$s_i-\text{ is the position of the real estate unit }i\text{ in the euclidean space }{\Re }^2;$$ E28

$${\underset{\_}{Q}}_j-\text{ is the minimum capacity of cluster }j\text{;}$$ E29

$${\overline{Q}}_j-\text{ is the maximum capacity of cluster }j\text{;}$$ E30

Variables:

$$z_j=\{{}_{\text{0, otherwise;}}^{\text{1, if a cluster }j\text{ is open,}}$$ E31

$${\overline{x}}_j-\text{ is the geometric center of cluster }j\text{;}$$ E32

$$y_{ij}=\{{}_{\text{0, otherwise;}}^{\text{1, if a real estate unit }i\text{ is assingned to cluster }j,}$$ E33

Model of the General Capacitated Centred Clustering Problem:

$$\text{(g- PACCG) Minimize (F }{\displaystyle \sum _{j\in J}^{}{z}_j})+{\displaystyle \sum _{j\in J}^{}}({\displaystyle \sum _{i\in I}^{}\left|\right|s_i-\overline{x_j}|{|}^2{y}_{ij}})$$ E34

Such that,

$${\displaystyle \sum _{j\in J}^{}{y}_{ij}}=1,\forall i\in I$$ E35

$${\displaystyle \sum _{i\in I}}{s}_i{y}_{ij}={\overline{x}}_j\left({\displaystyle \sum _{i\in I}^{}{y}_{ij}}\right),\forall j\in J$$ E36

$${\underset{\_}{Q}}_j{z}_j\le {\displaystyle \sum _{i\in I}^{}{y}_{ij}}\le {\overline{Q}}_j{z}_j,\forall j\in J$$ E37

$${\overline{x}}_j\in {\Re }^2\text{, }{z}_j,y_{ij}\in \{0,1\},\forall i\in I,\forall j\in J$$ E38

In the model (g-PACCG), the objective function aims to minimize the number of real estate unit groups to be visited and the sum of the dissimilarities of each of these clusters, [19]. A real estate unit can only be assigned to a single cluster, in the set of constraints [20]. In the constraints [21], we have the guarantee of the location of the center of each cluster at its geometrical center. The constraints [22] take into account the maintenance of the demand of individuals limited to the capacity of each specific cluster, and the constraints [23] specify the decision.

This is called the General Capacitated Centered Clustering Problem. The formulation above shows that it can only be reduced to a NP-Complete equivalent problem, which is the Min-Sum Clustering (MSCP) problem itself, (Garey & Johnson 1979).

The set of methodologies used for this problem consider a GRASP based type framework, where a multi-start greedy constrained (capacitated) clustering method followed by the improvement procedure (VNS), is used to find the solutions, (Mladenovic & Hansen 1997), (Feo & Resende, 1995).

The method has an unconstrained (static) phase and a constrained (multi-start, greedy). In the first step we develop the unconstrained clustering by HMS method. The second, actually the GRASP phase, we perform evaluations to hold the capacity constraints by different constructive strategies, differing in some sense from the original methodologies proposed by (Negreiros & Palhano, 2006). These methodologies consider the shape of the clusters built and also their capacity limits, exploring constructive Euclidean minimum spanning tree and Delaunay triangulation proximities, as the convex hull of the groups formed, to treat feasibility. The best configuration is then selected to be the solution, after a VNS improvement step, (Preparata & Shamos 1985).

The quality of the meta-heuristic proposed is suited to performance ratio and shape of the clusters, otherwise if the solution does not convince the manager, he/she can interfere directly in the result (as it is a spatial DSS), moving a set of real estate units or blocks from one cluster to another, and see the effect of the movement.

Figure 10.

Formation of real estate unit block clusters in the city of Sobral/CE, first phase of allocation and service division, using a proposed solution for the problem of Capacitated Centred Clustering Problem.

In order to solve the problem of territorial coverage division for the focal sanitary agent, we first run a method of generic restricted clustering, for the creation of the coverage areas of the agent groups (for example areas with 3024-3696 real estate units), and then for each area we generate the daily clusters (18-22 real estate units). The contrary can also be done. For each daily group we then generate a visiting list within the real estate units of the group, taking a traveling salesman`s path between two extremes of the group. Also, the same can be done if the travel is considered between street blocks. Figure 11 presents this methodological reality.

Figure 11.

Itinerary of a sanitary agent in subsequent days, among real estate units of a certain coverage area (cluster) after the restrictive clustering process in a certain area (generating sub-clusters).

This same methodology was used to design coverage areas and routes for the SP (special points) sanitary agents. The SPs are distributed into (Regional II), and first we cluster a number of agents and than make the routes between the SP’s. An agent that travels between different boroughs has to complete one borough at a time, as in the Clustered Travelling Salesman Problem, (Prunner, 2002). Figure 12, shows the results of this application in the city of Fortaleza.

Figure 12.

Itinerary of a Sanitary SP’s agent for a cycle of 15 working days in one borough (up) and 3 between boroughs (down), (Manager System)

4.1.3. Division of the agents work in the coverage areas

In this phase, using the previous example, since the agents have 42 working days within the area which is defined for their group, only 72-88 real estate units are visited per day, and the coverage of the entire city is slow and arduous. In this case, our interest is to distribute the agents by “macro-region” (clusters), in such a way that the (ideally) a representative sample of the total coverage of the city is explored each day. That is, the daily samples (sub-clusters) will present the picture of the city in regard to focuses. In this case, for our approach we consider that the agents must be closer to one another among distinct cluster while being as far apart as possible within the same cluster, though in the following days they must take real estate units that are the closest to the ones visited in the previous day.

This problem is related to a situation which seems to be multi-objective, with a dynamic coverage component. The expected model takes into account a process of dynamic localization that has been studied by many researchers and that has been reported in a recent survey about strategic location, (Owen & Drezner 1998).

To better illustrate how this may be done, Figures 13 presents a division of the agents’ work for the city of Sobral/CE, real estate unit by real estate unit, for a defined area (cluster), though it must be taken into account that the work of the agents acting in this area could be the most disperse among them, at the same time that the following day it would be undertaken in groups of real estate units (18-22) located in the neighborhood of those that the agent visited on the previous day. For that neighborhood to be obtained, one can use Delaunay triangulation methods, in which the centers of the daily real estate unit groups would be taken as being those of the displacement assessment (Preparata & Shamos 1985).

We will call this problem the Sanitary Agent Coverage Assignment Problem (SACAP). A preliminary {0,1} formulation for this problem may be considered as follows:

Sets:

$$a_c\text{ - each cluster }c{\text{ has a set of a}}_{\text{c}}\text{ sub-clusters;}$$ E39

$$C\text{ - is the set of Clusters (areas to be covered);}$$ E40

$$N(i)-\text{ are neighbour sub-clusters of sub-cluster }i\text{;}$$ E41

Parameters:

$$d_{ij}-\text{ is the distance between two agents }i\text{ and }j;$$ E42

$$H-\text{ is the horizon in working days;}$$ E43

$$M-\text{is a great number};$$ E44

Variables:

$$t_k-\text{ is the minimum distance between two agents in day }k;$$ E45

$$x_{lj}^k=\{{}_{0,\text{ otherwise}.}^{\text{1, if the agent }l\text{ visits the sub-cluster }j\text{ in day }k\text{;}}$$ E46

Model of Sanitary Agent Coverage Assignment Problem (SACAP):

$$\text{(SACAP) Maximize (}{\displaystyle \sum _{k=1}^H{t}_k})$$ E47

Such that,

$$t_k^{}\le d_{ij}+M\max (1-x_{li}^k,1-x_{l´j}^k),\forall k,\forall i,\forall j,\forall l,\forall l´;$$ E48

$${\displaystyle \sum _{l\in a_c}}{\displaystyle \sum _{k=1}^H{x}_{lj}^k}=1,\forall j\in C,\forall c\in C$$ E49

$${\displaystyle \sum _{j\in C}^{}}{x}_{lj}^k\le 1,\forall k,\forall l=1,\mathrm{...},a_c,\forall c\in C$$ E50

$$x_{lj}^k+{\displaystyle \sum _{j\notin N(i)}^{}}{x}_{lj}^{k+1}\le 1,\forall k,\forall l,\forall j$$ E51

$$t_k\ge 0,x_{lj}^k\in \{0,1\},\forall k,\forall l,\forall j$$ E52

In the model (SACAP), the objective function [24] searches to maximize the sum of the minimum displacement distances between two days in a row of the coverage period undertaken by the sanitary agents. The constraints [25] consider t _k as the shortest distance that separates two visited sub-clusters (real estate units of a visiting day). In the constraints [26], each sub-cluster of each cluster must be visited by an agent of the cluster. In [27] the constraints indicate that each agent of cluster c can only visit a sub-cluster from c. The constraints [28] consider that within a visiting period the visit to neighbor sub-clusters is only permitted on the following day. The constraints [29] consider the decision variables of the model, being the one that expresses the real distance and the binary allocation distance.

Other objective functions can be considered, such as in equations [30] and [31] below:

$$\text{(SACAP-1) Maximize}{\displaystyle \sum _{k=1}^H{(t_k)}^{\frac{1}{2}}}$$ E53

or in the same way,

$$\text{(SACAP-2) Maximize Min}{t}_k$$ E54

The SACAP model although designed to real estate units, a group of real state units belonging to the same block can define a block to be covered by an agent. The same model can be stated taking into account the blocks of the cities, since each block can be covered in less than a day of visit.

For this problem, by addressing blocks, a set of greedy heuristics were implemented based on clustering and routing, in dynamic context. The means of the heuristic developed is to keep track of the groups while the agents are as far as possible and moving in a route between neighbor blocks at his assigned area. The triangulation phase defines the neighbor of the blocks, and it is done by the Delaunay triangulation and an extension for treating the shape and elongated blocks, that the triangulation (algorithm for points) does not match as real neighbor of polygons in plane. In the second phase, we design the clusters and then the dynamic routes, (Serghine, 2006).

Figure 13.

Division of the labor using the Manager system, by means of the SACAP model. A) Division of the visits made by a group of agents in a defined service area for the group. B) Accurate visualization of the coverage of the agents and of the visits of a group in the area defined in Figure 13(a).

A test for a number of 10 boroughs for the Regional II– Fortaleza/CE, was done. Figure 14 shows the result of one of these instances considered. Although Figure 15 is a static view of the final solution, it can be seen that the neighborhood of the blocks was avoided in the routes by the heuristic, once it can not find feasible solutions for this instance of the SACAP. In fact, as the supervisor of Regional II considered, “it is not so important that this constraint may be fully satisfied”. Although, considering the related districting solution found, “gerrymandering” (elongated clusters) is not avoided, and for him “must be” avoided, the use of other criteria in the objective function as shape of the cluster, as overlapping of the shapes, and others, can be also addressed here as in districting problems, (Garfinkel & Nemhauser, 1970), (Blais et al 2003). Much research work must be done here, for this interesting problem.

Figure 14.

Neighbor graph associated to the blocks of the borough Dionísio Torres/Fortaleza-CE.

Figure 15.

A dynamic path and clustering for the borough of Dionísio Torres/Fortaleza-CE, instance with 20 agents in 12 working days

4.2. The planning process of spraying vehicles

Two models can be considered for scheduling spraying vehicles, periodical task scheduling and routing. The routing model over street networks is not considered once it was not applied in the field, although one can report to the Mixed Capacitated Arc Routing literature, for this approach. These models are related to situations where it is necessary to combat the mosquitoes in their adult phase, (Eiselt et al 1995), (Belenguer et al, 2006).

The problem of designing periodical visit to areas by spraying vehicles is inserted in a dynamic planning of the risk areas coverage, starting from the identified or the reported cases, or from a statistical knowledge of the expansionist behavior of the mosquito in the region. This methodology is often used when we are dealing with the problem of division of service among spraying vehicles that undertake the task during periods of epidemic outbreaks. Since the fleet of such equipment is limited, they are critically needed in this important moment. Moreover, in order to cover urban regions within metropolis or even in medium-sized cities, many coverage areas are necessary, as well as many vehicles to deal with the problem.

The phase of dimensioning the service sectors, either for the agents, or for the spraying vehicles, is undertaken before the scheduling phase, according to the following model. In that model, there is a guarantee that the service is dimensioned for a certain time period or a total service load (number of blocks to be served per day).

The planning problem is inserted within a context of problems for scheduling of periodical tasks, where there is a set of tasks to be undertaken in certain defined areas, at certain times (in the dengue case, for the spraying vehicle, from 5:00 A.M. to 7:00 A.M. and from 5:00 P.M. to 7:00 P.M., and for the agents directly in the residences and businesses, during the morning and the afternoon) and in a certain minimum and maximum service periodicity (intervals between two services). The periodical scheduling of tasks problem is NP-Hard, and it is a problem with few related studies, (Verhaegh et al 1998), (Baptist et al 2001). For the specific case, we can use a mathematical formulation, in the following way:

Premises: 1 area / 1 vehicle / 1 day, or one vehicle serves one area totally in one day

We want to undertake the scheduling task so as to minimize the fleet used, which must cover all areas over the minimum and the maximum stipulated periodicity need.

Sets:

H-is the planning horizon in subsequent days;

A-the set of areas to be covered;

Parameters:

LI(a)-inferior range over the number of days between two visits in area a;

LS(a)-superior range over the number of days between two visits in area a;

Variables:

$$x_{ia}^k=\{{}_{0,\text{ otherwise}}^{\text{1, if vehicle }i\text{ visits an area }a\text{in day }k\text{ ;}}$$ E55

$$z_a^k=\{{}_{0,\text{ otherwise}}^{\text{1, if an area }a\text{is visited in day }k\text{;}}$$ E56

$$y_i=\{{}_{0,\text{otherwise}.}^{\text{1, if vehicle }i\text{ is used;}}$$ E57

Periodical Scheduling of Vehicles in Areas Model (PSVA):

$$\text{(PSVA) Minimize (}{\displaystyle \sum _{i=1}^K{y}_i})$$ E58

Such that,

$${\displaystyle \sum _{i=1}^{LS(a)}{z}_a^k}\ge 1,\forall a;$$ E59

$$z_a^k={\displaystyle \sum _{i=1}^K{x}_{ia}^k},\forall a,\forall k$$ E60

$$z_a^k\le {\displaystyle \sum _{s=LI(a)}^{LS(a)}{z}_a^{k+s}},\forall a,\forall k=1,\mathrm{...},H-LS(a)$$ E61

$${\displaystyle \sum _{a=1}^A{x}_{ia}^k}\le y_i,\forall i,\forall k$$ E62

$$y_i{\text{ , z}}_{\text{a}}^{\text{k}}\text{ , }{x}_{ia}^k\in \{0,1\},\forall i,a,k$$ E63

In the model of Periodical Scheduling of Vehicles in Areas (PSVA), the objective function [32] searches to minimize the number of vehicles of the allocated fleet in the period. The constraints [33] consider that each area must be visited within the first LS(a) days. The constraints [34] establish a link between variables z and x. The constraints [35] consider that one must go back to each area, between LI(a) and LS(a) days after a visit. The constraints [36] consider that only one vehicle visits no more than one area per day. And finally, the constraints [37] present the decision variables of the Periodical Scheduling model.

We evaluated short instances of this problem using CPLEX. For the framework, we implemented a multi-start greedy heuristic to find solutions for real large instances. The heuristic contains a greedy construction phase which orders the major areas and also the minimum periodicity in a list of candidates. After that, for each randomly selected area from the list (or part of it), a feasible path is built. If a feasible path cannot be built, the process starts again. A number of tests were made with the multi-start greedy solution that returns good quality in comparison to optimal results for the situation where the areas have the same limits between two visits, (Negreiros et al 2001), (Coutinho 2003).

Most recently, Michelon et al (2008) present some general properties of the problem, an integer programming formulation for which they give the optimal solution of the linear relaxation, a trivial lower bound which is compared to the linear relaxation bound and a new greedy heuristic, (Michelon, Quadri, Negreiros, 2008).

4.3. Design the itinerary of spraying vehicles

Once the service areas are defined and the service of scheduling the agents is done, there is also the phase of establishing the service itinerary of the spraying vehicles, in such a way as to facilitate the work of the manager in the task of serving the population in epidemic situations. In this phase, we use models that are based on the Rural Postman Problem (RPP), in which it is guaranteed that the service will be accomplished with the passing of the spraying vehicle by all the blocks where its service has been requested, with the lowest cost in the itinerary, (Eiselt el al 1995), (Negreiros 1996), (Corberán et al 2000).

This problem actually relates to the minimization of the spending of insecticides and with the duration of the itinerary, besides the guarantee as to the complete coverage of the affected areas, since the spraying vehicles turn on the pulverizing pumps as soon as they enter the service areas, turning them off only when the task in each sector is concluded. The expense reduction would be reasonable, starting with a better elaboration of the itineraries, and, furthermore, the defined sectors would have a quicker service, (Negreiros 1996).

Since the itinerary of the rural postman is limited beyond the specific area, as well as to the quantity of insecticide present in the environment, there is the Constrained Itinerary using the Capacitated Arc Routing problem (CARP), initially proposed by Golden & Wong (1981) though taking into account, furthermore, the specific orientation in the routes for the passing of the spraying vehicle, considering that the pulverizing nozzle of the insecticide is fixed and is located at the right side. Once the network is mixed, it is worth to consider the techniques for the Mixed Capacitated Arc Routing Problem (MCARP), or the General Routing Problem (GRP), as in (Negreiros 1996), (Belenguer et al 2006).

For this problem, the basic ideas from the algorithm produced proposed by Negreiros (1996) are used, in a GRASP variation of a multi-start greedy mixed capacitated general routing heuristic and an improvement procedure for each route using a mixed rural postman problem approach, designed by Coutinho (2003). These procedures are before used for the garbage collection, and obtain high quality solutions also for the case of dengue combat. This problem fortunately was not evaluated on field, since there was no epidemic situation in the evaluation time.

Figures from 16 to 18 below show some of the visualizations of the output results of this model, to adequately organize the work of planning the logistics for the dengue prevention. Figure 16 shows a division process, for example, of region 02 in 4 sub-areas, with a capacity limited to 2000 liters of poison. In Figure 17, the service schedules of the area presume a fixed working program, in established days, with maximum service periodicity within the mosquito cycle and the thematic itinerary for servicing the area, where we can visualize a resulting multi-graph, with the possible itinerary that can be made by the spraying vehicle or by the health agent. Finally, in Figure 18, there is the problem of movement of the spraying vehicle, considering that the pulverizing nozzle will always be oriented towards the front of the residences, (Negreiros et al 2001).

The strong integration between the problems of coverage by the sanitary agents and by the spraying vehicles of the regions infested with larvae of the Aedes aegypti mosquito, their scheduling into periods and the distribution of the door-to-door service requires specific studies about the effectiveness of optimization methods that serve well he desires of the manager – optimization of costs, serving its needs in a rational way. We have been applying methodologies that we have developed that have been able to approach the problem of prevention and combat of dengue with a high level of reliability for the manager of the Zoonoses center, (Negreiros, 1996), (Negreiros et al 2001), (Coutinho, 2003), (Negreiros & Palhano, 2006).

Figure 16.

Division of areas and sub-areas where the spraying vehicles work per day.

Figure 17.

Proposed form for service calendar in a given area and corresponding multi-graph itinerary.

Figure 18.

View of the orientation graph of the spraying vehicle itinerary in an area (Praia de Iracema, Fortaleza) and its related RPP multi-graph solution where the tour of spraying is always pointing to the inner-center of the block or the right side of the vehicle (opposite side of the driver sit).

5. Statistical models for the prevention and combat of dengue

The use of statistical models for tracking the evolution of dengue is very frequent by the municipalities in Brazil and worldwide. General forecasts are considered in advance for prevention proposes but mostly in Brazilian cities they are disaggregated and processed by different institutions. Tracking the evolution of the disease is another important tool, but mostly not used. The integration of the forecasts and tracking methodologies to follow the disease is crucial. Decision makers may use these tools in an integrated environment to help focusing in the directions of the process.

In the following subsections we consider these problems, and ways to forecast and track the evolution of dengue for prevention proposes.

5.1. Forecasting Aedes aegypti presence

A usual technique for prevention is following dengue expansion by forecasting techniques over the evolution of the number of human cases. It is well known by health managers that the cycles of dengue in tropical areas have periodical meanings. The resurgence of the disease was followed by researchers. In Rio de Janeiro, the impact of the cyclic causes pandemics in periods of 5 to 7 years, as can be seen in the plots studied by Amaral, Voughon, Duarte (2009), Figure 19.

Figure 19.

Pandemias of Dengue in Rio de Janeiro (2002 and 2008)

Using the actual Data Bases as SQL-Server, PostGre or Oracle, the data can be stored conveniently by territory and periods. A number of techniques may be used for that, although there are many forecast methods, the selection of the most adequate to ensure and help the health manager is an important result. Freire, Xavier and Negreiros (2007) developed a procedure to automatic detect the best forecast from four classical forecasting methods: Random Walk, ARIMA, Holt-Winters and Neural Nets, and selecting the best of them by using a Kohonen Neural Net score classifier (Table 2). In Figure 20 it is shown the forecasts plotted by using the statistical software R, and the minimum-square-error (score) obtained for each forecast, in relation to the real result obtained for the period of the forecast. The data used were obtained from the information given by the municipality of Fortaleza from the years of 2002-2005.

Table 2.

Visualization of the forecasts by neural net vs desirable selection

This methodology was implemented in the system Webdengue, for forecasting boroughs, regions and city. This tool considers the information obtained from previous years which are stored in its data base. The best score obtained by the KHNN is then plotted to the user for evaluation and decision.

Figure 20.

MSE results obtained by evaluating the ranks (scores) using Kohonen Neural Net of different classical forecasting methods.

5.2. Tracking colony of Aedes aegypti or human cases by natural clusters methods

A number of works recently developing for dengue prevention, in Mexico and Singapore, are using internet to show where the human cases are for a specified period of evaluation. In Mexico, the project considers the use of the Google Earth^TM technology to track the Aedes presence, also including Decision Support System designed to follow data warehouse where management tools, plots, statistics and mapping visualization are delivered to detect in block the Aedes presence. In Singapore, thematic digital maps are generated which are more emphatic in delivering to the user precise information of places where the human cases occur to the population thought web maps and charts of evolution. Both technologies have their impact, in visualization and decision support, joining both are very useful and we consider in the Webdengue project the join of these processes tools to help health managers to track dengue, (Lozano-Fuentes et al 2008), (Eisen & Beaty 2008), (Lozano-Fuentes & Eisen 2009).

The city of Singapore, considers the importance of advising people by internet where the cases of dengue are in the last week. They publish weekly the principal groups formed by at least 3 human cases and define the center of the group as the potential area where dengue exists, and where the population have to take care of being infected by Aedes. Figure 21a shows the basic follow up in Singapore by internet, and Figure 21b shows both ideas integrated in the Webdengue environment also in the web.

Figure 21a.

Last week clusters of human cases in Singapore and evolution of the number of human cases published by the city of Singapore in the web.

Figure 21b.

Integrating visualizations between digital thematic mapping and Google Earth mapping systems in Webdengue for the city of Rio de Janeiro.

To model the Singapore strategy of defining these clusters, let be G a symmetric weighted graph G(V,E) generated from the vertices (points) defined by the set of spatial coordinates focus of Aedes or human cases identified in a certain period of time. Let define G(V,E) as a neighbor graph, where the set of edges are defined by e _ij ∈E, $$\forall$$ i,j ∈V, then equation define the neighbor graph:

$$e_{ij}^{}=\{{}_{0,\text{otherwise}}^{1,d_{ij}Max\text{{}{d}_{ik},d_{kj}\text{}},\forall i,j,k\in V}$$ E64

Figure 22.

Formation of clusters by defined distance (p.ex. 250m between human cases), Singapure strategy, the aggregation is considered if d _ij ≤ 250 and the resulting components of G(V,E) are of more than 3 vertices.

Figure 22 illustrates the use of neighbor graph to find groups of human cases. Although the technique used by the city of Singapore is very useful, it may obtain results that cannot incorporate to the set of clusters of vertices that are a bit far than the specified parameter, or even groups that are formed with distance between vertices a bit more far from the specified greater distance. To define the natural clusters, without distance parameter, but by an aggregation parameter (minimum number of elements that defines a cluster) we used the IGN method, by Negreiros, Xavier and Roldan (2005), that considers by hierarchical clustering the formation of the clusters using horizontal and or vertical cuts automatically processed in the related dendrogram, Figure 23.

Figure 23.

Dendrogram of the Euclidean graph at left, and the cutting curve for automatic selection of the aggregation of individuals (focus or human cases).

IGN can find easily the number of clusters without parameters, if the aggregations are well defined. If not, one may consider the use of neighbor graph to accomplish the disease.

6. Discussion

Decision Support Systems have been designed to epidemic and entomological control of dengue disease. Groups of researchers perform an important issue in this direction, but it is considerably difficult to implement management decision tools once the control operation of the Aedes varies widely from country to country.

This work shows the situation in Brazil, where there are two important forces that work for dengue. A preliminary force works in the direction of the mosquito hunting, by using vehicles and human force (agents) to verify real estate by real estate units the Aedes’ eggs, grubs and the adult mosquito. The second force uses the health system to attend the disease in humans, in its variety of forms and complications. The health manager is not a unique person it is formed of a number of persons all responsible to manage both sides of the process.

This work shows a framework of computational systems (Webdengue) that was tested and/or evaluated in three different Brazilian cities: Sobral, Fortaleza and Rio de Janeiro. Each test, revealed the necessity of including a number of tools (graphs, maps, charts, data base management system, GPS, hand-helds, statistics and optimization models) which consider state-of-the-art as classical methods for supporting the decision makers in many different directions. The tools include visualization in the web and cross data from Aedes presence and human cases for better decision making, Figure 24.

Figure 24.

Confronting human cases (circles) with the region of influence of Aedes focus (blocks in cyan) in Fortaleza/CE. By enlarging the influence zone of Aedes in 100m means for this case an increasing of 50% in the risk of dengue in the area, for the same period of time.

The tools need to be used mainly to shorten the time needed to process the information from the field or from health units to rapidly respond to managers where to allocate resources with optimal cost/benefit to the municipalities, and stop dengue increase. The systems may only be included if the changing factor does not eliminate previous effort in the organization of the forces, in fact they have to sum, although it will became another computational system in an increasingly set of software that are used to solve just parts of the hole problem.

The computational infrastructure needed for control and prevention of dengue, are mainly reported here, as in the Brazilian cities reality. The framework has been in development since 2002, and it is supported by a number of Brazilian research agencies and a private firm until today. The main step-forward of our system is the inclusion of the logistic models to organize the phase of Aedes increase. The other phase is also considered by a short number of research works worldwide. Our success in organizing the logistic of the agents were obtained in Fortaleza/CE, in 2005, when we maintain a region populated by approximately 300,000 habitants free of Aedes in the great majority of the places of control.

In Figure 25 we show the region that was tested showing the position of the following special points, and the situation in the end of November/2005 when we finish our test and in December/2005 when we follow the results without monitoring the evolution of the visits by the agents.

Figure 25.

Region of Fortaleza/CE where the text of the system was made in 550 SP. The following pictures show the situation of blocks in November/2005 (1 SP with Aedes) after following the agents and in December/2005 (13 SP with Aedes) when we stopped the use the Framework by the agents.

The difficulties in implementing the system in the field, is a great barrier to be transposed. Our experience with public health municipalities in Brazil was laborious. Main difficulty is the belief in spending money with control by software. In fact, once Dengue is re-emerging disease, Brazilian health managers only consider the problem “when it comes”. Once the agents are working day-by-day, they think they are doing the prevention, but careless with its quality. As can be seen in Figure 4, Brazilian indices reveal that this posture has to be change soon.

7. Conclusions

This study described, in general lines, the problem of Dengue in the tropical regions of the world, highlighting the World Health Organization’s concern in making the peculiarities of this disease accessible to researchers and public health officials, so that better and more effective methods of combating the disease can be made available.

A computational framework (WEBDENGUE) has been presented to support the activities of prevention and control of dengue. Furthermore, practical operational situations of problems related to the logistics for prevention and combat of dengue have been described, which consist of problems to be equated. With these problems in mind, a set of mathematical models for the logistical control of the sanitary agents visits and the spraying vehicles have been developed. Most of those models have already been incorporated.

The complexity of the problems involved demands the use of both the traditional and the latest optimization tools in order to find solutions to such problems. Such models are being solved by heuristics and incorporated in a SDSS to meet, in a timely manner, the needs of health officials in the assignment of the services of prevention and combat of dengue.

This Computational Framework was prepared for the cities of Sobral (Geographvs and Webdengue), in most total features for the city of Fortaleza (Geographvs, Hand-Held Agent and Supervisor, Webdengue, Manager) and more recently for the state of Rio de Janeiro (Integration with SINAN).

During the period of tests in Fortaleza, the framework was adapted to the reality of the service and helped 13 agents to follow their routine in Regional II, by June to November/2005. The success of the pilot project in Fortaleza came after the coverage of approximately 550 SP units during 14 cycles of 15 days (5443 visits), where just one SP (a building in construction) was found with Aedes grubs. Also, the municipality health managers evaluated with our team the tools and methodology used to manage the information and the organization of the work done in the field. They were very impressed by its impact with the agents and supervisors quality of work, also the information treatment flexibility and visibility to manage the disease, by crossing human cases and the Aedes presence in the field.

Most recently we use GeoGRAPHVS to prepare all the city of Fortaleza to track dengue. The project used the parallel version of the system where 7 people georreferenced in five months 48 thousand street segments and 18 thousand blocks, for the Fortaleza’s Municipality Secretary of Health. They are using the results of the work to follow the disease growth since 2009. Expectations of professional use of the Computational Framework are still great.

Acknowledgments

We would like to thank the Secretary of Social Development and Health of Sobral/CE and Fortaleza/CE, the Town Hall and Center of Zoonoses and Epidemiology of Sobral and Fortaleza/CE, for the support to this project in the field. We like to thank the CAPES/COFECUB project 0467/04, CNPq project PQ 202457 (pos-doctorate), and program ALFA-EUROPEAID project ALFA II-0457-FA-FCD-F1-FC, FUNCAP-FINEP/CE Empresas Competitivas, CNPq-RHAE Inovação projeto 505594/2004-8, and to GRAPHVS Ltda, to the financial support. We would also like to thank the GRAPHVS system development team for their commitment to making this work come true. We finally thank the State Secretary of Health (SESDC-RJ) and COPPETEC/RJ, for the support on Rio de Janeiro evaluation project 492/2008 process E-08/10471/2008.