A modified partially mapped multiCrossover genetic algorithm for Two-Dimensional Bin Packing Problem
Problem statement: Non-oriented case of Two-Dimensional Rectangular Bin Packing Problem (2DRBPP) was studied in this study. The objective of this problem was to pack a given set of small rectangles, which may be rotated by 90°, without overlaps into a minimum numbers of identical large rectangles. O...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Published: |
Science Publications
2010
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/12729/ |
| _version_ | 1848841914748502016 |
|---|---|
| author | Sarabian, Maryam Lee, Lai Soon |
| author_facet | Sarabian, Maryam Lee, Lai Soon |
| author_sort | Sarabian, Maryam |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | Problem statement: Non-oriented case of Two-Dimensional Rectangular Bin Packing Problem (2DRBPP) was studied in this study. The objective of this problem was to pack a given set of small rectangles, which may be rotated by 90°, without overlaps into a minimum numbers of identical large rectangles. Our aim was to improve the performance of the MultiCrossover Genetic Algorithm(MXGA)proposed from the literature for solving the problem.
Approach: Four major components of the MXGA consisted of selection, crossover, mutation and replacement are considered in this study. Initial computational investigations were conducted independently on the named components using some benchmark problem instances. The new MXGA was constructed by combining the rank selection, modified Partially Mapped Crossover (PMXm), mutation with two mutation operators and elitism replacement scheme with filtration.
Results: Extensive computational experiments of the new proposed algorithm, MXGA, Standard GA (SGA), Unified Tabu Search (UTS) and Randomized Descent Method (RDM) were performed using benchmark data sets.
Conclusion: The computational results indicated that the new proposed algorithm was able to outperform MXGA, SGA, UTS and RDM |
| first_indexed | 2025-11-15T07:50:49Z |
| format | Article |
| id | upm-12729 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-15T07:50:49Z |
| publishDate | 2010 |
| publisher | Science Publications |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-127292015-05-29T05:56:32Z http://psasir.upm.edu.my/id/eprint/12729/ A modified partially mapped multiCrossover genetic algorithm for Two-Dimensional Bin Packing Problem Sarabian, Maryam Lee, Lai Soon Problem statement: Non-oriented case of Two-Dimensional Rectangular Bin Packing Problem (2DRBPP) was studied in this study. The objective of this problem was to pack a given set of small rectangles, which may be rotated by 90°, without overlaps into a minimum numbers of identical large rectangles. Our aim was to improve the performance of the MultiCrossover Genetic Algorithm(MXGA)proposed from the literature for solving the problem. Approach: Four major components of the MXGA consisted of selection, crossover, mutation and replacement are considered in this study. Initial computational investigations were conducted independently on the named components using some benchmark problem instances. The new MXGA was constructed by combining the rank selection, modified Partially Mapped Crossover (PMXm), mutation with two mutation operators and elitism replacement scheme with filtration. Results: Extensive computational experiments of the new proposed algorithm, MXGA, Standard GA (SGA), Unified Tabu Search (UTS) and Randomized Descent Method (RDM) were performed using benchmark data sets. Conclusion: The computational results indicated that the new proposed algorithm was able to outperform MXGA, SGA, UTS and RDM Science Publications 2010 Article PeerReviewed Sarabian, Maryam and Lee, Lai Soon (2010) A modified partially mapped multiCrossover genetic algorithm for Two-Dimensional Bin Packing Problem. Journal of Mathematics and Statistics, 6 (2). pp. 157-162. ISSN 1549-3644; ESSN: 1558-6359 http://www.thescipub.com/abstract/10.3844/jmssp.2010.157.162 10.3844/jmssp.2010.157.162 |
| spellingShingle | Sarabian, Maryam Lee, Lai Soon A modified partially mapped multiCrossover genetic algorithm for Two-Dimensional Bin Packing Problem |
| title | A modified partially mapped multiCrossover genetic algorithm for Two-Dimensional Bin Packing Problem |
| title_full | A modified partially mapped multiCrossover genetic algorithm for Two-Dimensional Bin Packing Problem |
| title_fullStr | A modified partially mapped multiCrossover genetic algorithm for Two-Dimensional Bin Packing Problem |
| title_full_unstemmed | A modified partially mapped multiCrossover genetic algorithm for Two-Dimensional Bin Packing Problem |
| title_short | A modified partially mapped multiCrossover genetic algorithm for Two-Dimensional Bin Packing Problem |
| title_sort | modified partially mapped multicrossover genetic algorithm for two-dimensional bin packing problem |
| url | http://psasir.upm.edu.my/id/eprint/12729/ http://psasir.upm.edu.my/id/eprint/12729/ http://psasir.upm.edu.my/id/eprint/12729/ |