The network redesign problem for access telecommunications networks

The network redesign problem attempts to design an optimal network that serves both existing and new demands. In addition to using spare capacity on existing network facilities and deploying new facilities, the model allows for rearrangement of existing demand units. As rearrangements mean reassigning existing demand units, at a cost, to different facilities, they may lead to disconnecting of uneconomical existing facilities, resulting in significant savings. The model is applied to an access network, where the demands from many sources need to be routed to a single destination, using either low-capacity or high-capacity facilities. Demand from any location can be routed to the destination either directly or through one other demand location. Low-capacity facilities can be used between any pair of locations, whereas high-capacity facilities are used only between demand locations and the destination. We present a new modeling approach to such problems. The model is described as a network flow problem, where each demand location is represented by multiple nodes associated with demands, low-capacity and high-capacity facilities, and rearrangements. Each link has a capacity and a cost per unit flow parameters. Some of the links also have a fixed-charge cost. The resulting network flow model is formulated as a mixed integer program, and solved by a heuristic and a commercially available software.