Resumen

El análisis de los problemas de localización es un área fértil de investigación desde principios de siglo. El primer modelo de localización fue propuesto por Alfred Weber en 1909 [1], y domino por muchos años la literatura. Sin embargo, el área unificada de estudio denominada "Localización de Instalaciones" emerge hasta el año 1960. La investigación de Hakimi [2], publicada en 1964, estableció resultados importantes en la teoría de localización y generó un gran interés entre los investigadores.

Los problemas de localización, en su forma más general, se pueden describir de la siguiente manera. Un conjunto de clientes distribuidos espacialmente en un área geográfica demandan un cierto producto o servicio. La demanda de los clientes debe ser cubierta por una o varias instalaciones. Las instalaciones pueden operar en un marco de cooperación o competencia dependiendo del bien o servicio que sea requerido por el cliente. El proceso de decisión establece dónde se deben ubicar las instalaciones en el territorio deseado, tomando en cuenta los requerimientos de los clientes y las restricciones geográficas.

Dentro de los problemas localización se puede identificar tres elementos esenciales. Las instalaciones, que denotan un conjunto de objetos que serán localizados para proporcionar un servicio o producto. Las localizaciones, que se refieren al conjunto de posibles puntos para situar instalaciones. Finalmente, los clientes, que son los usuarios de las instalaciones que demandan ciertos servicios o productos [3].

El término instalación se utiliza para denotar una gran variedad de objetos para los cuales debemos determinar cierto espacio y posición, con el fin de optimizar su relación con respecto a otros objetos ya existentes. Algunos ejemplos de objetos en la teoría de localización son: almacenes, plantas productivas, escuelas, hospitales, centros comerciales, edificios públicos, etc. Las propiedades principales que caracterizan a las instalaciones son: su número y tipo.

En varios modelos de localización, el número de instalaciones está fijado a priori. En el caso más simple sólo se puede localizar una instalación. A este tipo de problema se le denomina "problema de instalación simple". En el caso general, el modelo considera simultáneamente varias instalaciones. A este tipo de problema se le denomina "problema multi-instalaciones".

Otra propiedad importante para las instalaciones está dada por su tipo. Esta propiedad especifica las características tales como capacidad, servicio y consideraciones sobre su estructura. En casos simples, los problemas de localización requieren que las instalaciones sean idénticas para poder proporcionar el mismo servicio o producto. Los modelos también se pueden diferenciar de acuerdo a servicio sencillo y multi-servicios, basándose en la capacidad de la instalación para proveer uno o varios tipos de servicios o productos. Algunos problemas de localización admiten instalaciones donde se considera que la capacidad de las instalaciones es ilimitada, mientras que otros buscan la mejor ubicación con una producción limitada. Por lo tanto, los problemas de localización también pueden clasificarse como capacitados o no capacitados.

El segundo elemento esencial para los modelos de localización, es el lugar físico en donde se va ubicar la instalación. El conjunto de ubicaciones es comúnmente llamado espacio solución y se puede representar de manera continua, discreta o de red (ver por ejemplo, [4], [5]):

• Espacio Discreto: cuando se especifica una lista de posibles lugares para ubicar instalaciones. En este se caso proporciona flexibilidad ya que es posible incorporar características de tipo geográficas y económicas al modelo.
• Espacio Continuo: son problemas que se consideran en el espacio Euclideano. El caso más típico, considera un espacio euclideanó de dos dimensiones.
• Representación de Redes: Para varias aplicaciones en las que se consideran servicios públicos y privados se consideran problemas de localización en los que se te tiene que operar utilizando una cierta infraestructura de red (red carretera, red vial, red ferroviaria, red aeroportuaria, oleoductos, etc.), que comúnmente se representa mediante un grafo. Los problemas de redes pueden ser continuos o discretos, dependiendo de sí las estaciones de servicio pueden ser ubicadas en las aristas o en los vértices del grafo que representa la infraestructura de red considerada. Cuando un modelo se encuentra definido mediante una representación de red, el grafo puede tener tomar distintas formas: grafo dirigido, grafo no dirigido, árbol [3].

