一种带脆度的尺寸可变装箱问题

摘要

作为经典装箱问题的扩展,尺寸可变装箱问题在现实生活中有着极高的应用背景.分析了尺寸可变装箱问题在解决货物装载运输问题上的不足,由此提出了一种带脆度的尺寸可变装箱问题.除了经典装箱问题中物品体积和箱子容量这两个参数,还引入了物品类型和箱子脆度等参数,给出了相关的数学模型.在经典的FFD(First Fit Decreasing)算法的基础上进行了推广,提出了新的启发式算法NFFD,它对箱子的特性进行了预处理,再进行装箱.分析了该算法的复杂性.对NFD、FFD和NFFD算法进行了数值模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,NFFD算法的效果是最好的.