Kubegebruik en Bin Packing

Stapelen: 3D-geometrie in elke aanhanger

Een standaard pallet in Noord-Amerika is 48 inch bij 40 inch (GMA-pallet). Dit is de fundamentele eenheid van logistieke geometrie.

Kubegebruik meet hoe efficiënt je een ruimte vult: werkelijk productvolume gedeeld door beschikbaar volume. Een aanhanger die vol is qua gewicht maar halfleeg qua volume heeft slecht kubegebruik. Een aanhanger verpakt tot aan het plafond heeft uitstekend kubegebruik.

Kolom stapelen: elke laag is identiek, dozen rechtstreeks bovenop elkaar. Structureel zwak maar gebruikt ruimte efficiënt.

Ineigratelend (windmolen) stapelen: afwisselende lagen worden 90 graden geroteerd. Veel stabieler maar creëert leegte aan de randen, wat 5-15% van de paletvoetafdruk verspilt.

Containerladingen is de echte geometrische uitdaging: rechthoekige dozen van verschillende maten in een 40-voet shippingcontainer passen (interne afmetingen ongeveer 39'5" x 7'8" x 7'10"). Dit is 3D bin packing: één van de klassieke NP-moeilijke problemen in informatica. Geen algoritme kan de optimale oplossing in redelijke tijd garanderen voor grote instanties.

In de praktijk gebruiken logistieke bedrijven heuristische benaderingen: grootste items eerst, vul vloeroppervlakte alvorens hoogte te stapelen, groepeer items per bestemming voor uitlaadefficiëntie.

Efficiëntie van Paletladingen

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 inch.

Waarom Routeoptimalisatie Moeilijk Wordt

Het Handelsreiziger Probleem (TSP)

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

De moeilijkheid is combinatorische explosie. Voor N haltes zijn er (N-1)!/2 unieke routes (gedeeld door 2 omdat met de klok mee & tegen de klok in dezelfde afstand hebben).

- 5 haltes: 12 routes: controleer ze allemaal in milliseconden

- 10 haltes: 181.440 routes: nog steeds hanteerbaar voor een computer

- 15 haltes: 43,6 miljard routes: duurt uren

- 20 haltes: 60,8 biljoen routes: duurt eeuwen

- 50 haltes: meer routes dan atomen in het waarneembare universum

TSP is NP-moeilijk: geen bekend algoritme kan het in polynomiale tijd oplossen. Naarmate N groeit, worden exacte oplossingen onmogelijk en moeten we heuristieken gebruiken: algoritmen die goede (maar niet gegarandeerd optimale) oplossingen snel vinden.

Veel gebruikte heuristieken:

- Dichtstbijzijnde buur: Van de huidige locatie altijd naar de dichtste onbezochte halte gaan. Snel maar produceert vaak routes met lelijke kruisingen.

- Convex-omhullingsinvoering: Begin met de buitenste haltes (de convex omhulling: de geometrische grens). Voeg dan stap voor stap inwendige haltes in waar ze de minste afstand toevoegen.

- 2-opt verbetering: Neem een voltooide route & probeer paren randen om te wisselen. Als je twee randen verwijdert & anders herverbindt en de route korter wordt, behoud je de wissel. Herhaal totdat geen verbetering meer mogelijk is.

Heuristieken versus Exacte Oplossingen

Een bezorgbedrijf heeft vandaag 12 haltes. De chauffeur gebruikt de dichtstbijzijnde-buur heuristiek: rijd op elk punt naar de dichtste onbezochte halte.

Zones, Dichtheid en het Vehicle Routing Problem

Last-Mile Bezorging: Waar Geometrie Economie Ontmoet

De laatste mijl: van distributiepunt naar de deur van de klant: maakt 40-50% van de totale verzendkosten uit. Het is het meest geometrisch beperkte deel van de toeleveringsketen.

Radiale routes van een depot: Bezorgwagens waaieren uit van een centraal distributiepunt. De route van elke vrachtwagen moet een compacte geografische zone bestrijken: geen twee wagens moeten elkaars territoria kruisen.

Bezorgdichtheid bepaalt alles. In een dicht stedelijk gebied kan een vrachtwagen 150 bezorgingen in een 8-uurs dienst doen. Op het platteland kan dezelfde vrachtwagen 20-30 doen. De geometrische reden: stedelijke haltes liggen dicht bij elkaar (korte rit tussen haltes) terwijl plattelandshaltes ver uit elkaar liggen.

Zona-gebaseerde routering verdeelt het servicegebied in geografische clusters. Elke zone wordt aan één voertuig toegewezen. Goede zones zijn compact (ruwweg cirkelvormig of vierkant) & aaneengesloten (geen gaten of geïsoleerde pockets). Het doel: minimaliseer de totale afstand met elke route onder de tijd-/capaciteitslimiet.

Het Vehicle Routing Problem (VRP) generaliseert TSP naar meerdere voertuigen. Gegeven een depot, N klanten, & K vrachtwagens (elk met capaciteits- & tijdbeperkingen), wijs klanten aan vrachtwagens toe & sequentialiseer elke vrachtwagenroute om de totale afstand te minimaliseren. VRP is ook NP-moeilijk.

Een goed ontworpen zonekaart creëert routes waarbij het pad van elke chauffeur een compacte geometrische vorm vormt: ruwweg een cirkel of lob die zich uitstrekt van het depot. Als je een route ziet die zichzelf kruist of overlapt met de zone van een ander voertuig, is de routering inefficiënt.

Zoneontwerp

Een bezorgbedrijf werkt vanuit een depot in het centrum van een stad. Ze hebben 4 chauffeurs & 200 bezorgingen verdeeld over een ruwweg cirkelvormig servicegebied met een straal van 10 mijl.