Solving the 3D Bin Packing Problem: Improved Heuristic Solutions for a Case in the Automotive Industry

  • Andreas Beham (Speaker)

Activity: Talk or presentationOral presentation


Solving the three dimensional bin packing problem is a very challenging task. Several more or less elaborate algorithms exist to solve the problem, among them the fast extreme point heuristic described by Crainic et al. 2008. In a research project funded by the Austrian Research Promotion Agency we applied this heuristic to real-world packing problems arising in the automotive industry for loading shipping containers and trucks. We developed several improvements to the heuristic and added additional constraints and decisions. In addition to the packing position, the heuristic decides on rotation and tilting an item. The added constraints are to consider items that are not stackable and must be put on the ground, items that can only bear a certain load, items that must be supported, items that must not be put on top of other items, and items that must be loaded before others. Together with our company partner we defined a matrix with coefficients of friction and calculated the required weight to fasten items in order to satisfy securing of cargo. In the talk we will describe the heuristic, the packing instances, show results and discuss further open issues.
Period11 Jul 2018
Event title29th European Conference On Operational Research
Event typeConference
LocationValencia, SpainShow on map