A hybrid algorithm for constrained order packing

A hybrid algorithm for constrained order packing

0.00 Avg rating0 Votes
Article ID: iaor201449
Volume: 22
Issue: 1
Start Page Number: 157
End Page Number: 186
Publication Date: Mar 2014
Journal: Central European Journal of Operations Research
Authors: ,
Keywords: bin packing, greedy algorithms, metaheuristics
Abstract:

Constraint order packing, which is an extension to the classical two‐dimensional bin packing, adds an additional layer of complexity to known bin packing problems by new additional placement and order constraints. While existing meta heuristics usually produce good results for common bin packing problems in any dimension, they are not able to take advantage of special structures resulting from these constraints in this particular two‐dimensional prolbem type. We introduce a hybrid algorithm that is based on greedy search and is nested within a network search algorithm with dynamic node expansion and meta logic, inspired by human intuition, to overrule decisions implied by the greedy search. Due to the design of this algorithm we can control the performance characteristics to lie anywhere between classical network search algorithms and local greedy search. We will present the algorithm, discuss bounds and show that their performance outperforms common approaches on a variety of data sets based on industrial applications. Furthermore, we discuss time complexity and show some ideas to speed up calculations and improve the quality of results.

Reviews

Required fields are marked *. Your email address will not be published.