Abstract: This paper studies a novel bin-packing problem that is widely encountered in logistics operations. The main novelty can be characterized by the fact that the cost of a bin is a concave function of the utilization of the bin. To solve the problem, an improved differential evaluation algorithm using group-based encoding scheme is proposed such that the shortcomings of enlarging search space that the conventional real and integer encoding methods may encounter are avoided. To comply with the group-based encoding scheme, we design new and tailored crossover and mutation operators so as to promote the transmission of the excellent genes. In order to further improve the performance of the algorithm, an adaptive local search strategy that uses items rearrangement as neighbors is embedded in solution framework to enhance the intensification ability. We test our algorithm on instances collected from an existing article over different concave cost functions. The computational results show that the proposed algorithm outperforms the BFD heuristics, and improves much more than the genetic algorithm.

Key words: bin packing problem, concave costs, differential evaluation, group based encoding scheme, adaptive local search

摘要： 研究了广泛存在于物流作业中一类新型的装箱问题,主要特征体现在箱子使用费用是关于装载率的凹函数。为求解问题,提出了一种基于分组编码策略的改进差分进化算法,以避免常规实数和整数编码方法存在放大搜索空间的不足。针对分组编码策略,定制化设计了以促进优秀基因传播为导向的新型变异和交叉操作,另外还嵌入了以物品置换为邻域的自适应局部搜索操作以增强局部搜索能力。对以往文献给出算例在不同凹费用函数下进行测试,实验结果显示所提出的算法明显优于BFD启发式算法,并且较遗传算法也有显著性改进。

关键词: 装箱问题, 凹费用函数, 差分进化, 分组编码, 自适应局部搜索