Technische Universiteit Delft
Faculteit Werktuigbouwkunde, Maritieme Techniek en Technische Materiaalwetenschappen
Transporttechnologie / Logistieke Techniek



M. Frumau Methoden voor Cutting & Packing problemen met onregelmatig gevormde voorwerpen.
Literatuuropdracht/scriptie, Rapport 95.3.LT.4547, Transporttechnologie, Logistieke Techniek.


De overeenkomst tussen cutting problemen en packing problemen ligt in het feit dat ze gebaseerd zijn op dezelfde logische structuur. Er wordt uitgegaan van twee groepen data: items en objecten.
De items vormen geometrische combinaties met elkaar waarna ze aan een object worden toegewezen. Deze geometrische combinaties worden patronen genoemd. Naast deze sterke overeenkomst, zijn er echter ook verschillen binnen het gebied. Om een goed overzicht van het gebied van de Cutting&Packing (C&P) te krijgen is er een opzet gemaakt van twee op elkaar aansluitende indelingen.

Bij de eerste indeling zijn de C&P problemen ingedeeld volgens de typologie in H. Dyckhoff "A typology of cutting and packing problems", European Journal of Operational Research, Vol.44 nr.2 (1990), pp.145-159. De typologie is gebaseerd op vier karakteristieken; namelijk: het aantal dimensies, de toekenningsvoorwaarden, het assortiment van items en het assortiment van objecten.
Het aantal dimensies wordt meestal aan de patronen of aan het probleem zelf gekoppeld. Dit is gelijk aan het minimale aantal dimensies dat nodig is om het patroon of probleem te beschrijven.
Bij de soort toekenning wordt er voor zowel items als objecten onderscheid gemaakt tussen het toekennen van een selectie en het toekennen van de hele verzameling aan patronen.
In verband met het assortiment van de items en objecten wordt er gekeken naar de samenstelling van de order met items en de soort beschikbare objecten. Dit kan variëren van identieke gedaante tot totaal verschillende gedaanten. De typering van C&P problemen bestaat dan uit een tupel van vier symbolen gevormd door de vier karakteristieken. (a/b/c/d)

Voor het aanbrengen van een verdergaande typering is een klassifikatie ontwikkeld op een tweede niveau. Het tweede niveau is gebaseerd op een indeling naar specifiek te onderzoeken probleemvelden. De grove indeling van de klassifikatie bestaat uit de onderverdeling in het aantal dimensies. Alhoewel het aantal dimensies ook al in de typologie van Dyckhoff verwerkt is, is er toch gekozen voor dergelijke grove indeling. Vaak bestaat er tussen problemen met een gelijk aantal dimensies een grotere overeenkomst in de wijze van aanpak dan dat men op grond van de typologie van Dyckhoff zou vermoeden. In de praktijk komen sommige problemen zo vaak voor dat deze tot een aparte klasse zijn verworden. Dit heeft tot gevolg dat de indeling uit zeven verschillende klassen is opgebouwd.

Uit de klasse van de niet-rechthoekige C&P problemen zijn de onregelmatige C&P problemen verder gestructureerd. De onregelmatige C&P problemen zijn met behulp van de systematiek in K.A. Dowsland en W.B. Dowsland "Packing Problems" European Journal of Operational Research Vol.56 nr.1, pp.2-14, ingedeeld in groepen naar de soort oplosmethode die wordt toegepast om een geschikt patroon te verkrijgen.
De eerste groep bestaat uit de groep van nestingmethoden. Onder een nestingmethode wordt verstaan de methode waarbij onregelmatige items in meer regelmatige vormen worden geplaatst, waarna deze eenvoudiger vormen op het bestemde object worden Geplaatst.
De tweede groep wordt de direkte plaatsingsmethoden genoemd. De items worden hierbij één voor één beschouwd en direkt volgens een bepaalde strategle op het object geplaatst.
De laatste groep wordt gevormd door de verbeteringsmethoden. Hieronder worden methoden verstaan waar een startpatroon wordt gegenereerd, dat vervolgens iteratief wordt verbeterd, totdat er een patroon ontstaat dat aan de gestelde eisen voldoet.

De methoden en algoritmen die onder de nestingmethoden en de direkte plaatsingsmethoden vallen zijn uitgebreid behandeld. De bespreking van de verbeteringsmethoden is, wegens gebrek aan informatie, beperkt gebleven tot een overzicht.

Nestingmethoden zijn in twee fasen onder te verdelen. De eerste fase produceert optimale regelmatige omsluitingen voor de aangeboden vormen of clustert eerst enkele vormen en omschrijft dan deze gevormde clusters. De regelmatige vormen worden tegels genoemd. Drie-, vier-, vijf- en zeshoeken zijn als tegels bruikbaar; polygonen met meer dan zes zijden zijn ongeschikt om te nesten.
De tweede fase creëert dan met behulp van deze tegels een optimaal patroon voor het object. Afhankelijk van de soort tegels die genest moeten worden, kunnen bestaande methoden, zoals rechthoekige packing algoritmen, worden toegepast om de tweede fase op te lossen.
Opvallend is dat de meeste nestingalgoritmen alleen de eerste fase van het nestingprobleem aanpakken. Een voordeel van de nestingmethoden is dat de procestijd die nodig is om een patroon te creëren vele malen korter is dan de tijd die een expert nodig heeft om een patroon met de hand samen te stellen. Hiernaast zijn de meeste nestingmethoden ook te combineren of uit te breiden met nieuwe of eerder ontwikkelde algoritmen zodat de methode aan de gewenste voorwaarden kan voldoen.

