Problemas de cubrimiento.

Aplicación

Karen Oliveros Félez

Trabajo de Fin de Grado en Matemáticas
Universidad de Zaragoza

Directora del trabajo: Herminia I. Calvete

27 de junio de 2017
Prólogo

La ubicación de las instalaciones siempre ha sido un elemento crítico en la planificación estratégica

de empresas privadas y públicas. La adquisición o construcción de nuevas instalaciones puede implicar
grandes costes para la empresa, por lo que determinar las mejores ubicaciones para las mismas es un
desafío estratégico importante. Este trabajo se enmarca en términos de Investigación Operativa y se
centra en la programación entera, específicamente en el problema de cubrimiento. El objetivo principal
es estudiar los problemas de cubrimiento y aplicarlos para resolver el problema de ubicación de las
instalaciones de bomberos en las provincias de Huesca y Teruel. La memoria está compuesta por tres
capítulos que se resumirán brevemente a continuación.
El capítulo 1 introduce la programación lineal y la programación lineal entera. Además, también
se define la relajación lineal de un problema entero, una “copia” del problema entero sin la restricción
de integridad en las variables. Se proporcionan tres métodos para resolver problemas enteros que uti-
lizan la relajación del problema. El método de ramificación y acotación divide el conjunto de posibles
soluciones del problema relajado en subconjuntos más pequeños y disjuntos, y elimina una parte del
conjunto anterior donde no hay soluciones para el problema entero. El método de planos de corte, en el
que, a grandes rasgos, se debe encontrar una desigualdad que todas las soluciones del problema entero
deben satisfacer y que se añadirá al problema como una nueva restricción (plano de corte). Finalmente,
el método de ramificación y corte combina los dos métodos anteriores. Se basa en el algoritmo de rami-
ficación y acotación y utiliza el algoritmo de plano de corte para ajustar más las relajaciones lineales.
El capítulo 2 modela el problema de dónde ubicar las instalaciones como un problema de cubrimien-
to de nodos. En este último, los nodos son ubicaciones (usuarios y posibles instalaciones) y los arcos
entre ellos son conexiones entre ubicaciones. Denotando por di j la distancia entre el nodo de usuario j y
el nodo de posible instalación i, y por D la distancia máxima entre un usuario y la instalación más cerca-
na, se dice que se proporciona un buen servicio si todos los usuarios tienen, a lo sumo, una distancia D a
la instalación más cercana. En este capítulo se proponen también algunas modificaciones del modelo bá-
sico que permiten representar diferentes situaciones. El problema de cubrimiento de conjuntos (LSCP)
modifica la función objetivo del modelo original para minimizar el coste de ubicar las instalaciones. El
problema de ubicación de cubrimiento maximal (MCLP) identifica la ubicación de un número especí-
fico de instalaciones p de modo que se maximice la demanda cubierta. El problema LSCP-Implícito
cuantifica el cubrimiento de un área determinada por niveles, y el objetivo de este modelo es alcanzar
esas coberturas de nivel para cada área con un número mínimo de instalaciones. El objetivo del proble-
ma de cubrimiento de conjuntos con fraccionamiento (CLSCP) es minimizar el número de instalaciones
ubicadas, cubriendo toda la demanda y teniendo en cuenta la capacidad máxima de las instalaciones.
Finalmente, el objetivo del problema de cobertura de conjuntos probabilístico (PSCP) es cubrir un área
de demanda minimizando las instalaciones ubicadas, teniendo en cuenta la probabilidad de ocupación
de las instalaciones. Este capítulo también proporciona una breve explicación sobre los métodos de so-
lución de los problemas de cubrimiento, problemas de clase NP-hard. También se da una idea general
de algunas técnicas exactas y metaheurísticas para la solución de los problemas de cubrimiento.
En el capítulo 3, se aplican algunos de los modelos presentados en el capítulo 2 al problema de la
ubicación de instalaciones de bomberos en Huesca y Teruel. CPLEX Studio, Excel y VRP Solver se
utilizarán para lograr este objetivo. En primer lugar, se muestra el entorno legal en el que se realiza este
estudio, regido por el Boletín Oficial de Aragón. La situación actual en las dos provincias se estudia
a través del MLCP. Con ayuda de LSCP, MLCP y LSCP-implícito se proponen mejoras a la situación

III
IV Prólogo

actual. El primero se ha utilizado para realizar diversos estudios en los que se tiene y no se tiene en
cuenta la ubicación actual de las instalaciones. El modelo MCLP se aplica para estudiar el caso de
que solo hay presupuesto para ubicar una o dos instalaciones más. Y, finalmente, el LSCP-implícito
contempla el caso en el que se desea que los núcleos urbanos más poblados tengan una mayor cobertura.
La memoria también incluye un Anexo con las distintas noticias publicadas en algunos periódicos
que han sido motivación de este trabajo, así como un Anexo de siglas.
Summary

The location of facilities has always been an important issue in strategic planning of private and pu-
blic companies. The acquisition or construction of new facilities may imply huge costs to the company,
therefore deciding the best locations for new facilities is an important strategic challenge. Operations
Research addresses this problem through integer programming and, in particular, covering problems.
The aim of this work is to understand covering problems and apply them to solve the firemen facility
location problem in Huesca and Teruel. This work consists of three chapters which are briefly summa-
rised below.

Chapter 1: An introduction to Integer Optimization

Chapter 1 gives an approach of what an integer problem is and it introduces linear programming.
First, the maximization linear problem and basic definitions in linear programming are given. Second,
a theorem and a corollary related to the existence of optimal solutions of linear problems are displayed.
Next, the definition of integer linear problem is given - which is a kind of optimization problem whose
variables must be integer. In order to solve this kind of problems, the definition of a linear relaxation of
an integer problem is introduced. In addition, three algorithms for solving integer problems that use the
relaxation of the integer problem are given.
The branch and bound algorithm start solving the relaxed problem. If its optimal solution is integer,
then the optimal solution is accomplished. If it is not, this procedure looks for an optimal solution by
branching, i.e., partitioning the set of possible solutions into subsets. Moreover, it attempts to prune the
enumeration by bounding the objective value of the subproblems generated by this partition.
The cutting-plane algorithm, as the algorithm described above, solves the relaxed problem of the
integer problem. If its optimal solution is integer, the problem has been solved. Otherwise the algorithm
iteratively refines the feasible set by means of linear inequalities, termed cuts or cutting planes. There-
fore a new problem stricter than the relaxation itself is defined in each iteration, hence in each iteration
we would be closer of the optimal solution.
The branch and cut algorithm combines both previously described algorithms. It is based on the
branch and bound algorithm and uses the cutting-plane algorithm to refine more the feasible set. Its
description is practically the same as that of the branch and bound algorithm but adding a cut step from
the cutting-plane algorithm.

Chapter 2: Covering problems

When deciding where to locate facilities that provide a service, it happens quite often that a customer
can receive this service only if they are under a certain distance to the closest facility. The problems that
share this property receive the name of covering problems. In these problems, customers and possible
facilities are modelled as nodes. Let I = {1, . . . , n} be the set of potential facilities and let J = {1, . . . , m}
be the set of customers. The distance between the facility i and the customer j is denoted by di j . If it
is assumed that D is the maximum allowed distance between a customer and the nearest facility and
di j 6 D ∀i ∈ I, j ∈ J then, it is said that the customer is covered.
The covering problem minimizes location costs while satisfying a specified level of coverage. De-
note by ai j a binary parameter which is 1 if distance from candidate facility i to the customer j is not
greater than D. Moreover, let us define the binary variable xi that indicates whether the facility is located

V
VI Summary

at point i or not. Therefore, the mathematical formulation of covering problem is:

n
min ∑ xi (1)
i=1
subject to
n
∑ ai j xi > 1, j = 1, . . . , m (2)
i=1
xi ∈ {0, 1}, i = 1, . . . , n. (3)
In this section, modifications are made to this formulation to reach different purposes. The first
model suggested is the Location Set Covering Problem (LSCP) which changes the original model’s
objective function. Its purpose is to minimize the cost of locating facilities assuming that facility location
cost varies from place to place. Hence, the parameter ci is added; it represents the fixed cost of locating
a facility at node i. Finally, the objective function of this model is ∑ni=1 ci xi .
The Maximal Covering Location Problem (MCLP) locates a fixed number of facilities p so that the
total demand within the maximum service distance of at least one facility is maximized. It allows not to
cover all the demand because of the resources limitations.
The LSCP-Implicit model assumes that each demand area can be covered not only by one facility
but also by two or more, so that each facility covers a percentage of demand.
The Capacitated Location Set Covering Problem (CLSCP) takes in account the demand of the cus-
tomers and the maximal capacity of the facilities. The aim of this problem is to minimize the number of
located facilities while also covering the whole demand.
The Probabilistic Set Covering Problem (PSCP) provides a dynamic aspect of the covering problem
which is frequently used in emergency facilities. Its aim is to cover a demand area minimizing the
located facilities bearing in mind the possibility of having the facility occupied when another customer
needs it.
This chapter also gives a brief explanation of the solution methods of the covering problems, which
are NP-hard class. Exact and metaheuristic techniques as Lagragian relaxation, tabu search, genetic al-
gorithms and simulated annealing are briefly presented.

Chapter 3: Application of covering problems to the location of firemen

facilities
This chapter applies the models described in Chapter 2 to the firemen facilities location problem.
CPLEX Studio, Excel and VRP Solver are used to accomplish this aim. First, it shows the legal envi-
ronment in which this study is carried out. The legal framework is ruled by different laws published
in ‘Boletín Oficial de Aragón’. It is established that each provincial council should have its own fire
department, therefore the provinces must be studied separately. In this work, Huesca and Teruel are
studied. The cities in which population is over 20,000 must have a firemen facility located. In addition,
the existing facilities of volunteer firemen will not be taken into account and the maximum intervention
time of 35 minutes must be guaranteed. In this work, we are going to stablish where a facility should be
located. A study carried out by specialists would take into consideration the type of facility that must be
located and the number of firemen that should be necessary, which is beyond the scope of this work.
The current situation in the two provinces is studied through the MLCP, assuming that firemen get
ready in 2 minutes. By using the LSCP, MLCP and LSCP-implicit improvements to this case have
been also proposed. The first one has been used to do several studies where the current location of the
facilities is and is not taken into account. The MCLP model has been used to study the case in which
there is only budget to locate one or two more facilities. The LSCP-implicit studies the possibility of
implementing a larger coverage in the most populated towns.
There are currently 20 firemen facilities in Huesca, 12 of which are professional ones. With these
professional firemen facilities, 28 towns are not covered. The optimal solution of LSCP model, without
taking into account the current facilities, indicates that 13 facilities must be located to cover the whole
territory. Nevertheless, only 4 out of the 12 facilities that are already located would be used. If the
Problemas de cubrimiento. Aplicación. - Karen Oliveros Félez VII