Los problemas de localización surgen de la necesidad de localizar centros para la satisfacción óptima de la demanda de un conjunto de clientes. La palabra cliente se usa para denotar objetos que requiere accesibilidad a un servicio o demandan un producto. Al tratar de analizar los problemas de localización, se debe de interactuar con clientes, por lo tanto es necesario conocer su distribución, demanda y comportamiento.

• Por distribución se asume que el cliente se distribuyen uniformemente o que se localizan en un punto específico o en los vértices de una red.
• En el caso de la demanda, a cada cliente se le asigna un valor que expresa la cantidad de servicio que requiere. La demanda puede representar la cantidad de producto o servicio requerido por un usuario o por un área o región geográfica. En ambos casos puede que no se conozca con certeza.
• La última característica del cliente es su comportamiento. En algunos casos, el cliente es libre de escoger desde cuál instalación desea ser servido, llevando a la pregunta; ¿el cliente siempre va a la instalación más cercana o utiliza otros criterios y preferencias para escoger la instalación? También, los clientes se pueden comportar de manera individual o grupal [3].

Un problema clásico de localización es el problema de la p-mediana. Este problema en su forma más simple se caracteriza por el tipo de instalaciones a ubicar, su localización y la relación con el cliente. Las instalaciones a ubicar no tienen restricciones de capacidad. El número de instalaciones se fija de acuerdo a un parámetro p, y ofrecen el mismo tipo de servicio. Los clientes requieren de una cantidad fija de servicios o bienes y por comodidad siempre escogen ser servidos por la instalación más próxima a su ubicación. La relación con las localizaciones se expresa a través de una función de distancia que representa la trayectoria más corta en la red para alcanzar la localización [3].

En esta tesis se propone un algoritmo heurístico que proporciona soluciones factibles para el problema estudiado. El algoritmo se basa en la metodología GRASP, se consideran dos fases: una fase de construcción y otra de mejora.

Se efectúan pruebas computacionales para evaluar el comportamiento del método. Los resultados obtenidos fueron satisfactorios ya que el algoritmo proporciona soluciones de buena calidad.

Como se revisó en los capítulos anteriores, el problema de la p-mediana se presenta en diversos campos de estudio y puede aplicarse para diferentes áreas; sin embargo, el hecho de que no se haya encontrado una fórmula matemática para obtener una solución factible en tiempo polinomial minimiza la posibilidad de utilizarlo en casos donde se necesite la respuesta óptima dentro del conjunto de resultados factibles en poco tiempo. Por lo tanto la utilización de métodos heurísticos está justificada dada la dificultad para resolver el problema, ya que le problema de la p-mediana es un problema NP-Duro. Por tal motivo el trabajo se enfocó desde un principio en la estrategia de algoritmos voraces aleatorizados o algoritmos GRASP con la finalidad de encontrar soluciones factibles a este problema de localización en el menor tiempo posible para satisfacer la restricción de tiempo inherente a los problemas de localización.

El algoritmo GRASP propuesto se describe y ejemplifica en el capítulo 4; sin embargo, para demostrar su funcionalidad se desarrolló un programa computacional que obtenga soluciones factibles para el problema de la p-mediana implementando el algoritmo GRASP propuesto. Este programa computacional fue creado por medio del lenguaje de programación C, cuya estructura se basa en las dos principales fases de este tipo de algoritmos: la fase de construcción del conjunto de soluciones factibles y la fase de mejora.

Índice de contenido

Capítulo 1. Introducción (archivo pdf, 95 kb)

Capítulo 2. El problema de la p-mediana (archivo pdf, 94 kb)

Capítulo 3. Metodología GRASP (archivo pdf, 117 kb)

Capítulo 4. GRASP aplicado al problema de la p-mediana (archivo pdf, 157 kb)

Capítulo 5. Experiencia computacional (archivo pdf, 127 kb)

Capítulo 6. Conclusiones (archivo pdf, 56 kb)

Referencias (archivo pdf, 78 kb)

Hernández Ramírez, C. M. 2004. Diseño de un algoritmo heurístico para el problema de localización p-mediana. Tesis Licenciatura. Ingeniería Industrial. Departamento de Ingeniería Industrial y Textil, Escuela de Ingeniería, Universidad de las Américas Puebla. Mayo. Derechos Reservados © 2004.