A 3D Offline Packing Algorithm considering Cargo Orientation and Stability
The box packing problem can be generalized as placing a batch of cargos with a specified number of different physical characteristics into a specified box. Suppose that a batch of cuboid cargos of different sizes are to be loaded into a batch of boxes of the same type, the cargos have constraints su...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2023-01-01
|
| Series: | International Journal of Distributed Sensor Networks |
| Online Access: | http://dx.doi.org/10.1155/2023/5299891 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849695891724697600 |
|---|---|
| author | Xianpei Wang Li Gong Haocheng Zhao Bowen Li Meng Tian |
| author_facet | Xianpei Wang Li Gong Haocheng Zhao Bowen Li Meng Tian |
| author_sort | Xianpei Wang |
| collection | DOAJ |
| description | The box packing problem can be generalized as placing a batch of cargos with a specified number of different physical characteristics into a specified box. Suppose that a batch of cuboid cargos of different sizes are to be loaded into a batch of boxes of the same type, the cargos have constraints such as orientation and stability. Taking the mean value of the reciprocal of space utilization as the objective function, this paper designs a hybrid genetic algorithm that combines genetic algorithm and tabu search algorithm. Aiming at the information of the packing sequence and the rotating state of the box in the packing scheme, a two-stage real number encoding method and decoding method based on random keys are designed, and a crossover operation based on partial random keys and uniform crossover is designed. In order to convert the solution searched by the optimization algorithm into the actual packing scheme, a heuristic loading algorithm is designed while using the positioning rule of the lower left corner, the space selection rule of the minimum space, and the division and merging rules of the remaining space. In the early stage, the roulette method was used to strengthen the global search ability, and in the later stage, the optimal preservation strategy was used to speed up the algorithm convergence. To make up for the shortcomings of the genetic algorithm’s weak local search ability and slow convergence speed, the tabu search algorithm was used as a mutation operation in the genetic algorithm. The solution in the generation is used as the initial solution of the tabu search algorithm, and the search process is carried out. Finally, this paper tests the proposed hybrid algorithm on 6 groups of weakly heterogeneous and strongly heterogeneous data in the BR dataset. The results prove that the proposed algorithm can reduce the usage of boxes. |
| format | Article |
| id | doaj-art-93a34ea1ba9a4c48b0609c5afa6a74ee |
| institution | DOAJ |
| issn | 1550-1329 |
| language | English |
| publishDate | 2023-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Distributed Sensor Networks |
| spelling | doaj-art-93a34ea1ba9a4c48b0609c5afa6a74ee2025-08-20T03:19:38ZengWileyInternational Journal of Distributed Sensor Networks1550-13292023-01-01202310.1155/2023/5299891A 3D Offline Packing Algorithm considering Cargo Orientation and StabilityXianpei Wang0Li Gong1Haocheng Zhao2Bowen Li3Meng Tian4Electronic Information SchoolElectronic Information SchoolElectronic Information SchoolElectronic Information SchoolElectronic Information SchoolThe box packing problem can be generalized as placing a batch of cargos with a specified number of different physical characteristics into a specified box. Suppose that a batch of cuboid cargos of different sizes are to be loaded into a batch of boxes of the same type, the cargos have constraints such as orientation and stability. Taking the mean value of the reciprocal of space utilization as the objective function, this paper designs a hybrid genetic algorithm that combines genetic algorithm and tabu search algorithm. Aiming at the information of the packing sequence and the rotating state of the box in the packing scheme, a two-stage real number encoding method and decoding method based on random keys are designed, and a crossover operation based on partial random keys and uniform crossover is designed. In order to convert the solution searched by the optimization algorithm into the actual packing scheme, a heuristic loading algorithm is designed while using the positioning rule of the lower left corner, the space selection rule of the minimum space, and the division and merging rules of the remaining space. In the early stage, the roulette method was used to strengthen the global search ability, and in the later stage, the optimal preservation strategy was used to speed up the algorithm convergence. To make up for the shortcomings of the genetic algorithm’s weak local search ability and slow convergence speed, the tabu search algorithm was used as a mutation operation in the genetic algorithm. The solution in the generation is used as the initial solution of the tabu search algorithm, and the search process is carried out. Finally, this paper tests the proposed hybrid algorithm on 6 groups of weakly heterogeneous and strongly heterogeneous data in the BR dataset. The results prove that the proposed algorithm can reduce the usage of boxes.http://dx.doi.org/10.1155/2023/5299891 |
| spellingShingle | Xianpei Wang Li Gong Haocheng Zhao Bowen Li Meng Tian A 3D Offline Packing Algorithm considering Cargo Orientation and Stability International Journal of Distributed Sensor Networks |
| title | A 3D Offline Packing Algorithm considering Cargo Orientation and Stability |
| title_full | A 3D Offline Packing Algorithm considering Cargo Orientation and Stability |
| title_fullStr | A 3D Offline Packing Algorithm considering Cargo Orientation and Stability |
| title_full_unstemmed | A 3D Offline Packing Algorithm considering Cargo Orientation and Stability |
| title_short | A 3D Offline Packing Algorithm considering Cargo Orientation and Stability |
| title_sort | 3d offline packing algorithm considering cargo orientation and stability |
| url | http://dx.doi.org/10.1155/2023/5299891 |
| work_keys_str_mv | AT xianpeiwang a3dofflinepackingalgorithmconsideringcargoorientationandstability AT ligong a3dofflinepackingalgorithmconsideringcargoorientationandstability AT haochengzhao a3dofflinepackingalgorithmconsideringcargoorientationandstability AT bowenli a3dofflinepackingalgorithmconsideringcargoorientationandstability AT mengtian a3dofflinepackingalgorithmconsideringcargoorientationandstability AT xianpeiwang 3dofflinepackingalgorithmconsideringcargoorientationandstability AT ligong 3dofflinepackingalgorithmconsideringcargoorientationandstability AT haochengzhao 3dofflinepackingalgorithmconsideringcargoorientationandstability AT bowenli 3dofflinepackingalgorithmconsideringcargoorientationandstability AT mengtian 3dofflinepackingalgorithmconsideringcargoorientationandstability |