El capítulo 1 es de introducción, y en él se resaltan algunas de las debilidades que presentan los modelos de localización continua existentes en la literatura y se marcan los objetivos de la tesis.

El capítulo 2 aborda el problema de la estimación de distancias de viaje reales mediante la utilización de funciones distancia inducidas por normas. Los estudios empíricos realizados demuestran que la norma l_2b, una generalización de la norma euclídea, es competitiva con la norma l_p ponderada, función esta última que ha sido sugerida por la mayoría de los investigadores como la mejor función predictora de distancias. Dependiendo de la región geográfica objeto de estudio una de las norma puede dar mejores resultados que la otra. También se estudia el problema de la selección del conjunto de datos que se utiliza para la estimación de los parámetros de las funciones predictoras. Los estudios ponen de manifiesto la importancia de elegir un buen conjunto de datos y que una manera de conseguirlo es considerar un conjunto que tenga ciudades distribuidas por toda la región y que represente la densidad de las ciudades en la región.

El capítulo 3 trata el problema de la descomposicón de polígonos (sin y con agujeros poligonales) en polígonos convexos mediante diagonales, esto es, sin introducir vértices adicionales. Este problema surge en Localización cuando la región donde se debe ubicar el centro es aproximada por poligonales; el resultado es un polígono, quizás con agujeros poligonales, que no puede ser descrito a través de un conjunto de restricciones, por lo que se hace necesaria su descomposición en conjuntos más sencillos, representables analíticamente. Los polígonos convexos no sólo son representables de forma muy sencilla mediante un conjunto de restricciones lineales, sino que además tienen muy buenas propiedades desde el punto de vista de la optimización. En el capítulo se presentan algoritmos rápidos e implementables, que ofrecen descomposiciones cuyo cardinal está acotado con respecto al cardinal de una descomposición óptima. También se presenta un procedimiento para la eliminación de diagonales no esenciales, y que es aplicable a cualquier descomposición por diagonales del polígono.

En el capítulo 4 se presenta el Análisis de Intervalos como herramienta para la resolución de problemas de Localización Continua. Además de hacer una revisión de las técnicas de Análisis de Intervalos que se emplean en la resolución de problemas de optimización, se presentan nuevos tests de eliminación de cajas no prometedoras diseñados expresamente para problemas bidimensionales, como los problemas de Localización. Asimismo, se establece la convergencia teórica de los algoritmos que utilizan, entre otros, los nuevos tests de eliminación. El capítulo también muestra cómo se pueden utilizar las técnicas del Análisis de Intervalos para la resolución de problemas perturbados y para la obtención de regiones casi-óptimas.

El capítulo 5 persigue dos objetivos. Por un lado presenta un modelo para la localizaicón de centros no deseados, más general y realista que los modelos existentes en la literatura. La idoneidad de la función objetivo para medir el grado de respulsión de los ciudadanos frente a la ubicación del centro es validada a través del estudio concreto del caso hipotético de ubicación de un vertedero en la Región de Murcia, mediante la realización de una encuesta a través de Internet. Tomando como base ese modelo, se realizan estudios computacionales encaminados a determinar la eficacia de los distintos tests de eliminación descritos en el capítulo anterior, y que es el segundo objetivo del capítulo. Los resultados demuestran que los nuevos tests diseñados para problemas bidimensionales consiguen acelerar la convergencia del algoritmo considerablemente. Por otra parte, otros mecanismos que para otro tipo de problemas de optimización suelen acelerar la convergencia (como el test de concavidad y el paso de Newton) tienen el efecto contrario cuando son aplicados a problemas de localización.
 

1.1. Introducción.....1
1.2. Algunas críticas.....3
1.3. Sumario.....5

2.1.Introducción.....9
2.1.1.El problema.....9
2.1.2.Algunas definiciones sobre distancias.....10
2.1.3.Algunas funciones predictoras de distancias en la Literatura.....14
2.1.4.Objetivos.....18
2.2. Propiedades de las funciones $l_{k,p,\theta }$ y $l_{b_1,b_2,\theta }$.....20
2.3.Criterios de ajuste y métodos de estimación de los parámetros.....33
2.4.Comparación entre las funciones $l_{k,p,\theta }$ y $l_{b_1,b_2,\theta }$.....36
2.5.La selección del conjunto de datos.....44
2.6.Conclusiones y líneas futuras de investigación.....54

3.1.Introducción.....57
3.1.1.Definiciones.....57
3.1.2.El problema.....62
3.1.3.Objetivos.....65
3.2.Descomposición de polígonos sin agujeros.....66
3.2.1.Algoritmos de descomposición.....66
Generación de un polígono convexo.....66
Algoritmos.....72
Modificación de los algoritmos para el caso de polígonos cuasi-in-simples.....74
Dependencia del vértice inicial.....78
3.2.2.Eliminación de diagonales no esenciales.....79
3.2.3.Estudios computacionales.....84
Problemas test.....84
Resultados computacionales.....85
Comparación con el algoritmo de Hertel y Mehlhorn.....89
3.3.Descomposición de polígonos con agujeros.....91
3.3.1.Descomposición mediante caminos.....91
Esquema general del algoritmo AguCam.....91
El trazado de diagonales.....95
El procedimiento Generar_Caminos.....101
3.3.2.Descomposición mediante absorción.....106
3.3.3.Eliminación de diagonales no esenciales.....109
3.4. Conclusiones y líneas futuras de investigación.....112