Bij de direkte methoden bestaat een groot verschil in complexiteit tussen de diverse methoden. De eerste methoden waren vrij eenvoudig en nauw verwant met handmatige methoden. De direkte methoden hebben allemaal één kenmerk gemeen, de items worden volgens een bepaalde plaatsingspolitiek in aangeboden volgorde op een object geplaatst. De methoden maken hierbij gebruik van single pass pakstrategieën. Het hele proces wordt dan voor verschillende ordeningen van de items of plaatsingen herhaald, waarna de beste oplossing wordt gekozen.
Sommige methoden benaderen onregelmatige vormen door meer regelmatige vormen. Zo kunnen bijna rechthoeken door een compositie van rechthoeken worden benaderd. Het is ook mogelijk dat onregelmatige delen worden benaderd door ze te clusteren en vervolgens te omschrijven door een eenvoudiger convex polycoon. De methoden hebben wel sterke overeenkomsten met de nestingmethoden, maar omdat de benaderde delen nog steeds onregelmatig zijn valt de methode onder de direkte plaatsingsmethoden.
Er is ook een methode ontwikkeld die geschikt is voor het plaatsen van zeer onregelmatige delen. De items worden niet benaderd door eenvoudiger vormen maar er wordt gebruik gemaakt van een verschuivingsalgoritme. De items worden dan langs een vector naar de gewenste positie bewogen.
Bij de meer complexe oplosmethoden wordt er vaak interdisciplinair gewerkt. Er is een methode ontwikkeld die gebaseerd is op technieken uit de artificial intelligence en de operationele research. Waarbij het probleem met een algemene oplostechniek opgelost wordt aan de hand van een zoektocht door de ruimte van kandidaatoplossingen. Ook is het mogelijk om plaatselijk verbeteringen in het patroon aan te brengen. De relatie met de verbeteringsmethoden is hierdoor sterk aanwezig.
Als vervolg op dit soort complexe methoden is er een gestructureerde aanpak voor layoutproblemen opgezet. De aanpak bestaat uit een effectief zoekproces gebaseerd op heuristieken waarbij verder ingegaan is op de mogelijkheden van artificial intelligence en de operationele research technieken.
Het voordeel van de direkte plaatsingsmethoden t.o.v. de nestingmethoden is dat er qua materiaalbenutting efficiëntere layouts gecreëerd kunnen worden. Een nadeel is dat de methoden over het algemeen complexer zijn en daardoor meer rekentijd kosten.

Verbeteringsmethoden zoeken voortdurend naar verbeteringen, of bevatten een metaheuristiek zoals 'simulated annealing', 'tabu search' of een genetisch algoritme waarmee het mogelijk wordt dat er ook oplossingen worden gegenereerd die slechter zijn dan de bestaande oplossing. Op deze wijze wordt getracht de beste globale oplossing te vinden en niet te blijven steken bij een lokaal beste oplossing.
De startlayouts worden meestal gecreëerd op een gelijksoortige wijze als bij de direkte plaatsingsmethoden plaatsvindt maar er zijn ook enkele methoden ontwikkeld die gebruik maken van nestingmethoden.
De verbeteringsmethoden beloven wel efficiëntere layouts dan bij de nestingmethoden en direkte plaatsingsmethoden te behalen zijn. Een nadeel is dat de meeste verbeteringsmethoden nog experimenteel van aard zijn en dat het mede hierdoor het moeilijk is om de benodigde informatie te bemachtigen. Tevens moet er rekening worden gehouden met het feit dat de methoden complexer zijn zodat er meer procestijd en geheugencapaciteit vereist is dan dat bij de twee andere groepen het geval is.

Er is nu een duidelijk beeld van de diverse onregelmatige C&P problemen ontstaan. Het is echter aan te bevelen om de onregelmatige C&P problemen verder te analyseren. Dit geldt met name voor de groep van verbeteringsmethoden. Hiernaast is het belangrijk dat er goede testmethoden worden ontwikkeld zodat de verschillende methoden beter met elkaar kunnen worden vergeleken.
Tevens zullen er door ontwikkeling van de techniek in de toekomst veel ontwikkelingen op het gebied van de onregelmatige C&P problemen plaatsvinden. Randvoorwaarden zijn hierbij wel dat de verschillende praktijkgebieden beter met elkaar gaan communiceren en dat er een goede standaardisatie wordt opgezet. Met de hier opgezette structuur is een stap in de goede richting gezet.


Rapporten studenten Logistieke Techniek
Gewijzigd: 1997.09.23; logistics@3mE.tudelft.nl , TU Delft / 3mE / TT / LT.