A DECOMPOSITION ALGORITHM FOR LOCAL ACCESS TELECOMMUNICATIONS NETWORK EXPANSION PLANNING
成果类型：
Article
署名作者：
BALAKRISHNAN, A; MAGNANTI, TL; WONG, RT
署名单位：
Massachusetts Institute of Technology (MIT); Nokia Corporation; Nokia Bell Labs; AT&T
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.43.1.58
发表日期：
1995
页码：
58-76
关键词：
摘要：
Growing demand, increasing diversity of services, and advances in transmission and switching technologies are prompting telecommunication companies to rapidly expand and modernize their networks. This paper develops and tests a decomposition methodology to generate cost-effective expansion plans, with performance guarantees, for one major component of the network hierarchy-the local access network. The model captures economies of scale in facility costs and tradeoffs between installing concentrators and expanding cables to accommodate demand growth. Our solution method exploits the special tree and routing structure of the expansion planning problem to incorporate valid inequalities, obtained by studying the problem's polyhedral structure, in a dynamic program which solves an uncapacitated version of the problem. Computational results for three realistic rest networks demonstrate that our enhanced dynamic programming algorithm, when embedded in a Lagrangian relaxation scheme (with problem preprocessing and Ideal improvement), Is very effective in generating good upper and lower bound;: Implemented on a personal computer, the method generates solutions within 1.2-7.0% of optimality. In addition to developing a successful solution methodology for a practical problem, this paper illustrates the possibility of effectively combining decomposition methods and polyhedral approaches.