Method and system for facility location optimization

• US 8,364,515 B1
• Filed: 05/11/2006
• Issued: 01/29/2013
• Est. Priority Date: 12/30/2005
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Procopiuc, Cecilia M
• Primary Examiner(s): Sterrett, Jonathan G
• Assistant Examiner(s): Swartz, Stephen S.
• Application Number:
  US11/382,826
• Time in Patent Office: 2,455 Days
• Field of Search: 705/14.38, 705/14.58
• US Class Current: 705/7.29
• 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: H04W 16/18 Network planning tools

Abstract

Systems and methods for optimization of facility locations are disclosed, for example, wireless telecommunications facility locations. Among a plurality of cluster points, corresponding to wireless customers, optimal locations are determined for a predetermined number of cluster centers, each cluster center having a predetermined cluster radius that defines a cluster area. Among a plurality of cluster points, optimal facility locations are determined for a variable number of cluster centers, each cluster center having a minimum acceptable economic value.

Claims

1. A method for selecting a set of cluster center locations in a communication network environment, the method comprising:

selecting, by a system including at least one processor, a first set of cluster center locations corresponding to a predetermined number of cluster centers to approximate identifying the set of cluster center locations associated with an overall clustering providing a predefined profit in clustering of at least some of a plurality of cluster points, wherein respective cluster centers of the predetermined number of cluster centers have respective predetermined cluster radii defining respective areas;

defining a first cluster area based on the respective areas of the respective cluster centers of the predetermined number of cluster centers;

determining, by the system, a first calculated value corresponding to cluster points, of the plurality of cluster points, that are within the first cluster area;

selecting a subset of cluster points from the plurality of cluster points using weighted randomized selection, based on the first calculated value, and selecting a corresponding subset of cluster centers, comprising wireless antennas, wherein the corresponding subset of cluster centers define a subset area of the first cluster area,

wherein the subset of cluster points has a predefined probability level of having a clustering of cluster points that provides at least a predefined portion of the overall clustering providing the predefined profit, based on the weighted randomized selection; and

selecting the set of cluster center locations, comprising a first cluster center location having a first profit and including a first portion of cluster points of the subset of cluster points, based on the first profit being greater than a second profit associated with a potential cluster center location excluded from the set of cluster center locations, to attain at least the predefined portion of the overall clustering providing the predefined profit based on all cluster center locations in the set of cluster center locations, wherein the first profit is determined without regard to respective distances of cluster points of the first portion of cluster points from a first cluster center associated with the first cluster center location, and the first portion of cluster points is located within a first area defined by a predetermined first cluster radius of the first cluster center.

2. The method of claim 1, wherein cluster points within the first cluster area have an associated cluster point value, and the calculating the first calculated value further comprises calculating a sum of the cluster point values within the first cluster area.

3. The method of claim 1, further comprising:

identifying a first cluster point associated with a first cluster-point profit, a second cluster point associated with a second cluster-point profit, and a third cluster point associated with a third cluster-point profit, wherein the first cluster-point profit is greater than the second cluster-point profit, which is greater than the third cluster-point profit, and wherein the first cluster point, the second cluster point, and the third cluster point are part of the subset of cluster points; and

selecting the first cluster point and the third cluster point to be in the first portion of cluster points, associated with the first cluster center location, over the second cluster point which is not selected to be included in the first portion of cluster points, wherein the second cluster point is closer in distance to the first cluster center than the first cluster point and the third cluster point, based on the first cluster point value being greater than the second cluster point value.

4. The method of claim 1, further comprising:

re-assigning a specified cluster point of the subset of cluster points from a first cluster associated with the first cluster center location to a second cluster associated with a second cluster location of the set of cluster center locations in response to the second cluster center location not meeting a predefined minimum acceptable profit per cluster center location, wherein the first cluster center location and the second cluster center location each at least meet the predefined minimum acceptable profit after the re-assigning of the specified cluster point to the second cluster.

5. The method of claim 1, wherein a particular cluster center of the predetermined number of cluster centers corresponds to a broadband wireless antenna having an associated economic cost, and a radius of the particular cluster center corresponds to a broadcasting range of the broadband wireless antenna.

