Cube Utilization and Bin Packing

Stacking: 3D Geometry in Every Trailer

Een standaard pallet in Noord-Amerika is 48 inch by 40 inch (GMA pallet). Dit is de fundamentale eenheid van logistiek geometrie.

Cube utilization meet hoe efficiënt u een ruimte vult: de werkelijke productvolume gedeeld door het beschikbare volume. Een trailer die vol is qua gewicht maar maar de helft vol is qua volume heeft slechte cube utilization. Een trailer die tot het plafond is opgestapeld heeft uitstekende cube utilization.

Column stacking: elke laag is identiek, dozen direct op elkaar. Structuurzwak maar ruimte efficiënt gebruiken.

Interlocking (pinwheel) stacking: alternatieve lagen zijn 90 graden gedraaid. Veel stabiel maar creëert gaten aan de randen, verloren gaat 5-15% van het pallet voetstuk.

Container loading is de echte geometrische uitdaging: vierkante dozen van verschillende maten passen in een 40 voet vrachtcontainer (binnenafmetingen ongeveer 39'5" x 7'8" x 7'10"). Dit is 3D bin packing: een van de klassieke NP-hard problemen in de wiskunde. Geen algoritme kan de optimale oplossing garanderen binnen redelijke tijd voor grote voorbeelden.

In de praktijk gebruiken logistiek bedrijven heuristische benaderingen: grootste items eerst, vloeroppervlak vullen voordat er gestapeld wordt in hoogte, groepen items op basis van bestemming voor efficiëntie bij het lossen.

Pallet Loading Efficiency

Je moet dozen laden die 12 inch lang, 10 inch breed & 8 inch hoog zijn op een standaard 48" x 40" pallet. De maximale stapelhoogte is 48 inches.

Waarom de routeoptimalisatie moeilijk wordt

Het Reisverkoperprobleem (TSP)

Stel dat je 10 klanten moet bezoeken en terug moet keren naar je depot. Wat is de kortste route? Dit is het Reisverkoperprobleem: een van de meest bestudeerde problemen in wiskunde en informatica.

De moeilijkheid zit in de combinatorische ontplooiing. Voor N stops zijn er (N-1)!/2 unieke routes (deling door 2 omdat kloksgewijs en tegen de klok in dezelfde afstand hebben.).

- 5 stops: 12 routes: controleren in milliseconden

- 10 stops: 181.440 routes: nog steeds haalbaar voor een computer

- 15 stops: 43.6 miljard routes: neemt uren in beslag

- 20 stops: 60.8 kwadrijoen routes: neemt eeuwen in beslag

- 50 stops: meer routes dan atomen in het zichtbare universum

TSP is NP-hard: er is geen bekend algoritme dat het in polynoom tijd kan oplossen. Naarmate N toeneemt, worden exacte oplossingen onmogelijk en moeten we heuristieken gebruiken: algoritmen die snel goede (hoewel niet gegarandeerd optimale) oplossingen vinden.

Gewone heuristieken:

- Nabijste steeds: Vanaf de huidige locatie ga je altijd naar de dichtstbijzijnde onbezochte stop. Snel, maar produceert vaak routes met lelijke kruisingen.

- Convex hull insertie: Begin met de buitenste stops (de convexen hull: de wiskundige grens). Plaats vervolgens interne stops een voor een waar ze de minste afstand toevoegen.

- 2-opt verbetering: Neem een afgeronde route en probeer paren van randen om te wisselen. Als het verwijderen van twee randen en ze op een andere manier opnieuw verbinden de route korter maakt, houd de wissel vast. Herhaal tot er geen verbetering meer wordt gevonden.

Heuristieken vs Exacte Oplossingen

Een bezorgbedrijf heeft vandaag 12 stops. Hun bestuurder gebruikt de heuristiek van de dichtstbijzijnde buur: op elk punt rijdt hij naar de dichtstbijzijnde onbezochte stop.

Zones, Density, and the Vehicle Routing Problem

Last-Mile Delivery: Where Geometry Meets Economics

De last mile: vanuit het distributiecentrum naar de deur van de klant: staat voor 40-50% van de totale transportkosten. Het is de meest geometrisch beperkte deel van de supply chain.

Radial routes from a depot: Bezorgwagens vertrekken vanuit een centraal distributiecentrum. De route van elke wagen moet een compact geografisch gebied afdekken: geen twee wagens moeten elkaar's territorium kruisen.

Delivery density bepaalt alles. In een dichtbevolkt stedelijk gebied kan een wagen 150 bezorgingen uitvoeren in een 8-urige dienst. In landelijke gebieden zou dezelfde wagen 20-30 kunnen doen. De geometrische reden: stedelijke stops zijn dicht bij elkaar (kort rijden tussen stops) terwijl landelijke stops verder uit elkaar liggen.

Zone-based routing deelt het servicegebied op in geografische clusters. Elke zone wordt toegekend aan één voertuig. Goede zones zijn compact (ongeveer cirkelvormig of vierkant) & contiguous (geen gaten of geïsoleerde pocketjes). Het doel: de totale afstand verminderen terwijl elke route onder de tijd/benodigde capaciteit blijft.

Het Voertuigroute probleem (VRP) generaliseert TSP naar meerdere voertuigen. Gegeven een depot, N klanten, & K trucks (elk met capaciteit & tijdbeperkingen), toewijzen klanten aan trucks & sequentie elke trucks route om de totale afstand te minimaliseren. VRP is ook NP-hard.

Een goed ontworpen zonekaart creëert routes waarbij elke bestuurders pad een gecompacter geometrisch formaat vormt: een ruwe cirkel of lobe die uitstroomt vanaf het depot. Als je een route ziet die zichzelf kruist of overlapt met de zone van een andere bestuurder, is de routing ondoeltreffend.

Zone Ontwerp

Een leveringsbedrijf werkt vanuit een depot in het centrum van een stad. Ze hebben 4 chauffeurs & 200 leveringen verspreid over een ongeveer cirkelvormig servicegebied met een straal van 10 mijl.