# Optimizing a capacitated clustering problem with Greedy search algorithm

So, I am trying to implement a greedy search algorithm to cluster a number of points. Each point has a specific demand and each cluster shouldn't exceed that demand. Now, when I run it for a smaller sample size, the clustering looks fine. But just when the sample size gets a bit larger, it just gets worse. Greedy search has an obvious backlog that, it will search for the local maxima/minima, but even after that, the results I am getting isn't making any sense. Also, I have added one more constraint that, the total intra-distance between the points of a cluster shouldn't exceed 40 km.

Sharing my sample code in R, and the output for both the smaller sample size and a larger sample size.

library(tidyverse)
library(data.table)
#Creating a sample dataframe with 100 points
#As the algorithm depends on the starting point
#Sorting it with long so that I will have one extreme point at the start

set.seed(123)
sc_1m <- data.frame(customer_lat= runif(100, 22,23),
customer_long= runif(100, 77, 78),
demand= runif(100, 10, 70))
sc_1m %>%
arrange((customer_long)) -> sc_1m

#Creating the distance matrix
library(sp)
d<- sc_1m[,c('customer_long','customer_lat')]
dm <- spDists(as.matrix(d), longlat = TRUE)

rownames(dm) <- seq(1:nrow(sc_1m))
colnames(dm) <- seq(1:nrow(sc_1m))

#Making the diagonals NA so that it is excluded from the counting

diag(dm) <- NA

nearestpoints <- data.frame(matrix(ncol = 6, nrow = 0))
colnames(nearestpoints) <- c("from", "to", "lon", "lat", "distance", "demand")

inputrowindex=1
outputrowindex=1
#The visited points are the 'To' points
visitedpoints <- c(rownames(dm))

while(length(setdiff(rownames(dm), visitedpoints)) > 0){
nearest <- which.min(dm[inputrowindex,])
if(length(nearest)==0) break

nearestpoints[outputrowindex, 1] <- rownames(dm)[inputrowindex]
nearestpoints[outputrowindex, 2] <- names(nearest)
nearestpoints[outputrowindex, 5] <- dm[inputrowindex, nearest]
nearestpoints[outputrowindex, 3] <- sc_1m[nearest, 'customer_long']
nearestpoints[outputrowindex, 4] <- sc_1m[nearest, 'customer_lat']
nearestpoints[outputrowindex, 6] <- sc_1m[nearest, 'demand']

dm[inputrowindex,] <- NA
dm[,inputrowindex] <- NA

visitedpoints <- c(visitedpoints, names(nearest))

inputrowindex = as.numeric(nearest) #Next point is the nearest
outputrowindex = outputrowindex + 1
}

#The nearestpoints dataframe gives me the point to point mapping of nearest points
nearestpoints

#Now I will run a while loop and cluster the points after setting a capacity
d_demand<-0
d_distance<-0
cluster_number<-1
cluster_list<- c()
i<-1
capacity_constraint <- 500
distance_constraint <- 40

#Only taking the points within the set limits for the time being

nearestpoints %>%
filter(distance<distance_constraint) %>%
filter(demand<capacity_constraint)-> nearestpoints

while (i <= nrow(nearestpoints)){
d_demand <- d_demand+ nearestpoints$$demand[i] d_distance <- d_distance + nearestpoints$$distance[i]
if(d_demand<=capacity_constraint & d_distance<= distance_constraint){
cluster_list[i] <- cluster_number
i<- i+1
}
else{
cluster_number <- cluster_number+1
d_demand <- 0
d_distance <- 0
i<-i
}
}

nearestpoints\$cluster <- cluster_list

#Visualise the polygon

nearestpoints_dt<- data.table(nearestpoints)
hulls = nearestpoints_dt[,.SD[chull(lon,lat)],by=.(cluster)]

ggplot() +
geom_point(data=nearestpoints_dt,aes(x=lon,y=lat,color=as.factor(cluster))) +
geom_polygon(data = hulls,aes(x=lon, y=lat, fill=as.factor(cluster),alpha = 0.5))+
theme_bw()+
coord_equal()+
theme_bw()+
theme(legend.position = 'none')+
ggtitle('Clusters') It is not the best one but it doesn't look very bad too. But when I try to cluster it for a larger real-life dataset, everything goes for a toss. Now, I understand there would be some kind of overlapping because the solution isn't optimum but how can the points be so spread like this? I can't figure this one out! What am I missing?

• If you want to understand why you get this solution, try to look at the algorithm step by step. For example, print the solution each time a new cluster is finished Aug 18, 2021 at 7:33
• @fontanf thank you! I can see now where they are going wrong now but still failed to understand how. Aug 19, 2021 at 5:14
• Actually, I don't understand your algorithm. Could you describe it and give the pseudo-code in the question, so that we can determine if it's an algorithmic issue or an implementation issue. Aug 19, 2021 at 9:36
• We have an open source java-based optimisation algorithm that does capacitated clustering, where clusters can have both a min and max quantity - could this be useful to you? - see github.com/PGWelch/territorium Aug 23, 2021 at 1:53
• @OpenDoorLogistics Thank you! The logic that has been deployed there is the same as I am trying to implement here. Aug 24, 2021 at 11:24

Your distance constraint for each cluster limits the sum of the distance from each cluster point to its nearest neighbor (excluding the last point selected for the cluster, whose nearest neighbor is not taken). It does not look at the total distance between all pairs of points in the cluster, nor the maximum distance between any pair of points (the cluster "diameter"). So a large set of points with low individual demand and short distances to their nearest neighbors can end up in a cluster, and they can wander quite far. Picture, for instance, four points arrayed as the corners of a square, each side of the square exactly distance_constraint / 4 from the next and all with low demand. They could form a cluster. (In fact, they side length could be distance_constraint / 3, since only three of the segments count toward the distance constraint.)