Bestimmung des Gepäckraumvolumens eines PKWs

Aufgabe besteht darin, möglichst viele starre Quader mit einem
Seitenverhältnis von $4:2:1$ in einen unregelmäßig geformten Container zu
packen. Motiviert durch die Struktur der bisher manuell erstellten Packungen
verfolgen wir einen diskreten Lösungsansatz. Dieses diskrete Packungsproblem
läßt sich auf die Berechnung einer größtmöglichen unabhängigen
Knotenmenge reduzieren.

Wir formulieren das Problem zunächst als ganzzahliges lineares Programm, das
allerdings nur für sehr kleine Instanzen mit angemessenem Rechenaufwand
beweisbar optimal gelöst werden kann. Daher stellen wir verschiedene
Heuristiken vor, die zum Beispiel auf einer Relaxierung des ganzzahligen
linearen Programms oder lokaler Suche basieren. Andere Heuristiken generieren
zunächst dichte Packungen für den Kern des Containers und reduzieren so das
Problem auf eine Reihe kleinerer Teilprobleme.