6. The method of claim 5, further comprising identifying a second portion of cluster points of the subset of cluster points as outlier cluster points that remain unclustered after the selecting of the set of cluster center locations, wherein the second portion of cluster points is associated with the potential cluster center location excluded from the set of cluster center locations.

7. The method of claim 1, wherein at least one cluster point of the plurality of cluster points corresponds to a location associated with a broadband customer.

8. The method of claim 7, wherein at least one cluster point value associated with the at least one cluster point corresponds to a monetary access charge associated with the at least one cluster point.

25. The method of claim 1, further comprising:

clustering a first cluster point and a second cluster point in the first cluster center location, wherein the first cluster point and the second cluster point are in the first portion of cluster points; and

determining a first cluster-point profit associated with the first cluster point and a second cluster-point profit associated with the second cluster point without regard to respective distances of the first cluster point and the second cluster point from the first cluster center.

26. The method of claim 25, further comprising:

determining the first cluster-point profit is greater than the second cluster-point profit even though the first cluster point is a further distance away from the first cluster center than the second cluster point.

27. The method of claim 25, further comprising:

determining the first profit of the first cluster center location based on the first cluster-point profit and the second cluster-point profit without regard to a sum of respective distances of the first cluster point and the second cluster point in relation to the first cluster center.

28. The method of claim 1, further comprising:

selecting the first set of cluster center locations corresponding to the predetermined number of cluster centers using a greedy algorithm to approximate the identifying of the set of cluster center locations associated with the overall clustering providing the predefined profit.

29. The method of claim 4, further comprising:

re-assigning the specified cluster point from the first cluster to the second cluster even though the specified cluster point is located a shorter distance away from the first cluster center than a second cluster center associated with the second cluster center location to facilitate enabling the second cluster center location to at least meet the predefined minimum acceptable profit.

9. A method for selecting a subset of cluster center locations associated with a communication network environment, the method comprising:

defining, by a system including at least one processor, a plane corresponding to a plurality of cluster points, wherein at least a portion of the plurality of cluster points is associated with a variable number of cluster centers, and cluster centers of the variable number of cluster centers have predetermined cluster radii;

dividing the plane into a plurality of horizontal strips, including at least a first strip and a second strip, each horizontal strip having a predetermined height corresponding to a predetermined cluster radius of a cluster center associated with that horizontal strip;

selecting, by the system, the subset of cluster center locations and associated cluster points comprising a subset of the plurality of cluster points within the plurality of horizontal strips, wherein the selecting the subset of cluster center locations includes enabling recovery of an economic cost relating to a subset of cluster centers, comprising wireless antennas, associated with the subset of cluster center locations within a predefined period of time, and at least one cluster center location of the subset of cluster center locations meets a predefined minimum acceptable economic profit; and

determining a first economic profit of a first cluster center location of the subset of cluster center locations without regard to respective geographic distances of cluster points of a first portion of cluster points of the subset of cluster points from a first cluster center associated with the first cluster center location,

wherein the first portion of cluster points is located within a first area defined by a predetermined first cluster radius of the first cluster center, and

wherein the subset of cluster center locations comprises the first cluster center location and excludes a potential cluster center location based on the first economic profit meeting the predefined minimum acceptable economic profit and a potential economic profit of the potential cluster center location not meeting the predefined minimum acceptable economic profit.

10. The method of claim 9, further comprising identifying a second portion of cluster points of the subset of cluster points as outlier cluster points that remain unclustered after the selecting of the subset of cluster center locations, wherein the second portion of cluster points is associated with the potential cluster center location excluded from the subset of cluster center locations.

11. The method of claim 9, wherein, for respective horizontal strips of the plurality of horizontal strips, respective heights of the respective horizontal strips equal twice respective cluster radii of the respective horizontal strips.

12. The method of claim 9, wherein the selecting of the subset of cluster center locations and the associated cluster points further comprises:

selecting the subset of cluster center locations and the associated cluster points based on a dynamic programming algorithm; and

decreasing the predefined minimum acceptable economic profit by a defined factor.

13. The method of claim 9, wherein the first cluster center corresponds to a broadband wireless antenna having an associated economic cost that is recoverable within the predefined period of time based on the first economic profit.

14. The method of claim 13, wherein a first predetermined radius of the first cluster center corresponds to a broadcasting range of the broadband wireless antenna.

