Πρόβλημα Πακετοποίησης - 2D Bin Packing Problem

Γενικά

Είναι το πρόβλημα κατά το οποίο η πλήρωση αποθηκευτικού χώρου μελετάται οι δύο διάστασεις (π.χ. πλάτος-μήκος). Τέτοια προβλήματα αφορούν:

• Τοποθέτηση αντικειμένων με αδιάφορο ύψος. π.χ. σε ελεύθερη επιφάνει, παλέτες σε φορτηγό
• Τοποθέτηση κιβωτίων διαφορετικών διαστάσεων (που δεν είναι standard) σε ράφια
• Φόρτωση πλοίων, κλπ

Διατύπωση του Προβλήματος

Πρόβλημα 2D Bin Packing: Θέλουμε να τοποθετήσουμε 2D ορθογώνια αντικείμενα που περιγράφονται από τις διαστάσεις του ύψους και του πλάτους (Wi, Hi) μέσα σε πολύ μεγαλύτερους ορθογώνιους χώρους (bins) που έχουν διάσταση (W, H).

Στρατηγική Τοποθέτησης

Για να χωράει ένα αντικείμενο στο χώρο θα πρέπει να ισχύει: wi <= W
hi <= H

Εάν το αντικείμενο χωράει τότε ακολουθούμε τον εξής τρόπο τοποθέτησης:
Τοποθετούμε το αντικείμενο πάνω αριστερά στον αποθηκευτικό χώρο. Αυτό δημιουργεί δυο νέους ελεύθερους χώρους όπως φαίνονται στο σχήμα, το χώρο V1 και τον ελεύθερο χώρο V2. Το αντικείμενο θα μπεί στον πρώτο χώρο ξεκινώντας από τα αριστερά που χωράει και θα τοποθετηθεί στην πάνω αριστερή θέση του ελεύθερου χώρου. Τώρα το αντικείμενο αυτό έχει δημιουργήσει άλλους δυο νέους αποθηκευτικούς χώρους V11 και V12, καθώς και τον χώρο V2 από την προηγούμενη κίνηση. Έτσι συνεχίζουμε μέχρι να τοποθετηθούν όλα τα αντικείμενα.

Γενικά 2D Προβλήματα Πακετοποίησης

Τα προβλήματα 2D πακετοποίησης μετατρέπονται σε προβλήματα διακριτής αριστοποίησης επιλέγοντας την κατάλληλη στρατηγική τοποθέτησης.



Τα κριτήρια για την τοποθέτηση ορίζουν και το πρόβλημα μας. Διάφορα κριτήρια είναι:

• minC = wjHj-wiHi, ελαχιστοποίηση του ελεύθερου εμβαδού
• ελαχιστοποίηση του μήκους ή του πλατους του αντικειμένου (||wj-wi|| ή ||Hj-Hi||)
• Touching areas: Εαν τοποθετήσουμε ένα αντικείμενο πόση περίμετρος του είναι κοινή με άλλα αντικείμενα, κλπ.