【运筹优化】基于堆优化的天际线启发式算法和复杂的评分策略求解二维矩形装箱问题 + Java代码实现

参考文献：
[1] S. C. Leung, D. Zhang, and K. M. Sim, “A two-stage intelligent search algorithm for the two-dimensional strip packing prob-lem,” European Journal of Operational Research, vol. 215, no. 1, pp. 57–69, 2011.
[2] L. Wei, H. Qin, B. Cheang, and X. Xu, “An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem,” International Transactions in Operational Research, vol. 23, no. 1-2, pp. 65–92, 2016.

【运筹优化】求解二维矩形装箱问题的算法合辑（Java代码实现）

一、天际线（SkyLine）启发式

1.1 天际线启发式简介

天际线启发式是一种简单而快速的打包方法。它只维护一个水平段的列表，这些水平段也被称为天际线段，由整个打包区域的顶端的线段组成。

一个天际线段可以由两个对象决定：左边的端点坐标（x，y）和线段的长度w。在天际线之上的是空间，它可以被看作是未打包区域的一个子集。

一个空间由三个对象定义：左墙的高度hl、右墙的高度hr和其对应的天际线段。

在这里插入图片描述
上图给出了一个天际线及其相应空间的例子。天际线用红色实线表示，空间S1和S2用绿色虚线表示。

一般来说，我们选择最低或最左的空间的端点作为放置点，如S1的端点3和4。

1.2 新天际线的生成

矩形只能放置在天际线的最左端或者最右端，一旦放置在天际线上，就会将被放置的天际线“切割”，即根据矩形的放置方式缩短为一条新的天际线。然后再将矩形的顶部的边作为一条新的天际线加入天际线队列中。也就是说，一般情况下，放置一个矩形会多生成一条天际线。
在这里插入图片描述

1.3 天际线的合并

在这里插入图片描述

二、堆优化

基于天际线算法每次取最低或最左线段的特殊性质，我们可以采用基于二叉堆实现的优先队列来存储天际线集合，以优化最佳天际线的取出效率。

在Java中直接可以使用PriorityQueue（线程不安全）或者PriorityBlockingQueue（线程安全）来存储天际线，其底层就是基于最小二叉堆实现的，可以实现动态排序。

三、复杂的评分策略

Leung等人（2011）和Wei等人（2016）提出了复杂的评分策略，为最低和最左边的空间选择最合适的矩形。

下图展示了hl小于hr的八种情况（类似的hl大于等于hr的情况只需要将hr和hl互换即可）。对于hl大于等于hr，类似地，也存在八种情况。我们会选择得分最高的放置方式，如果几个矩形有相同的得分，则选择索引较小的矩形的放置方式。

a) 矩形的宽等于天际线长度，且矩形的高等于hr
b) 矩形的宽等于天际线长度，且矩形的高等于hl
c) 矩形的宽等于天际线长度，且矩形的高大于hr
d) 矩形的宽小于天际线长度，且矩形的高等于hr，此时靠右放置
e) 矩形的宽等于天际线长度，且矩形的高大于hl小于hr
f) 矩形的宽小于天际线长度，且矩形的高等于hl
g) 矩形的宽等于天际线长度，且矩形的高小于hl
h) 矩形的宽小于天际线长度，且矩形的高不等于hr，此时靠右放置

在这里插入图片描述

四、Java代码实现

4.1 项目结构

在这里插入图片描述

4.2 data

下面都用data.txt进行测试，所以我就只给出它的内容了

data的格式要求如下：

边界的宽边界的高是否允许旋转（允许则写1，否则写0）
矩形宽矩形高
矩形宽矩形高
矩形宽矩形高
矩形宽矩形高
…
矩形宽矩形高

data.txt内容如下

4.3 entitys

4.3.1 Instance

实例对象：里面是整个问题的信息（包括边界尺寸、矩形集合等）

