Das optimale Warenlager mit pgRouting und R

In diesem Artikel wird behandelt, wie wir anhand der vorliegenden Kundendaten

• ein neuen Lagerstandort optimal bestimmt haben
• und wie das Lager organisiert sein muss, um bei zukünftig gleichbleibenden Aufträgen schnell und effizient kommissionieren werden kann.

Über das Projekt

Motivation

Der Artikel beinhaltet Ergebnisse aus unserer Projektarbeit im Fach Datascience aus dem Wintersemester 2022/2023 an der Hochschule Kaiserslautern (Fachbereich IMST).

Das Projekt wurde von Prof. Dr. Bastian Beggel betreut und in Zusammenarbeit mit Prof. Dr.-Ing. Martin Wölker durchgeführt.

Datengrundlage

Unsere Daten stammen aus dem Blogartikel von Prof. Dr.-Ing. Martin Wölker und sind nach Creative Commons (CC BY-NC-SA) lizenziert. Die Daten spiegeln Verkäufe, Materialstämme und Kundenstämme eines fiktiven mittelständigen Unternehmen namens Schrauben Karl GmbH wider.

Verwendete Technologien

• PostgreSQL
• pgRouting
• R mit R-Studio

Unser Repository

In unserem Repository ist der Code zu finden, mit den wir die Ergebnisse erzeugt haben: https://github.com/INF-HS-KL-BEGGEL/DS_WS_22_T1_wahre_logistik

Vorarbeit

Die Daten (Verkäufe, Materialstämme, Kundenstämme) liegen in Form einer Excel Datei vor. Diese Daten haben wir in Tabellen einer PostgreSQL Datenbank eingepflegt, um eine zentrale Datenquelle für R zu haben. Auch waren die SQL Anfragen von Vorteil.

Des weiteren haben wir mit pgRouting gearbeitet, welche auch eine PostgreSQL Datenbank benötigt. Hierfür waren auch einige Schritte nötig, um Routenberechnung für uns möglich zu machen, aber mehr dazu in unserem Blogartikel zu pgRouting.

Der optimale Warenlagerstandort

Zu beachten: Luftlinie (Orthodrome)

Da wir mit Strecken auf unserer blauen Kugel namens Erde arbeiten, müssen wir Distanzen nach der nichteuklidischen sphärischen Geometrie berechnen. Was im euklidischen Raum einer Strecke zwischen zwei Punkten entspricht, wird in der sphärischen Geometrie als Orthodrome (umgangssprachlich: "Luftlinie") bezeichnet.

Die Orthodrome auf der Erde als idealisierte Kugel mit Umfang von 40075 km wird wie folgt mit der Funktion L berechnet:

Geografische Kundenverteilung

Aus unseren Daten der fiktiven Firma Schrauben Karl GmbH konnten wir 5002 Kunden auf 114 Kundencluster abbilden. Diese sind in folgender Abbildung zu sehen:

Anzumerken ist, dass eine hohe Dichte an Kunden im Bereich Dortmund zu sehen ist. Demnach ist anzunehmen, dass sich das optimale Lager ungefähr westlich in der Mitte von Deutschland liegen müsste.

Überlegung: Den perfekten Ort/Gemeinde finden

Laut Statista gibt es im Jahr 2021 geschätzt 10789 Gemeinden in Deutschland (zur Statistik). Eine Überlegung war es, von jedem Ort in Deutschland zu den Kundenclustern zu routen und diese in unserer Datenbank zu speichern.

Dies würde bedeuten, dass 1229946 Routen berechnet werden musste. Zusätzlich muss der Rückweg auch berechnet werden, da sich dieser unterscheiden kann. D.h. die zu berechnenden Routen verdoppeln sich auf 2459892 Routen.

Darüber hinaus haben wir unsere Datenbank mit pgRouting auf leistungsschwacher und nicht skalierter Hardware gehostet. Das bedeutet, dass die Berechnung einer Route ca. 2 Sekunden gedauert hat. Nimmt man das zusammen, kommen wir auf ca. 57 Tage (2459892 Routen * 2 Sekunden) Berechnungszeit.

Um ein Gefühl für Komplexität für nur einen Standort zu bekommen, kann man in Abbildung 2 die ausgehenden und eingehenden Routen zu nur einem beliebig gewählten Lagerstandort in Deutschland sehen.

Für uns war das ein Problem, da wir nicht 57 Tage auf die Berechnung  der Routen warten konnten. Wenn sich dann noch ein Fehler einschleicht, müssten wir wieder 57 Tage auf unser Ergebnis warten.

Ein weiteres Problem wäre, dass wir Potentiale für Lagerstandorte außerhalb von Gemeinden nicht erfassen könnten (z.B. auf Felder außerhalb der Gemeinden, auf denen günstig ein Warenlager errichtet werden kann).

Unsere Lösung: Äquidistantes Raster über Deutschland

