克什克腾集装箱问题 - 豆丁网

　　克什克腾集装箱问题 - 豆丁网克什克腾集装箱尺寸 蛇口克什克腾集装箱查询 克什克腾集装箱 算法克什克腾集装箱问题 克什克腾集装箱船 盐田克什克腾集装箱公共查询 盐田克什克腾集装箱查询

　　东北大学数学建模团队 克什克腾集装箱装载模型 求解最大积载率 2011-8-22克什克腾集装箱装载问题 目录 摘要........................................................................................................................ 5.1.概念定义：........................................................................................ 5.2.算法框架：...................................................................................... 13 5.3. 长方体信息的记录.......................................................................... 14 5.3.1. 货物的唯一标识 145.3.2. 长方体所有顶点的获得 145.3.3. 长方体所有棱的获得 155.3.4. 长方体所有面的获得 155.4. 遍历所有占角动作.......................................................................... 16 5.4.1. 理论分析 165.4.2. 遍历所有的长方体 175.4.3. 对于每个长方体，找出所有的面并记录 185.4.4. 找出所有合法占角动作 185.5. 统计边度的算法.............................................................................. 18 5.5.1. 对于每一个长方体，找出所有棱并记录 185.5.2. 处理棱 185.5.3. 判断并统计边度 195.6. 模型求解.......................................................................................... 20 23摘要 所谓集装箱装载问题，就是将若干大小不同的长方体装进一个大小已知的长 方体容器，其目标是最大化容器的积载率。对于这一问题，本文参考前人经验， 提出一种求解此问题的基于最大穴度优先原则的启发式算法。算法中使用了两个 重要的策略：最大穴度原则和最小边度原则。让被装进去的长方体尽可能满足这 两条原则，最终使容器的装载率变得尽可能大。 关键字 装载率、穴度优先、边度、占角动作、格局 问题重述将货物装进集装箱是货物运输的一个重要的环节。随着物流业地发展，如何 提高集装箱的装载效率，从而节约成本成了社会上重要的问题。 在理论上，集装箱问题属于NP-hard 问题。由于NP-hard 问题存在巨大的 解空间，只要能够给出令用户满意的解，就有有一定意义。 问题分析首先对第四题的a 问进行分析：首先在容器的角落放最大的长方体，按照如 下原则向容器中继续放置长方体：放进容器的长方体始终占据由三个先前已放进 容器的长方体所形成的角，并且放置动作的穴度还要尽可能地大；若有多个穴度 最大的动作，就挑选边度最小的动作(边度体现了放进容器中各长方体所形成布 局的规整程度，在本文的模型建立与求解中将给出边度的详细定义)。一直到放 完为止。这样一来，放进容器的诸长方体就抱得非常紧凑，从而提高了容器的积 载率。参照这个方法，第一、二、三题都可以解出来。 问相当于多次执行a问，具体如下：对所有的货物执行a 得到一个最优的装箱方法和这个方法用到的货物；从原来的所有的货物中去掉前一次用到的货物，重复前一次操作；当所有的货物都装载完了，就可以得到最优 装载方法集装箱问题。 模型假设货物形状假设：假设所有的货物都是规则的长方体； 方向性约束假设：一般货物的方向性约束有两种，即任意旋转和水平旋转； 货物稳定性假设：所放入的货物都是； 货物位置假设：假设任意一件放入集装箱的货物的每一个面必须与集装箱的 面平行； 假设任意两件货物没有嵌入，即任意两件货物的重叠体积不大于0； 假设任意一件放入集装箱的货物不能超过集装箱的边界； 符号说明积载率 单个货物体积集装箱体积 l:长方体的长度；w：长方体的宽度； h：长方体的高度 分别是长方体B的中心坐标、前左下角 坐标和后右上角坐标； 中心坐标、前左下角坐标和后右上角坐标； 模型的建立与求解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 图5-1-2一个长方体和多个其它长方体间的距离:对给定的长方体B 个长方体组成的集合 与形成这个角以外的其它已放进容器的长方体(包括构成容器的6个长方体)的 距离为 的长度、宽度和高度。事实上，占角动作的穴度反映了即将放进容器的长方体和距离此长方体最近 的长方体(不包括形成此角的长方体a，b，c)的贴近程度。根据此定义，占角动 作的穴度不会大于1。当作此占角动作的长方体占据了由4 个或更多个长方体形 成的穴时，占角动作的穴度就等于1。当仅占据由3 个长方体形成的角时，占角 动作的穴度就小于1。在放置长方体的过程中，我们总是挑选穴度最大的占角动 作，并将对应的长方体按相应的方向放在容器中相应的位置上。 占角动作的边度：当占角动作所关联的长方体按占角位置放进容器之后，容 器中所有长方体(包括当前长方体和先前已放进容器的长方体)之间由于贴面形 成的棱和长方体自身未被占据的棱的总数称为此占角动作的边度。例如，当长方 位于A位置时，对应占角动作的边度为24，如图5-1-3a 所示；如果位于位 置B，对应占角动作的边度为27，如图5-1-3b 所示。边度越小，意味着放进容