4.1.Introducción.....115
4.2.Definiciones previas y Aritmética de Intervalos.....118
4.2.1.Notación.....118
4.2.2.Aritmética de intervalos.....120
4.2.3.Funciones inclusión.....122
4.2.4.Diferenciación automática.....127
4.3.Algoritmo prototipo y posibles especificaciones.....129
4.3.1.Algoritmo prototipo.....129
4.3.2.Subdivisión.....130
4.3.3.Selección de la nueva caja.....133
4.3.4.Criterios de parada.....135
4.4.Tests de eliminación y mecanismos de aceleración.....137
4.4.1.Tests y mecanismos generales.....138
Test del punto medio.....138
Test de factibilidad.....139
Test de monotonía.....141
Test de concavidad.....141
El paso de Newton.....142
4.4.2.Nuevos tests.....147
El test de la mejor esquina.....149
El test de monotonía sobre la frontera.....150
El test de reducción.....152
4.4.3.Orden de aplicación de los distintos tests.....154
4.4.4.Otros mecanismos de aceleración.....155
4.5.Convergencia.....157
4.6.Analogías y diferencias con respecto a los métodos BSSS y GBSSS.....168
4.7.Otras aplicaciones del Análisis de Intervalos en Localización.....171
4.7.1.Problemas perturbados.....171
4.7.2.Regiones $\epsilon $-óptimas.....175
4.8.Conclusiones y líneas futuras de investigación.....178

5.1.Introducción.....181
5.2.El modelo.....184
5.3.Validación del modelo.....189
5.3.1.La encuesta.....189
5.3.2.Análisis de los resultados.....195
5.4.Resolución del modelo mediante Análisis de Intervalos.....204
5.4.1.Estudio de los tests generales.....207
5.4.2.Estudio de los nuevos tests.....214
5.4.3.Estudio de la subdivisión.....220
5.5.Estudio de la sensibilidad.....222
5.6.Conclusiones y líneas futuras de investigación.....225

Chapter 1 is an introduction. We point out some of the weaknesses of the continuous locations models in the literature, and we enumerate the aims of the Ph.D.

Chapter 2 deals with the problem of estimating travel distances by norm functions. Empirical studies show that the l_2b-norm, an extension of the Euclidean norm, is competitive with the weighted l_p-norm, which has been proposed by many researches as the most suitable distance predicting function. Depending on the geographical region considered, either norm may be significantly better than the other. We also investigate how the selection of the data set representing the network of the region affects the ability of the distance predicting function at predicting distances. Through an empirical study it is shown that the selection of the data set dramatically affects the accuracy of the predictions. To obtain a suitable data set it is important to choose a good sample size, and a more  important point, the cities should be chosen so that they are distributed all over the region and represent the density of the cities in the region.

Chapter 3 is concerned with the problem of decomposing a polygon (without or with polygonal holes) into convex polygons by diagonals, that is, without adding new vertices. This problem arise in Location when the region where we have to locate the new facility is approximated by polygonal lines; as a result, we obtain a polygon, maybe with polygonal holes, which cannot be written through analytical constraints; that is why we need to decompose it into simpler sets. The most appropriate kind of sets into which decompose the polygon is into convex polygons, for both their easy analytical writing and good optimization properties. In this chapter we present quick and easy-to-implement algorithms, which produce partitions whose inefficiency in terms of the number of pieces is bounded with respect to the optimum. A procedure which removes the inessential diagonals of a partition by merging the polygons whose union remains a convex polygon is also presented.

In chapter 4 we present Interval Analysis as a tool for solving continuous location problems. Interval Analysis techniques for Global Optimization are revised, and new discarding tests of non-promising boxes, designed for bidimensional problems (e.g. location problems), are presented. Furthermore, we prove the convergence of the algorithms which use, among others, the new discarding tests. Finally, we show how Interval Analysis techniques can be used to solve perturbed problems and to obtain quasi-optimal regions.

The first aim of chapter 5 is to present a continuous location model for siting a non-noxious undesirable facility within a geographical region. The model is more realistic than other undesirable facility location models in the literature. The suitability of the objective function at measuring the repulsion of the inhabitants to the location of the facility is validated with the study of the hypothetical location of a garbage dump in the Autonomous Region of Murcia, carried out with a public opposition survey through Internet. Considering this model, we have carried out empirical studies to investigate the efficiency of the discarding tests presented in chapter 4, which is the second aim of this chapter. The results show that the new discarding tests may speed up the convergence of the algorithms considerably. Other accelerating devices which have proved to be very useful in other kind of optimization problems (such as the concavity test or the Newton step) do not seem to be useful when applied to location problems.