I dette indlæg giver jeg et kodeeksempel på hvordan en gruppe kunder kan tildeles et lager. Jeg betragter et tilfælde hvor et sæt af faste lagre har ubegrænset kapacitet. Den grundlæggende antagelse er, at der ikke er faste omkostninger og at omkostningerne kun afhænger af den euklidiske afstand mellem kunder og lager. Desuden tages der i dette eksempel ikke hensyn til krav om leveringstid eller andre begrænsninger på serviceniveau.

Algoritmen er meget enkel og minder om klyngealgoritmer (algoritmer til clusterdannelse). Den sløjfer gennem alle kunder og tilordner hver kunde til det nærmeste lager under hensyntagen til euklidisk afstand i breddegrad-længdegradssystemet. Nedenfor definerer jeg denne algoritme som en funktion:

# funktion til beregning af euklidiske afstande
euclidean_distance <- function(vc,df){
  sqrt((as.numeric(rep(vc[1],times=nrow(df)))-df[,1])^2+(as.numeric(rep(vc[2],times=nrow(df)))-df[,2])^2)
}

# funktion til tildeling af kunder til lagre
assignment_algorithm <- function(customers,warehouses){
  return_df <- as.data.frame(matrix(nrow=nrow(customers),ncol=3))
  colnames(return_df)<-c("lat","long","warehouses")
  for(i in 1:nrow(customers)){
    return_df[i,] <- c(customers[i,1],customers[i,2],which.min(euclidean_distance(customers[i,],warehouses)))
  }
  return_df
}

For at teste funktionen bygger jeg først to sæt med tilfældigt placerede kunder og lagre.

customer_df <- as.data.frame(matrix(nrow=1000,ncol=2))
colnames(customer_df) <- c("lat","long")
warehouse_df <- as.data.frame(matrix(nrow=4,ncol=2))
colnames(warehouse_df) <- c("lat","long")

customer_df[,c(1,2)] <- cbind(runif(n=1000,min=-90,max=90),runif(n=1000,min=-180,max=180))
warehouse_df[,c(1,2)] <- cbind(runif(n=4,min=-90,max=90),runif(n=4,min=-180,max=180))

Nedenfor viser jeg de øverste linjer i datarammen med kundeplaceringerne:

head(customer_df)

##         lat      long
## 1 -35.42042 -33.68156
## 2 -50.63025 -64.52526
## 3  43.71663 -36.22302
## 4 -53.30511 135.56315
## 5 -46.32125  84.83210
## 6  83.85849 -60.70374

Nedenfor viser jeg de øverste linjer i datarammen med lagerplaceringer:

head(warehouse_df)

##          lat      long
## 1 -41.007642  118.5673
## 2  81.968627  116.1495
## 3  11.971601  103.5034
## 4  -6.619224 -103.6206

Nu tildeler jeg kunder til lagre:

# anvend funktion
results_df <- assignment_algorithm(customer_df,warehouse_df)
# vis de øverste indlæg i datarammen
head(results_df)

##         lat      long warehouses
## 1 -35.42042 -33.68156          4
## 2 -50.63025 -64.52526          4
## 3  43.71663 -36.22302          4
## 4 -53.30511 135.56315          1
## 5 -46.32125  84.83210          1
## 6  83.85849 -60.70374          4

Derudover visualiserer jeg resultaterne med ggplot2:

library(ggplot2)
ggplot(data = results_df) + 
  geom_point(mapping = aes(x=lat,y=long,color=as.character(warehouses))) +
  scale_color_manual(values=c("darkblue","darkgreen","darkred","yellow")) +
  xlim(-90,90) + ylim(-180,180)

Lagrene er placeret som følger:

ggplot(data = warehouse_df) + geom_point(mapping = aes(x=lat,y=long)) + xlim(-90,90) + ylim(-180,180)

Linnart Felkl

Industriingeniør som gerne beskæftiger sig med optimering, simulation og matematisk modellering i R, SQL, VBA og Python