精华内容
下载资源
问答
  • 二维装箱问题的非线性优化方法
  • 二维装箱问题是具有广泛应用背景的一类组合优化问题 ,这类问题是 NP难问题 ,很难得到精确解 。将二维装箱问题表示为一个非线性规划模型 ,用变分分析中切锥的概念建立了这一优化问题的一阶最优性条件 。给出了求解这...
  • 二维装箱问题顾名思义就是将若干个矩形物品装进矩形箱子中,并且在装箱的过程中不允许将矩形物品斜着放(PS:下图就是不允许的装箱操作),同时在装箱过程中允许将物品旋转90度放置(但是为了简单地求解问题,我们...

    01 | 问题导入

    二维装箱问题顾名思义就是将若干个矩形物品装进矩形箱子中,并且在装箱的过程中不允许将矩形物品斜着放(PS:下图就是不允许的装箱操作),同时在装箱过程中允许将物品旋转90度放置(但是为了简单地求解问题,我们规定不允许将物品旋转90度),一般来说求解的目标是最小化箱子的使用数目。

     

    02 | 算法描述

    BL法全称是bottom-up left-justified,通俗点来说将一个要装箱的物品1先紧靠在箱子的右上角,如下图所示。

    展开全文
  • 一种二维装箱问题的建模方法

    千次阅读 2020-08-27 15:06:18
    模型参数 参数 说明 I I I 物件的集合 W W W 箱子的宽度 H H H 箱子的高度 w i w_i wi​ 物件 i i i 的长边 h i h_i hi​ 物件 i i i 的短边 决策变量 变量 类型 说明 p i p_i pi​ 0-1 物件 i i i 是否被装箱 x i x...

    模型参数


    参数说明
    I I I物件的集合
    W W W箱子的宽度
    H H H箱子的高度
    w i w_i wi物件 i i i 的长边
    h i h_i hi物件 i i i 的短边

    决策变量


    变量类型说明
    p i p_i pi0-1物件 i i i 是否被装箱
    x i x_i xi R + 0 R^0_+ R+0物件 i i i 的左下角顶点的横坐标
    y i y_i yi R + 0 R^0_+ R+0物件 i i i 的左下角顶点的纵坐标
    m i 1 m^1_i mi10-1物件 i i i 是否为长边沿横轴的放置方式
    m i 2 m^2_i mi20-1物件 i i i 是否为长边沿纵轴的放置方式
    l i , j l_{i, j} li,j0-1物件 i i i 是否位于物件 j j j 的左侧
    b i , j b_{i, j} bi,j0-1物件 i i i 是否位于物件 j j j 的下方

    约束条件


    (1) 左下角顶点的坐标范围:
    (1a) 横坐标:
    x i ≤ W − ( m i 1 ⋅ w i + m i 2 ⋅ h i ) ∀ i ∈ I x_i \leq W - (m^1_i \cdot w_i + m^2_i \cdot h_i) \quad \forall i \in I xiW(mi1wi+mi2hi)iI

    (1b) 纵坐标:
    y i ≤ H − ( m i 1 ⋅ h i + m i 2 ⋅ w i ) ∀ i ∈ I y_i \leq H - (m^1_i \cdot h_i + m^2_i \cdot w_i) \quad \forall i \in I yiH(mi1hi+mi2wi)iI

    (2) 放置方式:
    m i 1 + m j 2 = 1 ∀ i ∈ I m^1_i + m^2_j = 1 \quad \forall i \in I mi1+mj2=1iI

    (3) 位置关系:
    l i , j + l j , i + b i , j + b j , i + ( 2 − p i − p j ) ≥ 1 ∀ i ∈ I ∀ j ∈ I i ≠ j l_{i, j} + l_{j, i} + b_{i, j} + b_{j, i} + (2 - p_i - p_j) \geq 1 \quad \forall i \in I \quad \forall j \in I \quad i \neq j li,j+lj,i+bi,j+bj,i+(2pipj)1iIjIi=j

    (4) 坐标关系:
    (4a) 横坐标:
    x i − x j + W ⋅ l i , j ≤ W − ( m i 1 ⋅ w i + m i 2 ⋅ h i ) ∀ i ∈ I ∀ j ∈ I i ≠ j x_i - x_j + W \cdot l_{i, j} \leq W - (m^1_i \cdot w_i + m^2_i \cdot h_i) \quad \forall i \in I \quad \forall j \in I \quad i \neq j xixj+Wli,jW(mi1wi+mi2hi)iIjIi=j

    (4b) 纵坐标:
    y i − y j + H ⋅ b i , j ≤ H − ( m i 1 ⋅ h i + m i 2 ⋅ w i ) ∀ i ∈ I ∀ j ∈ I i ≠ j y_i - y_j + H \cdot b_{i, j} \leq H - (m^1_i \cdot h_i + m^2_i \cdot w_i) \quad \forall i \in I \quad \forall j \in I \quad i \neq j yiyj+Hbi,jH(mi1hi+mi2wi)iIjIi=j

    (5) 有效不等式,最大装箱空间:
    ∑ i ∈ I p i ⋅ ( w i ⋅ h i ) ≤ W ⋅ H \sum_{i \in I} p_i \cdot (w_i \cdot h_i) \leq W \cdot H iIpi(wihi)WH


    目标函数


    最大化,装箱空间:
    m a x ∑ i ∈ I p i ⋅ ( w i ⋅ h i ) max \sum_{i \in I} p_i \cdot (w_i \cdot h_i) maxiIpi(wihi)

    参考文献


    Haoyuan Hu, Xiaodong Zhang, Xiaowei Yan, etc. (2017). Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Method.


    展开全文
  • matlab二维装箱问题求解
  • 二维矩形装箱算法--二叉树--java实现.rar
  • 本程序能按照剩余空间最小的原则得出最优三维装箱顺序。
  • 题目描述 一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1*1, 2*2, 3*3, 4*4...他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你

    参考原文请点击打开链接

    题目描述

    一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵,所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。


    输入

    输入文件包括几行,每一行代表一个订单。每个订单里的一行包括六个整数,中间用空格隔开,分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾。


    输出

    除了输入的最后一行6个0以外,输入文件里每一行对应着输出文件的一行,每一行输出一个整数代表对应的订单所需的最小包裹数。


    样例输入
    0 0 4 0 0 1 
    7 5 1 0 0 0 

    0 0 0 0 0 0 


    样例输出


    思路解析:

    我们知道—— 6 * 6 、 5 * 5 、 4 * 4 以及 3 * 3 的数量除以4向上取整的数量之和是它们必须占用的箱子数量,于是我们可以预先算出这一结果。我们把 1 * 1 和 2 * 2 的盒子用于“塞缝”。对于 2 * 2 的盒子,可以“给 4 * 4 盒子塞缝”,一个4 * 4 盒子的空隙能用5个 2 * 2 盒子填满;3 * 3 盒子空隙所需要的 2 * 2 盒子个数可以用一个数组存。1 * 1 的盒子用来最后填缝。 
    若空隙已经填满了,还剩余了 1 * 1 和 2 * 2 的盒子,此时需要先处理2*2的盒子,按照9个 2 * 2 盒子装满1个箱子的规则,计算需要额外几个箱子,最后计算1 * 1 盒子。从而计算出答案。


    代码:

    public static void Souhu2()
    	{
    		Scanner in = new Scanner(System.in);
    		int a[]=new int[6];
    		while(in.hasNext())
    		{
    			int count=0;
    			for(int i=0;i<6;i++)
    			{
    				a[i]=in.nextInt();
    				if(a[i]==0)
    					count++;
    				if(count>=6)
    					return;
    			}
    			int N=0;
    			int y=0,x=0;
    			int temp[]={0,5,3,1};// temp[0]无意义,temp[i]:箱子中有i个3*3的商品时还可以放多少个2*2的箱子个数
    			N=a[5]+a[4]+a[3]+(a[2]+3)/4;//计算必须占用的箱子数量
    			y=5*a[3]+temp[a[2]%4];// 因为5*5和6*6盒子填充的箱子无法用2*2的盒子填充缝隙,
    								  //因此只需要计算4*4和3*3盒子填充的箱子理论上需要多少个2*2的盒子才能填满
    			if(a[1]>y)
    				N=N+(a[1]-y+8)/9;
    			x=36*N-36*a[5]-25*a[4]-16*a[3]-9*a[2]-4*a[1];
    			if(a[0]>x)
    				N=N+(a[0]-x+35)/36;
    			System.out.println(N);
    		}
    	}


    展开全文
  • 简单的二维装箱代码

    热门讨论 2012-08-01 23:51:31
    简单实现了二维装箱问题。不过仅仅是简单实现,排列7、8个矩形没问题,超过10个就要花N久了。。
  • 改进了FFA算法,提出了区间合并和最小浪费面积的概念,并阐述了实现的方法.最后,采用基于改进的FFA算法的混合遗传算法得到了较好的结果,并对结果进行了分析.
  • 多个车子,N个箱子,用二维矩形方式进行装车。采用二叉树实现。java
  • 二维下料matlab bl算法,bl.mat是主函数,可以直接运行
  • 2018华为软件挑战赛赛题中装箱部分的解答代码,可以作为尺寸成倍数关系的一维装箱问题解决方式的参考
  • 装箱问题遗传算法MATLAB求解。希望对你有用。装箱问题遗传算法MATLAB求解。希望对你有用。装箱问题遗传算法MATLAB求解。希望对你有用。
  • 今天小编为大家介绍二维矩形装箱问题(2D rectangular packing problem, 简称2DRP)以及在此基础上拓展的二维装箱问题(2D strip packing problem,简称2DSP),以及由____数据魔术师团队____提出的解决该问题的...

    写在前面

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

    前言

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

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

    问题介绍

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

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

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

    算法介绍

    描述装箱模式

    算法通过上界线(skyline)坐标点(candidate position) 的概念来描述装箱模式。
    在算法中,我们尽量将矩形放置在下方。简单来讲,上界线表示最上层矩形的上边界;坐标点代表所有上界线的左下角和右下角坐标。
    如图所示,图中最上层水平直线部分为该装箱方式的上界线,分为5段,分别记作 s 1 , s 2 , s 3 , s 4 , s 5 s_1,s_2,s_3,s_4,s_5 s1,s2,s3,s4,s5。图中实心圆点代表坐标点,共有3个左侧坐标点,3个右侧坐标点。
    在这里插入图片描述
    严谨表述为:

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

    s i − 1 s_{i -1} si1左端点的y坐标大于 s i s_i si左端点的y坐标,或线段 s i s_i si右端点的y坐标大于 s i + 1 s_{i+1} si+1大于右端点的y坐标时,标记 s i s_i si左端点或右端点为坐标点。
    其中 s 1 s_1 s1的左端点和 s k s_k sk的右端点一直是坐标点。

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

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

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

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

    评估装箱策略

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

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

    2.only fit。

    3.minimum local waste。

    4.maximum fitness number。

    5.earlist in sequence。

    禁忌搜索

    拓展:2DSP

    展开全文
  • 二维装箱

    千次阅读 2018-07-24 12:25:14
    //节点 public class Node { public int X { get; set; } public int Y { get; set; } public int W { get; set; } public int H { get; set; } public bool Is...
  • 【python】欧姆龙智能物料排布之二维装箱算法实现

    千次阅读 热门讨论 2020-02-24 10:13:52
    问题描述: 排布区域 平面区域为40×50(X方向×Y方向)的矩形。 物料描述 1、包含矩形和三角形两种形状。 2、矩形和三角形的总数为25个,每种形状至少有一个。 3、矩形和三角形的面积、数量随机。 排布规则 1、...
  • 装箱问题遗传算法MATLAB实现.doc,这份文档介绍了装箱问题遗传算法MATLAB实现,装箱问题遗传算法MATLAB实现.doc
  • 一、获取代码方式 获取代码方式1: 完整代码已上传我的资源: ...二维装箱问题是随着计算机技术的产生而出现的,大量出现 在 机 械 制 造、皮革服装加 工、汽车、造船、货物装载以及大规模集成电路板的设计等领域。排
  • 一种新的集装箱问题算法,适用二维
  • 二维矩形装箱算法之二叉树

    万次阅读 2018-03-21 15:28:29
    如何将所有二维矩形块放入一个矩形框内。2.在满足问题1的情况下,矩形框的最小宽度和高度是多少。期望的效果图: 下面我们就来解决以上问题。1. 把矩形块放在固定大小的框内假设有一个固定大小的矩形框,比如1024...
  • 现实物流活动中大量存在的易损、 易碎物品的运输问题属于带二维装箱约束的物流配送问题, 该问题是二维装箱问题与车辆路径问题这两个经典难题融合之后的一个新问题....
  • 二维矩形装箱问题

    2014-09-01 12:18:00
    装箱问题,是个NP问题...研究二维矩形装箱问题,是因为需要将小图拼成大图,作为一个大的texture加载到内存内,从而实现减少内存消耗的目的。 做游戏的都知道texturepacker工具,一款付费软件,有无限多个破解安装...
  • 有一些物品,需要将这些物品装到箱子中,求装箱情况,那么我们应该思考如何装箱装箱时要遵循什么样的准则。
  • 若小于或等于150则将第个数加入列表b, 若大于150则将第个数加入列表c,依次类推,直到所有数字完成比较形成数列(所有物品完成装箱)。</li><li>输出每一个列表中包含的数字,和...
  • 二维装箱子问题

    千次阅读 2019-04-25 08:44:18
    二维装箱子问题 题目:一个工厂生产的产品形状都是长方体,高度都是h,主要有11,22,33,44,55,66等6种。这些产品在邮寄时被包装在一个66h的长方体包裹中。由于邮费很贵,工厂希望减小每个订单的包裹数量以增加...
  • 装箱问题遗传算法MATLAB求解。希望对你有用。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,411
精华内容 2,564
关键字:

二维装箱问题