Algoritmi Di Nesting

[emanuele.croci]

Ciao a tutti,

vorrei sapere se qualcuno ha materiale, link da segnalare o consigli da dare per la realizzazione di algoritmi di nesting.

Cioè: a partire da una superficie piana, ad es. lamiera...tessuto... , vogliamo ricavare con un utensile di taglio il maggior numero possibile di forme uguali, riducendo al minimo lo sfrido.

Ciò eventualmente ruotando o "incastrando" tra loro le forme.

Esistono dei software free per fare ciò? Esiste una letteratura al riguardo?

Grazie e Ciao,

Emanuele

P.S.: Ero indeciso su dove postarlo, spero che "controllo e regolazione" sia OK!

[ifachsoftware]

Facendo delle ricerche con google con delle chiavi 2D BIN BACKING o 3D BIN BACKING avevo trovato degli algoritmi in C per la risoluzione di problemi con rettangoli o cubi.

Altre funzioni per l'ottimizzazione del taglio di sbarre in base alle lunghezze da ottenere per avere il minimo sfrido me le ero scritte da solo , trovando successivamente su un sito conferma delle mie scelte (ossia che spesso e' meglio una buona soluzione in tempi ragionevoli che l'ottima soluzione in tempi inaccettabili).

Ciao

Modificato: 21 febbraio 2006 da ifachsoftware

[Livio Orsini]

Emanuele suppongo che si debba partire da una pezzatura rettangolare e ricavarne un certo numero di sottoinsiemi, rettangolari, riducendo al minimo lo sfrido.

E' un vecchio problema. Io lo avevo affrontato circa 30 anni fa (con i mezzi di micro informatica del tempo, cioè 8085 e simili ). Gli algoritmi usati sono sempre di tipo euristico, ovverossia si ricerca l'ottimizzazione reiterando i tentativi. In pratica si inserisce il formato da tagliare ed i formati di taglio previsti ed il numero di pezzi per formato. L'algoritmo è simile ad, entro certi limiti, ad un algoritmo di ordinamento. Il programma parte sommando un certo numero di pezzi in modo casuale e calcola la superficie di scarto, poi riprova con una altra combinazione casuale e, se la superficie di sfrido è inferiore alla precedente, memorizza la nuova configurazione; poi si riprova fino a che lo sfrido è inferiore ad una certa soglia o fino a che è trascorso il tempo massimo.

Si può provare a rendere il sistema un poco più intelligente facendo una sorta di auto apprendimento. Se le forme sono sempre standard e variano solo per composizione, la cosa è fattibile. Cerco di spiegarmi meglio. Se, per esempio, la pezzatura di aprtenza èuò assumere solo due valori, e le pezzature di taglio sono comprese in un massimo di cinque formati, si può fare in modo che, dopo alcune ottimizzazioni, il programma abbia memorizzato le condizioni di aprtenza più favorevoli.

L'ottimizzazione di tagli per sola lunghezza è molto più agevole.

Comunque questo è uno dei problemi più "pesanti" da risolvere.

Modificato: 21 febbraio 2006 da Livio Orsini

[emanuele.croci]

Purtroppo il mio problema è anche più complesso, in quanto:

- la forma di partenza (foglio da cui ricavare i tagli) è sempre un rettangolo, di dimensioni variabili

- l'oggetto da ricavare è uno solo, però di forma a piacere, ad es. il disegno di un coccodrillo: da un rettangolo 4000x1000 voglio ricavare il maggior numero di coccodrilli di 600x200.... poi tra un'ora vorrò ricavare da un rettangolo 3000x1200 delle automobiline 500x300. E vorrei anche fare gli incastri, ad es. mettere i coccodrilli uno a testa in su e l'altro a testa in giù, oppure infiilare la coda di uno nella bocca di un altro, ecc.....

- Non considero invece tagli di figure "miste", ad es. NON voglio ricavare coccodrilli e automobiline insieme.

Ma qualche testo che permetta di "inquadrare" il problema esiste??

Grazie e Ciao,

Emanuele

[Piero Azzoni]