current locations were taken into account (using all the facilities currently located) 19 facilities should
be located. If it were not mandatory to use these facilities, but only convenient, 14 facilities should be
located, 8 of which would already exist. If we suppose that there is budget for one or two facilities,
where should we locate them? In the first case, the MCLP application shows that it should be placed in
Albalatillo and it would cover 11 more towns. In the second case, they should be placed in Albalatillo
and Jasa, and 18 more towns would be covered. The LSCP-Implicit model, supposing that Huesca,
Monzon, Barbastro, Fraga and Jaca needed three facilities for being covered, indicates that 16 facilities
should be placed, taking into account the facilities that already exist.
In Teruel, there are currently 19 firemen facilities, 15 of which are professional ones. With these
professional firemen facilities 24 towns are not covered. The optimal solution of LSCP model, without
taking into account the current facilities, indicates that 14 facilities must be located to cover the whole
territory. Nevertheless, only 2 out of the 15 facilities that are already located would be used. If the
current locations were taken into account (using all the facilities currently located) 20 facilities should
be located. If it were not mandatory to use these facilities, but only convenient, 15 facilities should be
located, 7 of which would already exist. If we suppose that there is budget for one or two facilities,
where should we locate them? In the first case, the MCLP application shows that it should be placed in
Cañada Vellida and it would cover 8 more towns. In the second case, they should be placed in Ababuj
and Santa Eulalia, and 14 more towns would be covered. The LSCP-Implicit model, supposing that
Teruel, Alcañiz and Andorra needed three facilities for being covered, indicates that 17 facilities should
be placed, taking into account the facilities that already exist.
Índice general

Prólogo III

Summary V

1. Introducción a la programación entera 1

1.1. Programación lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Optimización entera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3. Métodos para la resolución de problemas de optimización entera . . . . . . . . . . . . 3
1.3.1. Método de ramificación y acotación . . . . . . . . . . . . . . . . . . . . . . . 3
1.3.2. Método de planos de corte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.3. Método de ramificación y corte . . . . . . . . . . . . . . . . . . . . . . . . . 4

2. Problemas de cubrimiento 5
2.1. Formulación del problema de cubrimiento . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2. Algunas variantes del problema de cubrimiento . . . . . . . . . . . . . . . . . . . . . 6
2.2.1. Problema de cubrimiento de conjuntos. Location Set Covering Problem (LSCP) 6
2.2.2. Problema de cubrimiento maximal. Maximal Covering Location Problem (MCLP) 6
2.2.3. Problema de cubrimiento de conjuntos implícito (LSCP-Implicit) . . . . . . . 7
2.2.4. Problema de cubrimiento de conjuntos con fraccionamiento. Capacitated Loca-
tion Set Covering Problem (CLSCP) . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.5. Problema de cubrimiento de conjuntos probabilístico. Probabilistic Set Cove-
ring Problem (PSCP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3. Métodos de solución de los problemas de cubrimiento . . . . . . . . . . . . . . . . . . 10
2.3.1. Técnicas exactas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.2. Técnicas metaheurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3. Aplicación del problema de cubrimiento a la ubicación de instalaciones de bomberos en

Huesca y Teruel 13
3.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2. Estudio de la provincia de Huesca . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2.1. Aplicación del modelo LSCP . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2.2. Aplicación del modelo MCLP . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.3. Aplicación del modelo LSCP-Implicit . . . . . . . . . . . . . . . . . . . . . . 19
3.3. Estudio de la provincia de Teruel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3.1. Aplicación del modelo LSCP . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.2. Aplicación del modelo MLCP . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.3. Aplicación del modelo LSCP-Implicit . . . . . . . . . . . . . . . . . . . . . . 22

Anexo I: Motivación 29

Anexo II: Siglas 37

IX
Capítulo 1

Introducción a la programación entera

1.1. Programación lineal

La programación lineal es una técnica de la Investigación Operativa cuya finalidad es maximizar o
minimizar una función objetivo lineal, de manera que las variables de dicha función están sujetas a una
serie de restricciones expresadas mediante ecuaciones lineales.
El problema de optimización lineal escrito en forma estándar de máximo [3, 25] consiste en deter-
minar los valores de las variables decisión x1 , . . . , xn tales que

max Z = c1 x1 + c2 x2 + . . . + cn xn
sujeto a
a11 x1 + a12 x2 + . . . + a1n xn = b1
a21 x1 + a22 x2 + . . . + a2n xn = b2 (1.1)
...
am1 x1 + am2 x2 + . . . + amn xn = bm
xi > 0, i = 1, . . . , n.
Escrito en forma matricial el problema es:

max cX
sujeto a
(1.2)
AX = b
X >0

donde X: n × 1, A: m × n de rango m, b: m × 1 y c: 1 × n.

Definición 1.1. La región factible S de un problema de programación lineal es el conjunto de todos los
puntos que satisfacen todas las restricciones del problema, es decir

S = {X ∈ Rn : AX = b, X > 0}.

Un elemento de S se dirá solución factible, y el problema es no factible si S = 0.

/

Definición 1.2. Para un problema de maximización, una solución óptima del mismo es un punto en
la región factible tal que la función objetivo en ese punto es mayor o igual que el valor de la función
objetivo en cualquier otra solución factible.
Para un problema de minimización, una solución óptima es un punto en la región factible tal que la
función objetivo en ese punto es menor o igual que el valor de la función objetivo en cualquier otra
solución factible.

1
2 Capítulo 1.

Definición 1.3. Sea S un conjunto convexo de Rn . Se dice que un punto X ∈ S es un punto extremo de
S si no puede ponerse como una combinación convexa de dos puntos distintos de S.
Sea S un conjunto convexo cerrado de Rn . Un vector d de Rn no nulo es una dirección de S si
X + λ d ∈ S, ∀X ∈ S, λ > 0. Dos direcciones d1 y d2 son distintas si no son proporcionales.
Se dice que una dirección d es extrema si no puede escribirse como una combinación lineal positiva
de dos direcciones distintas.

Teorema 1.1. Sea el problema de optimización lineal de máximo en forma estándar (1.2) cuya región
de factibilidad es no vacía. Sean X1 , . . . , Xk los puntos extremos y d1 , . . . , dh las direcciones extremas de
la región factible. Una condición necesaria y suficiente para que el problema tenga solución óptima es
que
cdi 6 0, i = 1, . . . , h.
Además, si el problema tiene solución óptima, existe un punto extremo que es solución óptima del
problema.

Corolario 1.2. Sea el problema de optimización lineal de mínimo en forma estándar (1.2) cuya región
de factibilidad es no vacía. Sean X1 , . . . , Xk los puntos extremos y d1 , . . . , dh las direcciones extremas de
la región factible. Una condición necesaria y suficiente para que el problema tenga solución óptima es
que
cdi > 0, i = 1, . . . , h.
Además, si el problema tiene solución óptima, existe un punto extremo que es solución óptima del pro-
blema.

Definición 1.4. Se dice solución factible básica a un elemento de la región factible del problema (1.2)
con a lo sumo m valores no nulos, y tal que los vectores columna de la matriz A asociados a las compo-
nentes no nulas son linealmente independientes. Gráficamente una solución factible básica es un punto
extremo de la región de factibilidad.

Para resolver eficientemente el problema de optimización lineal se han diseñado distintos algoritmos
[3, 25]. Uno de los mas conocidos es el algoritmo simplex, que recorre puntos extremos de la región
factible. El algoritmo simplex parte de una solución factible básica. Esta solución se obtiene igualando
n − m variables a cero y resolviendo el sistema con las variables restantes. Las variables que se hacen
cero son las variables no básicas; el resto son las variables básicas. Partiendo de una solución factible
básica, el algoritmo simplex itera cambiando de una solución factible básica a otra adyacente con un
valor mejor (o no peor) de la función objetivo. El proceso continúa hasta que se alcanza una solución
factible básica X tal que cX > cX ∀X ∈ S en el problema de máximo (cX 6 cX ∀X ∈ S en el de mínimo)
o se encuentra una dirección extrema d para la que no se verifica la condición del teorema 1.1 o del
corolario 1.2. Si se encuentra esta dirección, el algoritmo concluye indicando que el problema es no
acotado.

1.2. Optimización entera

Un problema de optimización se dice lineal entero mixto (PEM) si coexisten variables enteras y
continuas. Su formulación es:
max cX + hY
sujeto a
(1.3)
AX + GY = b
X, Y > 0, X ∈ Zn
Problemas de cubrimiento - Karen Oliveros Félez 3

siendo X: n × 1, Y : p × 1, A: m × n, G: m × p, b: m × 1, h: 1 × p y c: 1 × n. En el caso de que todas las

variables están restringidas a ser enteras, el problema se dice entero puro (PEP) o entero puro binario
PEP 0 − 1 si las variables solo pueden tomar los valores 0 − 1.
p
El conjunto de posibles soluciones del PEM será S = {(X,Y ) ∈ Zn+ × R+ : AX + GY = b}.

Definición 1.5. Se denomina relajación del PEM (RPEM) al problema lineal

max cX + hY
sujeto a
(1.4)
AX + GY = b
X > 0, Y > 0.

El conjunto de soluciones factibles del problema (1.4) se denota como P0 .

1.3. Métodos para la resolución de problemas de optimización entera

Si el PEM tiene solución óptima, se denota como (X ∗ ,Y ∗ ) y Z ∗ al correspondiente valor óptimo del
PEM. Se denota (X 0 ,Y 0 ) y Z 0 a la solución optima y al valor óptimo del RPEM, respectivamente. Como
S ⊂ P0 se sigue que Z ∗ 6 Z 0 . Además, si X 0 es un vector entero entonces (X 0 ,Y 0 ) ∈ S y por lo tanto
Z ∗ = Z 0 . En este caso, el PEM está resuelto.
A continuación se van a describir tres estrategias [5] para enfrentarse al caso en el que al menos una
componente del vector X 0 es no entera.

1.3.1. Método de ramificación y acotación

El método de ramificación y acotación busca una solución óptima del PEM dividiendo el conjunto
P0 en subconjuntos más pequeños y disjuntos, eliminando, además, una parte del conjunto P0 que no
contiene soluciones factibles del PEM.

El algoritmo resuelve, en primer lugar, el problema RPEM. Si su solución óptima es entera, entonces
el algoritmo termina. Si no lo es, existirá una variable en la solución xk , tal que xk ∈
/ Z. El problema
original se divide en k problemas RPEM1 , . . . , RPEMk , cuyas restricciones son las del RPEM original,
añadiendo una restricción más sobre la variable xk . A continuación se resuelven los problemas por
separado. En el caso de que alguno de los problemas tenga solución entera, se comprueba si el valor de
la función objetivo de la solución entera es mayor (o menor, si es de mínimo) que el valor de la función
objetivo del resto de ramas. Si lo es, el algoritmo termina. Si no, se toma otro problema y se vuelve a
dividir en s problemas, repitiendo el proceso anterior.
Suponiendo que cada problema lineal se corresponde con un nodo en el árbol de enumeración, para
un nodo Ni , sea Zi el valor de la función objetivo del RPEMi . Sea N0 el nodo correspondiente al RPEM.
Entonces el proceso de ramificación y acotación procede de la siguiente manera:

0. Inicializar. L := {N0 }, Z = −∞, (X ∗ ,Y ∗ ) := 0.

/

1. ¿Finalización? Si L = 0,
/ la solución (X ∗ ,Y ∗ ) es óptima.

2. Elección de un nodo. Tomar Ni en L y eliminarlo de L .

3. Acotación. Resolver RPEMi . Si no es factible, ir al paso 1. En otro caso, tomar (X i ,Y i ) solución

optima del RPEMi y Zi el valor de su función objetivo.

4. Eliminación. Si Zi 6 Z ir al paso 1. Si (X i ,Y i ) es factible para el problema PEM, tomar Z := Zi y

(X ∗ ,Y ∗ ) := (X i ,Y i ) e ir al paso 1. En otro caso pasar al paso 5.
4 Capítulo 1.

5. Ramificación. En el RPEMi , construir k > 2 problemas lineales RPEMi1 , . . . , RPEMik con regio-
nes factibles más pequeñas cuya unión no contiene (X i ,Y i ), pero contiene todas las soluciones
del RPEMi con X ∈ Zn . Añadir los correspondientes nuevos nodos Ni1 , . . . , Nik al conjunto L e ir
a 1.

Existen distintas formas de construir los nuevos problemas RPEMi1 , . . . , RPEMik cuya descripción
puede verse en [5].

1.3.2. Método de planos de corte

Como antes, el algoritmo resuelve en primer lugar el problema RPEM. Si (X 0 ,Y 0 ) ∈ / S, la idea es
encontrar una desigualdad αX + γY 6 β que se satisface para todo punto en S pero tal que αX 0 + γY 0 >
β . La existencia de tal igualdad está garantizada cuando (X 0 ,Y 0 ) es una solución básica del problema
RPEM. Una desigualdad de tales características define un plano de corte que separa la solución (X 0 ,Y 0 )
del resto de conjunto S y define el nuevo conjunto P1 := P0 ∩{(X,Y ) : αX +γY 6 β } tal que S ⊆ P1 ⊂ P0 .
Así, se define un problema que es más exigente que el de relajación natural y que estará más cerca del
resultado del PEM. El proceso de planos de corte procede del siguiente modo:
Comenzando con i = 0,

1. Paso recursivo: Resolver el problema lineal RPEMi = max{cX + hY : (X,Y ) ∈ Pi }

a) Si la solución (X i ,Y i ) asociada a RPEMi pertenece a S, parar.

