装箱问题广泛存在于物流运输的车厢装载、集装箱装载、托盘装载,以及工厂企业的材料切割、成品包装、设施布局规划等场合中,甚至人们日常生活中的整理物品、日程安排、金钱管理等活动也经常涉及到装箱问题的求解,在文献里被归属为切割下料和装箱问题(Cutting and Packing Problems),是经典的NP-Hard问题。在当前经济环境下,库存与物流活动越来越显示出它的重要性,库存与物流相关技术受到学者越来越多的关注。如何降低库存与物流成本就成为一个很重要且迫切的问题。如果能够更有效地利用容器的空间,将节约搬运工作量与运输时间,进而降低库存压力与运输成本,提高库存与物流效率,最终能显著提高企业利润,这对于降低企业运营成本以及满足客户的需求具有重要意义。由于其NP-Hard问题特性,直接采用精确算法求解大规模装箱问题的最优解是不明智的,装箱的目的是求取一个合理的装箱方案,因此,采用启发式算法确保在有限的时间内求得近似解成为理论研究和实际应用的首选。本文研究附带剪切约束的单箱尺寸二维装箱问题(Two-dimension Single Bin Size Bin Packing Problem,2D-SBSBPP),即存在强异构的二维矩形物品集合,以及数量无限的单一矩形箱子,求能装入所有物品的、保证物品不重叠并呈现正交摆放状态的装箱方案,同时要求满足剪切约束条件,优化目标是消耗箱子总量最少。针对该问题,先后提出了三个各具特色的算法:VCH-RI、VCH-SP和HHBP。VCH-RI(Value Correction Heuristic based on Replacement and Insertion)属于构造型启发式算法,采用分层装箱布局。算法主要由三个步骤组成:(1)全部物品经过块组合过程后划分成多个层;(2)各层采用多背包算法装入多个箱;(3)选举其中最好的装箱布局图进行物品替换和加塞改善后纳入解集合。剩余物品重复执行上述三步骤程序,每次执行均获得一个解的构成元素,直至生成最后一个箱,生成的所有箱子构成一个装箱方案。经过数次迭代,选择最好的装箱方案作为最终解。在装箱过程中,通过价值修正策略避免了由于某些物品过快使用而产生局部最优而非全局最优的现象。VCH-SP(Value Correction Heuristic based on Spaces Packing)属于非层装箱布局的启发式算法。算法利用空间集列表对当前剩余空间设计了有效划分和物品填充策略,对相邻空间碎片的合并有效提高了面积利用率。每当一个箱子装满了或剩余空间已经无任何利用价值时,就打开另一个新的空箱继续装填直至剩余物品为零,最终获取一个装箱方案。算法通过修正物品价值调整物品的填充次序,形成附带新价值的物品集合,重新装箱,获得新的装箱方案,经过多次的迭代使解逐步趋优。HHBP(Hybrid Heuristic for the two-dimensional Bin Packing problem)属于精确算法和启发式算法相结合的混合算法,采用两阶段分层装箱布局。算法分两个时段求解,每个时段各产生一个解,并从中择优。在时段一使用列生成法(CG)求解余问题;同时使用部分选择算法,选择部分布局图作为时段一的解。基于时段一生成的所有装箱布局图的集合,通过CPLEX解整数线性规划问题,求得时段二的解。由于时段二中使用了计算时间约束,因此时段二的解不一定是最优解,HHBP算法将在时段一和时段二这两解间进行择优输出。本文最后对三个装箱算法的实验数据进行了汇总和分析,并与采用同一基准算例的其它文献进行了性能对比,结果显示三个算法各具特色,解的质量和时间性能都在可接受的范围内。与其它算法的横向比较也验证了算法的优良性能,这说明本文算法能够较好地解决二维装箱问题,提高物流管理效率,对企业实际运营具有较强的指导意义。