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.