b) En otro caso, resolver el problema de separación encontrando un plano de corte αX + γY 6
β que separa la solución (X i ,Y i ) de S. Definir
Pi+1 := Pi ∩ {(X,Y ) : αX + γY 6 β } y repetir el paso recursivo.

Una forma de construir estos planos de corte es el procedimiento de Gomory. Si existen variables
n
no negativas x1 , . . . , xn tales que ∑ a j x j = a0 , donde a0 ∈
/ Z, el corte de Gomory es
j=1

n
∑ (a j − ba j c)x j > a0 − ba0 c.
j=1

Las desigualdades que separan la solución del conjunto factible S se denominan desigualdades vá-
lidas.

1.3.3. Método de ramificación y corte

El método de ramificación y corte combina los dos métodos que se han visto en los anteriores
apartados, usando como algoritmo base el método de ramificación y acotación, y utilizando el algoritmo
de planos de corte para ajustar más las relajaciones lineales. Su descripción general es la del método de
ramificación y acotación descrita en el apartado 1.3.1, añadiendo el siguiente paso entre los pasos 4 y 5:

4’. ¿Adición de cortes? Se debe decidir si se fortalece la formulación del RPEMi o si se ramifica
directamente. En el primer caso, se fortalece RPEMi añadiendo planos de corte y se vuelve al
paso 3. En el segundo caso se procede al paso 5.
Capítulo 2

Problemas de cubrimiento

2.1. Formulación del problema de cubrimiento

