宁德东侨建设局网站,长沙网站定制,com域名注册优惠,传奇网站模块下载文章目录一、带顺序约束的二维矩形装箱问题二、剩余空间法三、完整代码实现3.1 Instance 实例类3.2 Item 物品类3.3 PlaceItem 已放置物品类3.4 Solution 结果类3.5 RSPackingWithWeight 剩余空间算法类3.6 Run 运行类3.7 测试案例3.8 ReadDataUtil 数据读取类3.9 运行结果展示…
文章目录一、带顺序约束的二维矩形装箱问题二、剩余空间法三、完整代码实现3.1 Instance 实例类3.2 Item 物品类3.3 PlaceItem 已放置物品类3.4 Solution 结果类3.5 RSPackingWithWeight 剩余空间算法类3.6 Run 运行类3.7 测试案例3.8 ReadDataUtil 数据读取类3.9 运行结果展示一、带顺序约束的二维矩形装箱问题
常规的二维矩形装箱问题只要求利用率尽可能大就可以了但是在现实场景中由于订单顺序等缘故有一些物品需要优先于其他物品进行装载这就诞生了本文要解决的“带顺序约束的二维矩形装箱问题”。
带顺序约束的二维矩形装箱问题给定每个物品一定的权重要求按照权重从大到小的顺序进行装载。这个问题用天际线算法也能解决但是效果很差如下图所示 所以就引出了本文的主角剩余空间法。经过测试剩余空间法的求解效果在带顺序约束的二维矩形装箱问题上可能优于天际线启发式算法。下面是剩余空间法排出的结果 想了解天际线启发式的朋友可以参考(【运筹优化】基于堆优化的天际线启发式算法和复杂的评分策略求解二维矩形装箱问题 Java代码实现) 二、剩余空间法
剩余空间法思路很简单每放入一个矩形就把空间按照下图的方式切成两部分剩余空间。最开始剩余空间就是整个容器。每次放置矩形找到最合适的剩余空间放就行了。
那么什么是最适合的剩余空间呢这就涉及到评价规则了。 常见的评价规则有下面三种
return itemW / remainingSpace.w; // 规则1矩形宽度和剩余空间宽度越接近分越高
return itemH / remainingSpace.h; // 规则2矩形高度和剩余空间高度越接近分越高
return (itemW*itemH) / (remainingSpace.w*remainingSpace.h); // 规则3矩形面积和剩余空间面积越接近分越高三、完整代码实现
3.1 Instance 实例类
public class Instance {// 边界的宽private double W;// 边界的高private double H;// 矩形列表private ListItem 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 ListItem getItemList() {return itemList;}public void setItemList(ListItem itemList) {this.itemList itemList;}public boolean isRotateEnable() {return isRotateEnable;}public void setRotateEnable(boolean rotateEnable) {isRotateEnable rotateEnable;}
}3.2 Item 物品类
public class Item {// 名字private String name;// 宽private double w;// 高private double h;// 权重private double weight;// 构造函数public Item(String name, double w, double h,double weight) {this.name name;this.w w;this.h h;this.weight weight;}// 复制单个Itempublic static Item copy(Item item) {return new Item(item.name, item.w, item.h,item.weight);}// 复制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 ListItem copy(ListItem items) {ListItem 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;}public double getWeight() {return weight;}public void setWeight(double weight) {this.weight weight;}
}3.3 PlaceItem 已放置物品类
public class PlaceItem {// 名字private String name;// x坐标private double x;// y坐标private double y;// 宽考虑旋转后的private double w;// 高考虑旋转后的private double h;// 是否旋转private boolean isRotate;// 权重private double weight;// 构造函数public PlaceItem(String name, double x, double y, double w, double h, boolean isRotate,double weight) {this.name name;this.x x;this.y y;this.w w;this.h h;this.isRotate isRotate;this.weight weight;}Overridepublic String toString() {return PlaceItem{ name name \ , x x , y y , w w , h h , isRotate isRotate , weight weight };}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;}public double getWeight() {return weight;}public void setWeight(double weight) {this.weight weight;}
}3.4 Solution 结果类
public class Solution {// 已放置矩形private ListPlaceItem placeItemList;// 放置总面积private double totalS;// 利用率private double rate;// 构造函数public Solution(ListPlaceItem placeItemList, double totalS, double rate) {this.placeItemList placeItemList;this.totalS totalS;this.rate rate;}public ListPlaceItem getPlaceItemList() {return placeItemList;}public void setPlaceItemList(ListPlaceItem 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;}
}3.5 RSPackingWithWeight 剩余空间算法类
public class RSPackingWithWeight {// 边界的宽private double W;// 边界的高private double H;// 矩形数组private Item[] items;// 是否可以旋转private boolean isRotateEnable;/*** param isRotateEnable 是否允许矩形旋转* param W 边界宽度* param H 边界高度* param items 矩形集合* Description 构造函数*/public RSPackingWithWeight(boolean isRotateEnable, double W, double H, Item[] items) {this.isRotateEnable isRotateEnable;this.W W;this.H H;this.items Item.copy(items);// 按权重排序Arrays.sort(this.items, new ComparatorItem() {Overridepublic int compare(Item o1, Item o2) {return -Double.compare(o1.getWeight(), o2.getWeight());}});}/*** return 放置好的矩形列表* Description 天际线启发式装箱主函数*/public Solution packing() {// 用来存储已经放置的矩形ListPlaceItem placeItemList new ArrayList();// 用来记录已经放置矩形的总面积double totalS 0d;// 剩余空间列表 [xywh]ListRemainingSpace remainingSpaceList new ArrayList();// 初始剩余空间就是整个容器remainingSpaceList.add(new RemainingSpace(0, 0, W, H));// 按照顺序放置矩形for (int i 0; i items.length; i) {double maxScore -1;int bestRemainingSpaceIndex -1;boolean bestRotate false;// 找到第一个没有被放置的权重最大的矩形i// 遍历所有剩余空间不旋转for (int j 0; j remainingSpaceList.size(); j) {double score score(items[i].getW(), items[i].getH(), remainingSpaceList.get(j));if (compareDouble(maxScore, score) -1) {maxScore score;bestRemainingSpaceIndex j;}}// 遍历所有剩余空间旋转if (isRotateEnable) {for (int j 0; j remainingSpaceList.size(); j) {double score score(items[i].getH(), items[i].getW(), remainingSpaceList.get(j));if (compareDouble(maxScore, score) -1) {maxScore score;bestRemainingSpaceIndex j;bestRotate true;}}}// 装载if (bestRemainingSpaceIndex 0) {RemainingSpace remainingSpace remainingSpaceList.remove(bestRemainingSpaceIndex);PlaceItem placeItem;if (bestRotate) {// 旋转placeItem new PlaceItem(items[i].getName(), remainingSpace.x, remainingSpace.y, items[i].getH(), items[i].getW(), true, items[i].getWeight());} else {// 不旋转placeItem new PlaceItem(items[i].getName(), remainingSpace.x, remainingSpace.y, items[i].getW(), items[i].getH(), false, items[i].getWeight());}placeItemList.add(placeItem);totalS (placeItem.getW() * placeItem.getH());remainingSpaceList.add(new RemainingSpace(remainingSpace.x, remainingSpace.y placeItem.getH(), placeItem.getW(), remainingSpace.h - placeItem.getH()));remainingSpaceList.add(new RemainingSpace(remainingSpace.x placeItem.getW(), remainingSpace.y, remainingSpace.w - placeItem.getW(), remainingSpace.h));}}// 输出for (int i 0; i placeItemList.size(); i) {System.out.println(第 (i 1) 个矩形为: placeItemList.get(i));}// 返回求解结果return new Solution(placeItemList, totalS, totalS / (W * H));}// 评分函数评价矩形放在剩余空间里的分数private double score(double itemW, double itemH, RemainingSpace remainingSpace) {if (compareDouble(remainingSpace.w, itemW) -1 || compareDouble(remainingSpace.h, itemH) -1) {// 超出剩余空间返回-1分return -1;}// 评分规则return itemW / remainingSpace.w; // 规则1矩形宽度和剩余空间宽度越接近分越高
// return itemH / remainingSpace.h; // 规则2矩形高度和剩余空间高度越接近分越高
// return (itemW*itemH) / (remainingSpace.w*remainingSpace.h); // 规则3矩形面积和剩余空间面积越接近分越高}/*** param d1 双精度浮点型变量1* param d2 双精度浮点型变量2* return 返回0代表两个数相等返回1代表前者大于后者返回-1代表前者小于后者* Description 判断两个双精度浮点型变量的大小关系*/private int compareDouble(double d1, double d2) {// 定义一个误差范围如果两个数相差小于这个误差则认为他们是相等的 1e-06 0.000001double 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);}}static class RemainingSpace {double x, y, w, h;public RemainingSpace(double x, double y, double w, double h) {this.x x;this.y y;this.w w;this.h h;}}}3.6 Run 运行类
public class Run extends javafx.application.Application {private int counter 0;Overridepublic void start(Stage primaryStage) throws Exception {// 数据地址String path src/main/java/com/wskh/data/data_weight.txt;// 根据txt文件获取实例对象Instance instance new ReadDataUtil().getInstance(path);// 记录算法开始时间long startTime System.currentTimeMillis();// 实例化剩余空间法对象RSPackingWithWeight rsPackingWithWeight new RSPackingWithWeight(instance.isRotateEnable(), instance.getW(), instance.getH(), instance.getItemList().toArray(new Item[0]));// 调用算法进行求解Solution solution rsPackingWithWeight.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 EventHandlerActionEvent() {Overridepublic 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);}}3.7 测试案例
270,28,0,
1,82.3,10.4,0.54
2,123.5,20.62,0.25
3,80.4,16.2,0.42
4,74,13.41,0.81
5,105.6,11.6,0.19
6,62.1,10.1,0.67
7,43.2,8,0.93
8,39.8,11.25,0.73
9,50,12,0.3
10,75,8.6,0.89
11,129.92,16.24,0.08
12,90.8,14.9,0.163.8 ReadDataUtil 数据读取类
public class ReadDataUtil {public Instance getInstance(String path) throws IOException {BufferedReader bufferedReader new BufferedReader(new FileReader(path));String input null;Instance instance new Instance();ListItem 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(split[0], Double.parseDouble(split[1]), Double.parseDouble(split[2]), Double.parseDouble(split[3])));}}instance.setItemList(itemList);return instance;}
}3.9 运行结果展示 第1个矩形为: PlaceItem{name7, x0.0, y0.0, w43.2, h8.0, isRotatefalse, weight0.93}
第2个矩形为: PlaceItem{name10, x43.2, y0.0, w75.0, h8.6, isRotatefalse, weight0.89}
第3个矩形为: PlaceItem{name4, x43.2, y8.6, w74.0, h13.41, isRotatefalse, weight0.81}
第4个矩形为: PlaceItem{name8, x0.0, y8.0, w39.8, h11.25, isRotatefalse, weight0.73}
第5个矩形为: PlaceItem{name6, x118.2, y0.0, w62.1, h10.1, isRotatefalse, weight0.67}
第6个矩形为: PlaceItem{name1, x180.3, y0.0, w82.3, h10.4, isRotatefalse, weight0.54}
第7个矩形为: PlaceItem{name3, x180.3, y10.4, w80.4, h16.2, isRotatefalse, weight0.42}
第8个矩形为: PlaceItem{name9, x118.2, y10.1, w50.0, h12.0, isRotatefalse, weight0.3}
求解用时:0.002 s
共放置了矩形8个
利用率为:0.7693518518518518
data:[{x:0.0,y:0.0,l:8.0,w:43.2}, {x:43.2,y:0.0,l:8.6,w:75.0}, {x:43.2,y:8.6,l:13.41,w:74.0}, {x:0.0,y:8.0,l:11.25,w:39.8}, {x:118.2,y:0.0,l:10.1,w:62.1}, {x:180.3,y:0.0,l:10.4,w:82.3}, {x:180.3,y:10.4,l:16.2,w:80.4}, {x:118.2,y:10.1,l:12.0,w:50.0}],
isRotate:[0, 0, 0, 0, 0, 0, 0, 0],
