基于海鸥算法的库区货位分配及优化研究.pdf

环保安全 ：收稿日期：；修回日期：基金项目：国家自然科学基金（）；国家自然科学基金（）；江苏省食品先进制造装备技术重点实验室自主研究课题资助项目（）；“六大人才高峰”（）。第一作者简介：吴伟开（），男，安徽黄山人，硕士研究生，主要研究方向为滚动轴承动态性能、信息管理系统。：基于海鸥算法的库区货位分配及优化研究吴伟开，何雪明，黄育鹏，（江南大学 机械工程学院，江苏 无锡 ；江南大学 江苏省食品先进制造装备技术重点实验室，江苏 无锡 ）摘要：针对自动化立体仓库库区货位分配存在的出入库速度慢、货架稳定性差以及货品相关性低的问题，课题组提出了一种优化方法。首先，进行数学模型的搭建，为各目标函数分配权重，对比较重要的目标函数进行人为增量，提升目标函数的计算值敏感程度，达到自我分辨的目的；其次，通过引入非线性动态移动参数，提出一种改进的海鸥算法，并采用种基准测试函数来验证改进算法的寻优能力。结果表明改进后的算法在精度以及寻优速度上都优于原始算法。该模型能够提升货物的出入库速度和货品相关性，保证货架稳定性，可有效提升立体仓库利用率。关键词：立体仓库；货位分配；库区优化；海鸥算法中图分类号：文献标志码：文章编号：（），（，；，）：，：；自动化立体仓库的自动存储 检索系统（，）能够根据指令自动完成货物存取和记录，对库存进行自动管理。与传统仓库相比，自动化立体仓库具有储货量大、占地面积小、出入库迅捷和企业管理与生产效率提高等优点 。针对自动化立体仓库的货位分配优化问题，国内外的许多专家学者进行了大量的探索和深究。等 研究了鱼骨机器人移动过滤系统第 卷 第 期 年 月轻工机械 （，）的存储分配优化问题，设计了一种自适应遗传算法（，）对提出的模型进行求解，并验证了其有效性。等 提出具有一些有效不等式的 混 合 整 数 线 性 规 划（，）模型，并将该模型用在仓库的货位分配中。等 研究了机器人移动履约系统（，）的存储分配优化问题，设计了贪心算法与改进模拟退火相结合的 阶段混合算法对模型进行求解。等 提出了一种基于云的信息物理系统（，）的拣选通行系统（，），采用启发式多目标遗传算法求解基于电子商务的仓库拣货作业的 存储指派问题（，）。等 提出了一种基于数据驱动的 区域聚类和存储位置分配分类方法。等 提出了一种基于产品周转率和从历史客户订单中获取的亲和力集成簇分配（，）策略，以 最 小 化 零 件 到 拣 货 系 统 的 检 索 时 间。等 针对现代仓储中自动化存储和检索过程，提 出 了 一 种 新 的 存 储 分 配 优 化 算 法（，），以实现存储机制的敏捷性。等 提出了一种新的粒子群优化（，）方法解决出库箱位指派问题。有关货位分配方面的研究大多集中在对算法进行改进，较少对货位分配的模型进行分析和研究。对于仓储中普遍存在的出入库速度慢、货架稳定性差及货品相关性低的问题，课题组将智能优化算法与数学模型结合起来解决实际仓储过程中存在的货位分配问题。库区货位分配问题描述对于自动化立体仓库，入库时存储位置就是出库时拿取的位置，因此在进行储位分配规划时只需确定出库时的条件即可。特定情况下，可能需要对所有位置进行一次重新分配，此时存储位置可能发生变化。货位分配时，一般要遵守下面这几个准则：最先进入仓库的产品，也应当最先出去，减少产品的在库时间，周转率高的产品应当放在离出库口较近的位置；为使得货架使用寿命较长，应采用“上轻下重”的摆放方式；尽量将相关性较大的产品安放位置靠近。因此，货位分配的目标可以总结为提高货品的出入库效率、保证货架的稳定性、提高存放货品之间的相关性。课题组针对产品的出库货位分配问题，根据上面总结的 个目标来进行货位分配的研究。库区货位分配的优化数学模型 库区货位分配模型参数模型参数是在货位分配模型中需要用到的各种变量和常量，应根据实际作业的情况赋予这些参数相应的值，货位分配模型的参数定义如表 所示。库区货位分配模型目标函数 货品出库效率由于立体仓库中的堆垛机速度是恒定的，可以通过缩短产品位置到出库口之间的距离（即缩短产品出库时间）来提高产品的出库效率。一般情况下，堆垛机表 模型参数 参数说明参数说明参数说明货架的排数单元货格的长度第 类产品的单位质量货架的列数单元货格的宽度 ，货位（，）上第 类产品的数量货架的层数单元货格的高度第 类产品的坐标均值货位的排号巷道的宽度（，）第 类产品的第 个所在储位坐标货位的列号 货位（，）上产品的周转率 第 类产品的第 个到 的距离货位的层号所有产品共 类所有 类产品的类内离散度距离和输送机的运输速度第 类产品，所有 类产品的均值坐标堆垛机沿 方向运输速度第 类产品的个数所有产品到 类产品中心 的离散度和堆垛机沿 方向运输速度第 类产品的第 个，所有产品均值坐标到出库口的距离轻工机械 年第期在巷道中运行是 个方向同时运动，因此有 个速度：一个是纵向的，另一个是横向的。根据这种实际情况，则需要得到这 个方向作业过程中花费的时间的最大值，即 （）。堆垛机在运输带上所花费的时间可表示为 。则该模型的出库效率函数公式为：（，）。（）其中，()。货品的相关性分析将一起入库的相关性大的产品放在较为靠近的位置，并归为一类品种，想要得到这样的效果就要使得相关产品之间距离之和累加最小。类内的离散度主要是指同品种的 个产品摆放的距离，那么用数学抽象化就是 个点之间的距离。将产品坐标除以产品数量就可以得到该类产品的坐标均值，即所有第 类货品的坐标均值为：（，）。（）计算同一品种的每个产品的坐标与这个类坐标均值之间的距离，即第 类货品的第 个到 的距离，公式表示为：（）（）（）槡。（）将算出来的距离值进行累加，所得的值越小则说明同一品种的产品摆放得越集中，即货品之间的类内离散度 为所有 类货品到 的距离之和：。（）最后计算类间离散度。同理先将所有种类的货品的类坐标均值算出来，即所有 类货品的均值坐标为：。（）然后将所有货品到 类货品均值坐标 的距离累加之和作为货品类间离散度之和：（）（）（）（）（）（）（）槡。（）综合考虑这 种离散度，才能使所摆放的货品之间的相关性最大。即货品应均匀地摆放在货架中，而且点应尽量离出库口较近。（）（）（）槡（）可以建立货品相关性的目标函数：。（）货架稳定性考虑到货物存放的安全问题，在存放物品时应当将重的产品放在货架的靠下层，较轻的产品则放在货架的较上层，用数学的方法来抽象就是每一层的货品的质量、数量和所在高度的乘积除以每一层的货品的质量和数量的乘积所得到的值越小，则重心越低，即目标函数公式如下：（，）。（）综上所述，货位分配的数学模型表达式为：（，）()()；（，）。（）在上述的货位分配模型函数公式中，目标函数式（）保证了货品的出库效率，同时也缩短了周转率较高的产品的出库时间；目标函数式（）使得在货架中放入的相关性较大或者同一品种的产品能够放在一起，保证了产品之间的相关性；目标函数式（）约束了入库产品摆放按照质量“上小下大”的原则进行摆放。最后将这几个目标函数统一在一起，得到最后的目标函数式（）。该问题属于一种复杂的多项式问题，可以采用海鸥算法对该问题进行优化求解。库区货位分配模型约束条件企业成品库存储区共有 排货架，每排货架共有 层 列。因此货位坐标的（，）值应当不能超过（，环保安全吴伟开，等：基于海鸥算法的库区货位分配及优化研究，）的值。同时货位坐标应为整数。所以模型的约束条件如下：，；，为整数。（）联立式（）和（），可得货位分配模型。上述模型是根据实际问题建立的，但是在实际运用与计算的时候发现根据该模型得到的结果并不是很好，为解决这一问题，提出为各目标函数分配权重，以及对比较重要的目标函数进行人为增量的方法，使该目标函数得到的数值再乘以一个固定的敏感系数，使得函数值增大。通过这样的方法使程序对该目标函数的计算值敏感，然后达到自我分辨的目的。对于目标 的函数，乘以一个固定的敏感系数 ，得到修改后的公式为：（，）()()。（）对于目标 的函数，在计算类内离散度的公式中乘以一个固定的敏感系数 ，可得到修改后的公式：（）。（）则目标 的函数公式为：（）。（）将各个目标函数加起来得到一个总的目标函数，再为各目标函数赋予合适的权重得到总目标函数公式：（）。（）式中 为权重数组 ，。库区货位分配的海鸥算法海鸥算法（，）是 和 通过研究海鸥的生物行为时提出的 ，能够使用相应的数学模型来表征这些行为，该算法的模型特征主要包括觅食迁徙和攻击猎物的行为，如图 所示。图 海鸥算法模型 海鸥优化算法特征 迁徙特征迁徙模型就是表示海鸥在全体移动寻找食物时产生的一种迁徙行为，在这种大范围，并且个体较为紧密的迁徙过程中，海鸥应当满足以下几个条件：）海鸥之间避免相互碰撞。海鸥们的位置不能够重叠，因此为防止海鸥之间产生相互碰撞，在位置更新的过程中加入一个移动参数 。海鸥避免相互碰撞如图 所示，公式如下：（）。（）式中：（）；，；为新的海鸥位置，与其他海鸥位置不产生冲突；为当前海鸥位置；为到目前位置迭代更新次数；为海鸥在迁徙过程中搜索猎物的移动参数；为控制移动参数的变化，一般取 ；为迭代更新次数；为设置的总迭代更新次数。图 海鸥之间避免相撞过程 ）向目前离猎物最近的海鸥靠近。在解决碰撞的问题后，海鸥们会向目前最靠近猎物的海鸥靠近，公轻工机械 年第期式如下：（）（），。（）式中：为当前海鸥向最靠近猎物海鸥的位置飞行方向；为随机变量，扰动新的海鸥的搜寻位置，增强全局寻优地能力；为一个随机数，范围是 ，；（）为当前最靠近猎物的海鸥位置。其他海鸥向最靠近猎物的海鸥位置靠近的过程如图 所示。图 海鸥向最佳海鸥移动 ）靠近最佳海鸥后更新位置。当向最佳海鸥靠近后，为避免碰撞会更新自己的位置且进行其他位置的探索，公式为：。（）式中 为当前海鸥与最佳海鸥之间的距离。海鸥向最佳海鸥方向靠近的过程并更新位置描述如图 所示。图 靠近最佳海鸥后位置 攻击特征海鸥们在捕食时的主要的行为特点是以一种螺旋式的飞行轨迹进行捕食，不断控制改变下降的角度以及飞行的半径，如图 所示。其数学描述如下：；（）（）（）。（）式中：为在下降过程中的飞行半径；为 ，内的一个随机值；，为螺旋飞行行为的常数变量；为自然对数的底数；（）为当前更新后的最优海鸥位置。海鸥算法在迭代更新的过程中，海鸥们能够向当前的最优海鸥靠近并更新自己的位置，增强全局的探索能力。图 捕猎模型 海鸥优化算法流程算法流程如下：）代入初始变量的值进行计算；）根据式（）（）计算海鸥当前位置；）计算每只海鸥个体的适应度值；）根据式（）更新海鸥的位置；）计算目前最优海鸥的位置以及适应度值，将迭代数加 ，进行下次迭代；）若当前迭代数小于最大的迭代数，则执行下一步流程，否则跳转至 ）；环保安全吴伟开，等：基于海鸥算法的库区货位分配及优化研究）得到最后最优的海鸥位置。海鸥优化算法改进通过对 算法的原理以及数学公式推导可以得知：算法的模型参数很少，算法的流程也较为简单易懂，比较容易实现，并且能够较好地模拟海鸥的迁徙和捕食行为；但是在迁徙的过程中并不能很好地更新自己的位置，这样就会使得算法在运行初期收敛较慢或者陷入局部最优。因此通过修改移动参数的方式设计了非线性动态移动海鸥算法（，），该想法是从国内外学者对粒子群算法进行改进的方法中产生的。课题组将这种算法的性能进行了对比，改进后的算法增强了算法的收敛速度，保证了算法的简易性和精确性。引入非线性动态移动参数，改进后海鸥算法的移动参数 更新公式为：()()()，。（）改进后的移动参数 能够非线性地从 变化到，这样使得海鸥在更新位置时能够扩大全局的搜索能力，同时随着 不断地变小，群体不断地向最优个体位置靠近，增强了算法的局部搜索能力。改进后的移动参数 与原移动参数 对比的趋势如图 所示。图 移动参数 随迭代次数变化趋势 改进后海鸥优化算法流程图 所示为改进后的海鸥算法执行流程。图 执行流程图 将式（）改为式（）代入计算海鸥当前位置，其中计算适应度值就是计算货位分配模型的总目标函数，将生成的货位坐标代入函数中即可。性能测试为了验证 的算法的性能，选取 个常用的基准测试函数对 ，和 进行性能对比测试，验证改进后的性能。其中函数 为单峰测试函数、为多峰测试函数。单峰测试函数可以用来评估算法的开发能力以及寻优能力，多峰函数可以用来评估算法的全局寻优能力。单峰测试函数见式（）（），多峰测试函数见式（）（）。）函数（）；（）（，）。（）函数（）()；（）（，）。（）函数（）（）（）；（）（，）。（）函数轻工机械 年第期（）（）；（）（，）。（）函数（）()槡()（()）；（）（，）。（）函数（）槡()；（）（，）。（）单峰函数测试结果见图 ，多峰函数测试结果见图 ，详细的结果对比如表 所示。实验设置种群初始规模为 ，迭代次数为 。图 优化结果曲线 图 优化结果曲线 图 优化结果曲线 图 优化结果曲线 图 优化结果曲线 环保安全吴伟开，等：基于海鸥算法的库区货位分配及优化研究图 优化结果曲线 表 性能测试对比 测试函数最优值 收敛迭代数 从图 中可以看出 的收敛速度均优于 和 ，由表 可知 的算法精度要优于 和 ；同时，从图中可看出 存在收敛速度慢、有时不易得到最优解等缺点，这在 的测试结果得到了明显的改善，说明了改进算法的有效性。课题组从移动参数方面进行的改进取得了较好的结果。结论为解决库区货位分配的出入库速度慢、货架稳定性差、货品相关性低 个问题，课题组建立货位分配数学模型，采用海鸥优化算法对该模型进行求解，结果表明：）通过在算法更新策略的公式中引入非线性动态参数，增强了算法的收敛速度、精确性以及早熟性。）用 个基准测试函数对算法的寻优精确度以及避免陷入局部最优的能力进行测试，改进后的算法在寻优精度和寻优速度上都优于原始算法，同时具备良好的避免陷入局部最优的能力。后续的研究中应考虑将具体行业仓储物品的特殊性也加入模型中，同时进一步优化算法性能。参考文献：王军锋自动化立体仓库储位分配策略优化的研究 北京：北京邮电大学，：，（）：，：，：，：，（）：，：，：，：，（）：，：，：，：，：轻工机械 年第期