Este artigo discute o problema de redimensionamento de uma rede de telefones públicos urbanos visando melhorar a lucratividade do negócio sujeito a exigências da Agência Nacional de Telecomunicações. O estudo tem um viés pragmático, dando ênfase à obtenção de uma boa solução usando meios ao alcance de empresas. Peculiaridades do problema conduzem à formulação de um modelo de localização e atribuição com cobertura mínima que, em escala real, assume um porte que inviabiliza sua solução exata por métodos convencionais de programação inteira mista. É, então, examinada a viabilidade de se obter uma boa solução sem recurso a métodos complexos e de difícil implementação. Discutem-se formas de redução e particionamento do problema, sua solução por interrupção prematura de algoritmo de ramificação e limitação (branch-and-bound) e, também, por meio de uma heurística simples e de fácil implementação. São apresentados os resultados de um ensaio computacional que indicam a viabilidade de aplicação do modelo no ambiente industrial.

This paper discusses the problem of downsizing urban public telephone networks to improve the profitability of this business under the regulation imposed by the Agência Nacional de Telecomunicações (Brazilian National Telecommunication Agency). This study presents a pragmatic approach emphasizing the production of a good solution for companies. Peculiarities of the problem lead to the formulation of a location-allocation model with minimal coverage constraints which, in actual scale, is too large for exact solution by means of conventional mixed integer programming methods. This leads to examining the feasibility of obtaining a good solution avoiding the use of complex methods of difficult implementation. Possible ways of reducing and partitioning the problem are discussed as well as their solution by means of premature interruption of a branch and bound algorithm and also by means of a simple and easy to implement heuristics. Results of a computational test are presented and indicate the feasibility of industrial applications of the model.