4
$\begingroup$

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. Any help would be great.

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

enter image description here 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.

Clustering on large data

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?

$\endgroup$
5
  • 1
    $\begingroup$ 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 $\endgroup$
    – fontanf
    Aug 18 at 7:33
  • $\begingroup$ @fontanf thank you! I can see now where they are going wrong now but still failed to understand how. $\endgroup$ Aug 19 at 5:14
  • 3
    $\begingroup$ 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. $\endgroup$
    – fontanf
    Aug 19 at 9:36
  • 1
    $\begingroup$ 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 $\endgroup$ Aug 23 at 1:53
  • $\begingroup$ @OpenDoorLogistics Thank you! The logic that has been deployed there is the same as I am trying to implement here. $\endgroup$ Aug 24 at 11:24
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ So, in order to restrict them to a cluster diameter, I need to have a centroid or central point too, right? $\endgroup$ Aug 19 at 5:21
  • 3
    $\begingroup$ No. You can restrict the maximum distance between any two points in the cluster. When you want to add a point to the cluster, you just check the max of its precomputed distances to the points already in the cluster. $\endgroup$
    – prubin
    Aug 20 at 14:56
-3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.