A heuristic algorithm for the three-dimensional container packing problem with zero unloading cost constraint

Abstract

Home delivery is one of the most important cost drivers in the e-commerce industry, and a recent study concluded that over 40% cost reduction for the dotcom companies can be achieved by offering home delivery system. This paper considers the home delivery system to cope with the threedimensional container packing problem (3DCPP), which is a crucial issue among logistics operations to pack a number of rectangular items (cargos) orthogonally onto a rectangular container so that the utilization rate of the container space is maximized. In our framework of home delivery, we assume that the routing of a consignment is given, and hence there is an order of unloading items with respect to a problem. If loading items doesn't take the unloading order into account, then it may lead to huge unloading costs (i.e., unloading and reloading other items many times). In this paper, the unloading cost with respect to a packing pattern is precisely defined according to the invisible and untouchable rule and an iterative heuristic algorithm based on the sub-volume scheme is proposed. Our approach is compared with the previous approaches by using standard benchmark data set, and our experimental results suggest our approach to be promising, as it can generate the packing patterns without unloading cost, which has a high utilization ratio, and the benchmark problems can be executed efficiently. © 2006 IEEE.