集装箱问题

东北大学数学建模团队集装箱装载模型求解最大积载率王智、余万科、傅天赋2011-8-22集装箱装载问题目录摘要........................................................................................................................3关键字....................................................................................................................31.问题重述......................................................................................................42.问题分析......................................................................................................53.模型假设......................................................................................................64.符号说明......................................................................................................75.模型的建立与求解......................................................................................85.1.概念定义：........................................................................................85.2.算法框架：......................................................................................135.3.长方体信息的记录..........................................................................145.3.1.货物的唯一标识.......................................................................145.3.2.长方体所有顶点的获得...........................................................145.3.3.长方体所有棱的获得...............................................................155.3.4.长方体所有面的获得...............................................................155.4.遍历所有占角动作..........................................................................165.4.1.理论分析...................................................................................165.4.2.遍历所有的长方体...................................................................175.4.3.对于每个长方体，找出所有的面并记录...............................185.4.4.找出所有合法占角动作...........................................................185.5.统计边度的算法..............................................................................185.5.1.对于每一个长方体，找出所有棱并记录...............................185.5.2.处理棱.......................................................................................185.5.3.判断并统计边度.......................................................................195.6.模型求解..........................................................................................206.参考文献：................................................................................................23摘要所谓集装箱装载问题，就是将若干大小不同的长方体装进一个大小已知的长方体容器，其目标是最大化容器的积载率。对于这一问题，本文参考前人经验，提出一种求解此问题的基于最大穴度优先原则的启发式算法。算法中使用了两个重要的策略：最大穴度原则和最小边度原则。让被装进去的长方体尽可能满足这两条原则，最终使容器的装载率变得尽可能大。关键字装载率、穴度优先、边度、占角动作、格局1.问题重述将货物装进集装箱是货物运输的一个重要的环节。随着物流业地发展，如何提高集装箱的装载效率，从而节约成本成了社会上重要的问题。在理论上，集装箱问题属于NP-hard问题。由于NP-hard问题存在巨大的解空间，只要能够给出令用户满意的解，就有有一定意义。2.问题分析首先对第四题的a问进行分析：首先在容器的角落放最大的长方体，按照如下原则向容器中继续放置长方体：放进容器的长方体始终占据由三个先前已放进容器的长方体所形成的角，并且放置动作的穴度还要尽可能地大；若有多个穴度最大的动作，就挑选边度最小的动作(边度体现了放进容器中各长方体所形成布局的规整程度，在本文的模型建立与求解中将给出边度的详细定义)。一直到放完为止。这样一来，放进容器的诸长方体就抱得非常紧凑，从而提高了容器的积载率。参照这个方法，第一、二、三题都可以解出来。第四题的b问相当于多次执行a问，具体如下：对所有的货物执行a问，得到一个最优的装箱方法和这个方法用到的货物；从原来的所有的货物中去掉前一次用到的货物，重复前一次操作；当所有的货物都装载完了，就可以得到最优装载方法。3.模型假设货物形状假设：假设所有的货物都是规则的长方体；方向性约束假设：一般货物的方向性约束有两种，即任意旋转和水平旋转；货物稳定性假设：所放入的货物都是；货物位置假设：假设任意一件放入集装箱的货物的每一个面必须与集装箱的面平行；假设任意两件货物没有嵌入，即任意两件货物的重叠体积不大于0；假设任意一件放入集装箱的货物不能超过集装箱的边界；4.符号说明积载率单个货物体积集装箱体积l:长方体的长度；w：长方体的宽度；h：长方体的高度；；；；；;，分别是长方体B的中心坐标、前左下角坐标和后右上角坐标；，和分别是长方体中心坐标、前左下角坐标和后右上角坐标；5.模型的建立与求解5.1.概念定义：格局：在某一时刻，容器中已经放入了若干个长方体，还有若干个长方体等待放入，这种状态称为一种格局。如图5.1-1所示；图5.1-1一种格局初始格局：容器中还没有放入任意一个长方体；终止格局：全部待放置的长方体已经放入容器；方向约束条件：根据假设，长方体能够任意旋转或者水平旋转，并且各个面都与容器的各面分别平行。占角动作：在某一格局下，若放入的长方体与容器中已有的长方体的面或容器的六个面中的三个面贴面，则称这种放入的动作为一个该长方体的一个占角动作。图5.1-1中的α放入容器的动作就属于占角动作。占角位置：某个长方体进行占角动作后，长方体所处的位置为占角位置。他图5.1-1中的α就处在占角位置上。占穴动作：某个长方形占据一个占角位置后，还和除这个角以外的其他面贴面，则此动作称为占穴动作。图5.1-1中的长方体β放入容器就属于占穴动作。占穴位置：某个长方体进行占穴动作后，长方体所处的位置为占学位置。图5.1-1中的长方体β就处在占穴位置。长方体i和长方体j的距离：（）式(1)定义的两长方体间的距离是两点之间曼哈顿距离的推广。例如，在图5-1-2中，两长方体之间的距离分别为0,l和。(a)(b)(c)图5-1-2一个长方体和多个其它长方体间的距离:对给定的长方体B和m个长方体组成的集合。令长方体B与之间的距离为，那么长方体B和m个长方体之间的距离定义为。占角动作的穴度：若将某一长方体按合法占角动作放进容器之后，长方体与形成这个角以外的其它已放进容器的长方体(包括构成容器的6个长方体)的距离为，则此占角动作的穴度，定义为式中，和分别为长方体的长度、宽度和高度。事实上，占角动作的穴度反映了即将放进容器的长方体和距离此长方体最近的长方体(不包括形成此角的长方体a，b，c)的贴近程度。根据此定义，占角动作的穴度不会大于1。当作此占角动作的长方体占据了由4个或更多个长方体形成的穴时，占角动作的穴度就等于1。当仅占据由3个长方体形成的角时，占角动作的穴度就小于1。在放置长方体的过程中，我们总是挑选穴度最大的占角动作，并将对应的长方体按相应的方向放在容器中相应的位置上。占角动作的边度：当占角动作所关联的长方体按占角位置放进容器之后，容器中所有长方体(包括当前长方体和先前已放进容器的长方体)之间由于贴面形成的棱和长方体自身未被占据的棱的总数称为此占角动作的边度。例如，当长方体a位于A位置时，对应占角动作的边度为24，如图5-1-3a所示；如果位于位置B，对应占角动作的边度为27，如图5-1-3b所示。边度越小，意味着放进容器的各长方体形成的布局越规整。因此，在放置过程中，若有多个占角动作的穴度都为最大，就选边度最小的占角动作。例如，在图5-1-3中，不论长方体a放在位置A还是位置B，占角动作的穴度都为1。但由于放在位置A所对应占角动作的边度更小，因此我们选择将长方体a放在位置A的占角动作。（a）（b）图5-1-3放置方向的优先序：对一个即将放进容器的长方体，最多有6个可选的方向，即lwh，wlh，lhw，whl，hlw，hwl。方向lwh意味着，而方向whl意味着，等等，这里和分别表示长方体前左下角和后右上角的坐标。本文中，放置方向的优先序取为1whwlhlhwwhlhlwhwl。点的优先序:对给定的两点和，如果满足如下三个条件中的一个，则称点的优先序大于点的优先序：1.；2.且；3.，且。5.2.算法框架：在当前格局之下，枚举所有的合法占角动作并计算每一个占角动作的穴度和边度。然后选择穴度最大的占角动作并将对应的长方体依相应的方向放在容器中相应的位置上，直到容器外已没有长方体可放或容器内再也不能按放置规则放下任何长方体时为止。需要注意的是，如果有多个穴度最大的占角动作，那么就按如下的选择原则挑选唯一一个占角动作：(1)挑选边度最小的占角动作；(2)挑选动作长方体体积最大的占角动作；(3)挑选动作长方体前左下角优先序最大的占角动作；(4)挑选具有最大方向优先序的占角动作；(5)挑选动作长方体编号最小的占