GRASP Optimization for the Strip Packing Problem with Flags, Waste Functions, and an Improved Restricted Candidate List
This research addresses the two-dimensional strip packing problem to minimize the total strip height used, avoiding overlapping and placing objects outside the strip limits. This is an NP-hard optimization problem. We propose a greedy randomized adaptive search procedure (GRASP), incorporating flags...
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-02-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/12/4/1965 |
| _version_ | 1797483054695972864 |
|---|---|
| author | Edgar Oviedo-Salas Jesús David Terán-Villanueva Salvador Ibarra-Martínez Alejandro Santiago-Pineda Mirna Patricia Ponce-Flores Julio Laria-Menchaca José Antonio Castán-Rocha Mayra Guadalupe Treviño-Berrones |
| author_facet | Edgar Oviedo-Salas Jesús David Terán-Villanueva Salvador Ibarra-Martínez Alejandro Santiago-Pineda Mirna Patricia Ponce-Flores Julio Laria-Menchaca José Antonio Castán-Rocha Mayra Guadalupe Treviño-Berrones |
| author_sort | Edgar Oviedo-Salas |
| collection | DOAJ |
| description | This research addresses the two-dimensional strip packing problem to minimize the total strip height used, avoiding overlapping and placing objects outside the strip limits. This is an NP-hard optimization problem. We propose a greedy randomized adaptive search procedure (GRASP), incorporating flags as a new approach for this problem. These flags indicate available space after accommodating an object; they hold the available width and height for the following objects. We also propose three waste functions as surrogate objective functions for the GRASP candidate list and use and enhanced selection for the restricted candidate list, limiting the object options to better elements. Finally, we use overlapping functions to ensure that the object fits in the flag because there are some cases where a flag’s width can be wrong due to new object placement. The tests showed that our proposal outperforms the most recent state-of-the-art metaheuristic. Additionally, we make comparisons against two exact algorithms and another metaheuristic. |
| first_indexed | 2024-03-09T22:41:25Z |
| format | Article |
| id | doaj.art-34c6a578b5d844288fb8e328d366a9f7 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-09T22:41:25Z |
| publishDate | 2022-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-34c6a578b5d844288fb8e328d366a9f72023-11-23T18:37:03ZengMDPI AGApplied Sciences2076-34172022-02-01124196510.3390/app12041965GRASP Optimization for the Strip Packing Problem with Flags, Waste Functions, and an Improved Restricted Candidate ListEdgar Oviedo-Salas0Jesús David Terán-Villanueva1Salvador Ibarra-Martínez2Alejandro Santiago-Pineda3Mirna Patricia Ponce-Flores4Julio Laria-Menchaca5José Antonio Castán-Rocha6Mayra Guadalupe Treviño-Berrones7Facultad de Ingeniería “Arturo Narro Siller”, Universidad Autonoma de Tamaulipas (UAT), Centro Universitario Tampico Madero, Tampico 89109, MexicoFacultad de Ingeniería “Arturo Narro Siller”, Universidad Autonoma de Tamaulipas (UAT), Centro Universitario Tampico Madero, Tampico 89109, MexicoFacultad de Ingeniería “Arturo Narro Siller”, Universidad Autonoma de Tamaulipas (UAT), Centro Universitario Tampico Madero, Tampico 89109, MexicoFacultad de Ingeniería “Arturo Narro Siller”, Universidad Autonoma de Tamaulipas (UAT), Centro Universitario Tampico Madero, Tampico 89109, MexicoFacultad de Ingeniería “Arturo Narro Siller”, Universidad Autonoma de Tamaulipas (UAT), Centro Universitario Tampico Madero, Tampico 89109, MexicoFacultad de Ingeniería “Arturo Narro Siller”, Universidad Autonoma de Tamaulipas (UAT), Centro Universitario Tampico Madero, Tampico 89109, MexicoFacultad de Ingeniería “Arturo Narro Siller”, Universidad Autonoma de Tamaulipas (UAT), Centro Universitario Tampico Madero, Tampico 89109, MexicoFacultad de Ingeniería “Arturo Narro Siller”, Universidad Autonoma de Tamaulipas (UAT), Centro Universitario Tampico Madero, Tampico 89109, MexicoThis research addresses the two-dimensional strip packing problem to minimize the total strip height used, avoiding overlapping and placing objects outside the strip limits. This is an NP-hard optimization problem. We propose a greedy randomized adaptive search procedure (GRASP), incorporating flags as a new approach for this problem. These flags indicate available space after accommodating an object; they hold the available width and height for the following objects. We also propose three waste functions as surrogate objective functions for the GRASP candidate list and use and enhanced selection for the restricted candidate list, limiting the object options to better elements. Finally, we use overlapping functions to ensure that the object fits in the flag because there are some cases where a flag’s width can be wrong due to new object placement. The tests showed that our proposal outperforms the most recent state-of-the-art metaheuristic. Additionally, we make comparisons against two exact algorithms and another metaheuristic.https://www.mdpi.com/2076-3417/12/4/1965strip packing problemNP-hard optimizationGRASPobject placing flag |
| spellingShingle | Edgar Oviedo-Salas Jesús David Terán-Villanueva Salvador Ibarra-Martínez Alejandro Santiago-Pineda Mirna Patricia Ponce-Flores Julio Laria-Menchaca José Antonio Castán-Rocha Mayra Guadalupe Treviño-Berrones GRASP Optimization for the Strip Packing Problem with Flags, Waste Functions, and an Improved Restricted Candidate List Applied Sciences strip packing problem NP-hard optimization GRASP object placing flag |
| title | GRASP Optimization for the Strip Packing Problem with Flags, Waste Functions, and an Improved Restricted Candidate List |
| title_full | GRASP Optimization for the Strip Packing Problem with Flags, Waste Functions, and an Improved Restricted Candidate List |
| title_fullStr | GRASP Optimization for the Strip Packing Problem with Flags, Waste Functions, and an Improved Restricted Candidate List |
| title_full_unstemmed | GRASP Optimization for the Strip Packing Problem with Flags, Waste Functions, and an Improved Restricted Candidate List |
| title_short | GRASP Optimization for the Strip Packing Problem with Flags, Waste Functions, and an Improved Restricted Candidate List |
| title_sort | grasp optimization for the strip packing problem with flags waste functions and an improved restricted candidate list |
| topic | strip packing problem NP-hard optimization GRASP object placing flag |
| url | https://www.mdpi.com/2076-3417/12/4/1965 |
| work_keys_str_mv | AT edgaroviedosalas graspoptimizationforthestrippackingproblemwithflagswastefunctionsandanimprovedrestrictedcandidatelist AT jesusdavidteranvillanueva graspoptimizationforthestrippackingproblemwithflagswastefunctionsandanimprovedrestrictedcandidatelist AT salvadoribarramartinez graspoptimizationforthestrippackingproblemwithflagswastefunctionsandanimprovedrestrictedcandidatelist AT alejandrosantiagopineda graspoptimizationforthestrippackingproblemwithflagswastefunctionsandanimprovedrestrictedcandidatelist AT mirnapatriciaponceflores graspoptimizationforthestrippackingproblemwithflagswastefunctionsandanimprovedrestrictedcandidatelist AT juliolariamenchaca graspoptimizationforthestrippackingproblemwithflagswastefunctionsandanimprovedrestrictedcandidatelist AT joseantoniocastanrocha graspoptimizationforthestrippackingproblemwithflagswastefunctionsandanimprovedrestrictedcandidatelist AT mayraguadalupetrevinoberrones graspoptimizationforthestrippackingproblemwithflagswastefunctionsandanimprovedrestrictedcandidatelist |