Optimizing a capacitated clustering problem with Greedy search algorithm

Question

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)[1])

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?

Answer 1

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.)

So if you want more compact clusters, you might want to switch you method of limiting distance to something like cluster diameter.

Answer 2

You're working without a framework in place but algorithms never help create a framework (R) algorithms never help create a framework. That requires sound knowledge of Graph Theory (Logical Topologies) and Combinatorics. Near-Node Selection will also fail mainly because it goes by Physical Topology.

So, this problem is real but the applied solutions aren't. And as long as they're conventional they will always have insurmountable limits.