机器人混合料多盘装载问题建模与求解

机器人混合料多盘装载问题建模与求解

在工业物流自动化领域，使用硬盘处理大量物质堆被认为是材料处理的最有效手段，但对磁盘负载问题的研究是实现有效方法的基础。托盘装载问题是指如何将一些特定规格尺寸的长方体箱子以尽可能多的数量放入一长方体容器内,最大限度地利用长方体容器的可用空间。若长方体箱子的高度相同,托盘装载问题可简化为将一些小矩形块放入大矩形的2维问题。它属于组合优化问题,国内外许多学者对此问题进行了深入研究并且取得了进展[1,2,3,4,5,6,7,8,9,10]。但这些研究只是单一尺寸物料的托盘装载问题,并且研究对象仅针对工程实践中单一托盘的情形。本文结合机器人混合码垛的工程实践需要,研究一种新型的混料多盘装载问题。1如何使用盘多盘盘封装如图1所示的机器人码垛工作站,无论是完成图1a所示的分拣任务,还是图1b所示的混合码垛功能,其本质是混料多盘装载问题。如果有足够多的托盘,混料多盘装载问题研究的内容可以简述如下:如何使用数量最少的长方体容器(托盘)装载大小不同、数量一定的长方体箱子。可见,混料多盘装载追求的目标是在满足规定约束条件的前提下,尽可能地合理布局箱子在托盘上的位置,以减小每一个托盘上的无用空间,使平面占有率最大化,从而使托盘使用总数目最小。在强调最小浪费的同时,也强调了最大的利用,二者是辩证统一的。2混料多盘装卸问题的数学模型在图2所示的托盘平面上,箱子既可以水平放置,也可以垂直放置。无论托盘还是箱子,将长边尺寸称为长度,短边尺寸称为宽度。研究目标是将所有给定的箱子装载到最小数量的托盘上。模型的输入参量如下:L为托盘长度;W为托盘宽度;li为箱子长度;wi为箱子宽度;Q为箱子总数;Δ为一个大数。混料托盘装载问题数学模型中使用的变量定义如下:xip为托盘p上箱子i的左下角的横坐标;yip为托盘p上箱子i的左下角的纵坐标;P为可用托盘数;σip为二进制变量,当箱子i放置于托盘p上时为1,否则为0;δi为二进制变量,当箱子i水平放置于托盘p上时为1,否则为0;τp为二进制变量,当托盘p被使用时为1,否则为0;Lijp为二进制变量,在托盘p上当箱子i放置于箱子j的左侧时为1,否则为0(设托盘p上箱子i的左下角的顶点为Vip,箱子j的左下角的顶点为Vjp,如果Vip位于Vjp的左侧,则称箱子i位于箱子j的左侧)。类似地,有二进制变量Rijp、Bijp、Tijp,分别表示当托盘p上箱子i放置于箱子j的右侧、下侧、上侧时为1,否则为0。Lijp、Rijp、Bijp和Tijp的定义暗示了托盘上箱子之间的相对位置。这里需要说明的是,对于如图3a～图3e的情形,即|xip-xjp|≤liδi+wj(1-δj)时,令Lijp=Rijp=0;对于见图4a～图4e的情形,即|yip-yjp|≤wiδi+lj(1-δj)时,令Bijp=Tijp=0。在上述分析的基础上,建立混料多盘装载问题的数学模型如下:minτ=∑p=1Pτp(1)minτ=∑p=1Ρτp(1)s.t.xip+liδi+wi(1-δi)≤xjp+(1-Lijp)Δ(2)xjp+ljδj+wj(1-δj)≤xip+(1-Rijp)Δ(3)yip+wiδi+li(1-δi)≤yjp+(1-Bijp)Δ(4)yjp+wjδj+lj(1-δj)≤yip+(1-Tijp)Δ(5)Lijp+Rijp+Bijp+Tijp≥σip+σjp-1(6)∑p=1Pσip=1i=1,2,⋯,Q(7)∑p=1Ρσip=1i=1,2,⋯,Q(7)∑i=1Qσip≤Pτpp=1,2,⋯,P(8)∑i=1Qσip≤Ρτpp=1,2,⋯,Ρ(8)xip+liδi+wi(1-δi)≤L(对所有i,p)(9)yip+wiδi+li(1-δi)≤W(对所有i,p)(10)Δ=max{∑i=1Qli,L}(11)Δ=max{∑i=1Qli,L}(11)Lijp=Rijp=0,当|xip-xjp|≤liδi+wj(1-δj)(12)Bijp=Tijp=0,当|yip-yjp|≤wiδi+lj(1-δj)(13)τp,δi,σip,Lijp,Rijp,Bijp,Tijp=0或1,xip,yip≥0i,j,p∈Z+,Z+为正整数;i<j式(2)～式(5)确保托盘平面上各箱子之间不重叠。只有位于同一托盘上的箱子数目超过1时才检查是否重叠,这种情形的考虑反映在式(6)中。约束式(7)保证了每一个箱子只能放在一个托盘上。在P个托盘中,有一些可能不被使用,而没被使用的托盘上是不能放置任何箱子的,式(8)描述了这种情形。约束式(9)和式(10)则表明放置于托盘上的所有箱子必须受到托盘尺寸的限制,不能超出托盘平面,即托盘上的箱子不能悬置。约束式(11)～式(13)是为了确保模型运行而针对式(2)～式(6)的附加条件。根据文献,本文建立的上述模型是一个混合整数规划模型,既包括0-1变量τp、δi、σip,也包括整数变量P,以及xip、yip等连续变量。可是,基于混料多盘装载问题的上述模型,因为P未知而不能被直接求解。为了求解的需要,可以采用迭代法,每次迭代使用不同的P值。注意到目标函数值仅能是整数,可以在一开始使用一个小值去检验是否能够找到一个可行解,如果这样的可行解存在,则它一定是最优的,否则逐量增加P的值重复迭代过程。为此,不以P=1开始,而是采用一个下界Pd为(14)其中,表示不小于r的最小整数。在此基础上,整个问题的求解思路可以简单概括为如下步骤:(1)令P=Pd;(2)令τp=1,p=1,2,…,P;(3)解数学规划问题(*),当获得可行解后停止,(*)表示由式(1)～式(13)的混合整数规划模型;(4)如果在步骤(3)中判断为不可解,则令P=P+1,然后返回步骤(2)。这里仅强调如何将混料多盘装载问题模型化,并给出相应的求解策略,而目的不在于如何开发一个旨在求解上述步骤(3)的应用程序。同时应当指出,如何找到可行解以及如何判断无解是能否正确求解问题的关键。为了检查模型的有效性,我们在LEGENDPC上使用了SJTU-WXLMPLP软件求解了一个小型算例,该算例的数据见表1。求解结果表明问题的一个可行解是P