Node placement and sizing for copper broadband access networks

We consider a node placement and sizing problem that arises in certain types of broadband access architectures, such as ADSL and FTTC. We consider three variants of the problem that become progressively more restrictive, to capture realistic planning concerns and to produce solutions that have desirable practical attributes. A distinguishing feature of the problem is a constraint that limits the distance between each customer and the placed node that is assigned to serve it. We present a dynamic programming algorithm to solve the two most practical variants of the problem, and we provide computational results for both realistic and randomly generated test problems.