写在前面

由于某些原因，这篇文章还没写完就作者就搞别的问题去了，写到一半很不好意思，大家可以去看原文对应的论文进一步研究：【A skyline heuristic for the 2D rectangular packing and strip packing problems】。祝大家学习顺利~

前言

今天为大家介绍二维矩形装箱问题（2D rectangular packing problem， 简称2DRP）以及在此基础上拓展的二维带装箱问题（2D strip packing problem，简称2DSP）。
这次介绍的算法运用了启发式算法**禁忌搜索算法（Tabu search，简称TS）**的相关知识，如果小伙伴们还没有掌握，可以在公众号内查阅以下推文：

对了解禁忌搜索的同学而言，相信这次的算法不会很难接受。话不多说，这就开始今天的介绍吧！

问题介绍

装箱问题广泛存在于物流运输的车厢装载、集装箱装载、托盘装载,以及工厂企业的材料切割、成品包装、设施布局规划等场合中。在当前经济环境下，库存与物流活动越来越显示出其重要性，如何降低库存与物流成本就成为一个很重要且迫切的问题。

本文中提到的“”二维矩形装箱装箱问题（2DRP）**，主要考虑二维情形下，所有目标项目都为矩形，目的是最大化可用面积，并允许矩形放置时正交旋转，是经典的NP-Hard问题：
给出n个$w_i\ast h_i$的维数为矩形。目标是将没有重叠的矩形正交地放置在一个尺寸为$W\ast H$的大矩形(称为sheet)中，使所有放置的矩形的总面积最大化。所有的维数都被认为是整数。本文介绍的算法允许矩形旋转90°，但不处理的断头可分性（guillotine-cut constraint）。

在此基础上，另一个和2DRP密切相关的切割和包装问题是二维带包装问题(2DSP)。给定n个矩形，任务是将所有矩形放置在一个宽度为W的矩形带，目标是最小化矩形带的高度H。

算法介绍

描述装箱模式

算法通过上界线（skyline） 和 坐标点（candidate position） 的概念来描述装箱模式。
在算法中，我们尽量将矩形放置在下方。简单来讲，上界线表示最上层矩形的上边界；坐标点代表所有上界线的左下角和右下角坐标。
如图所示，图中最上层水平直线部分为该装箱方式的上界线，分为5段，分别记作$s_1,s_2,s_3,s_4,s_5$。图中实心圆点代表坐标点，共有3个左侧坐标点，3个右侧坐标点。

严谨表述为：

用上界线表示当前的装箱模式，表示为一组水平线，满足以下性质：
1.每条线段的y坐标与下一条线的不同；
2.线段$s_j$右端的x坐标和$s_{j+1}$左侧末端的x坐标相同。

$s_{i-1}$左端点的y坐标大于$s_i$左端点的y坐标，或线段$s_i$右端点的y坐标大于$s_{i+1}$大于右端点的y坐标时，标记$s_i$左端点或右端点为坐标点。
其中$s_1$的左端点和$s_k$的右端点一直是坐标点。

算法按顺序一个一个放置矩形。每个矩形的位置，要么是左下角接触到线段的左端点，要么是其右下角接触到线段的右端点。每次放置矩形后，更新上界线和坐标点，用来描述新的装箱方式。
当矩形b被放置在线段$s_i$上时，上界线被更新。这需要两个步骤：

1.生成与b的上边缘对应的新线段，并更新受影响的现有线段。

b的宽度是否大于$s_i$会产生两种情况，下图分别展示了两种情况的示例，以及上界线如何更新。注意，(d)中的阴影区域被认为是浪费的空间，因为我们的算法不会考虑在其中放置任何矩形。

2.检查每条线段，如果它比相邻的两个线段都低，并且没有未放置的矩形可以放置在这个线段上（对于第一个和最后一个段，我们只将它们与它们相邻的一条线段进行比较），我们将它提升到它的下相邻段的高度并合并它们。
如图所示，阴影部分同样被认为是浪费的空间。

评估装箱策略

这里的装箱策略指：在当前装箱模式下，具体某个矩形的放置位置。我们利用以下规则评估每个位置：

1.spread construction。
对放置后y坐标的差值进行约束。放置矩形后，所有线段s的y坐标最大值与最小值之差不得超过限定值max_spread。

2.only fit。

3.minimum local waste。

4.maximum fitness number。

5.earlist in sequence。

禁忌搜索

拓展：2DSP