Das optimale Warenlager mit pgRouting und R

Ein Gastbeitrag vom Team Wahre Logistik
Lukas Felzmann, Alexander Opris, Felix Mayer

Datum der Originalveröffentlichung Jan 20. 2023; 6 min read

Der Artikel beinhaltet die Ergebnisse unserer Projektarbeit im Fach Datascience im Wintersemester 2022/2023 an der Hochschule Kaiserslautern (Fachbereich IMST). Das Projekt wurde von Prof. Dr.-Ing. Bastian Beggel betreut und in Zusammenarbeit mit Prof. Dr.-Ing. Martin Wölker durchgeführt.

Hier wird beschrieben, wie wir anhand der vorhandenen Kundendaten einen optimalen neuen Lagerstandort ermittelt haben und wie das Lager organisiert sein muss, um bei künftig gleichbleibenden Aufträgen schnell und effizient kommissionieren zu können.

DFS Warehouse, On Avenue E E, Thorp Arch Trading Estate.
Bild ↪ Ian S licensed for ↪ reuse under ↪ cc by

Über das Projekt

↪ Repository auf github

Unsere Daten stammen aus dem Blogeintrag "△ Logistics Case Studies: der Lieferschein" von Prof. Dr.-Ing. Martin Wölker und sind unter Creative Commons (CC BY-NC-SA) lizenziert. Die Daten spiegeln Umsätze, Materialstämme und Kundenstämme eines fiktiven mittelständischen Unternehmens namens Schrauben Karl GmbH wider. (Anm. Es handelt sich um anonymisiert Echtdaten aus einem meiner Projekte.)

Verwendete Technologien: PostereSOL, pgRouting, R mit R-Studio

In unserem ↪ Repository auf github ist der Code zu finden, mit den wir die Ergebnisse erzeugt haben

Vorarbeit

Die Daten (Verkäufe, Materialstämme, Kundenstämme) liegen in Form einer Excel Tabellendatei 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):

Eine Orthodrome (aus dem Griechischen: orthos für “gerade”, dromos für “Lauf”) ist die kürzeste Verbindung zwischen zwei Punkten auf einer Kugeloberfläche1. Sie ist immer ein Teilstück eines Großkreises. Für genauere Berechnungen über größere Entfernungen, insbesondere bis zu 2000 Kilometern, kann die Vincenty-Formel genutzt werden. Diese Formel berücksichtigt die Ellipsoidform der Erde und liefert sehr genaue Ergebnisse. (ergänzt. 25.2.24 wö)

Da wir mit Entfernungen auf unserer blauen Kugel namens Erde arbeiten, müssen wir Entfernungen in der nichteuklidischen Kugelgeometrie berechnen. Was im euklidischen Raum einer Strecke zwischen zwei Punkten entspricht, wird in der sphärischen Geometrie als Orthodrom (umgangssprachlich: "Luftlinie") bezeichnet. Die Orthodrome auf der Erde als idealisierte Kugel mit einem Umfang von 40075 km wird mit der Funktion L (Gl. 1) wie folgt berechnet:

Gl. I: Orthodrome Funktion der Erde zur Distanz/Luftlinienberechnung zwischen Ort A und Ott B

Abb. 1: Kundenduster aus den Kundenstamm-
daten der Firma Schrauben Karl GmbH

Geografische Kundenverteilung

Aus unseren Daten der fiktiven Firma Schrauben Karl GmbH konnten wir 5002 Kunden auf 114 Kundencluster abbilden. Diese sind in Abbildung 1 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. Eine Überlegung war es, von jedem Ort in Deutschland zu den Kundenclustern zu routen und diese in unserer Datenbank zu speichern. (Anm. Die Anzahl

aller Gemeinden in Deutschland betrug am Ende des Jahres 2022 insgesamt laut Statistischen Bundesamt 10.786. Ändert aber an der Aussage nichts.)

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. (Anm. Effizienter wäre sicher der Ansatz erst den gewichteten Schwerpunkt zu bestimmen und dann einen Radius um das Zielgebiet zu rastern und weit mit echten Karten zu arbeiten. Korrekterweise muss mit Fahrzeiten gerechnet werden. Aber das wäre mal eine wissenschaftliche Untersuchung wert)  

