装箱问题

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

装箱问题(Bin Packing)

目录

什么是装箱问题

  把一些箱子装入容器中是一个在工业生产中经常遇到的数学难题,比如集装箱的装箱问题。装箱问题是一个经典的组合优化问题,有着广泛的应用,在日常生活中也屡见不鲜。

  设有许多具有同样结构和负荷的箱子B1B2,… ,其数量足够供所达到目的之用。每个箱子的负荷(可为长度、重量等等.)为 C ,今有 n 个负荷为 wj,0 < wj < C , j = 1,2,…,n 的物品 J1J2,…,Jn 需要装入箱内。装箱问题就是指寻找一种方法,使得能以最小数量的箱子数将J1J2,…,Jn 全部装入箱内。

装箱问题的分类

  装箱问题可分为一维装箱问题,二维装箱问题,三维装箱问题三种。现实生活中常见的应该是三维装箱问题。

  一维装箱问题只考虑一个因素,比如重量、体积、长度等。

  二维装箱问题考虑两个因素——给定一张矩形的纸(布料、皮革),要求从这张纸上剪出给定的大小不一的形状,求一种剪法使得剪出的废料的面积总和最小。常见问题包括堆场中考虑长和宽进行各功能区域划分、停车场区位划分、包装材料裁切时考虑怎样裁切使得材料浪费最少、服装布料裁切、皮鞋制作中的皮革裁切等。

  三维装箱问题考虑三个因素——一般指长、宽、高。装车、装船、装集装箱等要考虑这三个维度都不能超。

  根据目标的不同,三维装箱问题可分成以下几类:

  箱柜装载问题(Three-Dimensional Bin Packing Problem,简称3D-BPP):给定一些不同类型的方型箱子和一些规格统一的方型容器,问题是要把所有箱子装入最少数量的容器中。

  容器装载问题(Three-Dimensional Container-Packing Problems,简称3D-CPP):在该问题中,所有箱子要装入一个不限尺寸的容器中,目标是要找一个装填,使得容器体积最小。

  背包装载问题(Three-Dimensional Knapsack Loading Problems,简称3D-KLP):每个箱子有一定的价值,背包装载是选择箱子的一部分装入容器中,使得装入容器中的箱子总价值最大。如果把箱子的体积作为价值,则目标转化为使容器浪费的体积最小。

本条目对我有帮助5
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您认为本条目还有待完善,需要补充新内容或修改错误内容,请编辑条目

本条目由以下用户参与贡献

刘维燎.

评论(共0条)

提示:评论内容为网友针对条目"装箱问题"展开的讨论,与本站观点立场无关。

发表评论请文明上网,理性发言并遵守有关规定。

MBA智库
打开APP

以上内容根据网友推荐自动排序生成