Cluster1

Top  Previous  Next

This function solves the problem of clustering customers (with demands), so load within the cluster is lower than sCapacity and geometric size of cluster is minimized.

 

Cost is defined through a matrix, which can be calculated by TCalc.Matrix, TCalc.MatrixDyn, TNetwork.Matrix, TNetwork.MatrixDyn or on your own.

 

Demand should be a much smaller number than sCapacity. Otherwise the algorithm isn't very good at finding a solution.

 

If Demand parameter is nil (not set), the algorithm assumes 1 for all customers. See also Swap.

 

The function returns number of clusters. Property Center holds information about which customer is the center of the cluster.

 

Property

Dimension

Demand

No of customers

Matrix

No of customers x customers

Assignment (output)

No of customers

Center (output)

No of clusters

Load (output)

No of clusters

 

Sample calculation time (demand = 1 for all customers):

 

Customers

Clustersize

No of clusters

Calculation time (msec)

100

10

10

~0

1000

100

10

31

1000

10

100

250

10000

1000

10

2500

10000

100

100

22219 (22 sec)

10000

10

1000

219656 (~ 4 minutes)

 

With 50000 customers the matrix has reached a size of 10 GB - to give an indication of the largest instances that can be handled.

On win32 the limit is appr. 25000 customers.

 

Syntax: Cluster1(sCapacity: TCost): integer;

 

This is an example with 1000 customers and 10 clusters. Clusters are here highlighted as polygons:

cluster