Raumausnutzung und Ladungspackung

Stapeln: 3D-Geometrie in jedem Trailer

Ein standardmäßiges Palettenformat in Nordamerika ist 48 Zoll breit und 40 Zoll tief (GMA-Palette). Dies ist die grundlegende Einheit der Logistik-Geometrie.

Raumausnutzung misst, wie effizient ein Raum genutzt wird: tatsächliche Produktvolumen geteilt durch verfügbares Volumen. Ein Trailer, der voll gewogen ist, aber nur zur Hälfte mit Volumen gefüllt ist, hat eine schlechte Raumausnutzung. Ein vollständig bis zur Decke gefüllter Trailer hat eine ausgezeichnete Raumausnutzung.

Säulenstapeln: Jede Schicht ist identisch, Kisten liegen direkt aufeinander. Strukturell schwach, aber effizient im Raumausnutzen.

Verknotetes Stapeln (Gabelstapeln): Alternierende Schichten sind um 90 Grad gedreht. Viel stabiler, aber erzeugt Lücken an den Rändern und verursacht einen Verlust von 5-15% des Paletten-Fußbodens.

Containerverladung ist die echte geometrische Herausforderung: Rechteckige Kisten verschiedener Größen in einen 40-Fuß-Transportcontainer (innere Abmessungen ungefähr 39'5" x 7'8" x 7'10"). Dies ist 3D-Ladungspackung: eines der klassischen NP-harten Probleme in der Informatik. Kein Algorithmus kann eine optimale Lösung in angemessener Zeit für große Instanzen garantieren.

In der Praxis verwenden Logistikunternehmen Heuristika: Zuerst die größten Gegenstände, erst dann die Höhe, bevor die Fläche des Bodens gefüllt wird, Gruppierung von Gegenständen nach Bestimmungsort für Effizienz beim Entladen.

Effizienz des Palettenverladens

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

Warum wird die Streckenoptimierung schwieriger

Das Reiseverkäufer-Problem (TSP)

Stell dir vor, du musst 10 Kunden besuchen und zurück zum Depot fahren. Welche ist die kürzeste Route? Dies ist das Reiseverkäufer-Problem: eines der am häufigsten untersuchten Probleme in Mathematik und Informatik.

Die Schwierigkeit liegt in der kombinatorischen Explosion. Für N Haltestellen gibt es (N-1)!/2 eindeutige Routen (geteilt durch 2, weil Uhrzeiten und gegen Uhrzeiten den gleichen Abstand haben).

- 5 Haltestellen: 12 Routen: prüfe sie in Millisekunden

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

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

- 20 Haltestellen: 60,8 Billionen Routen: dauert Jahrhunderte

- 50 Haltestellen: mehr Routen als Atome im beobachteten Universum

TSP ist NP-schwer: es gibt keine bekannte Algorithmen, die es in polynomialer Zeit lösen können. Je größer N wird, werden exakte Lösungen unmöglich und wir müssen Heuristiken verwenden: Algorithmen, die gute (aber nicht garantiert optimale) Lösungen schnell finden.

Häufige Heuristiken:

- Nächster Nachbar: Von der aktuellen Position immer zur nächsten unbesuchten Haltestelle. Schnell, aber oft führt es zu Routen mit hässlichen Kreuzungen.

- Einfügung im konvexen Hull: Beginne mit den äußersten Haltestellen (dem konvexen Hull: der geometrische Rand). Füge dann im Innern die Haltestellen ein, indem sie am wenigsten Abstand hinzufügen.

- 2-opt-Verbesserung: Nehme eine abgeschlossene Route und versuche, Paare von Kanten zu tauschen. Wenn das Entfernen von zwei Kanten und das Verbinden in einer anderen Weise die Route kürzer macht, behalte die Änderung bei. Wiederhole, bis keine Verbesserung mehr gefunden wird.

Heuristiken vs. exakte Lösungen

Ein Lieferunternehmen hat heute 12 Haltestellen. Ihr Fahrer verwendet den nächstgelegenen Nachbar-Heuristik: Bei jedem Punkt fährt er zur nächsten unbesuchten Haltestelle.

Zonen, Dichte und das Fahrzeugroutenproblem

Letzte-Meile-Lieferung: Wo Geometrie auf Ökonomie trifft

Die letzte Meile: von der Verteilungszentrale zum Kunden zu Hause: macht 40-50% des gesamten Transportkosten aus. Es ist der am stärksten geometrisch eingeschränkte Teil der Lieferkette.

Strahlförmige Strecken von einer Zulieferstation: Lieferfahrzeuge fahren von einem zentralen Verteilungszentrum aus. Jedes Fahrzeug sollte eine kompakte geografische Zone abdecken: keine beiden Fahrzeuge sollten sich gegenseitig die Strecke überkreuzen.

Lieferdichte bestimmt alles. In einer dichten städtischen Area könnte ein Fahrzeug 150 Lieferungen in einem 8-stündigen Schicht machen. In ländlichen Gebieten könnte das gleiche Fahrzeug 20-30 Lieferungen bewältigen. Der geometrische Grund: städtische Haltestellen sind eng beieinander (kurze Fahrt zwischen den Haltestellen) während ländliche Haltestellen sind weit voneinander entfernt.

Zonenbasiertes Routing teilt den Versorgungsraum in geografische Cluster auf. Jeder Zone wird ein Fahrzeug zugewiesen. Gute Zonen sind kompakt (ungefähr kreisförmig oder quadratisch) und kontinuierlich (ohne Lücken oder isolierte Taschen). Das Ziel: die Gesamtdistanz zu minimieren, während jeder Route unter der Zeit-/Leistungsgrenze bleibt.

Das Fahrzeugroutenproblem (VRP) generalisiert TSP für mehrere Fahrzeuge. Gegeben ein Depot, N Kunden und K Lastwagen (jeder mit Kapazitäts- und Zeitbeschränkungen), zugeteilt Kunden zu Lastwagen und sequenziert jeder Lastwagensroute, um die gesamte Entfernung zu minimieren. VRP ist auch NP-schwer.

Ein gut entworfenes Zonenplan erstellt Routen, bei denen sich der Weg jedes Fahrers zu einer kompakten geometrischen Form bildet: eine ungefähr kreisförmige oder Lobe, die vom Depot ausgeht. Wenn Sie eine Route sehen, die sich selbst kreuzt oder mit der anderen Fahrer's Zone überschneidet, ist die Routierung ineffizient.

Zonenentwurf

Ein Lieferunternehmen betreibt von einem Depot in der Innenstadt einer Stadt. Sie haben 4 Fahrer und 200 Lieferungen, die im Bereich eines rundlichen Servicebereichs mit einem Radius von 10 Meilen verteilt sind.