Abb.2: Beispielroute Potentieller Lagerstandorte
zu einem Kundencluster

Darüber hinaus haben wir unsere Datenbank mit pgRouting auf leistungsschwacher und nicht skalierter Hardware getestet. 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 war 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 war 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 auch die versteckten Potenziale zu erfassen, die nicht in Gemeinden/Orten liegen und um 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 Standorten des Zentrallagers auf nur 100. Unser Raster hatte eine Auflösung von ca. 87 km Radius zwischen den Rastplätzen.

Abb. 3: Äquidistante Rasterpunkte über Deutschland
die 5 besten Rasterpunkte sind rot hervorgehoben
(Anm.: Abb. 4 mit den 5 Rasterpunkte zusammengeführt.)

Damit sind nur noch 22800 Routen notwendig und die Rechenzeit reduziert sich auf akzeptable 13 Stunden. Dies haben wir dann auch so umgesetzt und eine Tabelle mit Lagerpunkt, Kundencharterpunkt, Hinweg in km und Rückweg in km erstellt.

Die fünf besten Standorte

Mit Hilfe der Tabelle der Routen der Rasterpunkte zu allen Kumdenclustern haben wir die fünf besten Rasterpunkte ermittelt, bei denen die Summe der Distanzen am geringsten ist. Dies stimmt mit unseren Annahmen und dem Kumdencluster in Abb. 1 überein, da sich eine hohe Kundendichte im Raum Dortmund befindet.

Ein großer Vorteil unserer Vorgehensweise ist, dass wir nun grob wissen, wo das optimale Lager liegt. Soll noch genauer ermittelt werden, kann im Teilbereich der fünf besten Standorte nochmals ein Raster aufgespannt werden. So kann noch einmal mit höherer Auflösung ermittelt werden, an welcher Stelle noch ein besserer Lagerstandort liegt.

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

Ein übersichtliches und effizientes Warenlager

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

Nachdem der optimale Standort für das Lager gefunden wurde, wird die Anordnung der Waren im Lager festgelegt. Hier kann die Verkaufshistorie genutzt werden, um zukünftige Verkäufe zu prognostizieren. Wir haben 131201 Lieferscheine aus dem Jahr 2010 der Schrauben Karl GmbH vorliegen, anhand derer wir analysieren können, auf welche Materialien im Laufe des Jahres besonders häufig zugegriffen wurde. Zusätzlich haben wir Zugriffsgrenzen definiert, um die Materialien in die Zugriffsklassen A, B oder C einzuteilen.

Die Klassen richten sich nach Zugriffen im Jahr. Mit dem Kriterium der ABC-Klassen für Zugriffe verteilen sich 53240 Materialien auf folgende Klassen (Anm.: Diese Klassifikation ist natürlich willkürlich, was für die Demonstration der Berechnung nicht relevant ist. Das Vorgehen entspricht aber nicht der Analyse der (Pareto-) Verteilung. In diesem Fall ist eine Einteilung in 5 Klassen angemessen.).

A: 10 oder mehr Zugriffe im Jahr            | 9971
B: 2 bis inklusive 9 Zugriffe im Jahr       | 22436
C: 1 Zugriff im Jahr                                 | 20833

