A heuristic for the container loading problem: A tertiary-tree-based dynamic space decomposition approach

作者：Wang Zhoujing; Li Kevin W^*; Levy Jason K

来源：European Journal of Operational Research, 2008, 191(1): 86-99.

DOI：10.1016/j.ejor.2007.08.017

• heuristics
• container loading problem
• dynamic space decomposition
• holistic loading
• tertiary tree

Increasing fuel costs, post-911 security concerns, and economic globalization provide a strong incentive for container carriers to use available container space more efficiently, thereby minimizing the number of container trips and reducing socio-economic vulnerability. A heuristic algorithm based on a tertiary tree model is proposed to handle the container loading problem (CLP) with weakly heterogeneous boxes. A dynamic space decomposition method based on the tertiary tree structure is developed to partition the remaining container space after a block of homogeneous rectangular boxes is loaded into a container. This decomposition approach, together with an optimal-fitting sequencing and an inner-right-corner-occupying placement rule, permits a holistic loading strategy to pack a container. Comparative studies with existing algorithms and an illustrative example demonstrate the efficiency of this algorithm.

• 出版日期2008-11-16
• 单位厦门大学