Protecting local access telecommunications networks: Toward a minimum-cost solution |
| |
Authors: | M J O’Sullivan C G Walker M L O’Sullivan T D Thompson A B Philpott |
| |
Affiliation: | (1) Department of Engineering Science, University of Auckland, Auckland, New Zealand |
| |
Abstract: | The problem of designing fibre-optic networks for local-access telecommunications generates (at least) three non-trivial subproblems.
In the first of these subproblems one must determine how many fibre-optic cables (fibres) are required at either end of a
street. In the next subproblem a minimum-cost network must be designed to support the fibres. The network must also provide
distinct paths from either end of the street to the central exchange(s). Finally, the fibre-optic cables must be placed in
protective covers. These covers are available in a number of different sizes, allowing some flexibility when covering each
section of the network. In this paper we describe a dynamic programming (DP) formulation for finding a minimum-cost (protective)
covering for the network (the third of the subproblems). This problem is a generalised set covering problem with side constraints
and is further complicated by the introduction of fixed and variable welding costs. The DP formulation selects covers along
each arc (in the network), but cannot exactly model the fixed costs and so does not guarantee optimality. We also describe
an integer programming (IP) formulation for assessing the quality of the DP solutions. The cost of the networks constructed
by the IP model is less than those designed using the DP model, but the saving is not significant for the problems examined
(less than 0.1%). This indicates that the DP model will generally give very good solutions. Furthermore, as the problem dimensions
grow, DP gives significantly better solution times than IP. |
| |
Keywords: | Telecommunications network Network design Dynamic programming Integer programming |
本文献已被 SpringerLink 等数据库收录! |
|