Da die Materialien nun einer Klasse zugeordnet sind, können die Lieferscheine einer Klassenkombination der enthaltenen Materialien zugeordnet werden. Beispielsweise enthalten Lieferscheine der Klasse [A] nur Materialien der Klasse A oder Lieferscheine der Klasse [A.B.C] nur Materialien der Klassen A, B und C. Abbildung 5 zeigt die prozentuale Verteilung der 131201 Lieferscheine nach Lieferscheinkombinationen. (Anm.: Eigentlich ganz richtig gedacht. Allerdings müssen Lieferungen betrachtet werden. Es gibt Lieferscheine, die mehrere Termine haben, was für mehrere Lieferungen spricht. Konsequenterweise müssen dann auch mehrere Lieferungen, die zeitnah in den gleichen Cluster gehen, in Sendungen gebündelt werden. Zudem sind bei den Lieferscheinen einige "ungewöhnliche" an einzelnen Tagen. Was ist das passiert?)

Abb. 5: Verteilung der Lieferscheinkombinationen abgeleitet von den Materialklassen
(Anm.: Die Artefakte werden durch das Format JPG des Originalbildes verursacht. Dies
ließe sich nur durch eine neue Grafik und Speichern als PNG beheben .... mal sehen.) 

Layout des Warenlagers nach ABC-Zonen

Da wir nun wissen, welche Materialien zur Klasse A, B oder C gehören und wie oft welche Kombinationen auf den Lieferscheinen vorkommen, können wir unser Lager entsprechend organisieren, um möglichst kurze Kommissionierzeiten zu erreichen. Dies wird dadurch erreicht, dass häufig vorkommende Materialkombinationen in den Lieferscheinen räumlich nahe beieinander liegen. Dadurch verkürzen sich die Wege zwischen den Materialien und somit auch die daraus resultierende Kommissionierzeit pro Auftrag.

Ein Beispiel für ein Layout nach ABC-Zonen würde zum Beispiel wie in Abbildung 6 aussehen:

Abb. 6: Beispiellayout für ein Lagerlayout nach ABC-Zonen der Zugriffe
(Anm.: Grundsätzlich wurde das Konzept der Zonung verstanden. Allerding wird unterstellt,
dass Lieferscheine nur disjunkte Materialien enthalten. Denn ein Material kann ja nur in
einer Zone liegen. Oder es wird in verschiedenen Zonen verteilt aber in welcher Menge?
In unserem Beispiel haben wir keine Inventurdaten und können so den Bestand nicht kennen.)

Fazit: Effizienz von ABC-Zonen im Vergleich zu Einzelzugriffen

Wenn wir stark modellieren und annehmen, dass alle Materialien eines Lieferscheins, die in einer gemeinsamen ABC-Zone liegen, einen einzigen Zugriff darstellen. Und vergleichen wir dies mit Zugriffen, bei denen jedes Material in einem Lieferschein als einzelner Zugriff betrachtet wird, erhalten wir folgende Ergebnisse:

• Es werden 525049 Einzelzugänge benötigt.
• Mit den ABC-Zonen sind nur noch 166594 Zugriffe notwendig.
• Im Vergleich dazu sind mit den ABC-Zonen nur 32% der Einzelzugriffe notwendig.

Zusammengefasst bedeutet dies, dass wir mit den Zonen in ABC-Klassenkombinationen eine Effizienzsteigerung von 68% erreicht haben.

Transparenzhinweis

Diese Seite wurden von mir nach dem Hackerangriff auf unsere Hochschule aus einem von Bastian gespeicherten PDF rekonstruiert und hier im im Blog dokumentiert. 

Anpassungen und Erläuterungen: Für das 1. Bild (Foto) habe ich die korrekte Quelle rekonstruiert, da Wikimedia eine Sekundärquelle ist. Statista ist ebenfalls eine Sekundärquelle. Die Anzahl der Gemeinden wird vom Statistischen Bundesamt veröffentlicht. 

Es wurden minor Edits mit DeepL-write und im Layout durchgeführt, für Textkorrekturen und um dem Blog gerecht zu werden.
Mann war das ein Aufwand 😏. t.b.c mit den anderen beiden Beiträgen. 

Blog: , Seite:
Version: 1.3 Mai 2023, Kontakt: E-Mail Martin Wölker
Pirmasens, Germany, 2018-, ausgelesen am: , Licence CC BY-NC-SA