Paper Info
Title
Heuristic/meta-heuristic methods for restricted bin packing problem
Abstract
This paper addresses a special bin packing problem in which each item can only be assigned to a subset of the bins. We name this problem as the restricted bin packing problem (RBPP). This paper is designed to explore the relationships of RBPP with classic NP-complete problems, and to resolve the restrictions of assignment through heuristic and meta-heuristic algorithms. A new heuristic algorithm named ‘Max-fit Based on Zigzag Sorting with Retained Feasibility’ is proposed. In this heuristic algorithm, a feasibility retaining rule is constructed to assure the assignment of every item; a zigzag sorting method is designed to improve the performance of the algorithm. Our heuristic algorithm is able to generate better results in comparison with existing heuristics. Greedy Randomized Adaptive Search Procedure (GRASP) and Simulated Annealing (SA) are exploited to obtain better solutions for RBPP. A new construction method based on cliques and zigzag sorting are built for GRASP and SA. The proposed methods are shown to have higher efficiency than traditional ones through numeric examples.
Year
DOI
Venue
2020
10.1007/s10732-020-09444-y
Journal of Heuristics
Keywords
DocType
Volume
Assignment, Zigzag sorting, GRASP, Simulated annealing, Bin packing
Journal
26
Issue
ISSN
Citations 
5
1381-1231
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Yu Fu100.34
Amarnath Banerjee224.09