Model and heuristic for a generalized access network design problem |
| |
Authors: | Mateus Geraldo R. Franqueira Raphaël Valéry L. |
| |
Abstract: | The generalized access network design problem consists of finding a topology, capacity assignment and routing that minimize the sum of costs to connect every pair of remote unit and its central node specified by the telecommunication company. We consider an integer programming formulation with a partial multicommodity structure. We analyze some aspects and extensions of the proposed model and we introduce a heuristic based on Lagrangian relaxation and the subgradient method. We report computational results for a set of randomly generated test problems. They include networks with up to 300 nodes and show that even problem instances defined in small networks can be extremely difficult problems. The heuristic generates effective and acceptable designs from the practical point of view. We compare our heuristic with a commercial code. This revised version was published online in June 2006 with corrections to the Cover Date. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |