本文主要是介绍二维托盘装载问题的建模与求解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、问题简介
二维托盘装载问题是托盘装载问题的一个特殊情况,它仅考虑了长度和宽度两个维度,忽略了高度这一维度,因此也被称为二维装箱问题(2D Bin Packing Problem)。该问题的目标是将一组不同长度和宽度的矩形箱子,无重叠地装载到一个固定大小的矩形托盘上,使得托盘的利用面积最大化,如下图所示为一个托盘装载问题的示意图。
通常而言,托盘装载问题主要包含以下约束:
(1)托盘的长宽固定
(2)箱子的长宽固定
(3)箱子之间不允许重叠
(4)所有箱子必须在托盘区域内
(5)箱子可以根据需要旋转90度
托盘装载问题的优化目标通常为最大化托盘利用面积,即装载后剩余的空余面积最小,相比三维托盘装载问题,二维版本忽略了高度这一维度的约束,问题的复杂度有所降低,但仍然属于NP难问题。常用的解决方法包括:
近似算法
(1)近似比分数算法 (APFA)
(2)最坏情况比率算法 (WSCRA)
启发式算法
(1)下一适合位置算法 (NFFA)
(2)最大空隙度算法 (LGA)
元启发式算法
(1)遗传算法
(2)模拟退火算法
(3)蚁群算法等
精确算法
(1)枚举法
(2)线性规划法等
二维托盘装载问题虽然是一个理论化简的模型,但也有现实应用场景,例如多层板条箱装载问题,纸板、木板、金属板等装载最优化,仓库地面区域规划与划分,集装箱货物装载优化等,本文首先对该问题进行建模,然后采用线性规划方法对该问题进行求解,受限于问题的复杂度,该方法仅适用于小规模的求解。
二、模型搭建
2.1 符号定义
2.2 数学模型
其中:
式(0)最大化装载箱子数量;
式(1)保证对于放置在托盘上的每个箱子互不重叠;
式(3)-(4)对变量类型进行约束。
稍微需要注意的是约束(1),两个箱子的边界是可以重合的,因此托盘上所有点都最多有一个箱子覆盖这样的描述是不成立的。
三、核心代码
3.1 求解代码
#求解器
model=Model('pallet loading')x,y=dict(),dict()
for i in lp:for j in wp:x[(i,j)]=model.addVar(vtype='B',name='x[{}][{}]'.format(i,j))y[(i,j)]=model.addVar(vtype='B',name='y[{}][{}]'.format(i,j))#目标函数
obj=0
for i in lp:for j in wp:if i+a<=L and j+b<=W:obj+=x[(i,j)]if i+b<=L and j+a<=W:obj+=y[(i,j)]
model.setObjective(obj,sense='maximize')#坐标点s和r
for r in range(L):for s in range(W):expr=0for i in lp:for j in wp:if (i<=r and i+a>r) and (j<=s and j+b>s) and i+a<=L and j+b<=W:expr+=x[(i,j)]if (i<=r and i+b>r) and (j<=s and j+a>s) and i+b<=L and j+a<=W:expr+=y[(i,j)]if expr:model.addCons(expr<=1,name='({},{})'.format(r,s))#求解
model.optimize()
3.2 可视化代码
def plot_box(points,puts,L,W):separate=10colors = ['#00FFFF','#7FFFD4','#000000','#0000FF','#8A2BE2','#A52A2A','#DEB887','#5F9EA0','#7FFF00','#D2691E','#FF7F50','#6495ED','#DC143C','#00FFFF','#00008B','#008B8B','#B8860B','#A9A9A9','#006400','#BDB76B']plt.figure(figsize=[20,20*W/L])plt.xlim(0,L)plt.ylim(0,W)num=len(points)for i in range(num):point=points[i]put=puts[i]if put=='x':for l in range(b*separate+1):plt.plot([point[0]+i for i in range(a+1)],[point[1]+l/separate for i in range(a+1)],color=colors[i%len(colors)])plt.plot([point[0] for i in range(b+1)],[point[1]+i for i in range(b+1)],color=colors[i%len(colors)])plt.plot([point[0]+a for i in range(b+1)],[point[1]+i for i in range(b+1)],color=colors[i%len(colors)])if put=='y':plt.plot([point[0]+i for i in range(b+1)],[point[1] for i in range(b+1)],color=colors[i%len(colors)])plt.plot([point[0]+i for i in range(b+1)],[point[1]+a for i in range(b+1)],color=colors[i%len(colors)])for w in range((b)*separate):plt.plot([point[0]+w/separate for i in range(a+1)],[point[1]+i for i in range(a+1)],color=colors[i%len(colors)])
四、测试结果
在这一小节中,用两个case来验证本文算法的有效性,第一个case规模较小,第二个case规模较大,求解时间较长,基本临近线性规划的求解极限。
4.1 简单case
在长宽分别为11、10的托盘中,放置长宽分别为4、3的箱子,最多放置的箱子数量为9,放置结果如下图所示。
4.2 复杂case
在长宽分别为200、100的托盘中,放置长宽分别为15,10的箱子,最多放置的箱子数量为133,放置结果如下图所示。
对于第二个case,直接求解其实还是比较有难度,为了加速求解,对可放置点进行了稀疏处理,理论上托盘上的最优放置点可以表示为:
该稀疏解不损失最优性,证明过程在论文中多有提及,不再赘述。
五、本文小结
本文建立了PLP问题的数学模型,并使用线性规划对该问题进行了求解,对于规模较大的问题,采用稀疏策略进行优化,完整代码见公众号,不定期更新各类运筹优化算法源码。
这篇关于二维托盘装载问题的建模与求解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!