A Cable Layout Model For Telecommunication Distribution Networks

Transcript

A Cable Layout Model for Telecommunication Distribution Networks Andrew B. Philpott and Stephen Miller Department of Engineering Science University of Auckland New Zealand [email protected] A bstract We present an integer linear programming model arising in capacity planning for local access telecommunications networks. This model assists planners in designing local access networks which will meet customer demand at least cost. We present some simple cases in which optimal solutions to the model can be found by dynamic programming, and a general instance which is solved using linear programming and branch-and-bound. 1 In trod u ction A voice-telephone network is typically modelled in two parts. Every telephone subscriber is connected to some local exchange by a circuit which usually consists of twisted-pair copper cable. This part of the network is called the local loop. The local exchanges are connected together in some network topology usually through tandem exchanges. This part of the system is often called the trunk network. In this paper we address a challenging problem arising in the design and di­ mensioning of the local loop network. Local access design problems have received increasing attention in the operations research literature (see e.g. [1]) due to the large savings in capital cost th at can be made by exploiting recent advances in combinatorial optimization. While recognizing the importance of optical and radio transmission media, we shall restrict attention in this paper to networks made up entirely of copper twisted pair. In copper cable local-access systems customers are connected to local exchanges by a tree network with a two-level structure. Groups of between 400 and 800 subscribers are connected to an intermediate cross-connection cabinet which is itself connected to the local exchange. The problem of simultaneously determining an optimal network layout and capacity allocation for all the subscribers served by a local exchange is too difficult to solve as a single model since some exchanges serve up to 25,000 subscribers. An alternative modelling approach is to decouple 157 the design of the distribution part of the local access network (which serves the subscribers from the cross-connection cabinet) from that of the feeder part of the network (which supplies the cross-connection cabinets from the local exchange). The distribution problem becomes: “given the location of a cross-connection cabinet and a set of subscribers to be connected to it determine a cable layout and a capacity allocation to connect all subscribers at least cost”. The feeder problem becomes: “given the location of a local exchange and a set of cross-connection cabinets to be connected to it determine a capacity allocation and cable layout to connect all cabinets to the exchange at least cost” . Observe that on the feeder side we must also determine where the cabinets are to be located, and which subscribers each cabinet should serve. ( For a more detailed discussion of the feeder problem and its relationship to the distribution problem see [2].) The remainder of this paper deals with the distribution problem of determining the optimal layout of copper twisted pair cable from a cross-connection cabinet at a fixed known location, to a region of subscribers who are to be served by it. The twisted pairs which serve these subscribers are supplied in cable of varying sizes (typically 50 pairs per cable). This cable is placed in PVC ducts which are buried in the ground. At every pair of sections a pillar is erected and the cable sheathing is cut to expose the pairs within. A number of these are extracted and connected to twisted pair drop lines which connect to the telephones in the dwellings on the pair of sections. 2 A one-dim ensional m odel A simple model of this distribution system can be devised when the cross-connection cabinet is located at one end of a long road of, say, S subscribers. The ^ pillars for these subscribers have already been installed and the trenches have been dug. The expense of doing this is independent of how the cable is laid out and so we can regard it as a sunk cost. We let the pillars be indexed by p = 1 , 2 ,. .. , Suppose th at fines are supplied in 50-pair cable. It remains to partition the pillars into groups, each of which is supplied by a single 50-pair cable. We seek to do this so as to minimize the cost of the installation. In order to construct a partition having least cost, we need to identify the costs associated with allocating a single 50-pair cable to a set of pillars. This cost will be made up of three components. First there is a capital cost associated with the cable and ducting. Secondly there is a shortage cost of not meeting demand for fines should this be higher than forecasted. Finally there is a repair and maintenance cost which depends on the number of pillars that the cable serves. We shall deal with simple models for estimating these in the following sections of the paper. First observe th at without loss of generality we can restrict attention to cables serving contiguous pillars. For each p < q let C( p , q) be the total cost of allocating a 50-pair cable to the q—p contiguous pillars, indexed by p, p + 1 ,. . . , 9—1Given these costs the partition problem becomes a simple Wagner-Whitin lot-sizing problem which can be solved by dynamic programming, where the recursion for 158 V( q) , the minimum cost of supplying service to pillars 1 ,2 ,..., q — 1 is: V(q) = mjn{K(p) + C(p, ?)}. 3 C apital C osts The capital component of C( p , q) is given by the distance d ( q — 1) from the cabinet to pillar q — 1 multiplied by the cost (c) per unit length of cable and cost ( D ) per unit length of PVC ducting. The cost of ducting is not entirely straightforward to estim ate since up to four 50-pair cables can occupy a single duct. If there are a large number of cables occupying a duct then this factor only really becomes im portant at the far end of the road where a single cable occupies the duct, and for a road requiring many cables we may allocate a ducting cost of ^ per m etre to each cable, giving total capital cost of C k {p , q) = (c+ ^ ) d ( q - l ) . (A more accurate representation of ducting cost can be made by adding an extra state k denoting the number of cables used. This gives the dynamic programming recursion (for capital costs only) V( q, k) = m in { V ( p , k - 1) + cd(q - 1) + D \ j ] d ( q - 1) - D \ ^ ± ] d ( p - 1)}.) p (This formula is straightforward to derive from the forward Kolmogorov equations.) The probability of a single fault occurring in workers in an interval (t , t + dt) is Yln=\ Pn(t)nPrdt. Thus the expected discounted cost CV (r, M ) of repairs of workers over a planning horizon [0,T] is given by rT n M Cw( r, M ) = / Fe~m £ pn(t)n/3rdtJo n=l If there are n working pairs then M — n spare pairs remain to be used. The probability th at one of these spares will be required by a new subscriber in the interval (t , t + dt) is Pn(t)(N ~ n)Xdt, and the probability that it will have failed by t is (1 — e~^rt). Thus the expected discounted cost of repairing faulty spares in (0, T) is .7 Cs ( r , M ) = / M—1 Fe~m ( 1 - e"'3' 1) £ P*(t)(N - n ) \d t. n=0 J° If we assume as above th at each pillar is allocated circuits, then the total expected discounted repair cost for a cable allocated to pillars p ,p -f 1 , . . . , q — 1 is 9-1 Sfl r =p q~P Cf(p,9) = £ {< V (r, L— J) + Cs (r, 'Sfl I-p Given the formulae above we may compute C(p, q) = CK (p, q) + CG(p, q) + CF(p, q) and apply the dynamic programming recursion (1). Observe that Cc{p, q) depends only on q —p which means that savings may be made by computing these quantities in advance. 161 6 A Full Layout Model Although the one-dimensional layout model outlined above will only really be ap­ plicable in a small number of cases it gives us the necessary tools to develop a layout model for cable distribution in two dimensions. We suppose th at we are given a network of streets in which P pillars have been installed to which cable must be reticulated from a cross-connection cabinet at a fixed known location. The cable will lie in ducting placed in trenches which are dug on each side of each street. As for the one-dimensioned model the cost of the trenching is a sunk cost. Given a subset of pillars we may compute the cost of supplying this subset with cable which travels from the pillars back to the cross-connection cabinet. This cost can be computed using the formula C(p, q) defined above for the one-dimensional problem with the convention th at d(q — 1) is interpreted as the distance from the furthest pillar in the subset along a path back through the trenching to the crossconnection cabinet. In most cases the cable will have to cross under some of the streets to reach the cabinet. The cost of trenching for these road crossings is not a sunk cost, so we would like to be able to include their cost in an optimization that is carried out. In practice we can postulate a set of I possible places where roads might be crossed and compute a set of shortest paths from the pillars to the cabinet which choose different combinations of road crossings. We assume th at each trench crossing the road can accommodate at most h cables. We note as an aside th at some improvements to the ducting cost estimate of j can be made in the two-dimensional model since it is unlikely in a two-dimensional model th at all cable leaving the cabinet will share the same trench, so trenches will in general contain fewer ducts. In practice the optimal solution often places no more than four cables in any trench. This allows a more accurate representation of ducting cost by approximating the average number of cables which share a duct at distance x from the cabinet by f ( x ) = d24^ x:2, where d is the distance from the cabinet to the furthest pillar. Thus the ducting cost allocated to a cable of length L is the integral of y from 0 to L giving a total capital cost of C k {p , q) = cL + D ( i To formalize how one might construct an optimization model for layout with road crossings, let j = 1,2, . . . , n index possible layouts for a single cable. Thus j = 5, say, might represent a cable following a path using several road crossings and servicing pillars p , p + 1 , . — 1. We denote the cost of the layout j by Cj. Here Cj = CK { p , q J ) + CG(p,q) + CF(p,q) where C g (p , q) and Cp{ p , q) are the same for every j which services p , p + l , . - ., <7—1, and C k (p , q, j ) now depends on j to account for the different paths that the cable might travel back to the cabinet. Let if cable j serves pillar p; ^PJ • f1 0, 1, otherwise, _/ 1, ^ ca,ble j crosses the road at location i; ,J 1 0, otherwise, and define C,- to be the cost of constructing a road crossing at location i. 162 The problem of laying out cable at least cost can now be formulated as a zero-one integer linear programming problem. ILP: minimize y ^ c 7-s7- + E g * j * n subject to apjxj ~ ^ p = 1 , 2 ,. .. , P, i=i n ^ kjXj ~ < 0, i = 1 ,2 ,... ,7, i=i e {o,i}. (2) (3) Here Xj = 1 in an optimal solution if cable layout j is included in the plan, and Z{ = 1 if a road crossing at location i is included in the plan. The first set of constraints (2) state th at each pillar must be visited by exactly one cable, and the second set of constraints (3) state th at if a cable crosses the road at i then we must incur the cost of trenching across the road, and this trench can carry at most h cables. Zero-one integer programming problems can be extremely difficult to solve. Most commercial codes use some form of branch-and-bound algorithm, which ef­ fectively enumerates all the possible zero-one choices of the variables. However without some form of control over the branching strategy generic codes can take a very long time to reach an optimal solution. The ZIP package designed by Ryan [3] is a suite of Fortran subroutines which allow the user a large amount of control over the optimization and branch-and-bound search strategy to the extent that custom software for any special class of zero-one integer programming problems can be designed in the ZIP environment in such a way as to exploit any structure present in the problem class. We have constructed a purpose-built code for solving ILP using ZIP subroutines. Since large instances of ILP are very difficult to solve without user intervention, our code allows the user to intervene and restrict the choice of road crossings after viewing the solution to the linear programming relaxation. Having set the road crossings, the model computes an integer solution to ILP with these road crossings. This solution is then used as an incumbent to give an initial bound for a branchand-bound search. W ith this strategy our code can solve problems with up to 200 pillars to optimality in about an hour of CPU time on a DEC Alpha workstation. 163 An example of a subdivision and the cable layout produced by our code is shown in Figure 1 below. Figure 1: Optimal cable layout for a typical subdivision. Key: £ cross-connection cabinet road crossing used pillars served by the same cable A ck now ledgm ents We would like to acknowledge the contributions of John Davenport, Bernadette Giacaman, and Jason Laws to this research. R eferences [1] C.Jack, S-R. Kai, A. Shulman, Design and Implementation of an Interactive Optimization System fo r Telephone Network Planning , Interfaces 23 (1993) pp 35-48. [2] A.B. Philpott, Capacity planning models for telecommunications distribution system s , Presented at ANZIAM Conference, Busselton WA, February 6, 1995. [3] D.M. Ryan, ZIP - A Zero-One Integer Programming Package fo r Scheduling , Report C.S.S. 85, A.E.R.E. Harwell, Oxfordshire (1980). 164