Non sono sicuro sui miei tag per questa domanda, ma in breve ....
Ho bisogno di risolvere un problema di imballaggio di parti industriali in casse, riducendo al minimo l'area di contenimento totale. Queste parti sono motori, o pompe, o componenti su misura, e hanno forme piuttosto insolite. Per alcuni, è possibile ipotizzare che una parte === cuboid rettangolare, ma alcuni non sono così semplici, cioè assumono una forma più simile a quella di un martello o di una lettera T. Con quelli, (assumendo la forma 2D), di direzione alternata di top & in basso, si possono imballare più oggetti nello stesso spazio, che se tutti i piani fossero nella stessa direzione. Esempio grezzo sotto con lettera "T" parti:
***** xxxxx ***** x ***** *** ooo
* x vs * x vs * x vs * x o
* x * xxxxx * x * x o
xxxxx xxx
In questo momento stiamo risolvendo il problema con qualcosa del genere:
- utilizzando il software CAD, crea i modelli reali di come vanno le cose nelle scatole di casse
- fai una stima delle dimensioni reali delle casse e amp; scrivili nel file Excel
(1) è una magra quantità di lavoro e come risultato abbiamo solo un numero limitato di voci possibili in (2), il file Excel.
Il bello è che programmare questo è relativamente facile. Data una combinazione di prodotti da inserire nelle casse, eseguiamo una ricerca e, se la voce esiste in Excel (o Database), la estrapoliamo. In caso contrario, diciamo "scusa, nessun dato!".
Non voglio necessariamente fare tutto il necessario per inventare un algoritmo pazzo che, data la descrizione di una parte geometrica, può allineare, ruotare e capire la parte migliore dell'imballaggio in una cassa, data la sua forma, ma forse lo faccio ..
Domanda
Bene, ecco la mia domanda: assumendo che io possa rappresentare le mie parti come 2D (per essere determinato come), e che alcune parti assomiglino alla lettera T, e alcune parti sembrano rettangoli, quale algoritmo posso usare per darmi una buona stima delle dimensioni dell'area che circonda, assicurando al contempo che le parti siano imballate in un'area minima possibile, per ridurre al minimo i costi di imballaggio / spedizione?
Ci sono algoritmi di approssimazione?
Vedendo come questo può diventare complesso, esiste una libreria che posso usare?
Il mio pensiero / approccio
Il mio approccio ingenuo sarebbe definire un modo per descrivere la posizione delle parti e posizionare la prima parte, calcolare l'area di copertura totale e amp; dimensioni. Quindi posizionare la seconda parte con orientamento a 0 gradi, ripetere, posizionarla a 180 gradi, ripetere (nel mio caso non credo che le rotazioni di 90 gradi siano significative a causa delle lunghe lunghezze delle parti). Procedere usando la forza bruta "attaccando" le altre parti nell'area di chiusura fino a quando tutte le parti vengono elaborate.
Potrei dover spostare alcune parti un po '(vedi 3 esempio pittorico sopra con le lettere T). Questo aggiunge uno strato di complessità 2D piuttosto che 1D. Non sono sicuro di come affrontarlo. Un'idea che ho sono algoritmi genetici, ma penso che occuperanno troppo tempo e potenza di elaborazione. Avrò bisogno di cercare le collisioni di forma, così come aggiungere spazio extra di imbottitura, dato che stiamo parlando di parti reali con irregolarità piuttosto che con blocchi immaginari perfetti. Temo che questo possa diventare geometricamente disordinato abbastanza velocemente, e preferirei mantenere le cose semplici, se possibile.
E se la migliore soluzione (pratica) fosse quella di mettere le cose in scatole di casse diverse anziché una sola? Questo può diventare un po 'più complicato. C'è anche un elemento umano coinvolto, cioè parti simili possono andare nella stessa scatola e sono quindi un vincolo da considerare. Alcune parti che non sono le stesse sono talvolta raggruppate per la spedizione e possono essere considerate come un oggetto comune raggruppato. A volte i clienti vogliono che le cose vengano spedite a modo loro, aggiungendo elementi umani ai vincoli. quindi ci sarà bisogno di un po 'di personalizzazione.