DECCO's current handling of the network involves the following manually performed operations: keeping records on all request routings; reconfiguring the network in an evolutionary way by inserting configuration changes at frequent intervals. If a computerization and optimization of these procedures could be accomplished, then the following could occur: (1) there might be significant cost-savings to the Government, even if only a few percent of the total cost were saved; (2) re-optimizations, due to changes in tariffs, could be (3) the effects of proposed tariff changes could be analyzed (4) the locations of inefficient sections or connections of the network could be determined more systematically. 1.3 The Solution Method Because of the nature of the Telpak tariff, direct terminal-toterminal connections could not minimize the cost of routing requests. There are significant bulk savings when request routes or sections of routes are combined into groups of 60 and 240. In addition, since cost as a function of number of combined circuits is not in a closed form and, moreover, is non-linear, the optimization problem could not be handled by presently available mathematical programming methods. the size of the network compounded the complexity of the problem. view of these factors, the following general decisions were made: a) Heuristic methods would be used throughout. b) Lastly, In The resulting program would be tested on smaller subproblems that could be more easily manipulated at reasonable computer cost. The specific method of solution used the following steps: 2) Find the shortest spanning tree of this initial set of 250 3) Decrease cost by decreasing the detour ratios** of these re- 4) Configure, at minimum cost, the remaining 1383 cities and 5) Decrease cost by introducing express trunks (long-distance, filled or very nearly filled D trunks) via another heuristic re-routing algorithm. (BYPASS) 6) Decrease cost by consolidating uneconomical links via still * See Appendix A for definitions and properties. **Detour Ratio of a Request airline distance of request _no. of mi. in request rt. through network 1.4 Problem Outputs The main outputs containing the problem solution are as follows: (See Appendix D for sample printouts.) 1. The network links, their respective circuit fills, and their Telpak breakdown (C's, D's, Ixc's). A link is a unique direct connection between any two nodes and is assumed to travel in a straight line between the nodes. 2. 3. The route of each request, listed by means of the links used. The total network cost (TOTCST), calculated from the Additional useful constants of the solution are discussed in Section 4. 1.5 Summary of Results The complete problem containing 1633 cities and 5552 requests was configured by a FORTRAN IV computer program developed and run on IBM 360/91 and /95 equipment. (Initial development runs were made on a UNIVAC 1108.) The complete program took about 23 hours of CPU time accumulated over 44 separate runs. A maximum of 1,234,040 bytes of core storage were required for any one run. (See 5.0 for complete results.) The number of required wire-miles configured were 9,345,396, and cost of the configuration was $3,528,318 per month rental charge. This yields a cost per required wire mile of $0.3775. The miles travelled by the circuits in the configuration were 11,314,383 which yields a cost per travelled wire-mile of $0.3118. The overall detour ratio (the travelled wire-miles divided by the required wire-miles) was 1.211. This means that the average circuit travelled a 21 percent greater distance than the direct point-to-point distance. Although the cost per required wire-mile is clearly the best indicator of the effectiveness of the algorithm, the data now collected under the present manual system does not permit that number to be calculated for the manually-obtained results. The only computed data available from the present manual system that is approximately equivalent are that 11,965,323 travelled circuit miles were configured at cost per travelled wire-mile of $0.3153. This number is approximately the same as that achieved by the computed configuration. The cost of the approximately equivalent manual configuration was $3,772,701.25 or somewhat more than the computed configuration. However, the manual configuration included a small number of multi-point circuits (circuits with more than two terminations) which were not included in the computed configuration. In addition, the total manual configuration includes an extra 7,308,729 travelled miles of GSA circuits not configured in the computer problem (and not included in the cost above). The total configuration problem thus is about 60 percent larger than actually configured by computer. It may be that the least economical circuits configured by the computer program might have had the benefit of the use of bulk trunks had the GSA portion of the network been included. In summary, an heuristic optimization program has been successfully run for a network of an extremely large size. A program for this size network has rarely if ever been attempted before. The inclusion of this program in the operational activities of DECCO is possible, but a systems analysis of DECCO data flow and operations must be accomplished, and a step-by-step conversion procedure designed, before installation can be achieved. 2.0 THE KEY TABLES In carrying out the solution method outlined in Section 1.3 and generating the outputs of Section 1.4, four very important tables of information are initiated and manipulated. The City and Request Tables contain the bulk of the input data. During the course of the program the Request, Link, and Route Tables collect the current network solution information. The final values in these last three tables contain the optimal route and link information. The final network cost is always calculated from the final Link Table circuit fills and the rate structure. (See Table 1.) These tables will now be described. 2.1 The City Table (LOCTAB) The given information for each city (node) consists of a four letter identification code (devised and used by DECCO) and a pair of integer geographic coordinates expressed in miles. Each city record in the table is five words long and contains: 2.2 The Request Table (REQLST or WREQ) The given information for each request consists of the coded names for the two terminal cities and the number of wires* (sub-voice Each request record is eight words long and grade circuits) required. 4. D Airline distance between Cities A and B, calculated by the Pythagorean Theorem and rounded up twice according to the procedure spelled out in the F.C.C. tariff regulations. 5. Detour Ratio (Calculated) 6. Working word used during the program 7. 8. Number of links in the request route (from program) Pointer to first word of request route in Route Table Note that REQLST is an integer array equivalenced to the real array WREQ so that the proper mode (integer or real) could be used at various points in the FORTRAN program. Also note that words 7 and 8 of a record contain the final output information necessary for reading the Route Table (See Figure 1 and Section 2.4). 2.3 The Link Table (LNKTAB) The Link Table is one of the two key output tables of the problem. It always contains the current information on the links chosen for the network routing configuration. The record for each link contains the following seven words: *In the final version of the program there are 12 wires per voice-grade circuit. This constant is stored in NWIRE. |