Ho ricevuto l'incarico di creare una stima di spedizione che suggerisca la migliore sistemazione di merci nel minor numero possibile di scatole:
-
Esiste un insieme finito di dimensioni della casella retangolare note
-
Ci sono molti oggetti retangolari arbitrari da imballare all'interno di scatole
-
Meno caselle dovrebbero essere utilizzate al meglio. Poiché la spedizione di due scatole 1x1x1 è molto più costosa di una scatola 1x2x1. Questa dovrebbe essere la priorità qui.
-
Dovrebbe anche essere ottimizzato per utilizzare le caselle più piccole possibile, come priorità di secondo livello. (es .: se viene presentata una scelta tra una scatola più grande e due piccole, dovrebbe scegliere la scatola più grande)
-
Gli oggetti possono essere ruotati per adattarsi alla scatola, ma la rotazione deve essere limitata ad incrementi di 45 ° al minimo (nelle mie ricerche sembra che alcune configurazioni consentano una rotazione di 45 gradi per adattarsi meglio alle scatole retangolari all'interno di una scatola retangolare più grande), ruotando di 90 ° lo standard da adottare.
-
Le scatole hanno un limite di peso e gli oggetti hanno pesi arbitrari (es .: un oggetto che è la dimensione è 1x1x1 può essere più pesante di un altro oggetto 2x2x2)
Ho studiato un po 'e ho trovato alcuni algoritmi astratti su bin packing e il problema dello zaino e sono venuti con la seguente variazione alquanto bruteforce, simile all'algoritmo best fit:
Sort the items in decrescent volume order (bigger first) on an "items to pack" list
For each item on this list:
Choose the smaller box that is on the "used boxes" list and has enough remaining volume and weight limit to fit the item (I will use fit here to mean fitting the dimensions and weight)
If there is not such box, create a new box from the know set of possible box sizes that is the smallest size that can fit the item's dimensions and weight and add it to the list of "used boxes".
If a box fits the item (using the fitting function bellow), add it to the list of "this box's items" and remove it from the "items to fit" list, marking it's relative 3d position inside the box.
Repeat from 2.1 until there is no item to be fitted on the "items to pack" list.
La funzione di controllo dell'adattamento utilizzata nel passaggio 2 sopra:
Check if the remaining volume of the box fits the volume of the item. If not, return false.
Check if the sum of "box's items" weight plus the current item weight is less or equal to the box weight limit. If not, return false.
Check the "box's items" list to choose the first box coordinate that has the smallest Y component and that has enough space for the item's width, depth and height, considering the other items placed as unavailable space.
If the item doesn't fit at it's current orientation rotate it on one of the 6 possible rotations, not assuming 45° rotations for simplicity. (Rotations that result in sizes that where already tested can be skipped. Eg.: rotating a box 180° gives the same dimmensions as the original position because all boxes and items have the same size for opposite faces and so can be skipped.)
If the item hasn't been rotated on all the possible ways back to its original orientation, try again from step 3.
If all rotations where tried and no fit was found, consider the current coordinate as unavailable space.
If there is not avaliable space to check, return false. Else, try again from step 3.
Voglio sapere se può esserci una soluzione migliore per il mio problema, dati i vincoli presentati.
Questo sembra funzionare sulla teoria ma non l'ho provato sul codice. Vorrei sapere se sto andando nella direzione giusta o ci sono modi migliori e performanti per farlo.
I riferimenti sarebbero grandiosi.
Modifica
Ho trovato alcune API di terze parti interessanti che fanno ciò che voglio, ma questo dovrà essere disconnesso, quindi non avrò accesso a queste.
Alcuni esempi sono:
Modifica 2:
Un esempio reale di problema da risolvere sarebbe:
- Ho 4 dimensioni di riquadro WxHxD: 10x12x18, 12x16x24, 16x20x30, 24x32x40
- Ho un ordine di 4 articoli, essendo 1 di dimensione 6x8x10, 2x 22x14x30 e 1x 22x4x20
Come posso adattare questo articolo a qualsiasi quantità di scatole di una o più dimensioni usando meno scatole possibile, usando le scatole più piccole possibili e lasciando meno spazio libero possibile?