Method and system for facility location optimization

• US 8,788,314 B2
• Filed: 11/21/2012
• Issued: 07/22/2014
• 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:
  US13/683,231
• Publication Number:
  US 20130079024A1
• Time in Patent Office: 608 Days
• Field of Search: 705/7.29, 705/14.57, 705/14.58, 705/39, 705/29, 700/36
• 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 system, comprising:

a memory to store computer-executable instructions; and

a processor, communicatively coupled to the memory, that facilitates execution of the computer-executable instructions to perform operations, comprising;

selecting a first set of cluster center locations corresponding to a predetermined number of cluster centers to facilitate identifying a set of cluster center locations associated with an overall clustering indicating a defined profit in clustering a subset of a plurality of cluster points, wherein the predetermined number of cluster centers have respective predetermined cluster radii defining respective areas, and the set of cluster center locations is associated with a communication network environment;

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

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

selecting the subset of the plurality of cluster points using a weighted randomization of the plurality of cluster points, based on the first value;

selecting a subset of cluster centers that correspond to the subset of the cluster points and comprise wireless antennas, wherein the subset of cluster centers define a subset area of the first cluster area,

wherein the subset of the plurality of cluster points has a defined probability level of having a clustering of cluster points that is determined to satisfy a condition with respect to a defined portion of the overall clustering, based on the weighted randomization; 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 satisfy the condition with respect to the defined portion of the overall clustering providing the defined 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 system of claim 1, wherein cluster points within the first cluster area have corresponding cluster point values, and the determining the first value further comprises summing the corresponding cluster point values of the cluster points within the first cluster area.

3. The system 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 system 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 defined minimum acceptable profit per cluster center location, wherein the first cluster center location and the second cluster center location each attain the defined minimum acceptable profit after the re-assigning of the specified cluster point to the second cluster.

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

6. The system 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 system of claim 1, wherein a cluster point of the plurality of cluster points corresponds to a location associated with a customer of a wireless service associated with a wireless antenna of the wireless antennas.

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

9. A system, comprising:

a memory to store computer-executable instructions; and

a processor, communicatively coupled to the memory, that facilitates execution of the computer-executable instructions to perform operations, comprising;

defining a plane corresponding to a plurality of cluster points, wherein 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 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 a 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 defined period of time, a cluster center location of the subset of cluster center locations meets a defined minimum acceptable economic profit, and the subset of cluster center locations is associated with a communication network environment; 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 defined minimum acceptable economic profit and a potential economic profit of the potential cluster center location not meeting the defined minimum acceptable economic profit.

10. The system 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 system 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 system 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 defined minimum acceptable economic profit by a defined factor.

13. The system of claim 9, wherein the first cluster center corresponds to a wireless antenna of the wireless antennas having an associated economic cost that is recoverable within the defined period of time based on the first economic profit, and a first predetermined radius of the first cluster center corresponds to a broadcasting range of the wireless antenna.

14. The system of claim 9, wherein a cluster point of the plurality of cluster points corresponds to a location associated with a customer of a wireless service associated with a wireless antenna of the wireless antennas, and a cluster point value associated with the cluster point corresponds to a monetary access charge associated with the cluster point.

15. A method, comprising:

defining, by a system including a processor, a grid in a plane corresponding to a plurality of cluster points, wherein cluster points of the plurality of cluster points are to be associated with a variable number of cluster centers comprising wireless antennas;

for cluster points of the plurality of cluster points, translating, by the system, 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, by the system, the plane into a plurality of horizontal strips including 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, by the system, a subset of cluster center locations and associated cluster points within the plurality of horizontal strips, wherein the subset of cluster center locations corresponds to a subset of cluster centers of the variable number of cluster centers;

determining, by the system, 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, by the system, 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 defined period of time and a cluster center of the subset of cluster center locations meets a defined 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 defined minimum acceptable economic profit and a second economic profit of the second cluster center location not meeting the defined minimum acceptable economic profit.

16. The method of claim 15, further comprising identifying, by the system, 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.

17. The method of claim 15, 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.

18. The method of claim 15, 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 defined minimum acceptable economic profit is unacceptable.

19. The method of claim 15, wherein the first cluster center corresponds to a wireless antenna of the wireless antennas that has an associated economic cost, and a first radius of the first cluster center corresponds to a broadcasting range of the wireless antenna.

20. The method of claim 15, wherein a cluster point of the plurality of cluster points corresponds to a location associated with a customer of a wireless service associated with a wireless antenna of the wireless antennas, and the cluster point is associated with a cluster point economic profit that is based on a monetary access charge paid by the customer.