Visualisierung von Verfahren für zweidimensionale Packprobleme

 

Der Begriff "Packproblem" wird vielen auf den ersten Blick nichts Konkretes sagen, indirekt hat sich wohl jeder schon damit beschäftigt, z.B. beim Einräumen eines Versandpaketes mit mehreren Utensilien. Dort stellt sich z.B. die Frage, ob auch alles hineinpaßt oder ob gar eine größere Verpackung verwendet werden muß. Auch beim erstmaligen Einräumen eines Küchenschrankes mit vielen Gläsern erkennt man nicht auf den ersten Blick, wie viele Gläser in dem Schrank Platz finden. Eine optimale bzw. suboptimale Lösung beruht hier entweder auf Erfahrungswerten oder wird durch mehr oder weniger planvolles Ausprobieren herausgefunden.

Ziel der Diplomarbeit war es, ein Computerprogramm zu entwickeln, das zwei verschiedene Lösungsmöglichkeiten für ein Packproblem visualisieren soll. Der Anwender soll dabei verstehen, wie die Lösungen zustande kommen, um sie gegebenenfalls selbst bei Bedarf schriftlich konzipieren zu können. Das Packproblem wurde dabei auf das zweidimensionale homogene Packproblem eingeschränkt. Zweidimensional bedeutet, daß die Höhe der Packstücke keine Relevanz für die Lösung hat. Homogen heißt, daß es sich um einheitliche Packstücke handeln muß, d. h. die Packstücke müssen alle die gleiche Maße besitzen.

Die Absicht der vorliegenden Arbeit ist es, einfache Techniken zur Lösung von zweidimensionalen homogenen Packproblemen zu vermitteln. Der Schwerpunkt der Arbeit lag dabei mehr auf der Visualisierung und nicht so sehr im Finden der optimalen Lösungen. Hierzu wurde diese Arbeit inhaltlich in mehrere Abschnitte untergliedert. Im ersten Abschnitt findet eine Einleitung in Lernprogramme und Operations Research statt, dem eine Einführung in das Thema "zweidimensionales homogenes Packproblem" folgt. Der dritte Abschnitt befaßt sich mit Grundbegriffen, die unbedingt notwendig sind, um eine Lösung zu verstehen. Auf diesen Grundbegriffen aufbauend, findet man im vierten Kapitel verschiedene Lösungverfahren bzw. -ansätze. Kapitel 5 stellt das zu dieser Arbeit entwickelte Computerprogramm "Pack-It" vor. Kapitel 6 beschäftigt sich damit, wie das Computerprogramm im einzelnen realisiert wurde. Schließlich befaßt sich Kapitel 7 mit einem Vergleich und einer anschließenden Bewertung der realisierten Verfahren.

Das erste realisierte Verfahren ist ein reines Zufallsverfahren, das die Packstücke zufällig anordnet. Das zweite Verfahren basiert auf den Grundideen der Verfahren "Guillotineschnitte", benutzt aber auch Zufallszahlen für die Anordnung der Packstücke. Die beiden Verfahren können mehrmals durchlaufen werden, am Ende wird jeweils die beste Lösung angezeigt. Zudem wird noch ein theoretischer Wert ermittelt, der zum Vergleich der Lösungen benutzt werden kann. Dieser theoretische Wert basiert auch auf Guillotineverfahren, gibt aber nicht unbedingt die optimale Anzahl an.


Autor: Harald Hartmann

Tips und Anregungen an: emiel@informatik.fh-augsburg.de
Stand: 21.03.2003