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:
