Problema de localización con barreras

Abstract

In location problems, the distance functions that model the travel distance between the elements of the problem play a fundamental role in the adequacy or fidelity of the theoretical problem to the real problem considered. Think, for example, of problems in the design of connective networks (to this type of problems belongs, to mention some realworld problem, the routing of pipelines on ships), often the sections of these networks must obey a particular structure or pattern, the distance functions are then convenient for calculating the distance between the nodes of the network. Another real feature of location problems, which is of great importance in achieving good modeling, is the constraint of the feasible solution space. This restriction is due to the presence in the environment where the problem is considered of bodies or obstacles, called barriers in the literature, that do not allow travelling or passing through them. The barrier distance functions are, in this case, the way to obtain the adequacy of the theoretical problem to the real problem. The object of study of the present End of Master Project are the mentioned barrier distance functions and their application to the location problems. The first chapter gives a brief summary of the elementary distance measures used in the modeling of location and transport problems, as well as their basic properties. The barriers distances, central concept of this End of Master Project, appear in the second chapter, where special attention is paid to the case of polyhedral barriers and where the main known results in the art are shown. More precisely, these distances are introduced in the chapter to address the problem of the minimum rectangular path in the presence of hyperparallelepiped complexes that perform as barriers in any real space of finite size. Extensions of the known results for the treatment of this problem in the planar case and new original methods for their exact resolution are the main contribution of this chapter and of the work in general. In the third chapter a particular case of the location problem with barriers is treated: the median problem in rectangular metric and in the context of hyperparallelepipeds that act as barriers in any real space of finite size. The methods developed in the second chapter are the basis for the construction of the new algorithms that solve such problem, which are presented in this chapter. The computational performance tests of the algorithms of the second and third chapters are collected in the fourth and final chapter.

En los problemas de localización, las funciones de distancia que modelan la distancia de viaje entre los elementos del problema juegan un papel fundamental en la adecuación o fidelidad del problema teórico al problema real considerado. Piénsese, por ejemplo, en los problemas de diseño de redes conectivas (a este tipo de problemas pertenece, por citar algún problema del ámbito real, el enrutamiento de tuberías en barcos), a menudo los tramos de estas redes deben de obedecer a una determinada estructura o patrón, las funciones de distancia son entonces convenientes para el cálculo de la distancia entre los nodos de la red. Otra característica real de los problemas de localización, de gran importancia a la hora de conseguir un buen modelado de los mismos, es la restricción del espacio de soluciones factibles. Dicha restricción se debe a la presencia en el entorno donde está considerado el problema de cuerpos u obstáculos, denominados barreras en la literatura, que no permiten el viaje o paso a través de ellos. Las funciones de distancia con barrera son, en este caso, la forma de conseguir la adecuación del problema teórico al problema real. El objeto de estudio del presente Trabajo de Fin de Máster son las mencionadas funciones de distancia con barreras y su aplicación a los problemas de localización. En el primer capítulo se ofrece un resumen suscinto de las medidas de distancia elementales usadas en el modelado de los problemas de localización y transporte, así como de sus propiedades básicas. Las funciones de distancia con barreras, concepto central del Trabajo de Fin de Máster, aparecen en el capítulo segundo, donde se presta especial atención al caso de barreras poliédricas y se muestran los principales resultados conocidos en la materia. Más concretamente, estas distancias son introducidas en el capítulo para abordar el problema del camino rectangular mínimo en presencia de complejos de hiperparalelepípedos barrera en cualquier espacio real de dimensión finita. Extensiones de resultados conocidos para el tratamiento de este problema en el caso plano y nuevos métodos originales para su resolución exacta son la principal contribución de este capítulo y del trabajo en general. En el capítulos (sic) tercero se trata un caso particular del problema de localización con barreras: el problema de la mediana en métrica rectangular y en el contexto de hiperparalelepípedos que actúan como barreras en cualquier espacio real de dimensión finita. Los métodos desarrollados en el segundo capítulo son la base para construir los nuevos algoritmos que resuelven dicho problema y que se presentan en este capítulo. Las pruebas de rendimiento computacional de los algoritmos de los capítulos segundo y tercero se recogen en el cuarto y último capítulo.