The Link Table is alphabetized on Cities A and B for purposes of program searches of this table. 2.4 The Route Table (ROUTAB) The Route Table is the second of the two key outputs of the problem. It consists entirely of pointers to the links in the Link Table that are in each route of a request. This indirect addressing scheme uses word 7 in the Request Table for the length of the request route (in links) and word 8 of that table for a pointer to the first word of that route in the Route Table (See Figure 1). Figure 1 Indirect Addressing Scheme for Route of a Request 3.0 THE ALGORITHMS The solution to this problem involves the sequential running of six programs. The first one (PREPRO) is a program that selects from the 1633 cities and 5552 requests a sub-problem of 250 cities. The five remaining programs (PASS1, ADDREQ, BYPASS, PASS2, and PASS3) are linked by a simple MAIN program. These five programs call upon an additional twenty-one subroutines to perform all the computations needed. A run-time generated restart capability was added to accommodate the long running time needed (22.8 hours of running time for the entire problem on the 360/91,95). Whenever a restart was implemented, magnetic tapes were used to store the current key tables. 3.1 Choosing a Subproblem (PREPRO) The programs PASS1, BYPASS, PASS2, and PASS3 were developed and tested on subproblems of the large problem. In order to form meaningful subproblems, the 1633 cities were ordered according to their required number of circuit-miles. This number was determined for each city (node) by calculating the circuit-miles (number of circuits x airline distance) for each request and then summing the required circuit-miles for all requests terminating at that city. Then for a problem with some number of chosen cities, only those requests were picked that had both terminal cities chosen. Table 2 shows the percent of total circuitmiles considered in each subproblem. PREPRO accomplished Step 1 in the solution method of Section 1.3. As a measure of the fraction of the network contained in each subproblem, the following quantity was calculated: # of Circuit-miles of Included Requests % Circuit-Miles = x 100 # of Circuit-miles of All Requests It includes the circuit-miles of only those requests which can be routed entirely within the subproblem network. It was decided to use a network of 250 cities as a subproblem to start with in the final solution. The MAIN program initializes the City and Request Tables by reading in the given city and request data. It also reads in four variable constants required by the programs. These constants are: XMDR, NOKC, XSIZE, and NWIRE. Their functions will be described later. The rest of MAIN is used to sequentially invoke the programs PASS1, BYPASS, PASS2, and PASS3. 3.3 First Network and First Optimization (PASS1) PASS1 contains three distinct segments to accomplish Steps 2 and 3 in the solution method of Section 1.3. These segments are: 3. Addition of links by decreasing detour ratios of requests. 3.3.1 Construction of the Shortest Spanning Tree: The initial network is established by linking the 250 city subproblem by a shortest distance spanning tree formed from the complete graph. The method used is essentially the one outlined in reference [1], Construction B, and uses the property that every node is connected to its closest neighbor node. One starts the construction by marking an arbitrary city (the first city in the City Table) 'in' the network and the rest of the cities 'out' of the network. At each iteration the closest 'out' city to the set of 'in' cities is found and is connected to its closest 'in' city. This newly established link is then sorted into the Link Table alphabetically and the 'out' city marked 'in'. This procedure terminates when all the cities have achieved an 'in' status. Searching through the 'in' cities was minimized by a judicious use of the minimum distance values found in each iteration. See Figure 2 for a sample construction. 3.3.2 Routing Requests Over the Spanning Tree: This part of PASS1 uses the shortest spanning tree properties that (a) there is only one path between any pair of cities and that (b) every node is reachable from every other node. (See Appendix A) Requests are routed over the entire tree by repeated tracings of chains** in the tree, each such tracing starting from a different root city. A sufficient number of chains are considered to have been traced when all requests have been given paths through the tree. The particular root city chosen for each tracing is always the one with the largest number of unrouted requests for which this city is an end point. This choice maximizes the possible number of requests that can be routed via each tracing. Starting at a root city, the program finds all chains in the spanning tree originating from that root city. This procedure finds the only route through the spanning tree between any two cities on a chain. *See Appendix A for definition and properties. **The word 'chain' is used interchangeably with 'path' throughout A chain may include a route or be included by a route. this paper. If any route so found is associated with a real request for service as defined by its terminal points, then the initial routing of the request has been determined. The program goes to a different root city when all chains from that root city have been traced. (See Table 3 for the trac ings of Figure 2's shortest spanning tree.) Note that not only is the Route Table initialized here, but the initial detour ratio for each request and the initial accumulated circuit fill of each link is computed and stored in the proper key tables. 3.3.3 Decreasing Detour Ratios of Requests: Before actually proceeding with this phase of the program, the COST subroutine is called in to establish the initial cost of this initial network. This is done by breaking down the link fill values (found in the Link Table) into Telpak units (Ixc, C, D) that minimize the cost per link. This calculation uses the Telpak rate structure (See Table 1). The sum of these link costs is then considered the initial cost of the network and is the quantity to be reduced by any optimization procedure. The initial configuration of the network is extremely inefficient. Many requests have very high detour ratios, meaning that they travel an extremely circuitous route from one end point to the other. The purpose of this first cost reduction program is to reduce the detour ratio by adding links that shorten the mileage travelled by requests. In order to investigate only that part of the network in the vicinity of the request being shortened (the primary request) (See 3.3.3.1) an ellipse is employed whose foci coincide with the end points of the primary request. Only those nodes of the network that fall on or within the ellipse are considered for this subproblem. Initially, the ellipse* is established with a relatively wide minor axis. If this results in too many cities within the ellipse than can be easily handled by the subproblem, the minor axis is reduced incrementally until an acceptable number of cities is obtained. The acceptable number of cities is established by NOKC, which is set at 20. In addition, the ellipse must be small enough so that at least one city of the route of the primary request falls outside the ellipse. This fact is necessary if the linkaddition program is to work properly. 3.3.3.1 Choosing Candidate Links. The primary request to be re-routed is always one that has not yet been a candidate for rerouting, and which has the largest detour ratio larger than XMDR = 1.15. This value of XMDR was found by trial and error on the basis of network cost saved versus computer time used. For the cities contained within the ellipse initially, a *The size of the ellipse used can be identified by its own detour ratio. For an ellipse, the detour ratio is defined as the sum of the distances from the foci to any point on the ellipse divided by the distance between the foci. For any ellipse, the sum of distances to any point on the ellipse from the foci is constant regardless of the point chosen. |