ALGORITHM FOR SYNTHESIZING ECONOMICAL DATA COMMUNICATION NETWORK

• US 3,703,006 A
• Filed: 10/28/1970
• Issued: 11/14/1972
• Est. Priority Date: 10/28/1970
• Status: Expired due to Term

• Current Assignee: Roshan L.A. Sharma
• Original Assignee: Roshan L.A. Sharma
• Inventors: Sharma, Roshan La.
• Primary Examiner(s): Botz, Eugene G.
• Assistant Examiner(s): Dildine, Jr., R. Stephen
• Application Number:
  US05/084,690
• Time in Patent Office: 748 Days
• Field of Search: 444/1 235/151.2
• US Class Current: 700/90
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: H04Q 3/0016 Arrangements providing connection between exchanges

Abstract

A technique for optimizing the connections of a plurality of stations to a central point wherein a connection link has a predetermined maximum line weight and where optimum is defined as a distance related cost comprising setting up a trial configuration in a computer and interchanging stations on adjacent links on a sequential and selective basis and comparing the cost of each selection with the previous lowest cost connection until a predetermined number of comparisons and selections have been completed.

Claims

1. The method of obtaining a preferred cost connection of a plurality of stations to a common center wherein the total cost is based on total distances involved in connecting said stations to the common center and the weights associated with the station connections comprising the steps of operating a computer under the control of stored program to:

select a station S11 furthest from the common center and assign it to a designated link;

select further stations for assignment to said designated link, each station of which is the closest to the last selected station, until the total link weight substantially equals a predetermined maximum;

compute the cost CO of the link from the furthest station to the common center upon consideration of the respective station connection weights;

repeat the selection and computation process for all previously unassigned stations until all stations are assigned in n links;

designate the links L1 to Ln as a first trial set;

form a second trial set of links on a pair-by-pair basis as follows;

choose the furthest city S11 from said common center in link L1, remove a station, S21 of another link L2, closest to said furthest city S11 from L2 and add it to the link L1, subtract stations from said L1 link which are closest to said common center, add them to said L2 link from which said closest city S21 was removed until the link weights of both links L1 and L2 are less than or equal to said predetermined maximum, and calculate the cost C1 of links L1 and L2 in their second trial form;

form a third trial set of links on a pair-by-pair basis as follows;

remove the city S11 from link L1 and add it to said link L2, adjust the weight of the two links L1 and L2 by removing one or more stations closest to said data center from said link L2 and adding said stations to said link L1 until the weights of the two links are equal to or less than said predetermined maximum link weight, calculate the cost C2 of links L1 and L2 in their third trial form;

compare costs C0, C1, and C2 of the three variations of link configurations and select the lowest cost configuration therefrom; and

repeat the station interchange and link cost computation process for each station in each link until all stations And links have been considered.

2. calculate the cost of each first trial link,

3. sequentially interchange stations between adjacent links to sequentially produce second sets of trial links, calculate the cost of each set of second trial links, sequentially select the lower cost set of trial links, and

4. provide an output indicative of the finally selected set of links.

5. Apparatus as claimed in claim 4 comprising;

in combination means for supplying visual information signals, connected to receive the output from said computer means.