Um die versteckten Potentiale, die nicht in Gemeinden/Orte liegen, zu ertasten und unnötige Berechnungen von benachbarten Positionen zu vermeiden, haben wir uns überlegt ein relativ gleichmäßiges Raster von ca. 100 Punkten über Deutschland zu legen (siehe Abb. 3). Dies reduziert die Komplexität von 10789 potentiellen Lagerstandorten auf nur 100. Unser Raster hatte eine Auflösung von ca. 87 km Radius zwischen den Rasterpunkten.

Damit sind nur noch 22800 Routen nötig und die Rechenzeit verringert sich auf vertretbare 13 Stunden. Dies haben wir dann auch so in die Tat umgesetzt und eine Tabelle mit Lagerpunkt, Kundenclusterpunkt, Hinweg in km und Rückweg in km angelegt.

Die fünf besten Lagerstandorte

Mithilfe der Tabelle der Routen von Rasterpunkten zu allen Kundencluster haben wir die fünf besten Rasterpunkte, bei der die Summe der Entfernung am geringsten ist, ermittelt. Dies deckt sich mit unseren Vermutungen und dem Kundencluster in Abb. 1, da eine hohe Dichte an Kunden im Bereich Dortmund liegen.

Ein großer Vorteil unseres Vorgehens ist, dass jetzt grob wissen, wo das optimale Lager liegt. Wenn noch genauer bestimmt werden soll, kann wieder im Teilbereich der fünf besten Standorte ein Raster gespannt werden. Somit kann nochmal mit höherer Auflösung ermittelt werden kann, an welcher Stelle sich noch ein besserer Warenlagerstandort befindet.

Da uns aber die Auflösung von ca. 87km pro Rasterpunkt gereicht hat, waren wir mit diesem Ergebnis zufrieden.

Ein übersichtliches und effizientes Warenlager

ABC-Zonen nach Zugriffen (aus den bisherigen Verkäufen)

Wenn der optimale Standort für das Warenlager gefunden wurde, geht es an das innere Layout des Warenlagers.

Hierbei kann die Verkaufshistorie genutzt werden, um zukünftige Verkäufe vorherzusagen. Uns liegen 131201 Lieferscheine aus dem Jahr 2010 von Schrauben Karl GmbH vor, mithilfe wir analysieren können, auf welche Materialien besonders oft über das Jahr zugegriffen wurde. Darüber hinaus haben wir Zugriffsgrenzen definiert, um die Materialien in die Zugriffsklassen A, B oder C einzuordnen.

Die Klassen richten sich nach Zugriffen im Jahr:

• A: 10 oder mehr Zugriffe im Jahr
• B: 2 bis inklusive 9 Zugriffe im Jahr
• C: 1 Zugriff im Jahr

Mit dem Kriterium der ABC-Klassen für Zugriffe verteilen sich 53240 Materialien auf folgende Klassen:

Da den Materialien jetzt eine Klasse zugewiesen wurde, können den Lieferschein eine Klassenkombination aus den beinhalteten Materialien zugewiesen werden.

Zum Beispiel beinhalten Lieferscheine der Klasse [A] nur Materialien aus der Klasse A oder Lieferscheine der Klasse [A,B,C] nur Materialen aus den Klassen A, B und C.

In Abbildung 5 ist die prozentuale Verteilung der 131201 Lieferscheinen nach Lieferscheinkombinationen dargestellt.

Die absoluten Zahlen können in der folgenden Tabelle ermittelt werden:

Layout des Warenlagers nach ABC-Zonen

Da wir jetzt wissen, welche Materialien zu der A, B oder C Klasse gehören und wie oft jede Kombinationen der Lieferscheine auftritt, können wir dementsprechend auch den Aufbau unseres Lagers organisieren, um möglichst kurze Kommissionierzeiten zu bekommen. Dies wird erreicht, da häufig auftretende Kombinationen von Materialien in Lieferscheinen, örtlich nah beieinander liegen. Und somit die Strecke zwischen den Materialien verkürzt und damit auch die daraus resultierende Kommissionierzeit pro Auftrag.

Ein Beispiel für ein Layout nach ABC-Zonen würde zum Beispiel so aussehen:

Fazit: Effizienz der ABC-Zonen im Vergleich zu einzelnen Zugriffen

Wenn wir stark modellieren und annehmen, dass alle Materialien in einem Lieferschein, die in einer gemeinsamen ABC-Zone liegen einen einzelnen Zugriff ausmachen. Und es mit Zugriffen vergleichen, bei dem jedes Material in einem Lieferschein als einzelner Zugriff gewertet wird, erhalten wir folgende Ergebnisse:

• Es sind 525049 einzelne Zugriffe nötig
• Mit den ABC-Zonen sind nur noch 166594 Zugriffe nötig
• Im Vergleich sind mit ABC-Zonen nur 32% der einzelnen Zugriffe nötig

Das heißt zusammenfassend, dass wir eine Effizienzsteigerung von 68% mit der Zonen in ABC-Klassenkombinationen erreicht haben.