Modelos para localização e conexão de facilidades baseados em fluxos

Abstract

Com o presente trabalho apresentamos alguns modelos para o problema de localização e conexão de facilidades. O problema de localização de facilidades consiste em encontrar os melhores locais de instalação de determinados serviços de modo a satisfazer o pedido de determinados clientes. O problema da conexão das facilidades determina a melhor forma de ligar as facilidades entre si. Neste trabalho consideramos os dois problemas em simultâneo. Utilizamos vários modelos, os modelos de fluxo multiproduto com uma mercadoria por cliente, fluxo multiproduto com uma mercadoria por facilidade e ainda modelos com base nas restrições de eliminação de sub-ciclos de Miller-Tucker-Zemlin. Testamos computacionalmente programas desenvolvidos para cada um dos modelos referidos usando o software Xpress e, finalmente, apresentamos as nossas conclusões relativamente aos resultados obtidos nos vários modelos utilizados tendo em conta o tempo computacional e a qualidade da solução obtida através das relaxações lineares dos modelos apresentados.

In this work we present models for the facility location problem and the facility connection problem. The facility location problem is to find the best places to install specific services to meet the request of certain customers. The problem of connecting the facilities is to determine the best way to connect the facilities between them. In this work we consider both problems simultaneously. We use several models, multicommodity flow models with a commodity per customer, multicommodity flow models with a commodity per facility and also models based on the well know Miller-Tucker-Zemlin subtour elimination constraints. We tested computationally programs developed for each of these models using the software Xpress and finally, we present our findings regarding the results obtained in the various models used considering the computation time used by the programs and the quality of the linear relaxation solutions of the models.