A fast algorithm for identifying minimum size instances of the equivalence classes of the Pallet Loading Problem

作者：Lu Yiping^*; Cha Jianzhong

来源：European Journal of Operational Research, 2014, 237(3): 794-801.

DOI：10.1016/j.ejor.2014.02.008

• Packing
• Pallet Loading Problem
• Equivalence class

In this paper, a novel and fast algorithm for identifying the Minimum Size Instance (MSI) of the equivalence class of the Pallet Loading Problem (PLP) is presented. The new algorithm is based on the fact that the PLP instances of the same equivalence class have the property that the aspect ratios of their items belong to an open interval of real numbers. This interval characterises the PLP equivalence classes and is referred to as the Equivalence Ratio Interval (ERI) by authors of this paper. The time complexity of the new algorithm is two polynomial orders lower than that of the best known algorithm. The authors of this paper also suggest that the concept of MSI and its identifying algorithm can be used to transform the non-integer PLP into its equivalent integer MSI.

• 出版日期2014-9-16
• 单位北京交通大学