/**
 * @Author：WSKH
 * @ClassName：Instance
 * @ClassType：
 * @Description：实例对象
 * @Date：2022/11/6/21:10
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class Instance {

    // 边界的宽
    private double W;
    // 边界的高
    private double H;
    // 矩形列表
    private List<Item> itemList;
    // 是否允许矩形旋转
    private boolean isRotateEnable;

    public double getW() {
        return W;
    }

    public void setW(double w) {
        W = w;
    }

    public double getH() {
        return H;
    }

    public void setH(double h) {
        H = h;
    }

    public List<Item> getItemList() {
        return itemList;
    }

    public void setItemList(List<Item> itemList) {
        this.itemList = itemList;
    }

    public boolean isRotateEnable() {
        return isRotateEnable;
    }

    public void setRotateEnable(boolean rotateEnable) {
        isRotateEnable = rotateEnable;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

4.3.2 Item

矩形对象：包括矩形的宽、高和名字信息

/**
 * @Author：WSKH
 * @ClassName：Item
 * @ClassType：
 * @Description：矩形对象
 * @Date：2022/11/6/19:39
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class Item {

    // 名字
    private String name;
    // 宽
    private double w;
    // 高
    private double h;

    // 构造函数
    public Item(String name, double w, double h) {
        this.name = name;
        this.w = w;
        this.h = h;
    }

    // 复制单个Item
    public static Item copy(Item item) {
        return new Item(item.name, item.w, item.h);
    }

    // 复制Item数组
    public static Item[] copy(Item[] items) {
        Item[] newItems = new Item[items.length];
        for (int i = 0; i < items.length; i++) {
            newItems[i] = copy(items[i]);
        }
        return newItems;
    }

    // 复制Item列表
    public static List<Item> copy(List<Item> items) {
        List<Item> newItems = new ArrayList<>();
        for (Item item : items) {
            newItems.add(copy(item));
        }
        return newItems;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getW() {
        return w;
    }

    public void setW(double w) {
        this.w = w;
    }

    public double getH() {
        return h;
    }

    public void setH(double h) {
        this.h = h;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

4.3.3 PlaceItem

已放置矩形对象：包括已放置矩形的坐标信息、是否旋转、宽高信息

/**
 * @Author：WSKH
 * @ClassName：PlaceItem
 * @ClassType：
 * @Description：已放置矩形对象
 * @Date：2022/11/6/20:06
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class PlaceItem {

    // 名字
    private String name;
    // x坐标
    private double x;
    // y坐标
    private double y;
    // 宽（考虑旋转后的）
    private double w;
    // 高（考虑旋转后的）
    private double h;
    // 是否旋转
    private boolean isRotate;

    // 构造函数
    public PlaceItem(String name, double x, double y, double w, double h, boolean isRotate) {
        this.name = name;
        this.x = x;
        this.y = y;
        this.w = w;
        this.h = h;
        this.isRotate = isRotate;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getX() {
        return x;
    }

    public void setX(double x) {
        this.x = x;
    }

    public double getY() {
        return y;
    }

    public void setY(double y) {
        this.y = y;
    }

    public double getW() {
        return w;
    }

    public void setW(double w) {
        this.w = w;
    }

    public double getH() {
        return h;
    }

    public void setH(double h) {
        this.h = h;
    }

    public boolean isRotate() {
        return isRotate;
    }

    public void setRotate(boolean rotate) {
        isRotate = rotate;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

4.3.4 SkyLine

天际线对象：包括天际线左端点坐标、天际线线段长度信息

/**
 * @Author：WSKH
 * @ClassName：SkyLine
 * @ClassType：
 * @Description：天际线对象
 * @Date：2022/11/6/19:55
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class SkyLine implements Comparable<SkyLine> {

    // 天际线左端点x坐标
    private double x;
    // 天际线左端点y坐标
    private double y;
    // 天际线长度
    private double len;

    // 构造函数
    public SkyLine(double x, double y, double len) {
        this.x = x;
        this.y = y;
        this.len = len;
    }

    // 天际线排序规则，y越小越优先，y一样时，x越小越优先
    @Override
    public int compareTo(SkyLine o) {
        int c1 = Double.compare(y, o.y);
        return c1 == 0 ? Double.compare(x, o.x) : c1;
    }

    // 重写ToString方法，方便打印查看天际线
    @Override
    public String toString() {
        return "SkyLine{" +
                "x=" + x +
                ", y=" + y +
                ", len=" + len +
                '}';
    }

    public double getX() {
        return x;
    }

    public void setX(double x) {
        this.x = x;
    }

    public double getY() {
        return y;
    }

    public void setY(double y) {
        this.y = y;
    }

    public double getLen() {
        return len;
    }

    public void setLen(double len) {
        this.len = len;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

4.3.5 Solution

结果对象：包括已放置矩形列表、已放置矩形总面积、装载利用率信息

/**
 * @Author：WSKH
 * @ClassName：Solution
 * @ClassType：
 * @Description：装箱结果类
 * @Date：2022/11/7/11:53
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class Solution {

    // 已放置矩形
    private List<PlaceItem> placeItemList;
    // 放置总面积
    private double totalS;
    // 利用率
    private double rate;

    // 构造函数
    public Solution(List<PlaceItem> placeItemList, double totalS, double rate) {
        this.placeItemList = placeItemList;
        this.totalS = totalS;
        this.rate = rate;
    }

    public List<PlaceItem> getPlaceItemList() {
        return placeItemList;
    }

    public void setPlaceItemList(List<PlaceItem> placeItemList) {
        this.placeItemList = placeItemList;
    }

    public double getTotalS() {
        return totalS;
    }

    public void setTotalS(double totalS) {
        this.totalS = totalS;
    }

    public double getRate() {
        return rate;
    }

    public void setRate(double rate) {
        this.rate = rate;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

4.4 util

读取数据的工具类，返回Instance对象

/**
 * @Author：WSKH
 * @ClassName：ReadDataUtil
 * @ClassType：
 * @Description：读取数据工具类
 * @Date：2022/11/6/19:39
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class ReadDataUtil {
    public Instance getInstance(String path) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new FileReader(path));
        String input = null;
        Instance instance = new Instance();
        List<Item> itemList = new ArrayList<>();
        boolean isFirstLine = true;
        while ((input = bufferedReader.readLine()) != null) {
            String[] split = input.split(" ");
            if (isFirstLine) {
                instance.setW(Double.parseDouble(split[0]));
                instance.setH(Double.parseDouble(split[1]));
                instance.setRotateEnable("1".equals(split[2]));
                isFirstLine = false;
            } else {
                itemList.add(new Item(UUID.randomUUID().toString(), Double.parseDouble(split[0]), Double.parseDouble(split[1])));
            }
        }
        instance.setItemList(itemList);
        return instance;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

4.5 model

天际线启发式算法类

/**
 * @Author：WSKH
 * @ClassName：SkyLinePacking
 * @ClassType：
 * @Description：天际线启发式算法求解二维矩形装箱问题
 * @Date：2022/11/6/19:39
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class SkyLinePacking {

    // 边界的宽
    private double W;
    // 边界的高
    private double H;
    // 矩形数组
    private Item[] items;
    // 是否可以旋转
    private boolean isRotateEnable;
    // 基于堆优化的天际线优先队列（PriorityBlockingQueue是线程安全的，底层基于最小二叉堆实现，具有高效动态排序能力）
    private PriorityBlockingQueue<SkyLine> skyLineQueue = new PriorityBlockingQueue<>();

    /**
     * @param isRotateEnable 是否允许矩形旋转
     * @param W              边界宽度
     * @param H              边界高度
     * @param items          矩形集合
     * @Description 构造函数
     */
    public SkyLinePacking(boolean isRotateEnable, double W, double H, Item[] items) {
        this.isRotateEnable = isRotateEnable;
        this.W = W;
        this.H = H;
        this.items = items;
    }

    /**
     * @return 放置好的矩形列表
     * @Description 天际线启发式装箱主函数
     */
    public Solution packing() {

        // 用来存储已经放置的矩形
        List<PlaceItem> placeItemList = new ArrayList<>();
        // 用来记录已经放置矩形的总面积
        double totalS = 0d;

        // 获取初始天际线(边界底部)
        skyLineQueue.add(new SkyLine(0, 0, W));

        // 记录已经放置的矩形
        boolean[] used = new boolean[items.length];

        // 开始天际线启发式迭代
        while (!skyLineQueue.isEmpty() && placeItemList.size() < items.length) {
            // 获取当前最下最左的天际线（取出队首元素）
            SkyLine skyLine = skyLineQueue.poll();
            // 初始化hl和hr
            double hl = H - skyLine.getY();
            double hr = H - skyLine.getY();
            // 提前跳出计数器(如果hl和hr都获取到了就可以提前跳出，节省时间)
            int c = 0;
            // 顺序遍历天际线队列，根据skyline和skyline队列获取hl和hr
            for (SkyLine line : skyLineQueue) {
                // 由于skyLine是队首元素，所以它的Y肯定最小，所以line.getY() - skyLine.getY()肯定都大于等于0
                if (compareDouble(line.getX() + line.getLen(), skyLine.getX()) == 0) {
                    // 尾头相连，是hl
                    hl = line.getY() - skyLine.getY();
                    c++;
                } else if (compareDouble(line.getX(), skyLine.getX() + skyLine.getLen()) == 0) {
                    // 头尾相连，是hr
                    hr = line.getY() - skyLine.getY();
                    c++;
                }
                // hl和hr都获取到了，就没必要继续遍历了，可以提前跳出节省时间
                if (c == 2) {
                    break;
                }
            }
            // 记录最大评分矩形的索引
            int maxItemIndex = -1;
            // 记录最大评分的矩形是否旋转
            boolean isRotate = false;
            // 记录最大评分
            int maxScore = -1;
            // 遍历每一个矩形，选取评分最大的矩形进行放置
            for (int i = 0; i < items.length; i++) {
                // 矩形没有放置过，才进行接下来的流程
                if (!used[i]) {
                    // 不旋转的情况
                    int score = score(items[i].getW(), items[i].getH(), skyLine, hl, hr);
                    if (score > maxScore) {
                        // 更新最大评分
                        maxScore = score;
                        maxItemIndex = i;
                        isRotate = false;
                    }
                    // 旋转的情况（矩形宽和高互换）
                    if (isRotateEnable) {
                        int rotateScore = score(items[i].getH(), items[i].getW(), skyLine, hl, hr);
                        if (rotateScore > maxScore) {
                            // 更新最大评分
                            maxScore = rotateScore;
                            maxItemIndex = i;
                            isRotate = true;
                        }
                    }
                }
            }
            // 如果当前最大得分大于等于0，则说明有矩形可以放置，则按照规则对其进行放置
            if (maxScore >= 0) {
                // 左墙高于等于右墙
                if (hl >= hr) {
                    // 评分为2时，矩形靠天际线右边放，否则靠天际线左边放
                    if (maxScore == 2) {
                        placeItemList.add(placeRight(items[maxItemIndex], skyLine, isRotate));
                    } else {
                        placeItemList.add(placeLeft(items[maxItemIndex], skyLine, isRotate));
                    }
                } else {
                    // 左墙低于右墙
                    // 评分为4或0时，矩形靠天际线右边放，否则靠天际线左边放
                    if (maxScore == 4 || maxScore == 0) {
                        placeItemList.add(placeRight(items[maxItemIndex], skyLine, isRotate));
                    } else {
                        placeItemList.add(placeLeft(items[maxItemIndex], skyLine, isRotate));
                    }
                }
                // 根据索引将该矩形设置为已经放置的矩形
                used[maxItemIndex] = true;
                // 将该矩形面积追加到totalS中
                totalS += (items[maxItemIndex].getW() * items[maxItemIndex].getH());
            } else {
                // 如果当前天际线一个矩形都放不下，那就上移天际线，与其他天际线合并
                combineSkylines(skyLine);
            }
        }
        // 返回求解结果
        return new Solution(placeItemList, totalS, totalS / (W * H));
    }


    /**
     * @param item     要放置的矩形对象
     * @param skyLine  矩形放置所在的天际线
     * @param isRotate 矩形是否旋转
     * @return 返回一个PlaceItem对象（放置好的矩形对象）
     * @Description 将矩形靠左放
     */
    private PlaceItem placeLeft(Item item, SkyLine skyLine, boolean isRotate) {
        // 生成PlaceItem对象
        PlaceItem placeItem = null;
        if (!isRotate) {
            placeItem = new PlaceItem(item.getName(), skyLine.getX(), skyLine.getY(), item.getW(), item.getH(), isRotate);
        } else {
            placeItem = new PlaceItem(item.getName(), skyLine.getX(), skyLine.getY(), item.getH(), item.getW(), isRotate);
        }
        // 将新天际线加入队列
        addSkyLineInQueue(skyLine.getX(), skyLine.getY() + placeItem.getH(), placeItem.getW());
        addSkyLineInQueue(skyLine.getX() + placeItem.getW(), skyLine.getY(), skyLine.getLen() - placeItem.getW());
        // 返回PlaceItem对象
        return placeItem;
    }

    /**
     * @param item     要放置的矩形对象
     * @param skyLine  矩形放置所在的天际线
     * @param isRotate 矩形是否旋转
     * @return 返回一个PlaceItem对象（放置好的矩形对象）
     * @Description 将矩形靠右放
     */
    private PlaceItem placeRight(Item item, SkyLine skyLine, boolean isRotate) {
        // 生成PlaceItem对象
        PlaceItem placeItem = null;
        if (!isRotate) {
            placeItem = new PlaceItem(item.getName(), skyLine.getX() + skyLine.getLen() - item.getW(), skyLine.getY(), item.getW(), item.getH(), isRotate);
        } else {
            placeItem = new PlaceItem(item.getName(), skyLine.getX() + skyLine.getLen() - item.getH(), skyLine.getY(), item.getH(), item.getW(), isRotate);
        }
        // 将新天际线加入队列
        addSkyLineInQueue(skyLine.getX(), skyLine.getY(), skyLine.getLen() - placeItem.getW());
        addSkyLineInQueue(placeItem.getX(), skyLine.getY() + placeItem.getH(), placeItem.getW());
        // 返回PlaceItem对象
        return placeItem;
    }

    /**
     * @param x   新天际线x坐标
     * @param y   新天际线y坐标
     * @param len 新天际线长度
     * @return void
     * @Description 将指定属性的天际线加入天际线队列
     */
    private void addSkyLineInQueue(double x, double y, double len) {
        // 新天际线长度大于0时，才加入
        if (compareDouble(len, 0.0) == 1) {
            skyLineQueue.add(new SkyLine(x, y, len));
        }
    }

    /**
     * @param skyLine 一个放置不下任意矩形的天际线
     * @return void
     * @Description 传入一个放置不下任意矩形的天际线，将其上移，与其他天际线进行合并
     */
    private void combineSkylines(SkyLine skyLine) {
        boolean b = false;
        for (SkyLine line : skyLineQueue) {
            if (compareDouble(skyLine.getY(), line.getY()) != 1) {
                // 头尾相连
                if (compareDouble(skyLine.getX(), line.getX() + line.getLen()) == 0) {
                    skyLineQueue.remove(line);
                    b = true;
                    skyLine.setX(line.getX());
                    skyLine.setY(line.getY());
                    skyLine.setLen(line.getLen() + skyLine.getLen());
                    break;
                }
                // 尾头相连
                if (compareDouble(skyLine.getX() + skyLine.getLen(), line.getX()) == 0) {
                    skyLineQueue.remove(line);
                    b = true;
                    skyLine.setY(line.getY());
                    skyLine.setLen(line.getLen() + skyLine.getLen());
                    break;
                }
            }
        }
        // 如果有进行合并，才加入
        if (b) {
            // 将最后合并好的天际线加入天际线队列
            skyLineQueue.add(skyLine);
        }
    }

    /**
     * @param w       当前要放置的矩形的宽
     * @param h       当前要放置的矩形的高
     * @param skyLine 该天际线对象
     * @param hl      该天际线的左墙
     * @param hr      该天际线的右墙
     * @return 矩形块的评分，如果评分为 -1 ，则说明该矩形不能放置在该天际线上
     * @Description 对矩形进行评分
     */
    private int score(double w, double h, SkyLine skyLine, double hl, double hr) {
        // 当前天际线长度小于当前矩形宽度，放不下
        if (compareDouble(skyLine.getLen(), w) == -1) {
            return -1;
        }
        // 如果超出上界，也不能放
        if (compareDouble(skyLine.getY() + h, H) == 1) {
            return -1;
        }
        int score = -1;
        // 左边墙高于等于右边墙
        if (hl >= hr) {
            if (compareDouble(w, skyLine.getLen()) == 0 && compareDouble(h, hl) == 0) {
                score = 7;
            } else if (compareDouble(w, skyLine.getLen()) == 0 && compareDouble(h, hr) == 0) {
                score = 6;
            } else if (compareDouble(w, skyLine.getLen()) == 0 && compareDouble(h, hl) == 1) {
                score = 5;
            } else if (compareDouble(w, skyLine.getLen()) == -1 && compareDouble(h, hl) == 0) {
                score = 4;
            } else if (compareDouble(w, skyLine.getLen()) == 0 && compareDouble(h, hl) == -1 && compareDouble(h, hr) == 1) {
                score = 3;
            } else if (compareDouble(w, skyLine.getLen()) == -1 && compareDouble(h, hr) == 0) {
                // 靠右
                score = 2;
            } else if (compareDouble(w, skyLine.getLen()) == 0 && compareDouble(h, hr) == -1) {
                score = 1;
            } else if (compareDouble(w, skyLine.getLen()) == -1 && compareDouble(h, hl) != 0) {
                score = 0;
            } else {
                throw new RuntimeException("w = " + w + " , h = " + h + " , hl = " + hl + " , hr = " + hr + " , skyline = " + skyLine);
            }
        } else {
            if (compareDouble(w, skyLine.getLen()) == 0 && compareDouble(h, hr) == 0) {
                score = 7;
            } else if (compareDouble(w, skyLine.getLen()) == 0 && compareDouble(h, hl) == 0) {
                score = 6;
            } else if (compareDouble(w, skyLine.getLen()) == 0 && compareDouble(h, hr) == 1) {
                score = 5;
            } else if (compareDouble(w, skyLine.getLen()) == -1 && compareDouble(h, hr) == 0) {
                // 靠右
                score = 4;
            } else if (compareDouble(w, skyLine.getLen()) == 0 && compareDouble(h, hr) == -1 && compareDouble(h, hl) == 1) {
                score = 3;
            } else if (compareDouble(w, skyLine.getLen()) == -1 && compareDouble(h, hl) == 0) {
                score = 2;
            } else if (compareDouble(w, skyLine.getLen()) == 0 && compareDouble(h, hl) == -1) {
                score = 1;
            } else if (compareDouble(w, skyLine.getLen()) == -1 && compareDouble(h, hr) != 0) {
                // 靠右
                score = 0;
            } else {
                throw new RuntimeException("w = " + w + " , h = " + h + " , hl = " + hl + " , hr = " + hr + " , skyline = " + skyLine);
            }
        }
        return score;
    }

    /**
     * @param d1 双精度浮点型变量1
     * @param d2 双精度浮点型变量2
     * @return 返回0代表两个数相等，返回1代表前者大于后者，返回-1代表前者小于后者，
     * @Description 判断两个双精度浮点型变量的大小关系
     */
    private int compareDouble(double d1, double d2) {
        // 定义一个误差范围，如果两个数相差小于这个误差，则认为他们是相等的 1e-06 = 0.000001
        double error = 1e-06;
        if (Math.abs(d1 - d2) < error) {
            return 0;
        } else if (d1 < d2) {
            return -1;
        } else if (d1 > d2) {
            return 1;
        } else {
            throw new RuntimeException("d1 = " + d1 + " , d2 = " + d2);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323

4.6 run

程序运行的主类，包括装箱结果的可视化展示

/**
 * @Author：WSKH
 * @ClassName：Application
 * @ClassType：
 * @Description：运行程序的主类
 * @Date：2022/11/6/19:39
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class Run extends javafx.application.Application {

    private int counter = 0;

    @Override
    public void start(Stage primaryStage) throws Exception {

        // 数据地址
        String path = "src/main/java/com/wskh/data/data.txt";
        // 根据txt文件获取实例对象
        Instance instance = new ReadDataUtil().getInstance(path);
        // 记录算法开始时间
        long startTime = System.currentTimeMillis();
        // 实例化天际线对象
        SkyLinePacking skyLinePacking = new SkyLinePacking(instance.isRotateEnable(), instance.getW(), instance.getH(), instance.getItemList().toArray(new Item[0]));
        // 调用天际线算法进行求解
        Solution solution = skyLinePacking.packing();
        // 输出相关信息
        System.out.println("求解用时:" + (System.currentTimeMillis() - startTime) / 1000.0 + " s");
        System.out.println("共放置了矩形" + solution.getPlaceItemList().size() + "个");
        System.out.println("利用率为:" + solution.getRate());
        // 输出画图数据
        String[] strings1 = new String[solution.getPlaceItemList().size()];
        String[] strings2 = new String[solution.getPlaceItemList().size()];
        for (int i = 0; i < solution.getPlaceItemList().size(); i++) {
            PlaceItem placeItem = solution.getPlaceItemList().get(i);
            strings1[i] = "{x:" + placeItem.getX() + ",y:" + placeItem.getY() + ",l:" + placeItem.getH() + ",w:" + placeItem.getW() + "}";
            strings2[i] = placeItem.isRotate() ? "1" : "0";
        }
        System.out.println("data:" + Arrays.toString(strings1) + ",");
        System.out.println("isRotate:" + Arrays.toString(strings2) + ",");

        // --------------------------------- 后面这些都是画图相关的代码，可以不用管 ---------------------------------------------
        AnchorPane pane = new AnchorPane();
        Canvas canvas = new Canvas(instance.getW(), instance.getH());
        pane.getChildren().add(canvas);
        canvas.relocate(100, 100);
        // 绘制最外层的矩形
        canvas = draw(canvas, 0, 0, instance.getW(), instance.getH(), true);
        // 添加按钮
        Button nextButton = new Button("Next +1");
        Canvas finalCanvas = canvas;
        nextButton.setOnAction(new EventHandler<ActionEvent>() {
            @Override
            public void handle(ActionEvent actionEvent) {
                try {
                    PlaceItem placeItem = solution.getPlaceItemList().get(counter);
                    draw(finalCanvas, placeItem.getX(), placeItem.getY(), placeItem.getW(), placeItem.getH(), false);
                    counter++;
                } catch (Exception e) {
                    Alert alert = new Alert(Alert.AlertType.WARNING);
                    alert.setContentText("已经没有可以放置的矩形了！");
                    alert.showAndWait();
                }
            }
        });
        //
        pane.getChildren().add(nextButton);
        primaryStage.setTitle("二维矩形装箱可视化");
        primaryStage.setScene(new Scene(pane, 1000, 1000, Color.AQUA));
        primaryStage.show();
    }

    private Canvas draw(Canvas canvas, double x, double y, double l, double w, boolean isBound) {
        GraphicsContext gc = canvas.getGraphicsContext2D();
        // 边框
        gc.setStroke(Color.BLACK);
        gc.setLineWidth(2);
        gc.strokeRect(x, y, l, w);
        // 填充
        if (!isBound) {
            gc.setFill(new Color(new Random().nextDouble(), new Random().nextDouble(), new Random().nextDouble(), new Random().nextDouble()));
        }else{
            gc.setFill(new Color(1,1,1,1));
        }
        gc.fillRect(x, y, l, w);
        return canvas;
    }

    public static void main(String[] args) {
        launch(args);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

4.7 运行结果展示

程序输出信息（最后两行是在前端画图用的，可以忽略）

求解用时:0.004 s
共放置了矩形39个
利用率为:0.97390625
data:[{x:0.0,y:0.0,l:115.0,w:59.0}, {x:59.0,y:0.0,l:115.0,w:21.0}, {x:80.0,y:0.0,l:115.0,w:46.0}, {x:374.0,y:0.0,l:99.0,w:26.0}, {x:258.0,y:0.0,l:99.0,w:116.0}, {x:179.0,y:0.0,l:99.0,w:79.0}, {x:126.0,y:0.0,l:102.0,w:53.0}, {x:179.0,y:99.0,l:118.0,w:79.0}, {x:258.0,y:99.0,l:111.0,w:116.0}, {x:374.0,y:99.0,l:102.0,w:26.0}, {x:138.0,y:102.0,l:63.0,w:41.0}, {x:0.0,y:115.0,l:39.0,w:59.0}, {x:59.0,y:115.0,l:60.0,w:21.0}, {x:90.0,y:115.0,l:50.0,w:48.0}, {x:0.0,y:154.0,l:86.0,w:55.0}, {x:80.0,y:165.0,l:33.0,w:58.0}, {x:146.0,y:165.0,l:114.0,w:33.0}, {x:55.0,y:175.0,l:97.0,w:25.0}, {x:80.0,y:198.0,l:82.0,w:66.0}, {x:379.0,y:201.0,l:108.0,w:21.0}, {x:291.0,y:210.0,l:99.0,w:88.0}, {x:258.0,y:210.0,l:66.0,w:33.0}, {x:179.0,y:217.0,l:111.0,w:79.0}, {x:0.0,y:240.0,l:87.0,w:55.0}, {x:55.0,y:272.0,l:55.0,w:24.0}, {x:258.0,y:276.0,l:47.0,w:27.0}, {x:149.0,y:279.0,l:46.0,w:30.0}, {x:79.0,y:280.0,l:76.0,w:70.0}, {x:285.0,y:309.0,l:44.0,w:94.0}, {x:380.0,y:309.0,l:58.0,w:20.0}, {x:258.0,y:323.0,l:56.0,w:27.0}, {x:149.0,y:325.0,l:73.0,w:30.0}, {x:0.0,y:327.0,l:73.0,w:55.0}, {x:55.0,y:327.0,l:61.0,w:24.0}, {x:196.0,y:328.0,l:51.0,w:62.0}, {x:285.0,y:353.0,l:44.0,w:49.0}, {x:334.0,y:353.0,l:47.0,w:34.0}, {x:81.0,y:356.0,l:42.0,w:68.0}, {x:179.0,y:379.0,l:21.0,w:103.0}],
isRotate:[0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0],
1
2
3
4
5

可视化展示

在这里插入图片描述

4.8 矩形顺序改进（按面积降序）

根据经验，我们知道如果优先放置面积较大的矩形，利用率可能会提高。所以我们可以做一个小优化，对读取到的矩形集合进行按面积的降序排序，然后再调用天际线算法进行求解。要做到按面积降序排序，我们将下面的代码修改一下：

在这里插入图片描述

        // 实例化天际线对象
        Item[] items = instance.getItemList().toArray(new Item[0]);
        // 按面积降序排列
        Arrays.sort(items, (o1, o2) -> {
            // 由于是降序，所以要加个负号
            return -Double.compare(o1.getW() * o1.getH(), o2.getW() * o2.getH());
        });
        SkyLinePacking skyLinePacking = new SkyLinePacking(instance.isRotateEnable(), instance.getW(), instance.getH(), items);
1
2
3
4
5
6
7
8

修改后输出（利用率变高了）：

求解用时:0.004 s
共放置了矩形22个
利用率为:0.9877375
data:[{x:0.0,y:0.0,l:116.0,w:113.0}, {x:113.0,y:0.0,l:116.0,w:111.0}, {x:224.0,y:0.0,l:116.0,w:99.0}, {x:323.0,y:0.0,l:116.0,w:20.0}, {x:343.0,y:0.0,l:95.0,w:57.0}, {x:343.0,y:95.0,l:89.0,w:57.0}, {x:0.0,y:116.0,l:100.0,w:113.0}, {x:113.0,y:116.0,l:100.0,w:108.0}, {x:221.0,y:116.0,l:81.0,w:102.0}, {x:323.0,y:116.0,l:58.0,w:20.0}, {x:329.0,y:184.0,l:117.0,w:71.0}, {x:221.0,y:197.0,l:54.0,w:108.0}, {x:0.0,y:216.0,l:88.0,w:113.0}, {x:113.0,y:216.0,l:88.0,w:99.0}, {x:212.0,y:251.0,l:107.0,w:117.0}, {x:374.0,y:301.0,l:99.0,w:26.0}, {x:330.0,y:301.0,l:94.0,w:44.0}, {x:0.0,y:304.0,l:96.0,w:98.0}, {x:98.0,y:304.0,l:96.0,w:84.0}, {x:182.0,y:304.0,l:73.0,w:30.0}, {x:238.0,y:358.0,l:37.0,w:92.0}, {x:182.0,y:377.0,l:23.0,w:50.0}],
isRotate:[0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
1
2
3
4
5

可视化展示

在这里插入图片描述

五、总结

天际线启发式算法的优势：

计算速度快（基于天际线放置矩形，无需进行重叠判断，上面的例子有100个矩形，而算法运行只需要0.004秒）
内存消耗少（算法整体采用递推方式运行，栈占用较少，天际线结构也较为简单）
求解质量高（基于复杂的评分策略保证解的质量，且从上面的例子我们也可以看出，算法求出来的装载结果利用率还是挺高的）

六、扩展

由于天际线启发式算法求解结果受矩形顺序所影响，故天际线启发式可以结合启发式算法进行迭代搜索求解，逐步改善解质量（例如：禁忌搜索算法、蚁群算法、遗传算法等）

【运筹优化】结合天际线启发式的禁忌搜索算法求解二维矩形装箱问题 + Java代码实现

【运筹优化】结合天际线启发式的蚁群算法求解二维矩形装箱问题 + Java代码实现

【运筹优化】结合天际线启发式的遗传算法求解二维矩形装箱问题 + Java代码实现

【运筹优化】结合天际线启发式的自适应遗传算法求解二维矩形装箱问题 + Java代码实现

相关阅读:
基地树洞 | 自动化小系列之浏览器篇
 Codeforces Round 905 (Div. 3) 题解 A-E
yocto machine class解析之st-partitions-image
20231010-学习笔记
 项目实践《小说网站数据爬取》
使用ES-Hadoop插件通过Hive查询ES中的数据
 浅议.NET遗留应用改造
 swiper轮播嵌入视频
 Linux安全—iptables详解（概念和filter表）
《算法导论》：矩阵乘法的Strassen算法代码实现
原文地址：https://blog.csdn.net/weixin_51545953/article/details/127719775

【运筹优化】基于堆优化的天际线启发式算法和复杂的评分策略求解二维矩形装箱问题 + Java代码实现

文章目录

一、天际线（SkyLine）启发式

1.1 天际线启发式简介

1.2 新天际线的生成

1.3 天际线的合并

二、堆优化

三、复杂的评分策略

四、Java代码实现

4.1 项目结构

4.2 data

4.3 entitys

4.3.1 Instance

4.3.2 Item

4.3.3 PlaceItem

4.3.4 SkyLine

4.3.5 Solution

4.4 util

4.5 model

4.6 run

4.7 运行结果展示

4.8 矩形顺序改进（按面积降序）

五、总结

六、扩展