Optimizing Mixed Box Packing Problem with an In-House built Application

Abstract

The three-dimensional knapsack problem aims to find the combination of given rectangles or boxes into a larger rectangle or box of fixed dimension. The optimization is an NP-Hard problem, which has no known algorithm can solve it in a polynomial time. This paper presents the case of knapsack problem in pallet combinatorial optimization at Automotive Aftermarket Division at Robert Bosch GmbH Japan. The division outsourced their packing process to a service provider called Provider. The palletization at Provider is done intuitively based on experiences. The author proposed to develop an in-house software that will determine the most optimal combination of boxes to pack in pallet box constraints to minimize waste of pallet capacity. A packing algorithm that considers up to 5 of volume, non-overlapping, box orientation, non-over packing and weight was proposed. The software was later developed based on the algorithm with Python language with GUI Tkinter. An additional Excel file with open source code from University of Bath was introduced to handle the visualization and animation of packing pattern.