Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms |
| |
| Affiliation: | 1. Warwick Business School, University of Warwick, Coventry, CV4 7AL, UK;2. School of Management, University of Bath, Claverton Down, Bath BA2 7AY, UK;3. Econometric Institute, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands;1. University Technology Centre for Computational Engineering, University of Southampton, Southampton SO16 7QF, UK;2. Southampton Business School, University of Southampton, Southampton SO17 8BJ, UK;3. Rolls-Royce plc, PO Box 31, Derby DE24 8BJ, UK;1. State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University, Beijing, 100044, China;2. Institute of Transportation System Science and Engineering, Beijing Jiaotong University, Beijing 100044, China;3. Institute for Transport Studies, University of Leeds, Leeds LS2 9JT, United Kingdom |
| |
| Abstract: | The well-known one-dimensional Bin Packing Problem (BPP) of whose variants arise in many real life situations is a challenging NP-Hard combinatorial optimization problem. Metaheuristics are widely used optimization tools to find (near-) optimal solutions for solving large problem instances of BPP in reasonable running times. With this study, we propose a set of robust and scalable hybrid parallel algorithms that take advantage of parallel computation techniques, evolutionary grouping genetic metaheuristics, and bin-oriented heuristics to obtain solutions for large scale one-dimensional BPP instances. A total number of 1318 benchmark problems are examined with the proposed algorithms and it is shown that optimal solutions for 88.5% of these instances can be obtained with practical optimization times while solving the rest of the problems with no more than one extra bin. When the results are compared with the existing state-of-the-art heuristics, the developed parallel hybrid grouping genetic algorithms can be considered as one of the best one-dimensional BPP algorithms in terms of computation time and solution quality. |
| |
| Keywords: | One-dimensional bin packing Grouping genetic algorithms Parallel computation Hybrid-heuristics |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