15. The method of claim 9, wherein at least one cluster point of the plurality of cluster points corresponds to a location associated with a broadband customer.

16. The method of claim 15, wherein at least one cluster point value associated with the at least one cluster point corresponds to a monetary access charge associated with the at least one cluster point.

30. The method of claim 9, further comprising:

selecting the subset of cluster center locations and the associated cluster points, wherein the subset of cluster point locations comprises the first cluster center location associated with the first economic profit and a second cluster center location associated with a second economic profit; and

assigning a first cluster point to the first portion of cluster points even though the first cluster point is located a shorter distance away from a second cluster center associated with the second cluster center location than the first cluster center to facilitate enabling the first cluster center location to at least meet the predefined minimum acceptable economic profit, wherein the second cluster center location also at least meets the predefined minimum acceptable economic profit.

17. A computer-readable storage device storing computer-executable instructions that, in response to execution, cause a system including at least one processor to perform operations, comprising:

defining a grid in a plane corresponding to a plurality of cluster points;

for cluster points of the plurality of cluster points, translating a cluster point to its nearest grid point and enlarging a predetermined cluster radius of a corresponding cluster center to a calculable cluster radius;

dividing the plane into a plurality of horizontal strips including at least a first strip and a second strip, wherein the plurality of horizontal strips have predetermined heights corresponding to the calculable cluster radius of the corresponding cluster center;

selecting a subset of cluster center locations and associated cluster points within the plurality of horizontal strips, wherein the subset of cluster center locations correspond to a subset of cluster centers of the variable number of cluster centers;

determining a first economic profit of a first cluster center location of the subset of cluster center locations without regard to respective geographic distances of cluster points of a first portion of cluster points of the subset of cluster points from a first cluster center associated with the first cluster center location, wherein the first portion of cluster points is located within a first area defined by a predetermined first cluster radius of the first cluster center; and

repeatedly shifting the first horizontal strip relative to the second horizontal strip to obtain a shifted set of horizontal strips and iteratively selecting the subset of cluster center locations and the associated cluster points for the shifted set of horizontal strips to identify overall clusterings associated with the shifted set of horizontal strips to facilitate obtaining a final clustering having a largest economic profit,

wherein the obtaining the final clustering having the largest economic profit includes selecting the subset of cluster center locations to enable economic cost relating to the subset of cluster center locations to be recoverable within a predefined period of time and at least one cluster center of the subset of cluster center locations at least meets a predefined minimum acceptable economic profit, and

wherein the subset of cluster center locations comprises the first cluster center location and excludes a second cluster center location based on the first economic profit meeting the predefined minimum acceptable economic profit and a second economic profit of the second cluster center location not meeting the predefined minimum acceptable economic profit.

18. The computer-readable storage device of claim 17, the operations further comprising identifying a second portion of cluster points of the subset of cluster points as outlier cluster points that remain unclustered after the selecting of the subset of cluster center locations, wherein the second portion of cluster points is associated with the second cluster center location excluded from the subset of cluster center locations.

19. The computer-readable storage device of claim 17, wherein, for respective horizontal strips of the plurality of horizontal strips, a height of a respective horizontal strip equals twice a respective calculable cluster radius associated with a respective cluster center of the variable number of cluster centers that is associated with that respective horizontal strip.

20. The computer-readable storage device of claim 17, wherein the selecting the subset of cluster center locations and the associated cluster points within the plurality of horizontal strips further comprises selecting of the subset of cluster center locations and the associated cluster points in response to determining that lowering the predefined minimum acceptable economic profit is unacceptable.

21. The computer-readable storage device of claim 17, wherein the first cluster center corresponds to a broadband wireless antenna having an associated economic cost.

22. The computer-readable storage device of claim 17, wherein a first radius of the first cluster center corresponds to a broadcasting range of a broadband wireless antenna.

23. The computer-readable storage device of claim 17, wherein a cluster point of the plurality of cluster points corresponds to a location associated with a broadband customer.

24. The computer-readable storage device of claim 17, wherein a cluster point of the plurality of cluster points is associated with a cluster point economic profit that is based on a monetary access charge paid by a broadband customer associated with that cluster point.

31. The computer-readable storage device of claim 17, the operations further comprising:

enlarging clusters respectively associated with the subset of cluster center locations to a second calculable cluster radius.