Optimal placering af flere lagre (algoritme i R)

I et tidligere indlæg viste jeg, hvordan et simpelt lagerplaceringsproblem med et enkelt lager kan løses ved at finde massepunktet af det relevante rumlige data. F.eks. ved at finde massepunktet af den rumlig fordelte efterspørgsel på varer. I dette indlæg vil vi placere flere lagre i deres massepunkt. Hertil udvikler og implementerer jeg en algoritme i R.

Vi bruger de funktioner der allerede er defineret i tidligere indlæg.

# eksempel se her: http://www.supplychaindataanalytics.com/single-warehouse-problem-locating-warehouse-at-center-of-mass-using-r/
center_of_mass <- function(x,y,w){
  c(crossprod(x,w)/sum(w),crossprod(y,w)/sum(w))
}

# eksempel se her: http://www.supplychaindataanalytics.com/proximity-based-spatial-customer-grouping-in-r
initial_centers <- function(customers,centers){
  quantiles <- c()
  for(i in 1:centers){
    quantiles <- c(quantiles,i*as.integer(nrow(customers)/centers))
  }
  quantiles
}

Vi vil kombinere disse to tilgange for at løse et problem med flere lagerplaceringer ved hjælp af massepunktteorien, dvs. ved at identificere centrum for den relevante masse (massen er f.eks. kundeefterspørgslen). Denne tilgang er anvendelig når vi allerede ved hvor mange lagre vi vil drive. Tilgangen i den aktuelle stilling er ikke tilstrækkelig til at løse et problem hvor vi endnu ikke ved, hvor mange lagre vi faktisk vil drive.

Jeg starter med at oprette en dataramme med 1000 tilfældigt distribuerede kunder med tilfældigt fordelt efterspørgsel.

customer_df <- as.data.frame(matrix(nrow=1000,ncol=3))
colnames(customer_df) <- c("lat","long","demand")
customer_df$lat <- runif(n=1000,min=-90,max=90)
customer_df$long <- runif(n=1000,min=-180,max=180)
customer_df$demand <- runif(n=1000,min=0,max=10)
head(customer_df)

##         lat       long   demand
## 1 -42.50378  137.62188 9.608067
## 2  47.79308  101.30536 9.510299
## 3 -14.17326   24.38595 1.610305
## 4 -85.34352 -151.29061 6.394425
## 5 -26.31244  112.75030 6.972434
## 6  55.01428   58.17198 2.797564

Derefter grupperer jeg kunderne ved hjælp af fremgangsmåden vist i et tidligere indlæg og anvender den definerede funktion initial_centers. Jeg vil finde 20 lagre, så jeg grupperer kunder i 20 grupper.

centeroids <- initial_centers(customer_df[,-3],20)
cluster_obj <- kmeans(customer_df[,-3],centers = customer_df[centeroids,-3])
customer_df$group <- cluster_obj$cluster
head(customer_df)

##         lat       long   demand group
## 1 -42.50378  137.62188 9.608067     2
## 2  47.79308  101.30536 9.510299     4
## 3 -14.17326   24.38595 1.610305     6
## 4 -85.34352 -151.29061 6.394425     8
## 5 -26.31244  112.75030 6.972434    18
## 6  55.01428   58.17198 2.797564    16

Som vist ovenfor tilføjede jeg det klyngebaserede gruppeindeks til kundens dataframe.

Nu vil jeg definere en funktion der gennemløber hver kundegruppe og identificere dets massepunkt. Kravet er, at der skal overgives en dataramme (et dataframe) som funktionsparameter, der indeholder en bredde, længdegrad, efterspørgsel og gruppekolonne – i nøjagtigt dette format:

multiple_centers_of_mass <- function(df){
  result_df <- as.data.frame(matrix(nrow=nrow(df),ncol=6))
  colnames(result_df) <- c("lat","long","demand","group","com_lat","com_long")
  result_df[,c(1,2,3,4)] <- df
  for(i in 1:length(unique(df[,4]))){
    sub_df <- result_df[result_df$group==i,]
    com <- center_of_mass(sub_df$lat,sub_df$long,sub_df$demand)
    result_df$com_lat[result_df$group==i] <- com[1]
    result_df$com_long[result_df$group==i] <- com[2]
  }
  result_df
}

Lad os teste den multiple_centers_of_mass-funktion, som jeg lige har defineret:

com_df <- multiple_centers_of_mass(customer_df)
head(com_df)

##         lat       long   demand group   com_lat   com_long
## 1 -42.50378  137.62188 9.608067     2 -25.97973  158.17382
## 2  47.79308  101.30536 9.510299     4  63.58158   84.91329
## 3 -14.17326   24.38595 1.610305     6 -21.20417   26.80993
## 4 -85.34352 -151.29061 6.394425     8 -64.12072 -145.48419
## 5 -26.31244  112.75030 6.972434    18 -33.15564   99.15738
## 6  55.01428   58.17198 2.797564    16  35.04988   44.42388

Lad os visualisere testresultaterne ved hjælp af et scatterplot fra ggplot2 R-pakken. Nedenfor ser du koordinaterne på de identificerede massecentre (optimale lagerplaceringer):

library(ggplot2)

lat_wh_vc <- unique(com_df$com_lat)
long_wh_vc <- unique(com_df$com_long)
warehouse_df <- as.data.frame(matrix(nrow=length(lat_wh_vc),ncol=2))
warehouse_df[,1] <- lat_wh_vc
warehouse_df[,2] <- long_wh_vc
colnames(warehouse_df) <- c("lat","long")
ggplot(warehouse_df) + geom_point(mapping = aes(x=lat,y=long)) + xlim(-90,90) + ylim(-180,180)

Kunderne er grupperet som vist nedenfor:

library(viridis)

## Warning: package 'viridis' was built under R version 3.5.3

## Loading required package: viridisLite

ggplot(com_df) + geom_point(mapping = aes(x=lat,y=long,color=group,size=demand)) +
  xlim(-90,90) + ylim(-180,180) + scale_color_viridis(discrete = FALSE, option = "D") + scale_fill_viridis(discrete = FALSE)