Lagerzuordnungsproblem: Kunden dem nächstgelegenen Lager zuordnen (mit R)

In diesem Beitrag gebe ich ein Codierungsbeispiel dafür an wie eine Gruppe von Kunden jeweils einem Lager zugeordnet werden kann, wobei eine Reihe von festen Lagern mit unbegrenzter Kapazität berücksichtigt werden. Die zugrunde liegende Annahme ist, dass es keine Fixkosten gibt und dass relevante Kosten nur von der euklidischen Entfernung zwischen Kunde und Lager abhängen. Darüber hinaus werden bei diesem Problem keine Vorlaufzeitanforderungen oder andere Service Level-bezogene Einschränkungen berücksichtigt.

Der Algorithmus ist sehr einfach und erinnert an Clustering-Algorithmen. Der Algorithmus durchläuft alle Kunden und ordnet jeden Kunden dem nächstgelegenen Lager zu, wobei die euklidische Entfernung und das Längen- und Breitengradsystem berücksichtigt werden. Im Folgenden definiere ich diesen Algorithmus als Funktion:

# Funktion zur Berechnung euklidischer Abstände
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 zum Zuweisen von Kunden zu Lagern
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
}

Zum Testen baue ich zuerst zwei Sets mit zufällig angeordneten Kunden bzw. Lagern.

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

Nun schaue ich mir die obersten Einträge im customer_df Datenrahmen an:

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

Unten zeige ich zudem die Kopfzeilen des warehouse_df Datenrahmens (Lagerstandorte):

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

Jetzt ordne ich die Kunden den Lagern zu:

# Funktion anwenden
results_df <- assignment_algorithm(customer_df,warehouse_df)
# Kopfzeile der Ergebnisse anzeigen
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

Außerdem visualisiere ich die Ergebnisse mit ggplot2:

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)

Die Lagerstandorte sind unten dargestellt:

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

In einem anderen Beitrag zeige ich, wie man ein Lager im Massenschwerpunkt allokiert, sodass man bspw. ein Lager im Zentrum der Kundennachfrage platzieren kann. Ich habe auch Beiträge darüber geschrieben, wie man eine Kundengruppe basierend auf der räumlichen Nähe in mehrere kleinere Cluster aufteilt. Dieser Ansatz kann z.B. verwendet werden um mehrere Lagerhäuser an jeweiligen Massenschwerpunkten zu lokalisieren.