APS排程:三维装箱优化算法


编辑导语: 什么是箱柜装载问题 箱柜装载问题,three-dimensional bin packing problem,简称3D-BPP。给定一些不同类型的方型箱子和一些规格统一的方型容器,问题是要把所…

什么是箱柜装载问题

箱柜装载问题,three-dimensional bin packing problem,简称3D-BPP。给定一些不同类型的方型箱子和一些规格统一的方型容器,问题是要把所有箱子装入最少数量的容器中。箱柜装载问题在现实生活中具有广泛的应用,例如在货运码头、物流、仓储等场所装车、装船、装集装箱等。

三维装箱示意
三维装箱示意

三维装箱问题存在禁忌搜索算法遗传算法模拟退火算法等研究和应用。

模拟退火算法

模拟退火算法(Simulated Annealing,SA)最早的思想是由N. Metropolis 等人于1953年提出。1983 年,成功将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。

模拟退火算法是一种通用的优化算法,理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用,诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性,从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

三维装箱数学模型

自主研发的箱柜装载问题算法引擎采用基于搜索树的精确算法,基本思想是把三维装箱问题归约(Reduce)到一个有向无环图(Directed Acyclic Graph)上的问题。算法支持的约束条件如下表所示。

约束
详细
集装箱约束
单一箱子高度不能超出门高
箱子总高度不能超出内高,总宽度不能超出内宽,总长度不能超出内长
箱子总重量不能超出集装箱载重
箱子总金额不能超出集装箱的金额限制
托盘总重量不能超过集装箱托盘重量约束
在接近门的xx米内,箱子总高度不能超出门高
箱子排序
按照木轴,木箱,托盘,纸箱的顺序装载
圆柱体约束
立放圆柱体H<xx或xx<H≤yy实行品字型堆码
立放圆柱体xx≤H≤yy实行田字形堆码
立放圆柱体需要满足堆叠层数的约束
立放圆柱体H>130只可以堆一层,可以在水平方向旋转
卧放圆柱体按照长方体支撑约束堆叠,但是下面只能放卧放圆柱体,上面不限
长方体上下支撑约束
同类箱子上下堆叠需要满足堆叠层数约束
同类箱子上下堆叠需要满足上轻下重约束
不同类箱子,箱子上面堆叠的总重量不能超出最大承重
箱子的上下支撑面大于xx%
长方体前后安全性约束
纸箱不能放置在yy米以上
加托箱子的约束
加托的箱子上面不能堆放箱子,下面不限
相邻提货点堆叠约束
相邻提货点箱子在堆叠的时候,交界处不能超过yy米
加托时约束
加托内堆叠时编织袋不能放在纸箱上面
同一个托盘不能放置两个提货点的箱子
圆柱体的纸箱不加托(按圆柱体规则摆放,排序依然在托盘后面)
只有天线(长度大于xx)才使用长托盘(长度大于yy),其他箱子放在其他托盘中,即天线只能用长托盘,长托盘也只能放天线

APS智能排产系统应该集成国内自主研发的顶尖的三维装箱引擎,实现三维装箱、路径规划与排产计划联动,同时考虑静态的装箱约束与动态的交货期约束,实现基于装箱顺序的生产计划模拟排程,以及基于计划执行结果的装箱调整优化,解决企业生产计划与装箱计划的闭环优化,三维装箱效果如下图所示。

三维装箱系统展示
三维装箱系统展示


最近更新于 2022-05-14 猿小六2021-10-16 发布, 已阅 2561 次。