Nidificazione della quantità massima di forme su una superficie

Question

Nell'industria, c'è spesso un problema in cui è necessario calcolare l'uso più efficiente del materiale, che si tratti di tessuto, legno, metallo ecc. Quindi il punto di partenza è X quantità di forme di date le dimensioni, fatte di poligoni e/o linee curve, e la destinazione è un altro poligono di dimensioni date.

Presumo che molte delle attuali suite CAM lo implementino, ma non avendo esperienza nell'uso di esse o dei loro interni, che tipo di algoritmo computazionale viene utilizzato per trovare l'uso più efficiente dello spazio? Qualcuno può indicarmi un libro o altro riferimento che discute questo argomento?

Answer 1

Dopo Andrea nella sua risposta mi indicò la direzione giusta e nominato il problema per me, ho deciso di scaricare i miei risultati di ricerca qui in una risposta separata.

Questo è davvero un problema di imballaggio e, per essere più precisi, è un problema di nidificazione. Il problema è matematicamente NP-difficile, e quindi gli algoritmi attualmente in uso sono approcci euristici. Non sembrano esserci soluzioni in grado di risolvere il problema in tempo lineare, tranne che per insiemi di problemi banali. La risoluzione di problemi complessi richiede da pochi minuti a ore con l'hardware attuale, se si desidera ottenere una soluzione con un buon utilizzo del materiale. Esistono decine di soluzioni software commerciali che offrono nidificazione di forme, ma non sono stato in grado di individuare alcuna soluzione open source, quindi non ci sono esempi reali in cui si possano vedere gli algoritmi effettivamente implementati.

Eccellente Descrizione della nidificazione e striscia problema nidificazione con le soluzioni storiche può essere trovato in un documento scritto da Benny Kjær Nielsen dell'Università di Copenaghen (Nielsen).

L'approccio generale sembra essere quello di mescolare e utilizzare più algoritmi noti al fine di trovare la migliore soluzione di annidamento. Questi algoritmi includono (Guided/Iterated) Local Search, veloce di vicinato Ricerca che si basa su No-Fit Polygon, e spintoni Euristica. Ho trovato un ottimo articolo su questo argomento con immagini di come funzionano gli algoritmi. Ha anche avuto benchmark delle diverse implementazioni software finora. Questo documento è stato presentato al Simposio internazionale sulla programmazione 2006 di S. Umetani et al (Umetani).

Una relativamente nuova ed eventualmente l'approccio migliore finora si riferiscono al Hybrid Genetic Algorithm (HGA), un ibrido costituito da Simulated Annealing e algoritmo genetico che è stata descritta da Wu Qingming et al dell'università di Wuhan (Quanming). Lo hanno implementato utilizzando Visual Studio, database SQL e GAOT (ottimizzazione degli algoritmi genetici) in MatLab.

Answer 2

Ti riferisci ad un noto dominio dell'informatica per l'informatica, per il quale esistono una serie di problemi definiti e di ricerca, sia per lo spazio bidimensionale che per lo spazio tridimensionale.

C'è un notevole materiale sulla rete disponibile per i problemi definiti, ma per trovarlo è necessario conoscere il nome del problema da cercare.

Alcuni pacchetti potrebbero adottare un appuratore euristico (che io sospetto che lo faranno) e alcuni potrebbero fare il possibile per calcolare tutte le possibilità di ottenere la risposta giusta.

http://en.wikipedia.org/wiki/Packing_problem