Implementación de un Algoritmo para Ubicar el Centro de una Red en Problemas de Localización

Resumen: La investigación de operaciones es la ciencia que brinda soporte a problemas de toma de decisiones que surgen en diversos ámbitos industriales. En particular, una de las areas de gran interés tanto práctico como científico es el de los problemas de localización. Un problema de localización típico tiene que ver con dónde ubicar/construir instalaciones para brindar un determinado tipo de servicio. El problema se modela normalmente como una red, los nodos corresponden a clientes y/o puntos potenciales de ubicación de las instalaciones, y los arcos (que unen a estos nodos) corresponden a las relaciones entre dichos puntos. Este artículo trata el problema de cómo ubicar el centro absoluto en una red, el cual consiste en encontrar un punto en la red cuya distancia al nodo más lejano es mínima. En este trabajo se realiza una implementación del algoritmo de Dvir y Handler, el cual es uno de los métodos existentes más eficientes para resolver este problema. El propósito del trabajo es ilustrar la operación del algoritmo y mostrar su eficiencia al resolver instancias de tamaño mayor a las reportadas originalmente por Dvir y Handler.

Abstract: Operations research is regarded as a scientific approach to decision-making problems arising in a number of industrial environments. In particular, location problems have become one of the most interesting and widely-applicable areas from both the practical and academic standpoint. One of the typical location problems deals with the issue of where to locate or build facilities so as to efficiently deliver a specific service. The problem is modeled as a network, where nodes are associated to customers or potential facility location sites, and arcs (joining pair of nodes) correspond to relationships between these nodes. This paper addresses the problem of locating the absolute center in a network. The problem may be stated as finding a point having a minimal distance to the farthest node in the network. In this work, an implementation of the Dvir-Handler algorithm, which is one of the most successful methods for this type of problems, is presented. This problem arises in diverse applications of facility location. The purpose of this work is both to illustrate how the method works and to corroborate its efficiency when tested on instances of considerably larger size than those reported by Dvir and Handler.