Premium
Hybrid greedy heuristics based on linear programming for the three‐dimensional single bin‐size bin packing problem
Author(s) -
Hifi Mhand,
Negre Stéphane,
Wu Lei
Publication year - 2014
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12035
Subject(s) - heuristics , bin packing problem , knapsack problem , mathematical optimization , container (type theory) , heuristic , selection (genetic algorithm) , linear programming , bin , integer programming , greedy algorithm , computer science , set (abstract data type) , metaheuristic , mathematics , algorithm , artificial intelligence , engineering , mechanical engineering , programming language
In this paper, we propose to solve the three‐dimensional single bin‐size bin packing problem (3D‐SBSBPP) using a simple strategy based on integer linear programming (ILP) heuristics, without using any improvement based on metaheuristics. We first propose an ILP that is converted into a series of three‐dimensional single knapsack problems (3D‐SKP). Then, the first tailored heuristic can be viewed as a hybrid approach in which both “selection” and “positioning” phases are combined. The first phase serves to select a subset of items where each of these items is susceptible to belonging to an active container. The positioning phase serves to pack a subset of items already preselected by the selection phase. Then, both phases cooperate till packing all items into their corresponding containers. The second heuristic can be viewed as an extended version of the first one. Indeed, before deciding whether the current container is closed or a new container is activated, “a local reoptimization phase” is considered. Finally, both proposed heuristics are evaluated on a set of random instances obtained by using the standard generator scheme of the literature. The provided results show that both proposed heuristics remain competitive when compared to the results obtained by one of the best methods of the literature.