non ne sono sisuro, ma mi pare esista qualcosa del genere nel settire tessile manifatturiero dove hanno stendono su apposite macchine piu' strati di tessuto e devono ricavare forme complesse che continuano a cambiare in aspetto e dimensione

prova a cercare li'

[ifachsoftware]

Prova

Qui

oppure

Qui

oppure

Qui

Qui

Qui

Qui

se non ti bastano impara ad usare google

Ciao

Modificato: 22 febbraio 2006 da ifachsoftware

[ifachsoftware]

Ti segnalo anche Questo link dove ci sono dei begli esempi in C che ti avevo citato.

Ciao

[emanuele.croci]

OK vedrò di imparare questo GOOOOOOgle...

Grazie per i link!

Ciao, Emanuele

[ingcris]

ciao... il tuo problema mi ricorda un teme d'esame di informatica 2 svolto al politecnico di milano.

ti do il link della pagina del professore:

http://www.elet.polimi.it/upload/brevegli/...enti/2000-2001/

e il link alla raccolta dei temi d'esame:

ftp://ftp.elet.polimi.it/outgoing/Luca.Br...01/tesa0001.pdf

nei temi d'esame vai a pagina 214 esercizio 1 "strada da lastricare".

mi sembra di aver capito che tutto cio possa c'entrare qualcosa, spero. è ovvio che dovrai adattare l'algoritmo di backtracking in questione al tuo caso

sperando che ti possa servire a qualcosa, ti saluto.

cristian

[emanuele.croci]

Ciao Cristian,

molto bella la raccolta di esercizi.

Il problema di pag.214 è concettualmente abbastanza simile al mio.

La differenza è che in quel problema, se a un certo punto SCEGLI una pietra, SAI anche come posarla.

Invece io dovrei (una volta scelta la pietra) provare un'infinità di combinazioni di rototraslazione per provare ad incastrarla al meglio alle pietre già posate.

E già questo punto, da solo, mi disorienta: come vedere se le 2 pietre si toccano o se ho raggiunto una distanza minima tra esse o se le posso ancora avvicinare??

Grazie e Ciao,

Emanuele

[ifachsoftware]

come vedere se le 2 pietre si toccano o se ho raggiunto una distanza minima tra esse o se le posso ancora avvicinare??

Potresti ridurre il contorno della tua sagoma a tanti segmenti e fare un algoritmo che prova le intersezioni tra tutti i segmenti ; il problema e' che i confronti saranno esponenziali e poi una volta rilevata l'intersezione devi risolvere il problema di calcolare la minima distanza e come puoi ben intuire ci vorranno tantissimi calcoli.

E' per questo motivo che io con altre applicazioni (piu' semplici) mi limitavo a trovare delle buone soluzioni in tempi decenti piuttosto che la soluzione ottimale in tempi tendenti all'infinito.

Ciao

Modificato: 23 febbraio 2006 da ifachsoftware

[Livio Orsini]

Probabilmete la soluzione al tuo problema è inscrivere le forme entro poligoni. Non credo che lo sfrido risultante dall'iscrizione in poligoni sia maggiore si quello che si avrebbe con sagome libere. In compenso i calcoli diminuiscono di molto e l'algortimo si semplifica di molto. Purtroppo questo tipo di ottimizzazioni si risolve quasi sempre in modo euristico e, molto difficilmente, lo si può approcciare in modo deterministico, mentre

[dcremonini]

Non voglio affatto scoraggiarti ma un'azienda di modellismo (i modelli cui mi riferisco sono quelli per fare i vestiti) aveva il tuo stesso problema ma in forma ancora più complessa poiché trattandosi di abbigliamento i pezzi erano tutti diversi uno dall'altro. L'azienda aveva del software per farlo (non conosco alcun dettaglio poiché era una chiacchierata) ma i risultati erano meno soddisfacenti in automatico che in manuale.

Aggiungo un link ad un documento che espone i risultati applicativi di un algoritmo di nesting:

http://www.ihi.co.jp/ihi/technology/gihou/image/38-1-7.pdf

Modificato: 23 febbraio 2006 da dcremonini

[emanuele.croci]

Grazie per il link, continuerò a pensarci su anche se la cosa appare ardua...

Ciao, Emanuele