×

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
First Claim
Patent Images

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.

View all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×