Los problemas de cubrimiento surgen al decidir dónde ubicar instalaciones que van a proveer ser-
vicios a usuarios, que solo podrán ser atendidos por la instalación más cercana si ésta se sitúa a una
distancia menor que una dada D. Por lo tanto, un usuario es atendido si está a una cierta distancia de la
instalación menor que D, en este caso, se dice que el individuo está cubierto. El primer modelo mate-
mático aplicado a este problema [8, 13, 24] minimiza el número de instalaciones que se deben ubicar
para que todos los clientes estén cubiertos.
Este problema [13] se formula como un problema de cubrimiento de nodos. Sea el grafo completo
G = (V, E) en el que el conjunto de los nodos V está formado por los elementos i ∈ I = {1, . . . , n}
que representan las posibles localizaciones de las instalaciones, y los elementos j ∈ J = {1, . . . , m},
que representan los posibles lugares donde se pueden requerir los servicios o áreas de demanda, que
en adelante serán llamados usuarios. Por lo tanto, se tiene que V = I ∪ J. El arco entre dos nodos i,
j representa la conexión entre una posible instalación y un usuario. El arco (i, j) tiene asociada una
distancia que se denota por di j . D denota la máxima distancia para proveer un servicio aceptable, es
decir, cuando di j 6 D se dice que la instalación i cubre al usuario j. Si esto ocurre para todos los
usuarios j ∈ J se dice que el conjunto de instalaciones I cubre el grafo G.
Para i ∈ I, j ∈ J, se define
( (
1 si di j 6 D 1 si se ubica la instalación en i
ai j = , xi =
0 en caso contrario 0 en caso contrario.

El parámetro binario ai j indica si la distancia desde el emplazamiento candidato i al usuario j es

o no mayor que D y las variables decisión xi binarias indicarán si la instalación se va a ubicar en la
localización i o no.
Con estas notaciones, el problema de cubrimiento (PC) puede formularse como:
n
min ∑ xi (2.1)
i=1
sujeto a
n
∑ ai j xi > 1, j = 1, . . . , m (2.2)
i=1
xi ∈ {0, 1} i = 1, . . . , n. (2.3)
El término (2.1) minimiza el número total de instalaciones. Las desigualdades (2.2) garantizan que cada
cliente j tiene ubicada al menos una instalación a una distancia menor o igual que D. En ocasiones,
estas restricciones se escriben sin utilizar el parámetro ai j como

∑ xi > 1, j = 1, . . . , m
i∈N j

5
6 Capítulo 2.

donde N j = {i ∈ I|di j 6 D} representa el conjunto de potenciales instalaciones que cubren al usuario j.

Finalmente, la restricción (2.3) asegura que las variables xi son binarias.
En ocasiones, a este modelo básico de cubrimiento se le aplican modificaciones para alcanzar dife-
rentes objetivos. En el siguiente apartado se formulan algunas de ellas.

2.2. Algunas variantes del problema de cubrimiento

El problema de cubrimiento básico se ha ido modificando y desarrollando a lo largo del tiempo
[4, 6, 16], añadiendo distintas restricciones o cambiando la función objetivo, para afrontar los distintos
casos de problemas de cubrimiento que han surgido.

2.2.1. Problema de cubrimiento de conjuntos. Location Set Covering Problem (LSCP)

El objetivo del problema de cubrimiento de conjuntos consiste en minimizar el coste de localiza-
ción suponiendo que ubicar una instalación en un vértice u otro tiene costes distintos. Con la notación
introducida en la sección 2.1 y añadiendo el parámetro ci , que representa el coste fijo de ubicar una
instalación en el nodo i ∈ I, el modelo se plantea como:
n
min ∑ ci xi (2.4)
i=1
sujeto a (2.2), (2.3).
En este problema, el término (2.4) minimiza el coste de ubicación de las instalaciones.

2.2.2. Problema de cubrimiento maximal. Maximal Covering Location Problem (MCLP)

Este modelo apareció por primera vez en 1974 [4] para abordar el problema de tener recursos limita-
dos. Su objetivo es identificar la ubicación de un número específico p de instalaciones de manera que se
maximice la demanda cubierta. En este modelo se permite no cubrir toda la demanda por la existencia
de limitaciones de recurso.
Se denota mediante g j la demanda de servicio en el usuario j y la variable binaria z j indica si el
usuario j es cubierto por alguna instalación o no,
(
1 si el usuario j es cubierto por alguna instalación
zj =
0 en caso contrario.
El problema MCLP se plantea de la siguiente manera:
m
max ∑ g jz j (2.5)
j=1
sujeto a
∑ xi > z j , j = 1, . . . , m (2.6)
i∈N j
n
∑ xi = p (2.7)
i
xi ∈ {0, 1} i = 1, . . . , n (2.8)
z j ∈ {0, 1} j = 1, . . . , m. (2.9)
La función objetivo del problema maximal (2.5) garantiza que la demanda total cubierta al ubicar las
instalaciones sea máxima. Las restricciones (2.6) relacionan las decisiones de ubicación de instalaciones
con el cubrimiento del área de demanda j, si no se ubican instalaciones que cubran al usuario j entonces
su demanda no será satisfecha. La restricción (2.7) especifica que únicamente p instalaciones deben ser
ubicadas. Las restricciones (2.8) y (2.9) garantizan que las variables sean binarias.
Problemas de cubrimiento - Karen Oliveros Félez 7

2.2.3. Problema de cubrimiento de conjuntos implícito (LSCP-Implicit)

Los modelos descritos anteriormente no tienen en cuenta si la instalación que cubre un conjunto
de nodos de demanda j está disponible en el momento en el que es requerido por un usuario. Si la
instalación i está dando servicio a un usuario j1 y en ese momento otro usuario j2 , cubierto únicamente
por la instalación i, requiere sus servicios, es posible que j2 no obtenga finalmente el servicio que ha
demandado y, por lo tanto, no esté realmente cubierto. Este tipo de situaciones se dan, por ejemplo, en
instalaciones de bomberos. Si un coche de bomberos está en una urgencia, entonces ese coche no puede
responder a otra llamada al mismo tiempo. Para modelar este tipo de situaciones se ha desarrollado el
modelo de problemas de cubrimiento implícito [16] en el que la cobertura de cada nodo de demanda
j es satisfecha por más de una instalación. Por ejemplo, en la figura 2.1 se puede observar que el área
de demanda está cubierta por dos instalaciones distintas i1 e i2 . Ambas cubren un porcentaje del área
de demanda de más del 50 por ciento. Si el cubrimiento de ambas instalaciones es complementario, la
totalidad del área de demanda estará cubierta.

i1

i2

Instalación

Cubrimiento de la instalación i1

Cubrimiento de la instalación i2

Área de demanda

Figura 2.1: Cubrimiento de un área de demanda por dos instalaciones.

Para cuantificar el tipo de cubrimiento de un usuario o área de demanda j, se denota mediante

k ∈ {1, . . . , K} el índice de nivel de cubrimiento. Por ejemplo, en la figura 2.1, K = 2 y por lo tanto
se admiten combinaciones de cubrimiento parcial por hasta dos instalaciones. El porcentaje mínimo
de cubrimiento en el nivel k se denota βk , es decir, βk indica qué porcentaje de cubrimiento parcial
se considera suficiente para el nivel k. El número mínimo de instalaciones para cubrir completamente
a nivel k es αk . Si se observa la figura 2.1, ambas instalaciones satisfacen un porcentaje mínimo de
cubrimiento β2 del 50 por ciento, pero ninguna de las dos independientemente cubriría completamente
el área de demanda. El conjunto de instalaciones potenciales que cubren el usuario j al menos βk se
denota Ω jk . En el caso de la figura 2.1 se tiene que Ω j2 = {i1 , i2 } y por lo tanto α2 = 2.
Por último, se define la variable decisión binaria w jk que indica si el usuario j está cubierto o no a
nivel k,

(
1 si el usuario j está cubierto al menos al nivel k
w jk =
0 en caso contrario.
8 Capítulo 2.

El problema se formula como:

n
min ∑ xi (2.10)
i=1
sujeto a
∑ xi > αk w jk , j = 1, . . . , m, k = 1, . . . , K (2.11)
i∈Ω jk
K
∑ w jk = 1, j = 1, . . . , m (2.12)
k=1
w jk ∈ {0, 1}, j = 1, . . . , m, k = 1, . . . , K (2.13)
xi ∈ {0, 1}, i = 1, . . . , n. (2.14)

La función objetivo (2.10) minimiza el número de instalaciones a construir. Las restricciones (2.11)
indican que para cubrir la demanda del usuario j completamente a nivel k, deben ubicarse al menos
αk instalaciones. Las restricciones (2.12) aseguran el cubrimiento a nivel k y las restricciones (2.12) y
(2.14) garantizan que las variables sean binarias.

2.2.4. Problema de cubrimiento de conjuntos con fraccionamiento. Capacitated Loca-

tion Set Covering Problem (CLSCP)
En el PC general se supone que la instalación i es capaz de cubrir toda la demanda del usuario j
cuando este último es atendido, es decir, se supone que las instalaciones no tienen restricción de capaci-
dad. En algunas situaciones, sin embargo, los usuarios tienen una demanda y no necesariamente toda ha
de ser atendida por una instalación, sino que puede fraccionarse. Este tipo de problemas se denominan
problemas de cubrimiento de conjuntos con fraccionamiento [6]. En este problema, se supone que las
instalaciones tienen una capacidad máxima, y los usuarios son asignados a las instalaciones pudiéndose
fraccionar su demanda. El objetivo es minimizar el número de instalaciones establecidas.
Sea ahora γ j la demanda del usuario j y sea ei la capacidad potencial de la instalación i. Se define
la variable ui j como la fracción de demanda del usuario j asignado a la instalación i. El modelo CLSCP
se plantea como

n
min ∑ xi (2.15)
i=1
sujeto a
∑ ui j > 1, j = 1, . . . , m (2.16)
i∈N j
m
∑ γ j ui j − ei xi 6 0, i = 1, . . . , n (2.17)
j
xi ∈ {0, 1}, i = 1, . . . , n. (2.18)
ui j > 0 i = 1, . . . , n, j = 1, . . . , m (2.19)

La restricciones (2.16) aseguran que la demanda de cada nodo j ∈ J sea asignada totalmente a
instalaciones cuya distancia a j sea menor que D. Las restricciones (2.17) aseguran que la demanda
total asignada a una instalación i no excede la capacidad de la misma. Por último, las restricciones
(2.18) aseguran que las variables sean binarias y las restricciones (2.19) aseguran la no negatividad de
las variables fraccionarias. Si se compara esta formulación con la del PC, se observan dos diferencias.
En primer lugar, se han agregado restricciones de capacidad de instalación y en segundo lugar, se han
agregado variables de asignación, ui j . Estas variables no son necesarias en el PC porque se supone que la
demanda será atendida por su instalación más cercana pero en el CLSCP la demanda no siempre puede
Problemas de cubrimiento - Karen Oliveros Félez 9

ser atendida por la instalación más cercana y se debe derivar a otra instalación. En ésta formulación se
asume que la demanda de un usuario no tiene que ser asignada completamente a la misma instalación.
Si el objetivo del problema es minimizar el coste total por la localización de las instalaciones se
n
debería cambiar la función objetivo (2.15) por la expresión ∑ ci xi .
i=1

2.2.5. Problema de cubrimiento de conjuntos probabilístico. Probabilistic Set Covering

Problem (PSCP)
Los problemas que se han formulado anteriormente han sido problemas deterministas cuyos pa-
rámetros no eran variables. Los modelos considerados en este apartado [8, 18] introducen un aspecto
más dinámico del problema de cubrimiento que, en especial, es usado frecuentemente en problemas de
instalaciones de emergencia.
Sea q la fracción de tiempo en el que la instalación está ocupada dando servicio, en adelante se
le dará el nombre de “fracción de ocupación”. El objetivo es asegurar un nivel mínimo de fiabilidad
ξ ∈ (0, 1) a los usuarios que van a requerir los servicios. Por tanto, la probabilidad de que una o más
instalaciones estén libres para dar servicio a la siguiente llamada de demanda del nodo j debe ser mayor
o igual que ξ . Por tanto se debe cumplir

∑ xi (2.20)
i∈N j
1−q > ξ, j = 1, . . . , m.
Como la fracción de ocupación q elevada al número de instalaciones en N j es la probabilidad de que
todas las instalaciones accesibles estén ocupadas, uno menos ésta cantidad proporciona la probabilidad
del suceso contrario, es decir, la probabilidad de que al menos una instalación i ∈ N j esté libre. El
problema se plantea como

n
min ∑ xi (2.21)
i=1
sujeto a
 
ln(1 − ξ )
∑ xi ≥ j = 1, . . . , m (2.22)
i∈N j ln(q)
xi ∈ N, i = 1, . . . , n. (2.23)

Nótese que (2.20) se ha escrito como (2.22), donde la variable x j puede tomar cualquier valor entero
positivo, lo que permite establecer múltiples instalaciones del mismo tipo en un mismo lugar. Este
problema usa una estimación de la fracción de ocupación y debido a como se ha formulado el problema,
es muy sensible a este valor de q. Por ello se ha propuesto una mejora al problema probabilístico anterior
que consiste en escribir la restricción de fiabilidad para cada punto de demanda j.
En primer lugar se va a definir q j la fracción media de ocupación de una región alrededor del
usuario j, que estará limitada por la distancia máxima D. Denotando t¯ la duración media de una llamada
o requerimiento de servicio, expresada en horas, νk la frecuencia de llamadas en el nodo de demanda
k expresada en llamadas/día y Mi = { j ∈ J|di j 6 D}, el conjunto de usuarios que están a una distancia
menor o igual que D de la instalación i se tiene:

t¯ · ∑ νk
k∈Mi
qj = .
24 · ∑ xi
i∈N j

Donde el numerador t¯ · ∑ νk representa el número de horas diarias necesitadas en la zona alrededor

k∈Mi
del usuario j limitada por D, y el denominador es el número de horas diarias disponibles de servicio en
10 Capítulo 2.

la misma zona. Por tanto, la ratio proporciona una estimación de la fracción de ocupación en la zona.
Nótese que el valor real de esta estimación de la fracción de ocupación no se calcula hasta que se conoce
el número de instalaciones en N j .
∑i∈N xi t¯
Para asegurar la fiabilidad ξ se debe exigir que 1 − q j j > ξ . Denotando Fj = · ∑ νk , en el
24 k∈M i
punto de demanda j se tiene que la restricción de fiabilidad es
  ∑ xi
i∈N j
 Fj 
1−  > ξ. (2.24)

∑ xi 
i∈N j

Por lo tanto, la formulación del modelo es

n
min ∑ xi (2.25)
i=1
sujeto a
n
∑ x j > b j, ∀j ∈ J (2.26)
i∈N j
xi ∈ {0, 1}, ∀i ∈ I (2.27)

donde b j es el entero más pequeño y positivo satisfaciendo

 b j
Fj
1− > ξ.
bj

2.3. Métodos de solución de los problemas de cubrimiento

Uno de los puntos clave para determinar si un algoritmo es bueno para resolver un determinado
tipo de problema es el tiempo de computación que requiere para resolverlo. Se denomina instancia a
un conjunto de datos específico de un problema dado. El tamaño de la instancia se mide por el espacio
requerido para guardar los datos.

Definición 2.1. Sea una función f : S −→ R+ , se dirá que f está acotada polinomialmente por la función
g : S −→ R+ si existe Φ : R −→ R un polinomio tal que f (s) 6 Φ(g(s)).

Un algoritmo se dice que resuelve un problema en tiempo polinomial si su tiempo de computación,

medido como el número de operaciones aritméticas que el algoritmo lleva a cabo, está acotado polino-
mialmente por el tamaño de la instancia. En este caso, se dice algoritmo polinomial.
Dependiendo del tipo de problema que se considera, pueden existir o no algoritmos polinomiales
que lo resuelvan. Los problemas se agrupan en clases de complejidad. La clase P es el conjunto de
problemas de decisión para los que existe un algoritmo polinomial para resolverlos. La clase NP, acró-
nimo en inglés de nondeterministic-polynomial, es el conjunto de problemas de decisión cuyo tiempo
de resolución es polinomial no determinista. Es decir, es la clase de problemas que se pueden resolver
en tiempo polinomial por una máquina de Turing no determinista. Los problemas NP-hard, que pueden
ser o no problemas de decisión, son los que al menos son tan difíciles de resolver como los problemas
más difíciles en la clase NP. Es decir, un problema es NP-hard si cumple que si existe un algoritmo
polinomial para su solución, entonces existe un algoritmo polinomial para cualquier problema en NP.
El problema de cubrimiento es de clase NP-hard [9, 13]. Por ser un problema de ésta clase se ha
invertido mucho esfuerzo en entender mejor la estructura de este modelo con intención de encontrar
formulaciones equivalentes que permitan desarrollar algoritmos más eficientes para obtener soluciones
Problemas de cubrimiento - Karen Oliveros Félez 11

más precisas. Para ello, se han desarrollado distintas técnicas: el preprocesamiento, el análisis polié-
drico y la relación del problema de cubrimiento con otros problemas. El preprocesamiento consiste en
simplificar el problema al máximo [15, 19, 22, 23]. Por ejemplo, al resolver un PC en el que se tiene
que minimizar se puede asumir que los coeficientes de la función objetivo son todos positivos. En caso
contrario, es decir, si existe un i ∈ N tal que ci 6 0, entonces se fijaría xi = 1 y quedaría un problema
a resolver con una variable menos. La formulación del PC puede ser mejorada estudiando la estructura
poliédrica de su politopo [2, 20]. Por otro lado, relacionar el PC con problemas clásicos ya estudiados
puede ser de utilidad a la hora de resolver el PC. Por ejemplo, es posible convertir un problema de
cubrimiento en uno de empaquetamiento o particionamiento y viceversa [12, 20].
Existen dos tipos de técnicas que se usan para la resolución de los PC, técnicas exactas y metaheu-
rísticas que se van a introducir brevemente a continuación.

2.3.1. Técnicas exactas

Las técnicas exactas tratan de resolver PC a través de algoritmos eficientes. Los algoritmos citados
en el capítulo 1, ramificación y acotación y planos de corte, son técnicas muy eficientes que resuelven
el problema general de optimización entera, pero existen modificaciones y otras técnicas que hacen uso
de las particularidades del problema de cubrimiento para ser más eficientes computacionalmente. Por
ejemplo, existe un método que es modificación del método de ramificación y acotación que aprovecha
la estructura de la formulación del problema de cubrimiento y sus soluciones [14]. En otro, se usa la
estrategia de ramificación y acotación donde la acotación se hace en las restricciones [7]. Otros métodos
exactos hacen uso de técnicas heurísticas y del método de Relajación Lagrangiana (RL) para obtener
cotas inferiores [2].

2.3.2. Técnicas metaheurísticas

Las técnicas metaheurísticas son procedimientos de búsqueda que no garantizan la obtención del
óptimo del problema considerado, pero proporcionan, en general, soluciones cercanas al óptimo en
tiempos computacionales razonables. Las técnicas metaheurísticas tratan de huir de óptimos locales
orientando la búsqueda en cada momento dependiendo de la evolución del proceso de búsqueda.
Entre los diferentes métodos que se han desarrollado en la literatura para resolver los problemas de
cubrimiento, es necesario destacar la RL. La RL es un método computacionalmente eficiente y puede
generar muy buenas soluciones en un tiempo razonable [10]. Además de usarse como un método heu-
rístico, se puede usar para proporcionar buenas cotas inferiores que pueden ser usadas, después, por
métodos de resolución exactos eficientes como el método de ramificación y corte [10]. La RL consiste
en identificar las restricciones complicadas, entendiendo como restricciones complicadas aquellas que
si no estuvieran en el problema, éste sería mucho más fácil de resolver. Considerando el problema de
optimización entera en forma matricial como

min cX + hY
sujeto a
AX + GY 6 b (2.28)
CX + HY 6 d
X,Y > 0, X ∈ Zn .

donde AX + GY 6 b son las restricciones complicadas, la RL con multiplicadores no negativos de

Lagrange λ del problema se define como

min cX + hY + λ (AX + GY − b)
sujeto a
(2.29)
CX + HY 6 d
n
X,Y > 0, X ∈ Z .
12 Capítulo 2.

La técnica de búsqueda tabú o “tabú search” [21] clasifica algunos movimientos (pasos de una
solución a otra) y los introduce dentro de una lista tabú. Los movimientos que se encuentran dentro de
esta lista no serán posibles de realizar. Usando determinadas restricciones en el proceso de búsqueda
de soluciones evita que el algoritmo quede atrapado en un conjunto de soluciones óptimas locales.
Es decir, ésta técnica resuelve el problema de los bucles impidiendo temporalmente movimientos que
podrían hacer volver a una solución recientemente visitada.
Los algoritmos genéticos o evolutivos [17] están inspirados en el proceso genético de adaptación de
los organismos vivos. A lo largo de generaciones las poblaciones de especies evolucionan en la natura-
leza acorde con los principios de selección natural. El método genético parte de un conjunto inicial de
soluciones a las que en cada iteración se les realizan manipulaciones y de las que se obtienen sucesivos
conjuntos de soluciones. Las manipulaciones más comunes son la selección, el cruce, la mutación y la
inversión. La selección está relacionada con la aptitud, y permite generar las sucesivas poblaciones. El
cruce consiste en sustituir algunos elementos del vector solución por los elementos correspondientes de
otro vector solución. La mutación de genes mantiene la diversidad genética de una generación de una
población a otra.
La técnica de recocido simulado [1] o en inglés “simulated annealing” pertenece a la clase de los
algoritmos aleatorios de búsqueda local que pueden ser usados para resolver problemas de optimización
NP-hard. Fue introducido [11] siguiendo una analogía con el proceso de recocido físico que era usado
para encontrar estados de baja energía de sólidos. Este método ha producido resultados interesantes en
la convergencia de los algoritmos de resolución y se ha aplicado a una gran variedad de problemas.
Capítulo 3

Aplicación del problema de cubrimiento a

la ubicación de instalaciones de bomberos
en Huesca y Teruel

3.1. Introducción
El objetivo de este capítulo es aplicar algunos modelos estudiados en el capítulo 2 al problema de
localización de instalaciones de bomberos en Huesca y Teruel (ver Anexo I). El Cuerpo de Bomberos
no sólo es responsable de la extinción de incendios en hogares, éstos atienden emergencias causadas por
la naturaleza como terremotos e inundaciones, o por el descuido o imprudencia de los ciudadanos como
accidentes y muchos incendios forestales. Además, también realizan labores de búsqueda, salvamento
y rescate. Por ello es importante tener una buena distribución de los servicios en todo el territorio,
pues un factor determinante en la efectividad del Cuerpo de Bomberos es el tiempo que tardan en
actuar (ver Anexo I). El objetivo de éste capítulo es determinar las localizaciones idóneas para ubicar
las instalaciones de bomberos. Para poder resolver computacionalmente los problemas mencionados se
usará IBM R ILOG R CPLEX R Optimization Studio 12.6.2 (CPLEX) 1 , una herramienta desarrollada
por IBM que, entre otras funciones, resuelve problemas de programación lineal y lineal entero. CPLEX
hace uso de variantes del método simplex y los métodos vistos en el capítulo 1 para resolverlos.
A continuación, se va a presentar cuál va a ser el marco de la legalidad sobre la que se va a trabajar,
establecida por las distintas leyes incluidas en el Boletín Oficial de Aragón (BOA). De acuerdo con la
LEY 1/2013, de 7 de marzo, de Regulación y Coordinación de los Servicios de Prevención, Extinción
de Incendios y Salvamento de Aragón,
Los municipios con población superior a veinte mil habitantes, deberán prestar, por sí,
asociados o a través de las distintas formas de gestión de los servicios públicos locales, el
de Prevención, Extinción de Incendios y Salvamento, sin perjuicio de que puedan solicitar
la dispensa de su prestación, en los términos establecidos en la legislación de régimen local.
Además,
Las Diputaciones Provinciales garantizarán por sí solas, o en colaboración con otras Ad-
ministraciones o entidades públicas, hasta que el Gobierno de Aragón ponga en funciona-
miento una organización propia, la prestación de los Servicios de Prevención, Extinción de
Incendios y Salvamento en aquellos municipios en los que, de acuerdo con la legislación
de régimen local, no resulte obligatoria su prestación y carezcan de Servicio propio.
Por lo tanto el territorio quedará separado en tres diputaciones provinciales y se deberá estudiar cada
provincia por separado, asegurando, a la vez, que existirá una instalación de bomberos en los municipios
con población superior a veinte mil habitantes. También deberá tenerse en cuenta que
1 [Link]

13
14 Capítulo 3.

Artículo 6. Personal operativo.

1. A los efectos de esta ley, se entiende como personal operativo de los Servicios de Preven-
ción, Extinción de Incendios y Salvamento los empleados públicos de las Administraciones
públicas aragonesas adscritos a los mismos asumiendo funciones específicas de prevención,
extinción de incendios y salvamento. [...]
Artículo 7. Bomberos voluntarios.
1. Los bomberos voluntarios son aquellas personas que prestan servicios de prevención,
extinción de incendios y salvamento de forma altruista, dentro de la estructura de cualquiera
de estos Servicios, y de manera complementaria a las funciones que, con carácter principal,
desarrolla el personal operativo profesional. No tienen la condición de personal funcionario
ni laboral. [...]
Además, el decreto por el que se regula la organización y funcionamiento de los Servicios de Prevención,
Extinción de Incendios y Salvamento de la Comunidad Autónoma de Aragón (DECRETO, 6 de octubre
de 2014, del Gobierno de Aragón) especifíca que
Artículo 9. Clasificación de los Parques de Bomberos. 1. Los Parques de Bomberos se
clasifican en:
a) Parques principales: Los parques principales son el Parque de referencia de una Zona de
Intervención. Tendrán funciones de coordinación en la prevención, capacidad de Interven-
ción y formación, así como primer escalón de mantenimiento y almacenamiento y apoyo
logístico. Estarán constituidos por bomberos profesionales [...]
b) Parques secundarios: Los parques secundarios estarán distribuidos en el territorio para
la atención inmediata de las emergencias. Estarán constituidos por bomberos profesionales
para una primera intervención, con el apoyo de bomberos voluntarios para intervenciones
complementarias [...]
c) Parques de apoyo: Son aquellas bases o parques de apoyo cuyo objetivo es la atención
de las emergencias en la isócrona de 35 minutos. Estarán constituidos por bomberos profe-
sionales, bomberos a tiempo parcial o bomberos voluntarios [...]
Los parques de apoyo tendrán la siguiente dotación mínima: Dos bomberos, un vehículo de
extinción con depósito de 500 litros. [...]
Es decir, para todo el territorio de la comunidad autónoma de Aragón deberá garantizarse un tiempo
máximo de intervención de los Servicios de Prevención de 35 minutos. En el estudio que se va a hacer a
continuación se va a determinar dónde deberían ubicarse las instalaciones. Un estudio con especialistas
en la materia debería determinar qué tipo de instalación debería ubicarse y el número de operarios
(profesionales y voluntarios) necesarios, lo que está fuera del alcance de ésta memoria. Como se ha
estimado el tiempo medio de reacción de los efectivos profesionales suele ser unos 2 minutos, quedarían
33 minutos para el desplazamiento2 . Así, se dirá que un municipio j esta cubierto si el tiempo de
desplazamiento por carretera del municipio más cercano en el que haya una instalación de bomberos
i hasta j es menor de 33 minutos. Y se llamará instalación a un parque en el que haya al menos dos
bomberos profesionales. Para simplificar el problema, el territorio de un municipio se dirá que esta
cubierto si el municipio al que pertenece está cubierto.

3.2. Estudio de la provincia de Huesca

En el año 2017, en la provincia de Huesca se contabilizaron 1563 intervenciones3 realizadas por el
Cuerpo de Bomberos de las cuales 183 correspondieron a incendios urbanos, 105 a fuegos forestales,
2 En
el caso de tener encuenta a los bomberos voluntarios, se reducirá el tiempo de desplazamiento a 30 minutos, por no
ser todo el colectivo miembros profesionales
3 [Link]

-[Link]
Problemas de cubrimiento - Karen Oliveros Félez 15

275 a salvamentos, 100 accidentes de tráfico y 900 a asistencias técnicas de todo tipo, como inundacio-
nes, escapes de gas, actuaciones invernales, limpieza de calzadas por siniestros, retirada de colmenas
de abejas y atenciones a animales. Para todos estos servicios el Cuerpo de Bomberos de Huesca cuenta
actualmente con 124 miembros profesionales, concentrados en las partes más pobladas de la provincia,
incluyendo los bomberos concentrados en la ciudad de Huesca.
En el Anexo X (Catálogo de medios y recursos) del Plan Territorial de Protección Civil de Aragón4
se observa que actualmente existen instalaciones de bomberos en los siguientes municipios5 : Huesca
(99), Almudévar (19), Ayerbe (31), Barbastro (40), Benabarre (45), Benasque (46), Biescas (50), Binéfar
(52), Boltaña (56), Castejón del Puente (69), Castejón de Sos (71), Fraga (90), Graus (95), Isábena (103),
Jaca (104), Monzón (121), Sabiñánigo (148), Sariñena (160), Villanova (188), Valle de Hecho (194).
En total son 20 instalaciones en toda la provincia de Huesca, en las que en 8 de ellas6 sólo hay efectivos
voluntarios.
Para averiguar cuántos municipios están realmente cubiertos con las instalaciones antes indicadas,
se ha implementado el problema MCLP con los datos actuales de Huesca, estableciendo como función
objetivo el número de municipios cubiertos. En primera instancia, se tendrán en cuenta todas las insta-
laciones de bomberos existentes, es decir, aquellas con y sin bomberos profesionales. Posteriormente se
considerarán sólo las estaciones con bomberos profesionales debido a que los bomberos voluntarios no
pueden ofrecer todos los servicios que podrían ofrecer los profesionales.
En ambos casos las variables xi , correspondientes a los municipios con instalaciones de bomberos
que se consideren quedan fijas, tomarán valor 1. El número de instalaciones máximas será p = 20 en el
primer caso y p = 12 en el segundo. Así, CPLEX tomará xi = 0 para el resto de variables, y el valor de
la función objetivo será el número de poblaciones cubiertas en estas condiciones.
Los parámetros ai j de la restricción 2.6 se han obtenido a partir de la matriz de tiempos de despla-
zamiento. Ésta última se ha conseguido con la herramienta VRP Solver en Excel modificada.

Figura 3.1: Hoja de excel de VRP Solver en la que se hallan las coordenadas.

VRP Spreadsheet Solver7 es un complemento de código abierto desarrollado para Microsoft Excel
por Günes Erdoǧan. Es una plataforma que permite representar, resolver y visualizar los resultados de
los problemas de rutas de vehículos (VRPs). Esta herramienta unifica Excel, GIS públicos y metaheu-
rísticos. Puede resolver VRPs de hasta 200 usuarios. En este trabajo ha sido necesario mudificar esta
4 que se puede obtener en la página web [Link]

Departamentos/Presidencia/AreasTematicas/Interior/Seguridad_proteccion_civil, accediendo al apartado

de Plan territorial de Protección Civil de Aragón
5 El número que tiene cada municipio entre paréntesis será la codificación que se ha usado en el programa CPLEX
6 Benasque, Biescas, Castejón del Puente, Castejón de Sos, Isábena, Jaca, Sariñena y Valle de Hecho.
7 Se puede obtener en la página oficial [Link]
16 Capítulo 3.

herramienta para la obtención de las coordenadas y la matriz distancias de los 202 municipios oscenses
y los 232 municipios turolenses. En la figura 3.1 se puede observar un fragmento de la hoja de excel
correspondiente al listado de los municipios de Huesca y las correspondientes coordenadas ya calcula-
das. El listado de los municipios correspondientes a las provincias de Huesca y Teruel, se han obtenido
de la página web del Instituto Nacional de Estadística. En la figura 3.2 se puede observar un fragmento
de la hoja de excel correspondiente al cálculo de las distancias entre todos los municipios de Huesca.
A la derecha quedan anotadas las combinaciones que Solver no proporciona y ha sido necesario calcu-
larlas manualmente. Nótese que, además de las distancias en kilómetros, Solver calcula los tiempos de
desplazamiento, que es el elemento que se usa para satisfacer la condición de los 35 minutos.

Figura 3.2: Hoja de excel de VRP Solver en la que se hallan las distancias y los tiempos de desplaza-
miento entre parejas de municipios.

VRP hace uso de la interfaz de programación de aplicaciones (API) de Bing Maps. Por lo tanto, para
poder obtener la matriz de tiempos de desplazamiento se ha necesitado crear una “llave” o key para que
VRP pueda comunicarse con la aplicación de Bing. De esta manera, VRP obtiene las coordenadas de
cada pueblo y, después, calcula los kilómetros por carretera reales y el tiempo de desplazamiento (según
la regulación estipulada de cada carretera) entre todas las parejas de pueblos.
Después de obtener todos los datos, se construye en Excel la matriz binaria An×m = (ai j ) asociada
con la siguiente función

=SI(prueba_logica;[valor_si_verdadero];[valor_si_falso])

y tomando el valor 1 si cumple que el valor del tiempo sea menor que el tiempo máximo, 0 en caso
contrario. A continuación, se implementa el modelo en CPLEX.

int npueblos = ...; range rpueblos = 1..npueblos;

int d[rpueblos]=...; int a[rpueblos][rpueblos]=...; int p=20;
dvar boolean local[rpueblos]; dvar boolean z[rpueblos];
maximize
sum(i in rpueblos) d[i] * z[i];
subject to {
forall(j in rpueblos)
sum( i in rpueblos )
a[i][j]*local[i]>=z[j];
sum(i in rpueblos) local[i]==p;
local[ 99 ] == 1; local[ 19 ] == 1; local[ 31 ] == 1; local[ 40 ] == 1;
local[ 45 ] == 1; local[ 46 ] == 1; local[ 50 ] == 1; local[ 52 ] == 1;
Problemas de cubrimiento - Karen Oliveros Félez 17

local[ 56 ] == 1; local[ 69 ] == 1; local[ 71 ] == 1; local[ 90 ] == 1;

local[ 95 ] == 1; local[ 103 ] == 1; local[ 104 ] == 1; local[ 121 ] == 1;
local[ 148 ] == 1; local[ 160 ] == 1; local[ 188 ] == 1; local[ 194 ] == 1;
}

Este programa necesita un fichero de datos, que se ha llamado [Link] en el que se incluyen el nú-
mero de municipios npueblos, el vector de demanda d[rpueblos], que en este caso será un vector de
unos para determinar el número de municipios cubiertos, y a[rpueblos][rpueblos] correspondiente
la matriz binaria mencionada anteriormente. Las variables correspondientes a la ubicación de instalacio-
nes se denotan por local[i]. Ejecutando el modelo, se observa que la función objetivo es 195, es decir,
se tiene que 7 municipios8 no están cubiertos. Por otro lado, si no se tienen en cuenta las instalaciones
con únicamente bomberos voluntarios y, por lo tanto, se aumenta el tiempo de desplazamiento posible
a 33 minutos, se obtiene que sólo 174 muncipios están cubiertos, quedando 28 sin cubrir9 .
En la figura 3.3 se observa que hay cinco municipios de la comarca del Sobrarbe que no están
cubiertos por ningún tipo de instalación. En Los Monegros, La Jacetania y Ribagorza, hay un territorio
muy amplio en el que sólo operan los bomberos voluntarios. A continuación, se va a hacer un estudio
aplicando los diferentes modelos para mejorar esta situación utilizando los menores recursos posibles.
En la provincia de Huesca sólo existe un municipio que supere los 20000 habitantes, la propia ciudad
de Huesca. Por lo tanto será el único municipio que por ley esté obligado a tener su propio Cuerpo de
Bomberos y por lo tanto tendrá, al menos, una instalación ubicada. Con esta excepción, tal y como se
ha planteado el problema, no existe ninguna restricción más sobre la localización de las instalaciones
de bomberos. En lo que sigue sólo se considerarán las instalaciones de bomberos profesionales y no se
tendrán en cuenta las instalaciones de voluntarios por tener una capacidad de actuación limitada.

3.2.1. Aplicación del modelo LSCP

El primer modelo de cubrimiento que se ha utilizado para resolver el problema de identificar la
ubicación de las estaciones de bomberos profesionales en la provincia de Huesca es el LSCP explicado
en el apartado 2.2.1. Para implementarlo en CPLEX se necesita el conjunto de parámetros binarios
ai j que se han obtenido en el apartado anterior. El tiempo máximo de desplazamiento se va a fijar en
33 minutos. Como no se sabe exactamente cuáles son los costes de ubicación en cada población, se
fijaran los costes ci = 1, de manera que se minimiza el número de instalaciones a ubicar. Así, el modelo
implementado, si no se tienen en cuenta las ubicaciones de las instalaciones actuales pero sí teniendo en
cuenta que en la ciudad de Huesca debería haber al menos una instalación, es:
int npueblos = ...; range rpueblos = 1..npueblos;
float coste[rpueblos]=...; int a[rpueblos][rpueblos]=...;
dvar boolean local[rpueblos];
minimize
sum(i in rpueblos) coste[i] * local[i];
subject to {
forall(j in rpueblos)
sum( i in rpueblos )
a[i][j]*local[i]>=1;
local[99]==1;
}
En este caso, la solución óptima indica que habría que ubicar 13 instalaciones10 para el cubrimiento
8 Bielsa,Fanlo, Gistaín, Palo, Plan, San Juan de Plan, Sopeira.
9 Aisa, Albalatillo, Alberuela de Tubo, Ansó, Aragüés del Puerto, Bielsa, Bonansa, Canal de Berdún, Capdesaso, Castejón
de Monegros, Fago, Fanlo, Gistaín, Jasa, Lalueza, Lanaja, Montanuy, Plan, Poleñino, San Juan de Plan, Sariñena, Sena, Torla-
Ordesa, Torre la Ribera, Valfarta, Veracruz, Villanueva de Sigena, Valle de Hecho.
10 en Ayerbe, Castigaleu, Fiscal, Fraga, Huesca, Laspaúles, Sabiñánigo, Salas Bajas, Santaliestra y San Quílez, Sariñena,

Tamarite de Litera, Tella-Sin y Puente la Reina de Jaca.

18 Capítulo 3.

Figura 3.3: Mapa comarcal de Huesca. Los municipios cubiertos por sólo bomberos voluntarios se han
pintado de color amarillo. Los municipios no cubiertos por ninguna estación de bomberos se han pintado
de color rojo

completo del territorio. Nótese que, comparando con las ubicaciones actuales, sólo se aprovecharían
cuatro de las instalaciones que ya hay instaladas. Por lo tanto, deberían desaparecer 8 de las 12 instala-
ciones existentes y se estarían desaprovechando recursos que ya existen. Sin embargo, si se fijan las 12
instalaciones de bomberos profesionales existentes y se ejecuta el modelo LSCP, se observa que el nú-
mero de instalaciones profesionales debería ser 17. Como es posible que ubicar 5 instalaciones nuevas
precise un presupuesto no disponible, lo ideal sería encontrar el equilibrio entre trasladar o suprimir el
menor número instalaciones posibles, de manera que todo el territorio quede cubierto.
Para lograr encontrar un equilibrio entre trasladar el menor número instalaciones posible y cubrir
todo el territorio, se decide que las poblaciones donde hay actualmente ubicadas instalaciones de bom-
beros tuvieran un coste de ubicación ci menor que en las poblaciones donde no existe actualmente una
instalación. En este caso, a los costes de las primeras se les ha dado el valor 0.5 y a las segundas el
valor 1. Tras ejecutar el programa, teniendo en cuenta que en Huesca debe haber una instalación, en la
Problemas de cubrimiento - Karen Oliveros Félez 19

solución óptima se observa que deberá haber ubicadas 14 instalaciones11 .

3.2.2. Aplicación del modelo MCLP

Habilitar nuevas instalaciones de bomberos o trasladarlas puede ser muy costoso. En ocasiones, es
posible que no se pueda cubrir todo el territorio con los recursos de los que se dispone, pero se puede
maximizar el territorio cubierto. Para ello utilizaremos el modelo MCLP descrito en el apartado 2.2.2.
En el apartado 3.2.1 se ha visto que para cubrir todos los pueblos, manteniendo las 12 instalaciones
ya existentes, se precisaba ubicar 5 instalaciones más. Si se dispusiera de presupuesto para sólo una o
dos instalaciones más, es interesante determinar dónde colocarlas para obtener el mayor cubrimiento del
territorio. Para ello, se fijan las variables xi = 1 correspondientes a los pueblos en los que hay instalación
y se cambia el número máximo de instalaciones por p = 13 (o p = 14 en el caso de dos instalaciones
más).
Si se dispusiera recursos para sólo una instalación de bomberos más, la ubicación idónea sería
Albalatillo, y con ella se cubrirían 11 pueblos más, por lo que en total serían 185 los pueblos cubiertos12
de 202. En el caso de que se tuvieran recursos para la ubicación de dos instalaciones más, lo idóneo
sería que se ubicaran en Albalatillo y Jasa y habría 192 pueblos cubiertos13 .

3.2.3. Aplicación del modelo LSCP-Implicit

En ocasiones, determinadas zonas son más susceptibles a desastres en los que tengan que intervenir
el Cuerpo de Bomberos y por lo tanto es posible que haya más de una llamada en una zona que está
cubriendo una sola instalación de bomberos. Esta susceptibilidad suele ir muy ligada al número de
habitantes de una zona entre otras características. Por ello, para asegurar un buen funcionamiento de
los servicios de emergencia, determinados núcleos urbanos requieren estar cubiertos por más de una
instalación.
El apartado LSCP-Implicit, descrito en el apartado 2.2.3, precisa la determinación de los niveles de
cubrimiento βk . En esta memoria se han fijado 3 niveles de cubrimiento βk donde el número mínimo de
instalaciones para cubrir completamente una zona a nivel k será αk y, en este caso, αk = k. Como hay
que ajustarse a los términos de la legalidad, en cualquiera de los 3 niveles de cubrimiento deberá cubrirse
toda la población, es decir, todos los municipios deberán poder ser atendidos en menos de 35 minutos.
En este caso, se exige a que los municipios mas poblados Huesca (99), Monzón (121), Barbastro (49),
Fraga (90) y Jaca (104) tengan una cobertura β3 , lo que implica que las correspondientes variables w jk
sean igual a 1.

int npueblos = ...; range rpueblos = 1..npueblos;

float coste[rpueblos]=...; int a[rpueblos][rpueblos]=...;
int K=...; range rnivel=1..K;
int alpha[rnivel]=...;
dvar boolean local[rpueblos];
dvar boolean w[rpueblos][rnivel];
minimize
sum(i in rpueblos) coste[i] * local[i];
subject to {
forall(j in rpueblos)
sum(k in rnivel)
w[j][k]>=1;
11 en Ayerbe, Barbastro, Benabarre, Binéfar, Boltaña, Bonansa, Fanlo, Fraga, Huesca, Sabiñánigo, Sariñena, Tella-Sin, Vi-

llanova y Puente la Reina de Jaca.

12 No se cubrirían las poblaciones: Aisa, Ansó, Aragüés del Puerto, Bielsa, Bonansa, Canal de Berdún, Fago, Fanlo, Gistaín,

Jasa, Montanuy, Plan, San Juan de Plan, Torla-Ordesa, Torre la Ribera, Veracruz y Valle de Hecho.
13 No se cubrirían las poblaciones: Bielsa, Bonansa, Fanlo, Gistaín, Montanuy, Plan, San Juan de Plan, Torla-Ordesa, Torre

la Ribera y Veracruz.
20 Capítulo 3.

forall(k in rnivel, j in rpueblos)

sum( i in rpueblos )
a[i][j]*local[i]>=alpha[k]*w[j][k];
local[99]==1; w[99][3]==1; w[121][3]==1;
w[49][3]==1; w[90][3]==1; w[104][3]==1;
}

Como en el apartado 3.2.1, ci = 1 para los municipios que no tienen ubicada una instalación y
ci = 0,5 para los que si que la tienen. Con estas condiciones, deberán ubicarse 16 instalaciones14 , de las
cuales nueve de ellas ya estarían instaladas y además de cumplir con las restricciones requeridas, cubre a
nivel β2 varias poblaciones como Binéfar que tiene 9.000 habitantes; Tamarite de Litera, Graus, Zaidín,
Binaced, Belver de Cinca, Albalate de Cinca, y Alcolea de Cinca con 2.000-1.000 habitantes; Fonz,
Ballobar, Sanmiguel del Cinca, Estadilla, Osso de Cinca, Alcampell, Almunia de San Juan, Peñalba,
Ontiñena con 1.000-500 habitantes; y San Esteban de Litera, Sena, Velilla de Cinca, Villanueva de
Sigena, Vencillón, La, Puebla de Castro, Capella, Berbegal, Pueyo de Santa Cruz, Castejón del Puente,
Candasnos, Isábena, Ilche, Azanuy-Alins, Labuerda, Alfántega, Castelflorite y Chalamera con 500-100
habitantes.

3.3. Estudio de la provincia de Teruel

En el año 2015 en la provincia de Teruel se realizaron más de 741 intervenciones15 . De ellas, 197
fueron servicios de extinción de incendios, 130 salvamentos, 166 de colaboración con otros servicios y
97 de suministro de agua. En sólo la primera mitad del año 2016 el Servicio de Prevención y Extinción
de Incendios y Salvamentos de la Diputación de Teruel realizó 434 intervenciones16 . Para realizar todos
estos servicios hay unos 100 efectivos profesionales en toda la provincia. La Diputación de Teruel posee
19 instalaciones de bomberos, en cuatro de las cuales sólo hay efectivos voluntarios. En el Anexo X del
Plan Territorial de Protección Civil mencionado en el apartado 3.2 se observa que actualmente existen
instalaciones de bomberos en los siguientes municipios: Alcañiz (13), Andorra (24), Calamocha (48),
Camarena de la Sierra (52), Cantavieja (55), Híjar (107), Loscos (122), Mosqueruela (142), Rubielos
de Mora (178), Samper de Calanda (181), Teruel (191), Torres de Albarracín (204), Utrillas (212),
Valdealgorfa (215) y Valderrobres (219). Hay instalación de bomberos con sólo efectivos voluntarios en
los municipios Albarracín (9), Bronchales (43), Orihuela del Tremedal (153) y Villarluengo (228).
Como en el apartado 3.2 se va a implementar el problema MCLP para analizar la situación actual
con las instalaciones de bomberos profesionales antes indicadas. También se implementará el MCLP
incluyendo las instalaciones de bomberos con sólo efectivos voluntarios, aunque en el resto de apartados
no se tendrán en cuenta. Los modelos utilizados son los presentados en el apartado 3.2, modificando el
fichero de datos, que ahora incluye los correspondientes a la provincia de Teruel.

14 en Alcolea de Cinca, Almudévar, Ayerbe, Barbastro, Benabarre, Boltaña, Fraga, Huesca, Lanaja, Laspaúles, Sabiñánigo,

Tella-Sin, Villanova, Yebra de Basa, Puente la Reina de Jaca y Vencillón.

15 [Link]

los-bomberos-de-la-diputacion-de-teruel-realizaron-mas-de-740-intervenciones-en-2015
16 [Link]

bomberos-diputacion-teruel-realizan-mas-400-servicios-lo-que-va-ano/
Problemas de cubrimiento - Karen Oliveros Félez 21

Figura 3.4: Mapa comarcal de Teruel. Los municipios cubiertos por sólo bomberos voluntarios se han
pintado de color amarillo. Los municipios no cubiertos por ninguna estación de bomberos se han pintado
de color rojo

La solución óptima proporcionada por CPLEX indica que de los 236 municipios de Teruel, 24 pue-
blos17 no estarán cubiertos por ninguna instalación de bomberos profesionales, unas 2680 personas. Si
se incluyen en el estudio las instalaciones sin efectivos profesionales, seguirían sin cubrirse 20 pue-
blos18 .
En la figura 3.4 se puede observar que sólo hay un municipio sin cubrir que no esté agrupado,
Abejuela, en la comarca Gúdar-Javalambre. El resto de municipios sin cubrir están agrupados en grupos
de tres a ocho municipios. Se puede observar, que la comarca menos cubierta es la Comunidad de Teruel,
en la que trece municipios en distintas agrupaciones no están cubiertas.
A continuación, se va a hacer un estudio de la ubicación de instalaciones de bomberos como se
17 Ababuj, Abejuela, Aguaviva, Aguilar del Alfambra, Almohaja, Alobras, Allepuz, Camañas, Camarillas, Castellote, El
Cuervo, Gúdar, Jabaloyas, Jorcas, Lidón, Miravete de la Sierra, Las Parras de Castellote, Peracense, Ródenas, Seno, Tormón,
Veguillas de la Sierra, Villar del Salz y Visiedo.
18 Los antes mencionados excepto Jabaloyas, Peracense, Ródenas y Villar del Salz
22 Capítulo 3.

ha hecho en el apartado 3.2. En la provincia de Teruel sólo existe un municipio que supere los 20000
habitantes, la propia ciudad de Teruel. Por lo tanto será el único municipio que por ley esté obligado
a tener su propio Cuerpo de Bomberos y por lo tanto una instalación ubicada. Como en el apartado
anterior, en lo que sigue, sólo se considerarán las instalaciones de bomberos profesionales.

3.3.1. Aplicación del modelo LSCP

Como en el apartado 3.2.1, para resolver el problema de identificar la ubicación de las estaciones de
bomberos profesionales se va a implementar el modelo LSCP con tiempo de desplazamiento máximo
33 minutos.
En primer lugar, el objetivo es minimizar el número de instalaciones a ubicar, estableciendo to-
dos los coeficientes ci = 1 ∀i. Si no se tienen en cuenta las ubicaciones de las actuales instalaciones
de bomberos y exigiendo que en la ciudad de Teruel haya una instalación de bomberos, la solución
óptima proporcionada por CPLEX indica que la solución óptima sería instalar 14 instalaciones19 . De
esta manera, sólo se aprovecharían 2 instalaciones de las 15 que ya hay. Si se exige ubicar una instala-
ción en los municipios donde ya existe una, la nueva solución óptima indica que habría que ubicar 20
instalaciones20 .
Para lograr encontrar equilibrio entre trasladar el menor número instalaciones posible y cubrir todo
el territorio, se va a proceder como en el apartado 3.2.1. Tras ejecutar el programa, teniendo en cuenta
que en Teruel debe haber una instalación, en la solución óptima se observa que deberá haber ubicadas
15 instalaciones21 , 7 de las cuales ya estarían ubicadas.

3.3.2. Aplicación del modelo MLCP

Como en el apartado 3.2.2, existen ocasiones que no es posible cubrir todo el territorio con los
recursos de los que se dispone. En el apartado anterior, el modelo LSCP ha revelado que se necesitarían
5 instalaciones más además de las que ya se dispone para cubrir todo el territorio. Suponiendo que
sólo hay recursos para una o dos instalaciones más, el número máximo de instalaciones p será 16 en el
caso de obtener recursos para ubicar una instalación más, o 17 en el caso de obtener recursos para dos
instalaciones adicionales.
En el primer caso, ubicando la instalación en Cañada Vellida se cubrirían 8 municipios más y que-
darían sin cubrir 16 municipios22 . En el segundo caso, ubicando las instalaciones en Ababuj y Santa
Eulalia se conseguiría cubrir 14 municipios más y quedarían sin cubrir 10 municipios23 .

3.3.3. Aplicación del modelo LSCP-Implicit

Como en el apartado 3.2.3 se van a considerar tres niveles de cubrimiento βk . En Teruel los muni-
cipios con más de 5.000 habitantes son Teruel, Alcañiz y Andorra, por lo tanto, se va a exigir que en
estos núcleos haya una cobertura β3 . Además, como lo idóneo sería trasladar el menor número de ins-
talaciones posibles, fija ci = 1 si el municipio i no tiene ubicada actualmente una instalación y ci = 0,5
en otro caso. Con estas condiciones se deberían ubicar 17 instalaciones24 , 10 de las cuales ya estarían
19 en Aguaviva, Albalate del Arzobispo, Cantavieja, Huesa del Común, Jorcas, Libros, Manzanera, Monreal del Campo,
Montalbán, Nogueruelas, Royuela, Santa, Eulalia, Teruel y Valjunquera.
20 en Ababuj, Abejuela, Alcañiz, Alobras, Andorra, Calamocha, Camarena de la Sierra, Cantavieja, Foz-Calanda, Híjar, Los-

cos, Mosqueruela, Rubielos de Mora, Samper de Calanda, Santa Eulalia, Teruel, Torres de Albarracín, Utrillas, Valdealgorfa
y Valderrobres.
21 en Alcorisa, Calamocha, Cantavieja, Fuentespalda, Híjar, Loscos, Manzanera, Monteagudo del Castillo, Moscardón, Mos-

queruela, Santa Eulalia, Teruel, Utrillas, Valdealgorfa y Villel.

22 Abejuela, Aguaviva, Almohaja, Alobras, Castellote, El Cuervo, Gúdar, Jabaloyas, Miravete de la Sierra, Las Parras de

Castellote, Peracense, Ródenas, Seno, Tormón, Veguillas de la Sierra y Villar del Salz
23 Abejuela, Aguaviva, Alobras, Castellote, El Cuervo, Jabaloyas, Las Parras de Castellote, Seno, Tormón y Veguillas de la

Sierra.
24 en Alcorisa, Andorra, Calamocha, Camarena de la Sierra, Cantavieja, Fuentespalda, Híjar, Loscos, Manzanera, Montea-

gudo del Castillo, Mosqueruela, Rubiales, Santa Eulalia, Teruel, Torres de Albarracín, Utrillas y Valdealgorfa.
Problemas de cubrimiento - Karen Oliveros Félez 23

instaladas. Además, se conseguiría una cobertura β2 para las siguientes poblaciones: Alcorisa y Calanda
con 4.000-2.000 habitantes; Albalate del Arzobispo, Hijar y Mas de las Matas con 2.000-1.000 habi-
tantes; Aguatón, Alba, Alloza, Ariño, Berge, Cañizar del Olivar, Castel de Cabra, Castelserás, Ejulve,
Estercuel, Fonfría, Foz-Calanda, Gargallo, Libros, La Mata de los Olmos, Molinos, Muniesa, Oliete,
Los Olmos, Pozondón, Torremocha de Jiloca, Urrea de Gaén y Villel con menos de 1.000 habitantes.
Bibliografía

[1] E. Aarts and J. Korst. Selected topics in simulated annealing. In C. C. Ribeiro and P. Hansen,
editors, Essays and surveys in metaheuristics, Operations Research/Computer Science Interfaces
Series, pages 1–37. Springer, 2002.
[2] E. Balas and A. Ho. Set covering algorithms using cutting planes, heuristics, and subgradient
optimization: a computational study. In M.W. Padberg, editor, Combinatorial Optimization, pages
37–60. Springer, 1980.
[3] M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali. Linear Programming and Network Flows. Wiley-
Interscience, Hoboken, NJ, third edition, 2005.
[4] R. Church and C. ReVelle. The maximal covering location problem. Papers of the Regional
Science Association, 32:101–118, 1974.
[5] M. Conforti, G. Cornuéjols, and G. Zambelli. Integer Programming Models. Springer, London,
UK, first edition, 2014.
[6] J. R. Current and J. E. Storbeck. Capacitated covering models. Environment and Planning B:
Planning and Design, 15(2):153–163, 1988.
[7] J. Etcheberry. The set-covering problem: A new implicit enumeration algorithm. Operations
Research, 25(5):760–772, 1977.
[8] R. Z. Farahani, N. Asgari, N. Heidari, M. Hosseininia, and M. Goh. Covering problems in facility
location: A review. Computers & Industrial Engineering, 62(1):368–407, 2012.
[9] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-
Completeness. W. H. Freeman and Company, 1979.
[10] M. Guignard. Lagrangean relaxation. Top, 11(2):151–200, 2003.
[11] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science,
220(4598):671–680, 1983.
[12] J. Krarup and P.M. Pruzan. The simple plant location problem: survey and synthesis. European
Journal of Operational Research, 12(1):36–81, 1983.
[13] G. Laporte, N. Stefan, and F. S. da Gama. Location Science. Springer, London, UK, first edition,
2015.
[14] C. E. Lemke, H. M. Salkin, and K. Spielberg. Set covering by single-branch enumeration with
linear-programming subproblems. Operations Research, 19(4):998–1022, 1971.
[15] L. A. N. Lorena and F. B. Lopes. A surrogate heuristic for set covering problems. European
Journal of Operational Research, 79(1):138–150, 1994.
[16] A. T. Murray, D. Tong, and K. Kim. Enhancing classic coverage location models. International
Regional Science Review, 33(2):115–133, 2010.

25
26

[17] C. Reeves. Genetic algorithms. In F. Glover and G. A. Kochenberger, editors, Handbook of Me-
taheuristics, volume 57 of International Series in Operations Research and Management Science,
pages 55–82. Springer, 2003.

[18] C. ReVelle and K. Hogan. The maximum reliability location problem and α-reliable p-center
problem: Derivatives of the probabilistic location set covering problem. Annals of Operations
Research, 18(1):155–173, 1989.

[19] R. Roth. Computer solutions to minimum-cover problems. Operations Research, 17(3):455–465,

1969.

[20] A. Sassano. On the facial structure of the set covering polytope. Mathematical Programming,
44(1-3):181–202, 1989.

[21] R. S. Sexton, B. Alidaee, R. E. Dorsey, and J. D. Johnson. Global optimization for artificial neural
networks: A tabu search application. European Journal of Operational Research, 106(2-3):570–
584, 1998.

[22] C. Toregas and C. ReVelle. Optimal location under time or distance constraints. Papers in Regional
Science, 28(1):133–144, 1972.

[23] C. Toregas and C. ReVelle. Binary logic solutions to a class of location problems. Geographical
Analysis, 5(2):145–155, 1973.

[24] C. Toregas, R. Swain, C. ReVelle, and L. Bergman. The location of emergency service facilities.
Operations Research, 19(6):1363–1373, 1971.

[25] W. L. Winston. Operations Research: Applications and Algorithms. Duxbury Press, 2003.
Anexos

27
Anexo I: Motivación

La falta de bomberos en Huesca triplica los 35 minutos de respuesta que impone la ley | Noticias de Aragón en [Link]

1 de 3

29
30 Anexos

La falta de bomberos en Huesca triplica los 35 minutos de respuesta que impone la ley | Noticias de Aragón en [Link]

2 de 3
Problemas de cubrimiento. Aplicación. - Karen Oliveros Félez 31

La falta de bomberos en Huesca triplica los 35 minutos de respuesta que impone la ley | Noticias de Aragón en [Link]

3 de 3
32 Anexos

14/3/2018 Un incendio arrasa varias viviendas de un bloque en Murillo de Gállego | Noticias de Zaragoza provincia en [Link]

ZARAGOZA PROVINCIA

Un incendio arrasa varias viviendas de un bloque

en Murillo de Gállego
Los ocho inquilinos que había en ese momento salieron ilesos, pero el edi cio de dos plantas ha quedado
seriamente dañado. La alcaldesa denuncia los elevados tiempos de respuesta de los bomberos, que llegaron
a los 50 minutos de darse la alerta

Actualizada 14/03/2018 a las 12:31 Rubén Darío Núñez Huesca

Etiquetas Huesca Murillo de Gállego Zaragoza provincia Comarca Hoya de Huesca Rubén Darío Núñez

Incendio en un edi cio de Murillo de Gállego

Un virulento incendio ha arrasado esta pasada madrugada varias viviendas de un bloque de dos plantas en la
localidad de Murillo de Gállego. Afortunadamente no ha habido que lamentar daños personales, pero los
desperfectos materiales son considerables ya que se teme incluso por la estructura del edi cio, compuesto
por diez apartamentos. 

La alcaldesa de Murillo y diputada de Podemos Aragón, Marta de Santos, ha agradecido la labor de los
bomberos de Ejea de los Caballeros, de El Burgo de Ebro y de Huesca, así como la de los voluntarios de
Protección Civil de la Hoya de Huesca, pero ha criticado los elevados tiempos de respuesta ya que ha

[Link] 1/4
Problemas de cubrimiento. Aplicación. - Karen Oliveros Félez 33

14/3/2018 Un incendio arrasa varias viviendas de un bloque en Murillo de Gállego | Noticias de Zaragoza provincia en [Link]

asegurado que los primeros profesionales llegaron en 50 minutos. "Los tiempos de actuación son básicos
para minimizar los daños", ha subrayado.

El fuego se declaró en el edi cio Peña Rueba, ubicado junto a la carretera A-132. La primera alerta se dio al
112 a las 21.38, aunque se había iniciado mucho antes ya que todo indica que se originó en la chimenea de
una de las viviendas de la planta superior, "y cuando se dieron cuenta, el incendio ya se había extendido hacia
la cubierta", ha asegurado Marta de Santos.

El 112 movilizó al parque de bomberos de la DPZ con base en Ejea de los Caballeros, ubicado a 60
kilómetros, y también al servicio del Ayuntamiento de Huesca, a unos 40 kilómetros. No obstante, los
primeros en llegar fueron los voluntarios de la Hoya de Huesca desde la cercana localidad de Ayerbe con un
vehículo ligero, que echaron agua sobre el edi cio a la espera de que llegaran los profesionales. Los
bomberos acudieron dos camiones, una autoescala, un camión nodriza y varios vehículos ligeros. A las
22.51 se dio por controlado el fuego y a partir de la 1.00 de la madrugada se dedicaron a labores de
desescombro, según ha informado la DGA y la DPZ. 

En el momento del incendio había varias viviendas ocupadas con ocho personas, entre ellas un niño de 9
años. El 112 desplazó una ambulancia de modo preventivo pero aunque no tuvo que atender a ningún herido.
Algunos de los afectados se realojaron en un hostal y otros en casas de vecinos del pueblo "que se han
volcado totalmente", ha agradecido la alcaldesa. Además, a primera hora de la mañana el área de Servicios
Sociales de la Comarca de la Hoya de Huesca ha contactado con el Ayuntamiento para ofrecer su ayuda
también a los afectados. 

[Link] 2/4
34 Anexos

14/3/2018 Un incendio arrasa varias viviendas de un bloque en Murillo de Gállego | Noticias de Zaragoza provincia en [Link]

Los bomberos de la DPZ, inspeccionando los daños del edi cio. Ayuntamiento de Murillo de Gállego

Los bomberos de Ejea y los técnicos municipales están inspeccionado esta mañana el estado del edi cio "y
parece que van a tener que quitar peso a la estructura porque el tejado se está hundiendo", ha explicado la
alcadesa. Una de las viviendas ha quedado totalmente calcinada y las adyacentes también están seriamente
dañadas. Los inquilinos de los apartamentos han podido retirar parte de sus pertenencias.

Marta de Santos se ha mostrado aliviada porque el edi cio, por fortuna, estaba aislado. "Si llega a pasar en
cualquier otra casa del pueblo donde están unas pegadas con otras, arde entero con los tiempos de
intervención que tenemos aquí". Y en este sentido ha lamentado que pese a pertenecer a la comarca de la
Hoya de Huesca, el 112 activó primero a los bomberos de la DPZ en lugar de la capital oscense. "Es un
protocolo que no tiene mucha lógica porque actúan primero los que están más lejos", ha señalado.

[Link] 3/4
Problemas de cubrimiento. Aplicación. - Karen Oliveros Félez 35

Figura 5: Noticia del Periódico de Aragón del viernes, 29 de septiembre de 2017

Figura 6: Noticia del Diario Altoaragón del viernes, 29 de septiembre de 2017

36 Anexos

Figura 7: Noticia del Heraldo de Aragón del viernes, 29 de septiembre de 2017

Anexo II: Siglas

PEM: problema de optimización lineal entero mixto.

RPEM: relajación del problema de optimización lineal entero mixto.

PC: problema de cubrimiento.

LSCP: Location Set Covering Problem, en castellano problema de cubrimiento de conjuntos.

MCLP: Maximal Covering Location Problem, en castellano problema de cubrimiento maximal.

LSCP-Implicit: Location Set Covering Problem-Implicit, en castellano problema de cubrimiento

de conjuntos implícito.

CLSCP: Capacitated Location Set Covering Problem, en castellano problema de cubrimiento de

conjuntos con fraccionamiento.

PSCP: Probabilistic Set Covering Problem, en castellano problema de cubrimiento de conjuntos

probabilístico.

Clase P: conjunto de problemas de decisión para los que existe algoritmo polinomial para su
resolución.

Clase NP: nondeterministic-polynomial problems. Conjunto de problemas de decisión cuyo tiem-

po de resolución es polinomial no determinista.

Clase NP-hard: nondeterministic-polynomial hard problems. Conjunto de problemas de decisión

duros.

RL: Relajación Lagrangiana.

37