精华内容
下载资源
问答
  • 二维装箱问题算法
    千次阅读
    2021-11-30 12:50:48

    一、获取代码方式

    获取代码方式1:
    完整代码已上传我的资源: 【二维装箱】基于matlab遗传算法求解矩形地块二维装箱放置优化问题【含Matlab源码 1556期】
    点击上面蓝色字体,直接付费下载,即可。

    获取代码方式2:
    付费专栏优化求解(Matlab)

    备注:
    点击上面蓝色字体付费专栏优化求解(Matlab),扫描上面二维码,付费299.9元订阅海神之光博客付费专栏,凭支付凭证,私信博主,可免费获得5份本博客上传CSDN资源代码(有效期为订阅日起,三天内有效);
    点击CSDN资源下载链接:5份本博客上传CSDN资源代码

    二、二维装箱简介

    1 引言
    二维装箱问题是随着计算机技术的产生而出现的,大量出现 在 机 械 制 造、皮革服装加 工、汽车、造船、货物装载以及大规模集成电路板的设计等领域。排样布局的优劣直接与材料的成本及经济效益相关。目前主要存在的问题是材料的利用率偏低

    更多相关内容
  • 二维箱式包装 所罗门·博斯韦尔 一个基于JukkaJylänki的文章包装箱的的二维箱包装库 该库用于脱机打包。 Jukka文章中的所有算法试探法和优化都包括在内。 可获得用Flask和ReactJS制作的Web演示。打包性能随优化...
  • 二维装箱】基于matlab遗传算法求解矩形地块二维装箱放置优化问题【含Matlab源码 1556期】.zip,【二维装箱】基于matlab遗传算法求解矩形地块二维装箱放置优化问题【含Matlab源码 1556期】,objection.m,运行结果2....
  • 二维装箱算法实现矩形地块放置优化问题,使用遗传算法优化
  • 此源程序为解决一集装箱装载问题,但是为维和三维算法提供了很好的思路。
  • 多个车子,N个箱子,用二维矩形方式进行装车。采用二叉树实现。java
  • 二维矩形装箱算法--二叉树--java实现.rar
  • 文章目录一、何为二维矩形排样代码编写项目结构pom文件data.txtInstance类PlacePoint类PlaceSquare类Solution类Square类 一、何为二维矩形排样 代码编写 项目结构 pom文件 <?xml version="1.0" encoding="UTF-...


    一、何为二维矩形装箱问题?

    给定一个矩形容器和若干个小的矩形,需要在不超出容器的情况下,求出利用率最高的小矩形放置方案,一个可行的放置方案如下图所示:
    在这里插入图片描述
    本文首先展示我最初的做法,该做法运行速度快,但求解质量差。最后会展示改进后的方法,改进后,虽然运行速度下降了约10倍运行速度下降了约10倍,但是解的质量提高了3%


    二、代码编写

    1.项目结构

    在这里插入图片描述

    2.pom文件

    <?xml version="1.0" encoding="UTF-8"?>
    <project xmlns="http://maven.apache.org/POM/4.0.0"
             xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
             xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
        <modelVersion>4.0.0</modelVersion>
        <groupId>com.wskh</groupId>
        <artifactId>2DRP</artifactId>
        <version>1.0</version>
        <properties>
            <maven.compiler.source>17</maven.compiler.source>
            <maven.compiler.target>17</maven.compiler.target>
        </properties>
        <dependencies>
            <dependency>
                <groupId>org.openjfx</groupId>
                <artifactId>javafx-controls</artifactId>
                <version>15.0.1</version>
            </dependency>
            <dependency>
                <groupId>org.projectlombok</groupId>
                <artifactId>lombok</artifactId>
                <version>1.18.20</version>
            </dependency>
            <dependency>
                <groupId>junit</groupId>
                <artifactId>junit</artifactId>
                <version>4.12</version>
            </dependency>
        </dependencies>
    </project>
    

    3.data.txt

    400 400 0
    59 115
    26 99
    68 97
    41 63
    99 116
    21 60
    79 118
    113 85
    86 55
    33 114
    76 70
    27 47
    117 40
    30 46
    60 62
    87 55
    21 108
    60 67
    82 93
    44 49
    84 96
    89 34
    47 34
    94 44
    117 80
    91 62
    112 73
    37 92
    50 48
    113 100
    24 55
    56 27
    103 21
    61 24
    116 111
    51 62
    67 76
    95 57
    113 116
    63 49
    44 56
    52 47
    33 66
    102 53
    117 107
    40 106
    109 27
    79 99
    40 82
    98 96
    105 105
    94 31
    97 78
    50 23
    86 22
    39 59
    54 92
    37 67
    81 102
    58 33
    113 88
    117 71
    20 58
    65 63
    20 116
    114 69
    117 29
    99 88
    90 49
    35 80
    84 87
    79 111
    97 25
    115 21
    82 66
    79 84
    71 38
    68 80
    57 82
    30 73
    102 31
    68 42
    109 106
    40 42
    24 71
    95 101
    39 94
    100 108
    102 26
    57 89
    108 54
    92 107
    38 62
    38 32
    115 46
    68 37
    106 84
    55 73
    48 103
    107 64
    

    4.Instance类

    package com.wskh.entitys;
    
    import lombok.Data;
    
    import java.util.List;
    
    /*
    **  Create by: WSKH0929
        Date:2021-11-05
        Time:20:16
    */
    @Data
    public class Instance {
        private double L,W;
        // 是否可以旋转
        private boolean isRotateEnable = true;
        private List<Square> squareList;
    }
    

    5.PlacePoint类

    package com.wskh.entitys;
    
    import lombok.AllArgsConstructor;
    import lombok.Data;
    import lombok.NoArgsConstructor;
    
    /*
    **  Create by: WSKH0929
        Date:2021-11-05
        Time:21:08
    */
    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    public class PlacePoint implements Comparable<PlacePoint>{
        private double x,y;
    
        @Override
        public int compareTo(PlacePoint o) {
            // 优先往下排 然后优先往左排
            int compare_y = Double.compare(y,o.y );
            if(compare_y!=0){
                return compare_y;
            }else{
                return Double.compare(x,o.x);
            }
        }
    }
    

    6.PlaceSquare类

    package com.wskh.entitys;
    
    import lombok.AllArgsConstructor;
    import lombok.Data;
    import lombok.NoArgsConstructor;
    
    /*
    **  Create by: WSKH0929
        Date:2021-11-05
        Time:20:18
    */
    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    public class PlaceSquare {
        private double x,y,l,w;
    }
    

    7.Solution类

    package com.wskh.entitys;
    
    import lombok.AllArgsConstructor;
    import lombok.Data;
    import lombok.NoArgsConstructor;
    
    import java.util.List;
    
    /*
    **  Create by: WSKH0929
        Date:2021-11-05
        Time:20:17
    */
    @Data
    @NoArgsConstructor
    @AllArgsConstructor
    public class Solution {
        private double rate;
        private Instance instance;
        private List<Square> squareList;
        private List<PlaceSquare> placeSquareList;
    }
    

    8.Square类

    package com.wskh.entitys;
    
    import lombok.AllArgsConstructor;
    import lombok.Data;
    import lombok.NoArgsConstructor;
    
    /*
    **  Create by: WSKH0929
        Date:2021-11-05
        Time:20:00
    */
    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    public class Square {
        private String id;
        private double l,w;
    }
    

    9.TabuMapTree类

    package com.wskh.model;
    
    import com.wskh.entitys.Square;
    import lombok.Data;
    
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    /*
    **  Create by: WSKH0929
        Date:2021-11-26
        Time:22:21
    */
    @Data
    public class TabuMapTree {
    
        Map<String,TabuMapTree> sonTreeMap = new HashMap<>();
    
        Square nodeSquare;
    
        public void add(List<Square> squareList, int index){
            if(index>=squareList.size()){
                return;
            }
            if(nodeSquare == null){
                nodeSquare = squareList.get(index);
                index++;
            }
            Square square = squareList.get(index);
            String id = square.getId();
            if(sonTreeMap.containsKey(id)){
                sonTreeMap.get(id).add(squareList,index+1);
            }else{
                TabuMapTree tabuMapTree = new TabuMapTree();
                tabuMapTree.setNodeSquare(square);
                sonTreeMap.put(id,tabuMapTree);
                sonTreeMap.get(id).add(squareList,index+1);
            }
        }
    
        public boolean contains(List<Square> squareList,int index){
            if(index>=squareList.size()){
                return true;
            }
            Square square = squareList.get(index);
            String id = square.getId();
            if(sonTreeMap.containsKey(id)){
                return sonTreeMap.get(id).contains(squareList,index+1);
            }else{
                return false;
            }
        }
    
        public void show(){
            for (String key : sonTreeMap.keySet()) {
                String id = sonTreeMap.get(key).getNodeSquare().getId();
                sonTreeMap.get(key).show();
            }
        }
    
        // 判断两个Squre是否相等
        public boolean isEq(Square square1, Square square2){
            return square1.getId().equals(square2.getId());
        }
    
    }
    

    10.TabuSearch类

    package com.wskh.model;
    
    import com.wskh.entitys.*;
    import lombok.Data;
    
    import java.util.*;
    
    /*
    **  Create by: WSKH0929
        Date:2021-11-05
        Time:20:26
    */
    @Data
    public class TabuSearch {
        public  final int MAX_GEN = 300;//最大的迭代次数(提高这个值可以稳定地提高解质量,但是会增加求解时间)
        public  final int N = 50;//每次搜索领域的个数(这个值不要太大,太大的话搜索效率会降低)
        public  int sqNum ;//矩形数量,手动设置
        public HashMap<String,TabuMapTree> tabuTreeMap = new HashMap<>();
        public  List<Square> initGhh;//初始顺序
        public  List<Square> bestGh;//最佳顺序
        public  List<Square> LocalGh;//当前最好顺序
        public  List<Square> tempGh;//存放临时顺序
        public  int bestT;//最佳的迭代次数
        public Solution bestSolution;//最优解
        public  Solution LocalSolution;//每次领域搜索的最优解(领域最优解)
        public  Solution tempSolution;//临时解
        public  int t;//当前迭代
        public Random random;//随机函数对象
        // 问题实例
        public Instance instance;
        double L,W;
    
        public TabuSearch(Instance instance) throws Exception {
            this.instance = instance;
            this.initGhh = new ArrayList<>(instance.getSquareList());
            // 初始化变量
            random = new Random(System.currentTimeMillis());
            L = instance.getL();
            W = instance.getW();
            sqNum = initGhh.size();
        }
        public Solution search() throws Exception {
            // 获取初始解
            getInitSolution();
            System.out.println(bestSolution.getRate());
            //开始迭代,停止条件为达到指定迭代次数
            while (t<=MAX_GEN){
                //当前领域搜索次数
                int n = 0;
                LocalSolution = new Solution();
                LocalSolution.setRate(0);
                while (n <= N){
                    // 随机打乱顺序 得到当前编码Ghh的邻居编码tempGh
                    tempGh = generateNewGh(new ArrayList<>(initGhh),new ArrayList<>(tempGh));
                    // 判断其是否在禁忌表中
                    if(!judge(tempGh)){
                        // 如果不在
                        // 加入禁忌表
                        enterTabooList(tempGh);
                        tempSolution = evaluate(tempGh);
                        if(tempSolution.getRate() > LocalSolution.getRate()){
                            // 如果临时解优于本次领域搜索的最优解
                            // 那么就将临时解替换本次领域搜索的最优解
                            LocalGh = new ArrayList<>(tempGh);
                            LocalSolution = tempSolution;
                        }
                    }else{
                        throw new Exception("重复");
                    }
                    n++;
                }
                if(LocalSolution.getRate() > bestSolution.getRate()){
                    //如果本次搜索的最优解优于全局最优解
                    //那么领域最优解替换全局最优解
                    bestT = t;
                    bestGh = new ArrayList<>(LocalGh);
                    bestSolution = LocalSolution;
    //                bestSolution = evaluate(bestGh);
                }
                initGhh = new ArrayList<>(LocalGh);
                t++;
                System.out.println("当前迭代次数为:"+t+",当前最佳利用率为:"+bestSolution.getRate());
            }
            //求解完毕
            System.out.println("最佳迭代次数:"+bestT);
            System.out.println("最佳利用率为:"+bestSolution.getRate());
            return bestSolution;
        }
        //评价函数
        public Solution evaluate(List<Square> squareList){
            Solution solution = new Solution();
            solution.setInstance(instance);
            solution.setSquareList(new ArrayList<>(squareList));
            List<PlaceSquare> placeSquareList = new ArrayList<>();
            // 创建可放置角点
            List<PlacePoint> placePointList = new ArrayList<>();
            placePointList.add(new PlacePoint(0,0));
            // 开始按照顺序和规则放置
            for (int i = 0; i < squareList.size(); i++) {
                PlacePoint placePoint = null;
                boolean b = false;
                Square square = squareList.get(i);
                for (int j = 0; j < placePointList.size(); j++) {
                    placePoint = placePointList.get(j);
                    PlaceSquare placeSquare = new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW());
                    if(!isOverlap(placeSquareList,placeSquare)){
                        b = true;
                        // 移除当前角点
                        placePointList.remove(j);
                        //新增已放置的square
                        placeSquareList.add(new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW()));
                        // 新增两个可行角点
                        placePointList.add(new PlacePoint(placePoint.getX()+square.getL(),placePoint.getY()));
                        placePointList.add(new PlacePoint(placePoint.getX(),placePoint.getY()+square.getW()));
                        // 重新排序
                        Collections.sort(placePointList);
                        // 跳出内层循环
                        j = placePointList.size();
                    }
                }
                if(!b && instance.isRotateEnable()){
                    double l = square.getL();
                    double w = square.getW();
                    square.setL(w);
                    square.setW(l);
                    for (int j = 0; j < placePointList.size(); j++) {
                        placePoint = placePointList.get(j);
                        PlaceSquare placeSquare = new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW());
                        if(!isOverlap(placeSquareList,placeSquare)){
                            b = true;
                            // 移除当前角点
                            placePointList.remove(j);
                            //新增已放置的square
                            placeSquareList.add(new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW()));
                            // 新增两个可行角点
                            placePointList.add(new PlacePoint(placePoint.getX()+square.getL(),placePoint.getY()));
                            placePointList.add(new PlacePoint(placePoint.getX(),placePoint.getY()+square.getW()));
                            // 重新排序
                            Collections.sort(placePointList);
                            // 跳出内层循环
                            j = placePointList.size();
                        }
                    }
                    square.setL(l);
                    square.setW(w);
                }
            }
            // 设置已经放置的矩形列表
            solution.setPlaceSquareList(new ArrayList<>(placeSquareList));
            // 计算利用率
            double rate = 0.0f;
            double s = 0.0f;
            for (PlaceSquare placeSquare : placeSquareList) {
                s += (placeSquare.getL()*placeSquare.getW());
            }
            rate = s/(L*W);
            solution.setRate(rate);
            return solution;
        }
        // 判断放置在该位置是否超出边界或者和其他矩形重叠
        public boolean isOverlap(List<PlaceSquare> placeSquareList,PlaceSquare tempPlaceSquare){
            // 出界
            if(tempPlaceSquare.getL()>L||tempPlaceSquare.getW()>W){
                return true;
            }
            // 出界
            if(tempPlaceSquare.getX()+tempPlaceSquare.getL()>L||tempPlaceSquare.getY()+tempPlaceSquare.getW()>W){
                return true;
            }
            for (PlaceSquare placeSquare : placeSquareList) {
                // 角点重合
                if(placeSquare.getX()==tempPlaceSquare.getX()&&placeSquare.getY()==tempPlaceSquare.getY()){
    //                placeSquareList.remove(placeSquare);
    //                return true;
                }
                // 判断即将要放置的块是否与之前放置的块有重叠
                if(isOverlap2(placeSquare,tempPlaceSquare)){
                    return true;
                }
            }
            return false;
        }
        // 判断即将要放置的块是否与之前放置的块有重叠
        public boolean isOverlap2(PlaceSquare placeSquare,PlaceSquare tempPlaceSquare){
    
            double x1 = Math.max(placeSquare.getX(), tempPlaceSquare.getX());
            double y1 = Math.max(placeSquare.getY(), tempPlaceSquare.getY());
            double x2 = Math.min(placeSquare.getX()+placeSquare.getL(), tempPlaceSquare.getX()+tempPlaceSquare.getL());
            double y2 = Math.min(placeSquare.getY()+placeSquare.getW(), tempPlaceSquare.getY()+tempPlaceSquare.getW());
    
            if(x1 >= x2 || y1 >= y2) {
                return false;
            }
    
            return true;
    
        }
        // 生成初始解
        public void getInitSolution() throws Exception {
            bestSolution = evaluate(new ArrayList<>(initGhh));
            tempSolution = bestSolution;
            bestGh = new ArrayList<>(initGhh);
            tempGh = new ArrayList<>(initGhh);
            LocalGh = new ArrayList<>(initGhh);
        }
        //加入禁忌队列
        public void enterTabooList(List<Square> squareList){
            if(tabuTreeMap == null){
                tabuTreeMap = new HashMap<>();
            }
            Square square = squareList.get(0);
            String id = square.getId();
            if(tabuTreeMap.containsKey(id)){
                tabuTreeMap.get(id).add(new ArrayList<>(squareList),1);
            }else{
                TabuMapTree tabuMapTree = new TabuMapTree();
                tabuMapTree.setNodeSquare(square);
                tabuMapTree.add(new ArrayList<>(squareList),1);
                tabuTreeMap.put(id,tabuMapTree);
            }
    
        }
        //生成新解
        public List<Square> generateNewGh(List<Square> localGh,List<Square> tempGh) {
            tempGh = new ArrayList<>(localGh);
            Collections.shuffle(tempGh);
            return tempGh;
        }
        //判断路径编码是否存在于禁忌表中
        public boolean judge(List<Square> Gh){
            Square square = Gh.get(0);
            if(tabuTreeMap.containsKey(square.getId())){
                return tabuTreeMap.get(square.getId()).contains(Gh,1);
            }else{
                return false;
            }
        }
        // 判断两个Squre是否相等
        public boolean isEq(Square square1,Square square2){
            return square1.getId().equals(square2.getId());
        }
    }
    

    11.ReadDataUtil类

    package com.wskh.util;
    
    import com.wskh.entitys.Instance;
    import com.wskh.entitys.Square;
    
    import java.io.BufferedReader;
    import java.io.FileNotFoundException;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.UUID;
    
    /*
    **  Create by: WSKH0929
        Date:2021-11-05
        Time:20:10
    */
    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<Square> squareList = new ArrayList<>();
            boolean isFirstLine = true;
            while ((input=bufferedReader.readLine())!=null){
                String[] split = input.split(" ");
                if(isFirstLine){
                    instance.setL(Double.parseDouble(split[0]));
                    instance.setW(Double.parseDouble(split[1]));
                    if(split[2].equals("1")){
                        instance.setRotateEnable(true);
                    }else{
                        instance.setRotateEnable(false);
                    }
                    isFirstLine = false;
                }else{
                    squareList.add(new Square(UUID.randomUUID().toString(),Double.parseDouble(split[0]),Double.parseDouble(split[1])));
                }
            }
            instance.setSquareList(squareList);
            return instance;
        }
    }
    

    12.Application类

    package com.wskh;
    
    import com.wskh.entitys.Instance;
    import com.wskh.entitys.PlaceSquare;
    import com.wskh.entitys.Solution;
    import com.wskh.model.TabuSearch;
    import com.wskh.util.ReadDataUtil;
    import javafx.event.ActionEvent;
    import javafx.event.EventHandler;
    import javafx.scene.Camera;
    import javafx.scene.PerspectiveCamera;
    import javafx.scene.Scene;
    import javafx.scene.canvas.Canvas;
    import javafx.scene.canvas.GraphicsContext;
    import javafx.scene.control.Alert;
    import javafx.scene.control.Button;
    import javafx.scene.input.KeyEvent;
    import javafx.scene.layout.AnchorPane;
    import javafx.scene.paint.Color;
    import javafx.stage.Stage;
    
    import java.lang.management.GarbageCollectorMXBean;
    import java.util.List;
    import java.util.Random;
    
    /*
    **  Create by: WSKH0929
        Date:2021-11-05
        Time:19:55
    */
    public class Application 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";
            TabuSearch model = new TabuSearch(new ReadDataUtil().getInstance(path));
            Solution solution = model.search();
            //
            Instance instance = solution.getInstance();
            AnchorPane pane = new AnchorPane();
            pane = plot(pane,solution);
            Canvas canvas = new Canvas(instance.getL(),instance.getW());
            pane.getChildren().add(canvas);
            canvas.relocate(100,100);
            // 绘制最外层的矩形
            canvas = draw(canvas,0,0,instance.getL(),instance.getW());
            // 添加按钮
            Button nextButton = new Button("Next +1");
            Canvas finalCanvas = canvas;
            nextButton.setOnAction(new EventHandler<ActionEvent>() {
                @Override
                public void handle(ActionEvent actionEvent) {
                    try {
                        PlaceSquare placeSquare = solution.getPlaceSquareList().get(counter);
                        draw(finalCanvas,placeSquare.getX(),placeSquare.getY(),placeSquare.getL(),placeSquare.getW());
                        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 AnchorPane plot(AnchorPane pane, Solution solution) {
            System.out.println(solution);
    
            // 绘制里面的矩形
    //        List<PlaceSquare> placeSquareList = solution.getPlaceSquareList();
    //        System.out.println(placeSquareList.size());
    //        for (PlaceSquare placeSquare : placeSquareList) {
    //            canvas = draw(canvas,placeSquare.getX(),placeSquare.getY(),placeSquare.getL(),placeSquare.getW());
    //        }
            return pane;
        }
    
        private Canvas draw(Canvas canvas,double x,double y,double l,double w){
            GraphicsContext gc = canvas.getGraphicsContext2D();
            // 边框
            gc.setStroke(Color.BLACK);
            gc.setLineWidth(4);
            gc.strokeRect(x,y,l,w);
            // 填充
            gc.setFill(new Color(new Random().nextDouble(),new Random().nextDouble(),new Random().nextDouble(),new Random().nextDouble()));
            gc.fillRect(x,y,l,w);
            return canvas;
        }
    
        public static void main(String[] args) {
            launch(args);
        }
    
    }
    

    三、改进前运行结果(95%)

    在这里插入图片描述
    迭代300次,设置不允许旋转,最终求得利用率为:93%
    在这里插入图片描述
    迭代300次,设置允许旋转,最终求得利用率为95%
    在这里插入图片描述
    可以看到,虽然整体放得还是挺满了,但是放置的很不规整,导致很多空间是存在缺口的,这种现象是导致利用率不高的主要原因。后面我会对此做出改进,加入评分机制,每次放入和自己临近的矩形长或宽较为相似的矩形,以此来减少缺口的出现。


    四、改进 ------ 引入评价指标,修改生成新解的规则

    之前的旋转和放置都是比较盲目的,为了在单次装载中得到最好的结果,我们可以每次从庞大的候选矩形中根据一定的标准选出当前状态最佳放置矩形(即每次放入和自己临近的矩形长或宽较为相似的矩形,以此来减少缺口的出现),如此一来,便可以充分利用候选集中的优质资源,提高单次放置的利用率。
    修改后的代码如下(将之前的TabuSearch、PlacePoint和Application类做了一点小修改):

    1.PlacePoint(修改后)

    package com.wskh.entitys;
    
    import lombok.AllArgsConstructor;
    import lombok.Data;
    import lombok.NoArgsConstructor;
    
    /*
    **  Create by: WSKH0929
        Date:2021-11-05
        Time:21:08
    */
    @Data
    @NoArgsConstructor
    public class PlacePoint implements Comparable<PlacePoint>{
        private double x,y,len;
    
        public PlacePoint(double x, double y, double len) {
            this.x = x;
            this.y = y;
            this.len = len;
        }
    
        public PlacePoint(double x, double y) {
            this.x = x;
            this.y = y;
        }
    
        @Override
        public int compareTo(PlacePoint o) {
            // 优先往下排 然后优先往左排
            int compare_y = Double.compare(y,o.y );
            if(compare_y!=0){
                return compare_y;
            }else{
                return Double.compare(x,o.x);
            }
        }
    }
    

    2.TabuSearch02类

    package com.wskh.model;
    
    import com.wskh.entitys.*;
    import lombok.Data;
    
    import java.util.*;
    
    /*
    **  Create by: WSKH0929
        Date:2021-11-05
        Time:20:26
    */
    @Data
    public class TabuSearch02 {
        public  final int MAX_GEN = 3000;//最大的迭代次数(提高这个值可以稳定地提高解质量,但是会增加求解时间)
        public  final int N = 200;//每次搜索领域的个数(这个值不要太大,太大的话搜索效率会降低)
        public  int sqNum ;//矩形数量,手动设置
        public HashMap<String,TabuMapTree> tabuTreeMap = new HashMap<>();
        public  List<Square> initGhh;//初始顺序
        public  List<Square> bestGh;//最佳顺序
        public  List<Square> LocalGh;//当前最好顺序
        public  List<Square> tempGh;//存放临时顺序
        public  int bestT;//最佳的迭代次数
        public Solution bestSolution;//最优解
        public  Solution LocalSolution;//每次领域搜索的最优解(领域最优解)
        public  Solution tempSolution;//临时解
        public  int t;//当前迭代
        public Random random;//随机函数对象
        // 问题实例
        public Instance instance;
        double L,W;
    
        public TabuSearch02(Instance instance) throws Exception {
            this.instance = instance;
            this.initGhh = new ArrayList<>(instance.getSquareList());
            // 初始化变量
            random = new Random(System.currentTimeMillis());
            L = instance.getL();
            W = instance.getW();
            sqNum = initGhh.size();
        }
        public Solution search() throws Exception {
            long start = System.currentTimeMillis();
            // 获取初始解
            getInitSolution();
            System.out.println(bestSolution.getRate());
            //开始迭代,停止条件为达到指定迭代次数
            while (t<=MAX_GEN){
                //当前领域搜索次数
                int n = 0;
                LocalSolution = new Solution();
                LocalSolution.setRate(0);
                while (n <= N){
                    // 随机打乱顺序 得到当前编码Ghh的邻居编码tempGh
                    tempGh = generateNewGh(new ArrayList<>(initGhh),new ArrayList<>(tempGh));
                    // 判断其是否在禁忌表中
                    if(!judge(tempGh)){
                        // 如果不在
                        //加入禁忌表
                        enterTabooList(tempGh);
                        tempSolution = evaluate(new ArrayList<>(tempGh));
                        if(tempSolution.getRate() > LocalSolution.getRate()){
                            // 如果临时解优于本次领域搜索的最优解
                            // 那么就将临时解替换本次领域搜索的最优解
                            LocalGh = new ArrayList<>(tempGh);
                            LocalSolution = tempSolution;
                        }
                    }else{
    //                    throw new Exception("重复");
                    }
                    n++;
                }
                if(LocalSolution.getRate() > bestSolution.getRate()){
                    //如果本次搜索的最优解优于全局最优解
                    //那么领域最优解替换全局最优解
                    bestT = t;
                    bestGh = new ArrayList<>(LocalGh);
                    bestSolution = LocalSolution;
    //                bestSolution = evaluate(bestGh);
                }
                initGhh = new ArrayList<>(LocalGh);
                t++;
                System.out.println("当前迭代次数为:"+t+",当前最佳利用率为:"+bestSolution.getRate());
            }
            //求解完毕
            System.out.println("最佳迭代次数:"+bestT);
            System.out.println("最佳利用率为:"+bestSolution.getRate());
            System.out.println("用时:"+(System.currentTimeMillis()-start)+"ms");
            return bestSolution;
        }
        //评价函数
        public Solution evaluate(List<Square> squareList){
            Solution solution = new Solution();
            solution.setInstance(instance);
            solution.setSquareList(new ArrayList<>(squareList));
            List<PlaceSquare> placeSquareList = new ArrayList<>();
            // 创建初始可放置角点
            List<PlacePoint> placePointList = new ArrayList<>();
            placePointList.add(new PlacePoint(0,0,L));
    
            // 开始按照顺序和规则放置
            for (int i = 0; i < placePointList.size();) {
                PlacePoint placePoint = placePointList.get(i);
                double maxMark = -1.0d;
                int maxIndex = -1;
                double isRotate = -1,curMarks = -1;
                for (int j = 0; j < squareList.size(); j++) {
                    Square square = squareList.get(j);
                    double[] arr = getMarks(placePoint, square,placeSquareList);
                    double is_rotate = arr[0];
                    curMarks = arr[1];
                    if( curMarks > 0 && curMarks>maxMark){
                        maxMark = curMarks;
                        maxIndex = j;
                        isRotate = is_rotate;
                    }
                }
                if(maxIndex<0 && i<placePointList.size()){
                    i++;
                }else if(maxIndex<0 && i >= placePointList.size()){
                    break;
                }else{
                    Square square = squareList.remove(maxIndex);
                    double l = square.getL();
                    double w = square.getW();
                    if(isRotate>0){
                        // 表示进行了旋转
                        square.setL(w);
                        square.setW(l);
                    }
                    // 移除当前角点
                    placePointList.remove(i);
                    //新增已放置的square
                    placeSquareList.add(new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW()));
                    // 新增两个可行角点
                    double surplus = placePoint.getLen() - square.getL(); // 剩余长度
                    if(surplus>0){
                        placePointList.add(new PlacePoint(placePoint.getX()+square.getL(),placePoint.getY(),surplus));
                    }
                    placePointList.add(new PlacePoint(placePoint.getX(),placePoint.getY()+square.getW(),square.getL()));
                    // 重新排序
                    Collections.sort(placePointList);
    //                System.out.println(placePointList);
                    i = 0;
                    // 还原矩形
                    if(isRotate>0){
                        // 表示进行了旋转
                        square.setL(l);
                        square.setW(w);
                    }
                }
            }
            // 设置已经放置的矩形列表
            solution.setPlaceSquareList(new ArrayList<>(placeSquareList));
            // 计算利用率
            double rate = 0.0f;
            double s = 0.0f;
            for (PlaceSquare placeSquare : placeSquareList) {
                s += (placeSquare.getL()*placeSquare.getW());
            }
            rate = s/(L*W);
            solution.setRate(rate);
            return solution;
        }
        // 评价该点的得分
        private double[] getMarks(PlacePoint placePoint,Square square,List<PlaceSquare> placeSquareList){
            // 返回{是否旋转,分数}
            double delta = 0,mark1 = -1d,mark2 = -1d;
            PlaceSquare placeSquare = new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW());
            if(isOverlap(placeSquareList,placeSquare)){
                mark1 = -1.0d;
            }else{
                delta = Math.abs(placePoint.getLen()-square.getL());
                mark1 = 1 - delta/placePoint.getLen();
            }
            mark2 = -1.0d;
            if(instance.isRotateEnable()){
                placeSquare = new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getW(),square.getL());
                if(!isOverlap(placeSquareList,placeSquare)){
                    delta = Math.abs(placePoint.getLen()-square.getW());
                    mark2 = 1 - delta/placePoint.getLen();
                }
            }
            if(mark1>=mark2){
                return new double[]{-1d,(int)(mark1*10)};
            }
            return new double[]{1d,(int)(mark2*10)};
        }
        // 判断放置在该位置是否超出边界或者和其他矩形重叠
        public boolean isOverlap(List<PlaceSquare> placeSquareList,PlaceSquare tempPlaceSquare){
            // 出界
            if(tempPlaceSquare.getL()>L||tempPlaceSquare.getW()>W){
                return true;
            }
            // 出界
            if(tempPlaceSquare.getX()+tempPlaceSquare.getL()>L||tempPlaceSquare.getY()+tempPlaceSquare.getW()>W){
                return true;
            }
            for (PlaceSquare placeSquare : placeSquareList) {
                // 角点重合
                if(placeSquare.getX()==tempPlaceSquare.getX()&&placeSquare.getY()==tempPlaceSquare.getY()){
                    placeSquareList.remove(placeSquare);
                    return true;
                }
                // 判断即将要放置的块是否与之前放置的块有重叠
                if(isOverlap2(placeSquare,tempPlaceSquare)){
                    return true;
                }
            }
            return false;
        }
        // 判断即将要放置的块是否与之前放置的块有重叠
        public boolean isOverlap2(PlaceSquare placeSquare,PlaceSquare tempPlaceSquare){
    
            double x1 = Math.max(placeSquare.getX(), tempPlaceSquare.getX());
            double y1 = Math.max(placeSquare.getY(), tempPlaceSquare.getY());
            double x2 = Math.min(placeSquare.getX()+placeSquare.getL(), tempPlaceSquare.getX()+tempPlaceSquare.getL());
            double y2 = Math.min(placeSquare.getY()+placeSquare.getW(), tempPlaceSquare.getY()+tempPlaceSquare.getW());
    
            if(x1 >= x2 || y1 >= y2) {
                return false;
            }
    
            return true;
    
        }
        // 生成初始解
        public void getInitSolution() throws Exception {
            Collections.shuffle(initGhh);
            bestSolution = evaluate(new ArrayList<>(initGhh));
            tempSolution = bestSolution;
            bestGh = new ArrayList<>(initGhh);
            tempGh = new ArrayList<>(initGhh);
            LocalGh = new ArrayList<>(initGhh);
        }
        //加入禁忌队列
        public void enterTabooList(List<Square> squareList){
            if(tabuTreeMap == null){
                tabuTreeMap = new HashMap<>();
            }
            Square square = squareList.get(0);
            String id = square.getId();
            if(tabuTreeMap.containsKey(id)){
                tabuTreeMap.get(id).add(new ArrayList<>(squareList),1);
            }else{
                TabuMapTree tabuMapTree = new TabuMapTree();
                tabuMapTree.setNodeSquare(square);
                tabuMapTree.add(new ArrayList<>(squareList),1);
                tabuTreeMap.put(id,tabuMapTree);
            }
    
        }
        //生成新解
    //    public List<Square> generateNewGh(List<Square> localGh,List<Square> tempGh) {
    //        tempGh = new ArrayList<>(localGh);
    //        Collections.shuffle(tempGh);
    //        return tempGh;
    //    }
        public List<Square> generateNewGh(List<Square> localGh,List<Square> tempGh) {
            Square temp;
            //将Gh复制到tempGh
            tempGh = new ArrayList<>(localGh);
    
            for (int i = 0; i < 6; i++) {
                int r1 = 0;
                int r2 = 0;
    
                while (r1==r2){
                    r1 = random.nextInt(tempGh.size());
                    r2 = random.nextInt(tempGh.size());
                }
                //交换
                temp = tempGh.get(r1);
                tempGh.set(r1,tempGh.get(r2));
                tempGh.set(r2,temp);
            }
    
            return new ArrayList<>(tempGh);
        }
        //判断路径编码是否存在于禁忌表中
        public boolean judge(List<Square> Gh){
            Square square = Gh.get(0);
            if(tabuTreeMap.containsKey(square.getId())){
                return tabuTreeMap.get(square.getId()).contains(Gh,1);
            }else{
                return false;
            }
        }
        // 判断两个Squre是否相等
        public boolean isEq(Square square1,Square square2){
            return square1.getId().equals(square2.getId());
        }
    }
    

    3.Application(修改后)

    package com.wskh;
    
    import com.wskh.entitys.Instance;
    import com.wskh.entitys.PlaceSquare;
    import com.wskh.entitys.Solution;
    import com.wskh.model.TabuSearch;
    import com.wskh.model.TabuSearch02;
    import com.wskh.util.ReadDataUtil;
    import javafx.event.ActionEvent;
    import javafx.event.EventHandler;
    
    import javafx.scene.Scene;
    import javafx.scene.canvas.Canvas;
    import javafx.scene.canvas.GraphicsContext;
    import javafx.scene.control.Alert;
    import javafx.scene.control.Button;
    
    import javafx.scene.layout.AnchorPane;
    import javafx.scene.paint.Color;
    import javafx.stage.Stage;
    
    import java.util.Random;
    
    /*
    **  Create by: WSKH0929
        Date:2021-11-05
        Time:19:55
    */
    public class Application 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";
    //        TabuSearch model = new TabuSearch(new ReadDataUtil().getInstance(path));
            TabuSearch02 model = new TabuSearch02(new ReadDataUtil().getInstance(path));
            Solution solution = model.search();
            //
            Instance instance = solution.getInstance();
            AnchorPane pane = new AnchorPane();
            pane = plot(pane,solution);
            Canvas canvas = new Canvas(instance.getL(),instance.getW());
            pane.getChildren().add(canvas);
            canvas.relocate(100,100);
            // 绘制最外层的矩形
            canvas = draw(canvas,0,0,instance.getL(),instance.getW());
            // 添加按钮
            Button nextButton = new Button("Next +1");
            Canvas finalCanvas = canvas;
            nextButton.setOnAction(new EventHandler<ActionEvent>() {
                @Override
                public void handle(ActionEvent actionEvent) {
                    try {
                        PlaceSquare placeSquare = solution.getPlaceSquareList().get(counter);
                        draw(finalCanvas,placeSquare.getX(),placeSquare.getY(),placeSquare.getL(),placeSquare.getW());
                        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 AnchorPane plot(AnchorPane pane, Solution solution) {
            System.out.println(solution);
    
            // 绘制里面的矩形
    //        List<PlaceSquare> placeSquareList = solution.getPlaceSquareList();
    //        System.out.println(placeSquareList.size());
    //        for (PlaceSquare placeSquare : placeSquareList) {
    //            canvas = draw(canvas,placeSquare.getX(),placeSquare.getY(),placeSquare.getL(),placeSquare.getW());
    //        }
            return pane;
        }
    
        private Canvas draw(Canvas canvas,double x,double y,double l,double w){
            GraphicsContext gc = canvas.getGraphicsContext2D();
            // 边框
            gc.setStroke(Color.BLACK);
            gc.setLineWidth(2);
            gc.strokeRect(x,y,l,w);
            // 填充
            gc.setFill(new Color(new Random().nextDouble(),new Random().nextDouble(),new Random().nextDouble(),new Random().nextDouble()));
            gc.fillRect(x,y,l,w);
            return canvas;
        }
    
        public static void main(String[] args) {
            launch(args);
        }
    }
    

    五、改进后效果(利用率98.8%)

    在这里插入图片描述

    六、后话

    其实改进的时候还改进了生成新解的方法,之前是用Collections.shuffle(list)的方式进行打乱的,这种方法是java自带的,内部的机制我也不是很清楚,猜测可能使用这种打乱方式会使新解和旧解序列相差较大,导致领域搜索失效,后来我采用两两互换重复6次的方法,即保证了较大的搜索域,又保证了不过于跳动。最终,改变随机生成新解的方法,使结果提高了0.8个百分点;其次,最重要的改进就是评分机制,它使得我们可以充分利用候选集丰富的资源,每次只选对结果最有利的矩形放入,尽可能的让剩余空间被占满,加入评分机制,使得结果提高了近3个百分点。

    展开全文
  • 问题装箱有关:我们有尺寸相同的容器和各种尺寸的箱子。 目标是使用尽可能少的容器来装满所有的盒子。 他们 == 方法== 我们的方法是对所有高度递减的框进行排序(如果发生冲突,则宽度递减)。 然后,我们将盒子...
  • 二维装箱问题是具有广泛应用背景的一类组合优化问题 ,这类问题是 NP难问题 ,很难得到精确解 。将二维装箱问题表示为一个非线性规划模型 ,用变分分析中切锥的概念建立了这一优化问题的一阶最优性条件 。给出了求解这...
  • 针对二维矩形条带装箱问题提出了一种启发式布局算法,即底部左齐择优匹配算法(lowest—level left align bestfit,简称LLABF).LLABF算法遵循最佳匹配优先原则,该原则综合考虑完全匹配优先、宽度匹配优先、高度...
  • 二维装箱问 题 是 随 着 计 算 机 技 术 的 产 生 而 出现的,大量出现 在 机 械 制 造、皮 革 服 装 加 工、汽 车、造船、货物装载以及大规模集成电路板的设计等领域。排样布局 的 优 劣 直 接 与 材 料 的 成 本 ...

    1 简介

    通过分析人工排列的思考过程和实际经验,提出一种解决二维规则物体排列问题的算法。通过计算可放置点和可放置空间,高效解决物块的排列问题。应用遗传算法,求得最优的排列方案。实际应用证明了该算法的有效性。二维装箱问 题 是 随 着 计 算 机 技 术 的 产 生 而 出现的,大量出现 在 机 械 制 造、皮 革 服 装 加 工、汽 车、造船、货物装载以及大规模集成电路板的设计等领域。排样布局 的 优 劣 直 接 与 材 料 的 成 本 及 经 济效益相关。目前主要存在的问题是材料的利用率偏低,造成巨大的浪费。对于规模较大的生产厂家来说,即使是材料利 用 率 有 很 小 的 提 升,也 会 带 来巨大的经济效益。

    2 部分代码

    function [F,newX2]=objection(X)

    global  data NUM layout

    %%

    H=200;

    L=200;

    X1=X(1:NUM);

    X2=X(NUM+1:end);

    X2=X2(X1);

    newX2=X2;

    for i=1:NUM

      if X1(i)>1

        newX2(i)=sum(layout(1:X1(i)-1))+X2(i);

      end

    end

    % F=sum(data(newX2,4));

    % return;

    flag=1;

    F=0;

    sizeX=0;%记录左右以用长度

    sizeY0=0;%记录上下以用长度

    sizeY1=0;

    j=1;

    k=1;

    for i=1:NUM

        if i==1

    %        sizeX=data(newX2(i),1);

           sizeX=data(newX2(i),1)+data(newX2(i),5);

           sizeY0=0;

           sizeY1=data(newX2(i),2)+data(newX2(i),4);

           F=F+data(newX2(i),6);

           row(1,1)=newX2(i);

        else

            if sizeX+data(newX2(i),1)+data(newX2(i),5)<H

               if sizeY0+data(newX2(i),2)+data(newX2(i),4)<L

                 sizeY1=max(sizeY1,sizeY0+data(newX2(i),2)+data(newX2(i),4));

                 sizeX=sizeX+data(newX2(i),1)+data(newX2(i),5);

                 F=F+data(newX2(i),6);

                 k=k+1;

                 row(j,k)=newX2(i); %记录摆放顺序

               else

    %                flag=0;

                   break;

               end

            else

                if sizeY1+data(newX2(i),2)+data(newX2(i),4)<L

                    sizeY0=sizeY1;

                    sizeY1=sizeY1+data(newX2(i),2)+data(newX2(i),4);

                    sizeX=data(newX2(i),1);

                    F=F-data(newX2(i-1),6)+data(newX2(i),7)+data(newX2(i),6);%表示去除最右侧单元体东西间距,计算容积率之和

                    j=j+1;

                    k=1;

                    row(j,k)=newX2(i);%记录摆放顺序

                else

    %                 F=F-data(newX2(i-1),6)+data(newX2(i),8)+data(newX2(i),6);

    %                 flag=0;

                    break;

                end

            end

        end

    end

    row %记录摆放顺序

    [a,b]=size(row);

    B=row(a,:);%

    for i=1:b

        if B(i)~=0

         F=F-data(B(i),6)+data(B(i),8); %最后一层,去除南北间距后,计算容积率之和

        end

    end

    if flag==0

       F=F+1000; 

    end


     

    3 仿真结果

    4 参考文献

    [1]田大肥, 申喜, and 周巍. "二维装箱问题的遗传算法求解." 舰船电子工程 34.1(2014):5.

    博主简介:擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真,相关matlab代码问题可私信交流。

    部分理论引用网络文献,若有侵权联系博主删除。

    展开全文
  • matlab二维装箱问题求解
  • 1 题目 将若干个矩形物品装进矩形箱子中,并且在...2 装箱算法 2.1 所有装箱算法 参考【A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing】 以下我将会介绍其中一.

    在这里插入图片描述

    1 题目

    将若干个矩形物品装进矩形箱子中,并且在装箱的过程中不允许将矩形物品斜着放,即平行于横坐标。一般来说求解的目标是最小化箱子的箱子数目或者是箱子空间占用率。

    当该算法适用于矩阵存储时,求解的最优目标是箱子的最大化空间占用率。以下即是求解的过程

    2 装箱算法

    2.1 所有装箱算法

    参考【A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing

    在这里插入图片描述

    以下我将会介绍其中一种叫Bottom-Left装箱算法。算法过程就是,矩形从箱子的右上角开始进入,先尽可能向下移动,再向左移动,一直循环,直至不再移动。在以下算法过程中,以0-1背包问题的思路去实现,即某个矩形装进箱子,则flag相应为1,未装进的flag为0。输出单个箱子占用率。

    2.2 Bottom-Left具体算法过程

    初始化是,输入箱子大小[W,H]

    再输入每一个矩形的长和宽

    4 5

    4 7

    4 2

    4 4

    7 4

    初始装箱顺序为:12345

    在这里插入图片描述

    第一步:装第一个矩形,从右上角进入,一直向下移动,然后移动一直向左移动,直到左下角。用一个列表记录装进箱子的矩阵。表示为【x,y,width,height】x和y使右上角坐标。该矩形的flag标记为1。

    在这里插入图片描述

    第二步:装第二个矩形,先将矩形放入右上角,再判断第二个矩形是否与箱子中的矩形是否相交(overlap函数)。如果相交,就不放进箱子,换下一个矩形,如果不相交,计算可向下移动的距离(downHAtPoint函数),向下移动,并更新矩形位置(Update_itemRP函数),最后计算可向左移动的距离(leftWAtPoint函数),向左移动,并更新位置,直至可移动距离为0。将第二个矩形最终位置信息【x,y,width,height】添加进列表。该矩形的flag标记未1。

    在这里插入图片描述

    第三步:剩下的矩形,和第二步一样。如果该矩形装不进箱子,就换下一个矩阵,继续装,直至遍历完所有箱子。

    在这里插入图片描述

    3 Python 实现

    本算法实现中,只用了一个箱子。如果想要多个箱子来装,可以修改本人去掉注释的地方,启用下一个箱子。

    3.1 main.py主函数

    from tools import *
    import random
    
    #   BL(bottom-up left-justified)法求解二位装箱问题
    #   @BetterBench
    #   思想:首先将选中的物体放在箱子的右上角,然后尽量向下向左作连续移动,直到不能移动为止
    # 输入参数
    itemNum=30 #物品数目
    AllItem=np.array([[random.randint(1, 5) for j in range(1, 3)] for i in range(1,itemNum+1)])  #随机生成30个物品,[width,height]
    Bin=[10,10] #箱子宽度与高度
    ran=list(range(itemNum))
    random.shuffle(ran) #随机生成装箱序列
    
    ansBXY=np.zeros((itemNum,3))  #[箱子编号,X坐标,Y坐标]
    RPNXY=[];
    BinNum=1;
    flagItem=np.zeros(itemNum) #标记物品是否被装入箱子,0没有装入,1装入
    # 开始装箱
    
    for i in range(itemNum):
        if flagItem[ran[i]]==0:
            item=AllItem[ran[i],:]
            itemRP=Bin  #起点全部在箱子右上角顶点
            flagOL=overlap(item,AllItem,itemRP,RPNXY) #如果重合flagOL=1;反之flagOL=0
            if flagOL==0:
                itemRP=finalPos(item,AllItem,itemRP,RPNXY) #更新物品从当前位置向下向左移动后到最终位置后右上角顶点坐标
                RPNXY.append([ran[i],itemRP[0],itemRP[1]]) # 记录装进箱子的矩形【ID,width,height】
                flagItem[ran[i]]=1
    # 启用第下一个箱子
    # if list(flagItem).count(0)>0:
    #     BinNum=BinNum+1
    #     RPNXY=[]
    

    输出哪些矩形被装进箱子

    print(flagItem)
    

    array([0., 0., 1., 1., 1., 0., 1., 0., 1., 1., 0., 0., 1., 1., 1., 1., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0.])

    计算箱子占用率

    rect_area = 0
    bin_area = Bin[0]*Bin[1]
    for id in RPNXY:
      width,height = AllItem[id[0]]
      rect_area += width*height
    print('占用率:{}'.format(rect_area/bin_area))
    

    占用率:0.81

    可视化装箱后的结果

    import matplotlib.pyplot as plt
    import matplotlib.patches as patches
    import random
    fig, ax = plt.subplots(1, 1)
    ax1 = fig.gca()
    for i in RPNXY:
        width,height = AllItem[i[0]]
        rx,ry = i[1],i[2]
        lx,ly = rx-width,ry-height
        plt.xlim((0, Bin[0]))
        plt.ylim((0, Bin[1]))
        color = "#"+''.join([random.choice('0123456789ABCDEF') for j in range(6)])
        rect = patches.Rectangle((lx, ly), width,height,linewidth=1, facecolor = color)
        ax1.add_patch(rect)
    plt.show()
    

    在这里插入图片描述

    3.2 overlap函数

    判断物品item在当前位置itemRP与箱子中其他物品是否有重合,如果有重合FlagOL=1,反之FlagOL=0。

    # 输入item:   物品[宽度,高度]
    # 输入Item:   各个物品[宽度,高度]
    # 输入itemRP: 此时物品右上角顶点坐标[x,y]
    # 输入RPNXY:  当前箱子中所有物品右上角顶点坐标数组
    # 输出flagOL: 如果重合flagOL=1;反之flagOL=0
    def overlap(item,Item,itemRP,RPNXY):
        flagOL=0  # 初始化不存在重合情况
        itemLBP=[itemRP[0]-item[0],itemRP[1]-item[1]] #左下角顶点坐标
        A = Rectangle(itemLBP[0],itemLBP[1],item[0],item[1])
        num=len(RPNXY) # 箱子中物品数目
        if num>0:
            for i in range(num):
                width=Item[RPNXY[i][0],0]  #Item(RPNXY(i,1),:)宽度
                height=Item[RPNXY[i][0],1]  #Item(RPNXY(i,1),:)高度
                LBPXY=[RPNXY[i][1]-width,RPNXY[i][2]-height]  #在箱子中的当前矩形Item(RPNXY(i,1),:)的左下角顶点坐标
                B = Rectangle(LBPXY[0],LBPXY[1],width,height)
                area=rectint(A,B)#计算物品A与B相交的面积
                #如果AB相交,则满足下列关系
                if area>0:
                    flagOL=1
                    break
        return flagOL
    

    3.3 finalPos函数

    计算一个新的矩形从当前位置向下向左移动后到最终位置后右上角顶点坐标

    # 输入item:   物品[宽度,高度]
    # 输入Item:   各个物品[宽度,高度]
    # 输入itemRP: 此时物品右上角顶点坐标[x,y]
    # 输入RPNXY:  当前箱子中所有物品右上角顶点坐标数组
    # 输出finalRP:物品item在箱子内任意位置向下向左移动后到最终位置后右上角顶点坐标
    def finalPos(item,Item,itemRP,RPNXY):
        # 当物品item不能再继续下降或不能继续左移的时候,跳出循环
        while 1:
            downH=downHAtPoint(item,Item,itemRP,RPNXY) #计算物品item在箱子内itemRP位置处可以下降的最大高度
            leftW=0
            itemRP=Update_itemRP(itemRP,downH,leftW) #更新物品item当前位置右上角顶点坐标
            downH=0
            leftW=leftWAtPoint(item,Item,itemRP,RPNXY) #计算物品item在箱子内itemRP位置处可以向左移动的最大距离
            itemRP=Update_itemRP(itemRP,downH,leftW) #更新物品item当前位置右上角顶点坐标
            if (downH==0)and (leftW==0):
                finalRP=itemRP
                break
        return finalRP
    

    3.4 downHAtPoint函数

    使用downHAtPoint()函数可以计算在当前箱子中,矩形在当前位置可以下降的最大高度。

    # 计算在当前箱子中,物品item在箱子内任意位置可以下降的最大高度
    # 输入item:   物品[宽度,高度]
    # 输入AllItem:   各个物品[宽度,高度]
    # 输入itemRP: 此时物品右上角顶点坐标[x,y]
    # 输入RPNXY:  当前箱子中所有物品右上角顶点坐标数组
    # 输出downH:  物品item在箱子内任意位置可以下降的最大高度(如果能装入当前箱子,则downH为正数;如果不能装入当前箱子,则为负数)
    def downHAtPoint(item,AllItem,itemRP,RPNXY):
        bottomLine=Point_Horizontal_Line(item,itemRP)  #物品下端水平线段左右两端坐标[leftx,lefty,rightx,righty]
        RP_NUM=len(RPNXY) #箱子内物品数目
        if RP_NUM!=0:
            sRPNXY=np.array(sorted(list(RPNXY), key=lambda x:x[2],reverse=True))#将RPNXY按照Y坐标降序排列
            sRBPNXY=sRPNXY.copy()
            sRBPNXY[:,1]=sRPNXY[:,1]-AllItem[sRPNXY[:,0],0]  #将RPNXY按照Y坐标降序排列后的左上角顶点坐标
            
            topLine=np.concatenate((sRBPNXY[:,1:3],sRPNXY[:,1:3]),axis=1)  #物品按照Y坐标降序排列后,物品上端水平线段左右两端坐标[leftx,lefty,rightx,righty]
            # 逐个遍历sRPNXY中的物品
            alldownH=[]  # 储存所有满足相交条件的下降距离
            for i in range(RP_NUM):
                #判断两条水平线段经过竖直移动后是否会相交,flag=1相交,flag=0不相交
                #两条水平线段距离是多少,如果竖直移动后相交,HD为正数,反之为负数
                flag,HD=Horizontal_Lines_Intersect(bottomLine,topLine[i,:])
                if (flag==1) and (HD>=0):
                    alldownH.append(HD)
            # 如果不存在满足相交条件的物品,则直接下降到箱子最底端
            if len(alldownH)==0:
                downH=itemRP[1]-item[1]
            else:  # 如果存在满足相交条件的物品,则下降距离为alldownH中的最小值
                downH=min(alldownH)
        else:
            downH=itemRP[1]-item[1]  #此时箱子没有物品,物品直接下降到箱子底端
        return downH
    

    3.5 Update_itemRP函数

    计算物品在箱子中从右上角下降downH又向左移动leftW后,右上角顶点的坐标

    # 输入itemRP: 此时物品右上角顶点坐标[x,y]
    # 输入downH:  物品item从右上角可以下降的最大高度
    # 输入leftW:  物品item从右上角下降最大高度以后,可以向左移动的最大距离
    # 输出itRPXY: 物品item在箱子中下降downH又向左移动leftW后,右上角顶点的坐标
    def Update_itemRP(itemRP,downH,leftW):
        h=itemRP[1]-downH  #y坐标
        w=itemRP[0]-leftW   #x坐标
        return [w,h]
    

    3.6 leftWAtPoint函数

    计算在当前箱子中,物品item在箱子内任意位置可以向左移动的最大距离

    # 输入item:   物品[宽度,高度]
    # 输入Item:   各个物品[宽度,高度]
    # 输入itemRP: 此时物品右上角顶点坐标[x,y]
    # 输入RPNXY:  当前箱子中所有物品右上角顶点坐标数组
    # 输出leftW:  物品item在箱子内任意位置可以向左移动的最大距离
    def leftWAtPoint(item,Item,itemRP,RPNXY):
        leftLine=Point_Vertical_Line(item,itemRP)  #物品左端竖直线段上下两端坐标[topx,topy,bottomx,bottomy]
        RP_NUM=len(RPNXY)#箱子内物品数目
        if RP_NUM!=0:
            sRPNXY=np.array(sorted(list(RPNXY), key=lambda x:x[0]))  #将RPNXY按照X坐标降序排列
            sRBPNXY=sRPNXY.copy()
            sRBPNXY[:,2]=sRPNXY[:,2]-Item[sRPNXY[:,0],1] #将RPNXY按照X坐标降序排列后的右下角顶点坐标
            rightLine=np.concatenate((sRPNXY[:,1:3],sRBPNXY[:,1:3]),axis=1)#物品按照X坐标降序排列后,右端线段上下两端坐标[topx,topy,bottomx,bottomy]
            #逐个遍历sRPNXY中的物品
            allLeftW=[]  #储存所有满足相交条件的左移距离
            for i in range(RP_NUM):
                #判断两条竖直线经过水平移动后是否会相交,flag=1相交,flag=0不相交
                #两条竖直线段距离是多少,如果平移动后相交,HD为正数,反之为负数
                flag,HD=Vertical_Lines_Intersect(leftLine,rightLine[i,:])
                if (flag==1) and (HD>=0):
                    allLeftW.append(HD)
            # 如果不存在满足相交条件的物品,则直接移动箱子最左端
            if len(allLeftW)==0:
                leftW=itemRP[0]-item[0]
            else: #如果存在满足相交条件的物品,则左移距离为allLeftW中的最小值
                leftW=min(allLeftW)
        else:
            leftW=itemRP[0]-item[0]
        return leftW
    

    3.7 其他小功能的函数

    from matplotlib.pyplot import axis
    import numpy as np
    # 矩形类,[x,y,width,height]左下角坐标、长和宽
    class Rectangle:
        def __init__(self, x, y,w,h):
          self.x = x
          self.y = y
          self.width = w
          self.height = h
          
    def Horizontal_Lines_Intersect(line1,line2):
        # 判断两条水平线段经过竖直移动后是否会相交,如果相交,计算两条水平线段竖直距离是多少
        # 思路:分5种情况:1)左方不相交;2)左方相交;3)右方相交;4)右方不相交;5)line1完全包含line2
        # 输入line1:  第一条线段[x1,y1,x2,y2]
        # 输入line2:  第二条线段[x1,y1,x2,y2]
        # 输出flag:  判断两条水平线段经过竖直移动后是否会相交,flag=1相交,flag=0不相交
        # 输出HD:  两条竖直线段距离是多少,如果平移动后相交,HD为正数,反之为负数
        #第一种情况,line1完全在line2左方,即line1右端顶点x坐标小于等于line2左端顶点x坐标,且两条线段经过竖直移动后不会相交
        if line1[2]<=line2[0]:
            flag=0
            HD=line1[1]-line2[1]
        #第二种情况,line1在line2左方,即line1右端顶点x坐标大于line2左端顶点x坐标且小于等于且line2右端顶点x坐标,但两条线段经过竖直移动后会相交
        elif (line1[2]>line2[0]) and (line1[2]<=line2[0]):
            flag=1
            HD=line1[1]-line2[1]
        #第三种情况,line1在line2右方,即line1左端顶点x坐标大于等于line2左端顶点x坐标且小于且line2右端顶点x坐标,但两条线段经过竖直移动后会相交
        elif (line1[0]>=line2[0]) and (line1[0]<line2[2]):
            flag=1
            HD=line1[1]-line2[1]
        #第四种情况,line1完全在line2右方,即line1左端顶点x坐标大于等于line2右端顶点x坐标,且两条线段经过竖直移动后不会相交
        elif line1[0]>=line2[2]:
            flag=0
            HD=line1[1]-line2[1]
        #第五种情况,line1完全包含line2,即line1左端顶点x坐标小于等于line2左端顶点x坐标,
        #line1右端顶点x坐标大于等于line2右端顶点x坐标,且两条线段经过竖直移动后会相交
        else:
            flag=1
            HD=line1[1]-line2[1]
        return flag,HD
      
    # 根据物品右上角顶点坐标和物品宽度和高度,求出物品下端水平线段左右两端坐标[leftx,lefty,rightx,righty]
    # 输入item:  物品[宽度,高度]
    # 输入RPXY:物品右上角顶点坐标[x,y]
    # 输出leftLine:  物品下端水平线段左右两端坐标[leftx,lefty,rightx,righty]
    def Point_Horizontal_Line(item,RPXY):
        。。。
        return bottomLine
     
    # 判断两条竖直线段经过水平移动后是否会相交,如果相交,计算两条竖直线段水平距离是多少
    # 思路:分5种情况:1)上方不相交;2)上方相交;3)下方相交;4)下方不相交;5)line1完全包含line2
    # 输入line1:  第一条线段[topx,topy,bottomx,bottomy]
    # 输入line2:  第二条线段[topx,topy,bottomx,bottomy]
    # 输出flag:  判断两条竖直线经过水平移动后是否会相交,flag=1相交,flag=0不相交
    # 输出HD:  两条竖直线段距离是多少,如果平移动后相交,HD为正数,反之为负数
    def Vertical_Lines_Intersect(line1,line2):
        # 第一种情况,line1完全在line2上方,且两条线段经过平移后不会相交
        if line1[3]>=line2[1]:
            flag=0
            HD=line1[0]-line2[0]
        # 第二种情况,line1在line2上方,但两条线段经过平移后会相交
        elif (line1[3]<line2[1])and (line1[3]>=line2[3]):
            flag=1
            HD=line1[0]-line2[0]
        # 第三种情况,line1在line2下方,但两条线段经过平移后会相交
        elif (line1[1]<=line2[1]) and (line1[1]>line2[3]):
            flag=1
            HD=line1[0]-line2[0]
        # 第四种情况,line1完全在line2下方,且两条线段经过平移后不会相交
        elif line1[1]<=line2[3]:
            flag=0
            HD=line1[0]-line2[0]
        else:
            flag=1
            HD=line1[0]-line2[0]
        return flag,HD
     
    # 根据物品右上角顶点坐标和物品宽度和高度,求出物品左端竖直线段上下两端坐标[topx,topy,bottomx,bottomy]
    # 输入item:  物品[宽度,高度]
    # 输入RPXY:物品右上角顶点坐标[x,y]
    # 输出leftLine:  物品左端竖直线段上下两端坐标[topx,topy,bottomx,bottomy]
    def Point_Vertical_Line(item,RPXY):
      。。。
        
    

    在这里插入图片描述

    # 计算两个矩形相交的面积,和MATLAB中rectint函数作用一样
    def rectint(rect1, rect2):
        xl1, yb1, xr1, yt1 = rect1.x,rect1.y,rect1.x+rect1.width,rect1.y+rect1.height # (xl1, yb1)为矩形左下角坐标, (xr1, yt1)为右上角坐标
        xl2, yb2, xr2, yt2 = rect2.x,rect2.y,rect2.x+rect2.width,rect2.y+rect2.height # (xl2, yb2)为矩形左下角坐标, (xr2, yt2)为右上角坐标
        xmin = max(xl1, xl2)
        ymin = max(yb1, yb2)
        xmax = min(xr1, xr2)
        ymax = min(yt1, yt2)
        width = xmax - xmin
        height = ymax - ymin
        if width <= 0 or height <= 0:
            return 0
        cross_square = width * height
        return cross_square
    

    4 缺点及改进

    装箱顺序会影响占用率。比如会存在如下所示的装箱方案,物品4应该放置到物品2的上面。可以通过调整装箱顺序,让4和2调换一下装箱顺序,就可以达到更好的效果。

    当矩阵数量庞大的时候,可以采用优化算法,来搜索最佳的排列组合,达到最大占用率。比如以人工蜂群算法实现。
    在这里插入图片描述

    import numpy as np
    import random, math, copy
    import matplotlib.pyplot as plt
    from tools import *
    import random
     
    
    def fitness(Bin,AllItem,ran):
        # ran 是装箱顺序
        itemNum=AllItem.shape[0] #物品数目
        RPNXY=[];
        flagItem=np.zeros(itemNum) #标记物品是否被装入箱子,0没有装入,1装入
        # 开始装箱
    
        for i in range(itemNum):
            if flagItem[ran[i]]==0:
                item=AllItem[ran[i],:]
                itemRP=Bin  #起点全部在箱子右上角顶点
                flagOL=overlap(item,AllItem,itemRP,RPNXY) #如果重合flagOL=1;反之flagOL=0
                if flagOL==0:
                    itemRP=finalPos(item,AllItem,itemRP,RPNXY) #更新物品从当前位置向下向左移动后到最终位置后右上角顶点坐标
                    if len(itemRP)>0:
                        RPNXY.append([ran[i],itemRP[0],itemRP[1]])
                        flagItem[ran[i]]=1
        rect_area = 0
        bin_area = Bin[0]*Bin[1]
        for id in RPNXY:
            width,height = AllItem[id[0]]
            rect_area += width*height
        score = rect_area/bin_area
        print('利用率:{}'.format(score))
        return score
     
    class ABSIndividual:
        def __init__(self,bin,item):
            self.score = 0.
            self.invalidCount = 0                      #无效次数(成绩没有更新的累积次数)
            self.bin = bin  #箱子宽度与高度
            self.allitem = item
            self.ran =  list(range(self.allitem.shape[0]))# 装箱顺序
            self.calculateFitness()        
     
        def calculateFitness(self):
            self.score = fitness(self.bin,self.allitem,self.ran)          #计算当前成绩
            
    class ArtificialBeeSwarm:
        def __init__(self, foodCount, onlookerCount,Bin, item, maxIterCount=1000, maxInvalidCount=200):
            self.foodCount = foodCount                  #蜜源个数,等同于雇佣蜂数目
            self.onlookerCount = onlookerCount          #观察蜂个数 
            self.item = item                          #各参数上下界
            self.maxIterCount = maxIterCount            #迭代次数
            self.maxInvalidCount = maxInvalidCount      #最大无效次数
            self.Bin = Bin
            self.foodList = [ABSIndividual(self.Bin,self.item) for k in range(self.foodCount)]   #初始化各蜜源
            self.foodScore = [d.score for d in self.foodList]                             #各蜜源最佳成绩
            self.bestFood = self.foodList[np.argmax(self.foodScore)]                      #全局最佳蜜源
     
        def updateFood(self, i):                                                  #更新第i个蜜源
            vi = copy.deepcopy(self.foodList[i])
            order =list(range(vi.allitem.shape[0]))
            random.shuffle(order) #随机生成装箱序列
            vi.ran = order
            vi.calculateFitness()
            if vi.score > self.foodList[i].score:           #如果成绩比当前蜜源好
                self.foodList[i] = vi
                if vi.score > self.foodScore[i]:            #如果成绩比历史成绩好(如重新初始化,当前成绩可能低于历史成绩)
                    self.foodScore[i] = vi.score
                    if vi.score > self.bestFood.score:      #如果成绩全局最优
                        self.bestFood = vi
                self.foodList[i].invalidCount = 0
            else:
                self.foodList[i].invalidCount += 1
                
        def employedBeePhase(self):
            for i in range(0, self.foodCount):              #各蜜源依次更新
                self.updateFood(i)            
     
        def onlookerBeePhase(self):
            foodScore = [d.score for d in self.foodList]  
            maxScore = np.max(foodScore)        
            accuFitness = [(0.9*d/maxScore+0.1, k) for k,d in enumerate(foodScore)]        #得到各蜜源的 相对分数和索引号
            for k in range(0, self.onlookerCount):
                i = random.choice([d[1] for d in accuFitness if d[0] >= random.random()])  #随机从相对分数大于随机门限的蜜源中选择跟随
                self.updateFood(i)
     
        def scoutBeePhase(self):
            for i in range(0, self.foodCount):
                if self.foodList[i].invalidCount > self.maxInvalidCount:                    #如果该蜜源没有更新的次数超过指定门限,则重新初始化
                    self.foodList[i] = ABSIndividual(self.bound)
                    self.foodScore[i] = max(self.foodScore[i], self.foodList[i].score)
     
        def solve(self):
            trace = []
            trace.append((self.bestFood.score, np.mean(self.foodScore)))
            for k in range(self.maxIterCount):
                self.employedBeePhase()
                self.onlookerBeePhase()
                self.scoutBeePhase()
                trace.append((self.bestFood.score, np.mean(self.foodScore)))
            print(self.bestFood.score)
            self.printResult(np.array(trace))
     
        def printResult(self, trace):
            x = np.arange(0, trace.shape[0])
            plt.plot(x, [(1-d)/d for d in trace[:, 0]], 'r', label='optimal value')
            plt.plot(x, [(1-d)/d for d in trace[:, 1]], 'g', label='average value')
            plt.xlabel("Iteration")
            plt.ylabel("function value")
            plt.title("Artificial Bee Swarm algorithm for function optimization")
            plt.legend()
            plt.show()
     
    if __name__ == "__main__":
        random.seed()
        itemNum = 1000
        AllItem=np.array([[random.randint(1, 5) for j in range(1, 3)] for i in range(1,itemNum+1)])  #随机生成30个物品,[width,height]
        Bin=[100,100] #箱子宽度与高度
        iternum = 100 # 迭代次数
        maxInvalidCount = 50
        abs = ArtificialBeeSwarm(30, 30, Bin,AllItem, iternum, maxInvalidCount)
        abs.solve()
        print()
    

    5 完整代码下载

    https://github.com/BetterBench/BetterBench-Shop

    展开全文
  • 一种新的集装箱问题算法,适用二维
  • 题目描述一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,...他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。输入输入文件包括几行,每一...
  • This project originates from my bachelor thesis in computer science at the University of Paderborn. It deals with a library for two dimensional packing problems (which arise for example in leather cut...
  • 简称2DRP)以及在此基础上拓展的二维装箱问题(2D strip packing problem,简称2DSP),以及由____数据魔术师团队____提出的解决该问题的一钟启发式算法。 这次介绍的算法运用了启发式算法**禁忌搜索算法(Tabu ...
  • 二维下料matlab bl算法,bl.mat是主函数,可以直接运行
  • 2维装箱问题基于遗传算法求解二维装箱问题。。。。
  • 求解二维装箱问题的强化学习启发式算法.pdf
  • 简单的二维装箱代码

    热门讨论 2012-08-01 23:51:31
    简单实现了二维装箱问题。不过仅仅是简单实现,排列7、8个矩形没问题,超过10个就要花N久了。。
  • 之前我已经写过一篇禁忌搜索算法求解二维矩形装箱问题(java代码实现),如果有对二维矩形装箱问题的背景不是很了解的朋友可以去看看 2 代码迁移 项目的大体框架(一些实体类,数据读取类等)和禁忌搜索算法求解二维...
  • Matlab 三维装箱遗传算法实现

    千次阅读 2022-01-29 22:26:24
    % 使用遗传算法得到最大装载方式 % 定义初始种群为100个 % 交叉方式为两两交叉组合,分裂概率为0.7 % 变异方式为随机变异,变异概率为0.3 % 然后进行选择 选择前面最优的100个 rateCom=0.7;%结合概率 rateAbe=0
  • 利用混合单新遗传算法求解二维装箱问题.pdf
  • 这里的装箱问题和我们在算法上归纳的装箱问题不是一个概念!也就是不同于下面这篇博客里的装箱问题。 【C++】2018华为软挑:模拟退火+贪心FF解决装箱问题_玛丽莲茼蒿的博客-CSDN博客本文的主要工作是补充这篇博客的...
  • 基于三维装箱问题算法研究-1 的基础上,对整个装箱过程发生的函数进行简单封装
  • 改进了FFA算法,提出了区间合并和最小浪费面积的概念,并阐述了实现的方法.最后,采用基于改进的FFA算法的混合遗传算法得到了较好的结果,并对结果进行了分析.
  • 求解二维矩形装箱问题算法研究.pdf
  • 二维矩形装箱算法之二叉树

    万次阅读 2018-03-21 15:28:29
    如何将所有二维矩形块放入一个矩形框内。2.在满足问题1的情况下,矩形框的最小宽度和高度是多少。期望的效果图: 下面我们就来解决以上问题。1. 把矩形块放在固定大小的框内假设有一个固定大小的矩形框,比如1024...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,801
精华内容 1,520
关键字:

二维装箱问题算法

友情链接: 车发送数据.rar