Würfelnutzung und Bin-Packing

Stapeln: 3D-Geometrie in jedem Anhänger

Eine Standardpalette in Nordamerika ist 48 Zoll mal 40 Zoll (GMA-Palette). Dies ist die grundlegende Einheit der Logistikgeometrie.

Würfelnutzung misst, wie effizient Sie einen Raum füllen: tatsächliches Produktvolumen dividiert durch verfügbares Volumen. Ein Anhänger, der voll nach Gewicht, aber zur Hälfte leer nach Volumen ist, hat eine schlechte Würfelnutzung. Ein bis zur Decke gepackter Anhänger hat eine ausgezeichnete Würfelnutzung.

Säulenstapelung: Jede Schicht ist identisch, Kisten direkt übereinander. Strukturell schwach, aber nutzt Platz effizient.

Verflochtenes (Windmühlen-)Stapeln: abwechselnde Schichten werden um 90 Grad gedreht. Viel stabiler, aber erzeugt Hohlräume an den Kanten und verschwendet 5-15% der Palettengrundfläche.

Container-Beladung ist die eigentliche geometrische Herausforderung: rechteckige Kisten verschiedener Größen in einen 40-Fuß-Schiffscontainer (innere Abmessungen ungefähr 39'5" x 7'8" x 7'10") passen. Dies ist 3D-Bin-Packing: eines der klassischen NP-schweren Probleme der Informatik. Kein Algorithmus kann die optimale Lösung in angemessener Zeit für große Instanzen garantieren.

In der Praxis verwenden Logistikunternehmen heuristische Ansätze: größte Artikel zuerst, Bodenfläche vor Stacking-Höhe füllen, Artikel nach Ziel gruppieren für Entlade-Effizienz.

Palettenlade-Effizienz

Sie müssen Kisten laden, die 12 Zoll lang, 10 Zoll breit & 8 Zoll hoch sind, auf eine Standardpalette von 48" x 40". Die maximale Stacking-Höhe beträgt 48 Zoll.

Warum Routenoptimierung schwer wird

Das Traveling-Salesman-Problem (TSP)

Angenommen, Sie müssen 10 Kunden besuchen und zum Depot zurückkehren. Was ist die kürzeste Route? Dies ist das Traveling-Salesman-Problem: eines der am meisten untersuchten Probleme in Mathematik und Informatik.

Die Schwierigkeit ist kombinatorische Explosion. Für N Stopps gibt es (N-1)!/2 eindeutige Routen (Teilung durch 2, da Uhrzeigersinn & Gegenuhrzeigersinn die gleiche Entfernung sind).

- 5 Stopps: 12 Routen: überprüfen Sie alle in Millisekunden

- 10 Stopps: 181.440 Routen: noch machbar für einen Computer

- 15 Stopps: 43,6 Milliarden Routen: dauert Stunden

- 20 Stopps: 60,8 Billiarden Routen: dauert Jahrhunderte

- 50 Stopps: mehr Routen als Atome im beobachtbaren Universum

TSP ist NP-schwer: kein bekannter Algorithmus kann es in Polynomzeit lösen. Mit wachsendem N werden exakte Lösungen unmöglich und wir müssen Heuristiken verwenden: Algorithmen, die schnell gute (aber nicht garantiert optimale) Lösungen finden.

Häufige Heuristiken:

- Nächster Nachbar: Gehen Sie vom aktuellen Ort aus immer zum nächsten unbesuchten Stopp. Schnell, aber erzeugt oft Routen mit hässlichen Kreuzungen.

- Konvexe Hülle Einfügung: Beginnen Sie mit den äußersten Stopps (der konvexen Hülle: der geometrischen Grenze). Fügen Sie dann nacheinander innere Stopps ein, wo sie die geringste Entfernung hinzufügen.

- 2-opt-Verbesserung: Nehmen Sie eine fertige Route & versuchen Sie, Kantenpaare zu tauschen. Wenn das Entfernen von zwei Kanten & Neuverdrahten auf andere Weise die Route kürzer macht, behalten Sie den Tausch. Wiederholen Sie, bis keine Verbesserung gefunden wird.

Heuristiken gegen exakte Lösungen

Ein Lieferunternehmen hat heute 12 Stopps. Der Fahrer verwendet die Nächster-Nachbar-Heuristik: Fahren Sie an jedem Punkt zum nächsten unbesuchten Stopp.

Zonen, Dichte und das Vehicle-Routing-Problem

Lieferung der letzten Meile: Wo Geometrie auf Wirtschaft trifft

Die letzte Meile: vom Verteilzentrum zur Kundentür: macht 40-50% der Gesamtversandkosten aus. Es ist der geometrisch am meisten eingeschränkte Teil der Lieferkette.

Radiale Routen von einem Depot: Lieferwagen strahlen von einem zentralen Verteilzentrum aus. Die Route jedes Lastwagens sollte eine kompakte geografische Zone abdecken: Keine zwei Lastwagen sollten sich gegenseitig kreuzen.

Lieferdichte bestimmt alles. In einem dicht besiedelten Stadtgebiet könnte ein Lastwagen in einer 8-Stunden-Schicht 150 Lieferungen vornehmen. In ländlichen Gebieten könnte der gleiche Lastwagen 20-30 verwalten. Der geometrische Grund: Stadtliche Stopps sind dicht beieinander (kurze Fahrt zwischen Stopps), während ländliche Stopps weit entfernt sind.

Zonenbasierte Routenführung teilt das Servicegebiet in geografische Cluster ein. Jede Zone wird einem Fahrzeug zugewiesen. Gute Zonen sind kompakt (ungefähr kreisförmig oder quadratisch) & zusammenhängend (keine Lücken oder isolierte Taschen). Das Ziel: Minimieren Sie die Gesamtentfernung, während Sie jede Route unter der Zeit-/Kapazitätsgrenze halten.

Das Vehicle-Routing-Problem (VRP) verallgemeinert TSP auf mehrere Fahrzeuge. Angesichts eines Depots, N Kunden & K Lastwagen (jeder mit Kapazitäts- & Zeitbeschränkungen) weisen Sie Kunden Lastwagen zu & sequenzieren Sie die Route jedes Lastwagens, um die Gesamtentfernung zu minimieren. VRP ist auch NP-schwer.

Eine gut gestaltete Zonenkarte erstellt Routen, in denen der Weg jedes Fahrers eine kompakte geometrische Form bildet: einen groben Kreis oder eine Lobe, die sich vom Depot erstreckt. Wenn Sie eine Route sehen, die sich selbst kreuzt oder mit der Zone eines anderen Fahrers überlappt, ist die Routenführung ineffizient.

Zonengestaltung

Ein Lieferunternehmen betreibt ein Depot in der Stadtmitte. Sie haben 4 Fahrer & 200 Lieferungen, die über ein ungefähr kreisförmiges Servicegebiet mit einem 10-Meilen-Radius verteilt sind.