基于指派问题的自动化仓库复合出入库作业优化.pdf

基于指派 问题 的自动化仓库 复合 出入库作业优化 杨磊刘会谢晓飞招智生何梦溪 华南理工大学经济与贸易学院 广州 5 1 0 0 0 6 摘要 研究了自动化立体仓库中的出入库调度优化问题 首先对堆垛机的作业类型和时间进行了分析和 对比 然后提出利用指派问题的匈牙利算法对堆垛机的复合作业循环时间进行优化 最后将该算法运用于实例 进行优化 并与动态规划 的逆序递归求解进行 了比较 得 H 指派问题的匈牙利算法更优的结论 关键词 自动化立体仓库 作业时间 指派 问题 匈牙利算法 优化 中图分类号 T P 2 7 8 文献标识码 A 文章编号 1 0 0 1 0 7 8 5 2 0 1 0 l1 0 0 2 0 0 5 Abs t r a ct The p a p e r s t u d ie s t h e d is pa t ch ing o pt imiz a t io n pr o b le m wit h a u t o ma t ic s t o r a g e a nd r e t r ie v a l s y s t e m a n a ly z e s a n d co mp a r e s t h e o p e r a t i o n t y p e a n d t im e o f t h e s t o r a g e a n d r e t r ie v a l ma ch i n e S R M fir s t ly t h e n p r o p o s e s t h e o p t im i z a t io n f o r t h e co mp le x o p e r a t io n cy cle t ime o f t h e S RM b y u s in g t h e Hu n g a r ia n a lg o r it h m a n d fi n a lly u t iliz e s t h is a lg o r it h m int o p r a ct ica l e x a mp le f o r o p t imiz a t io n a n d e o n lp a r e s it wit h t h e d y na mic p r o g r a mming al g o r it hm t hu s t o r e a ch t he co ne lu s io n t h a t t h e Hu n g a r ia n is mo r e a d v a n t a g e o u s Ke ywo r ds a ut o ma t ic s t o r a g e a nd r e t r ie v a l s y s t e m o pe r a t io n t ime a s s ig n me nt pr o ble m Hun g a r ia n al g o r it h m o pt i miz a t io n 近些年 随着 国 内制造业和进 出 口贸易的高 速增长 中国的物流业有 了长足 的发 展 自动化 立体仓库也越来越 多地应用 于各个行业 自动化 上体仓库具有存储 容量大 空 间利用 率高 可靠 及安全 高等优点 自动化立体 仓库 的出现和 发展大大提 高了仓库 的作业效率 特别 是出入库 效率 自动化立体仓 库的出入库效 率直接影响着 整个物流 系统 的效率 因而研究 如何提高 自动化 立体仓库 的作业效率十分必要 本文从 自动化立体仓 库 中的关键设 备 堆 垛机 的作业 时间人手 分析对 比了堆垛 机的单一 作业循环 时间和复合作业循环 时间 并 通过指派 问题 的匈 牙 利算 法对 出入库 的调 度进 行 了优 化 分析 1 作业时 间的计算 堆垛机的作业循环 时间是 自动化立体仓库总 体设计 的 1个重要参数 它决定 了系统是否能满足 出 入库 能力 的需 要和堆 垛机性 能参 数 的选 择 堆垛机的出 入库搬运 分为单一 作业循环和复合 作业循环 2种 如图 1 所示 单一作业循环时间 f fl l I f Il o f Il 式 中 为堆垛机从原始位置处至 p点往返运 华南理工大学大学生创新基地建设项 目 教育部人文社会科 学研究项 目基金 0 9 Y J C 6 3 0 0 8 5 华南理T 大学 中央高 校基本科研业 务费专项资金资助 2 0 0 9 S Z 0 0 2 2 3 张佳伟 楼佩煌 输送胶带跑偏 白动化检测及液压矫 正技术 J 机械T程师 2 0 0 8 1 0 2 6 2 8 4 王春奇 李学光 聂刚 等 一种新 自动纠偏装置 的结构和工作原理 J 山东煤炭科技 2 0 0 9 0 3 81 8 2 5 王存 明 新型带式输送机尾带 自动纠偏装置 J 起重 运输机械 2 0 0 5 1 1 2 7 2 9 6 高志安 郭峰 壬峰 等 基于 I n T o u ch的带式输送 一 2 0 一 作 地 机实 时监 控 系 统 J 煤 矿 机 械 2 0 0 8 1 2 1 2 0 1 2 2 者 址 邮 编 收稿 日期 董 甲东 安徽省安庆市菱湖南路 1 2 8号安庆师范学院现 代 教育技术 中心 2 46 01l 2 01 0 0 4 1 5 起重运输机械 2 0 1 0 1 1 行 水平 起升 的时间 t q o 为堆垛机从原始位置 处至 q点往返运行 水平 起升 的时间 为单 一 作业循环 中固定不变的动作时间总和 包括定 位 货位探测 货叉作业循环等 图 1 作业路径及运行所需时间 复合作业循环时间 1 TT l 2 T t p q t o 2 式 中 t 为堆垛机从原始位置处至 P点 水 平 起升 然后运行到 q点 最后返 回原始位置 处的时间 t 为复合作业循环 中固定 不变 的动作 时间总和 包 括定位 货位 探测 货 又作 业循环 等 2单一作业与循环作 业的时间比较 由于堆垛机 的水平运动 和垂 直运动是 可 以同 时进行的 所 以计 算堆垛机运行时 间时选取 一次 运行最长的那段 时间 设 和 分别 为堆垛机的 水平运行速度和垂直运行速度 以堆垛机 的起 始位置为起 点 将仓库货架 货 位模拟为平面直角坐标 假设 P点在仓库 中的坐 标为 l Y 1 则 t 2 ma x 1 y l 同 理 2 m a x 2 2 另外 不管是在单 一作业或者 是复合作业 的 情况下 堆垛机 的固定不变 的动作 时间总和基本 是一样的 即 t t 假 设 P点 到 q点的水平距 离为 垂直距离为 则在复合作业情况下有 f p l q t p q m a x L v L y vt t m a x L v L y v 了l叩 q j 故 一 f 了1 一 m a x L Lm 2 m a x L x f IIl 1 印 一 J 由图 1可知 显然 1 叩 了 1 m a L 故 t t 复合作业更加节省堆垛机 的运 行时间 起重运输机械 2 0 1 0 1 1 3 复合作业的优化策略 对 自动化立体仓库进行路 径优化 即追求完 成所有任务操作所需 时间的最小化 根据前 面的 背景知识可知 复合 作业出入库方式 比单一作业 出入库方 式节约时间 因此 这里仅对复 合任务 进行路径优化 如图 1所示 0点代表巷道 口 P点代表入库 位置 q点代 表出库位置 t 表示复合作 业周期 0 表示堆垛机从 点运行 到 点并进行相关作业 所需的时间 则复合作业周期 t t 叩 t t 完 成任务所需的总时间 t t t t k i 1 J 1 式 中 r n表示入库货位 的数量 n表示出库货 位的数量 表示巷道 口到入库货位进行操作所需 时间 表示 出库 口到巷道 口进行操作所需时间 袁 示从配对好的入库货位 i到出库货位 所需要 的时间 t 表示从 配对好 的入库货位 或者出库货 位到巷道 口所需要的时间 t t 之和 为固 定 值 而任 务 选择和 配 i 1 1 对将影 响复合作业的优化效果 所 以 优化 目标变 为寻找一个最佳任务配对的 组合 使 t t 之和最小 优化策略如下 1 将一批任 务分成 出库 任务 和入库 任务 数量分别为 m和 2 并得到它们的货位坐标 2 计算所有入库货位与 出库货物之 间的路 程 以及运行时间 并用表格将 数据列 出 假设表 格的行表示入库货位 列表示出库货位 3 如果 m n 即入库货位数量大于出库数 量 则在表中添加 m一 2行 表格 中的数值为 由 0 点到入库货位的运行时间 4 如果 n m 即出库货位数量大于入库数 量 则在表 中添加 n m列 表格中的数值为由出 库货位到 0点的运行时间 5 模型可理解为厂个人分担厂项工作的指派 问题 以求 得最 小消耗 少量 的组合对可采用库 恩提 出的有关指派问题 的匈牙利算法进行笔算得 出最优解 大量 的组合对可采用 编程 的方法进行 组合 一 21 6 对 于最优解 已确定 的组合对之间的执 行顺序对整体 的优化没有影 响 可 先进 行组合对 的复合作业 而配对好 的则进行单独作业 4利用指 派 问题 建立数 学模型 并用匈 牙 利 算法进行求解 引入变量 表示指派入库 口 i与出库 口 J 之 间的关系 并令 l 当出库 口 i与入库 口配对组成复合作业 x O 一 1 0 当出 库口i与入库口 未配对组成复合作业 数学模型为 C k 1 1 2 k 1 个入库 口与 1 个出库 口组合 k 1 i 1 2 k 1 个出库 口与 1 个入库 口组合 其中 c 表示进行复合作业时 堆垛机从入库 口 i到出库 口 所需 时间 而每个约束条件则表示 每个人 口或者每个 出口最多能与 1个 出口或入 口 组合形成 1 个复合作业 采用匈牙 利算法 直接 进行 求解 基本 原理 为了实现 目标极小 在 系数矩 阵元 素 C 0的条 件下 如果能使矩阵具有 1组处 于不 同行不 同列 的0元素 C 0 画上 圈符 号 表示 对应 该元素的决 策变量 1 未 画圈元 素对应 的决 策 变量 o 那么目 标函 数值 c 0为最小 这样 的组合解 就是最 优解 具 体步 骤如下 1 建立新矩阵 矩阵的内容 为堆垛机从 出 口到人 口运行所需要的时间 即矩阵第 i行第 J 列 的值为 c 根据 m与 n的关系 添加行和列使矩 阵成为行数与列数一致的矩阵 2 从矩阵的每行 或列 减去或加上 1个 常数 称为行位势 或者 称为列位势 构 成新矩阵 c c u f 使 其每行 每列 一 2 2 一 都出现 0元素 3 画圈 由某行或列 中 0元 素最少 的行或 列开始 将 0画成 同时划去 所在 的行和列 的其他 0元素 若 元素的数 目等于矩 阵的阶数 则得到这个指派 问题的最优解 若 m r 9 6 1 3 6 1 4 1 9 6 I 1 5 6 1 0 8 6 8 l f 2 0 4 7 2 1 2 1 9 2 l L 2 2 8 1 8 8 1 9 2 2 4 8 15 6 10i 68 6 98 6 9 67 2 12 19 2 7 28 18 8 19 2 24 8 18 68 J 1I I l 20 4 I 1 L22 儿 J r 0 4 4 4 lo 1 厂 0 4 4 4 8 l l 9 6 4 8 0 2 I I 9 6 4 8 0 0 f l l l l l 1 3 2 0 4 8 1 2 f I 1 3 2 0 4 8 1 0 f L 4 0 0 4 6 j L 4 0 0 4 4 j l 4 0 0 4 4 J 4 由于 的数量为 3 矩阵的阶数 4 故需 要进入下一步 画 并画线 I J v l3 2 4 8 1 0 4 l 0 4 4 5 当所 有的 0元 素都被直线覆盖后 增加 相应缺少 的0元素 0 u V l3 2 4 8 1 0 4 I 1 0 4 4 K B 1 2 8 4 4 9 3 6 l 1 0 3 6 4 4 4 4 8 9 6 5 2 0 1 2 8 4 4 9 6 3 6 0 0 3 6 6 继续画圈 于是得到矩阵 r 4 4 4 4 8 l 9 6 5 2 0 I I 1 2 8 4 4 9 6 I L 3 6 0 3 6 对应矩阵原来 的意义可知 1 2 4 6 7 3 5 0是最佳配对 完成任务所需 的时间为 1 8 3 2 S 如果不采用优化算法 直接以原顺序 0 1 2 3 4 5 6 7 0执行 则完成任务所需要 的 一 2 3 伸 缩 臂 叉 车 转 向 系 统 的 设 计 汪 小莹 陕西建工集团总公司 西安7 1 0 0 0 3 摘要 介绍了伸缩臂叉车转向系统的组成和设计要求 并通过对负荷传感转向系统原理的研究 设计了 伸缩臂叉车负荷传感转 向系统 关键词 伸缩臂叉车 转向系统 负荷传感 设计 中图分类号 T H 2 4 2 文献标识码 A 文章 编号 1 0 0 1 0 7 8 5 2 0 1 0 1 1 0 0 2 4 0 4 Ab s t r a ct T h e p a p e r in t r o d u ce s t h e d e s ig n r e q u ir e me n t s a n d t h e co mp o s it io n o f t h e s t e e r in g s y s t e m o f t h e t e lh a n d le r a n d d e s ig n s t h e lo a d in g s e n s in g s t e e ri n g s y s t e m f o r t h e t e lh a n d le r t h r o u g h t h e s t u d y in g t h e t h e o r y o f t h e lo a d in g s e n s in g s t e e r ing s y s t e m Ke y wo r d s t e lh a n d le r s t e e r in g s y s t e m lo a d in g s e n s in g d e s ig n 伸缩臂叉车将汽车起重机 的伸缩臂 结构与传 统叉车的装卸功能有机地结合 可通过 改变其 伸 缩臂的长度 来 达到要求 的作业高度和距 离 具 有有效作业距离大 作业高度高 可越障作业 一 机多用 的特 点 可以配属多种快换装置 实现 叉取 装载 举升 等作 业 伸缩臂 叉车广泛应 用 于军事 农业 建筑行业 集小型起重机 装 载 机 叉车 高空作业平 台 农用拖 拉机 的功 能于 一 身 是一种多功能搬 运 举升设 备 是现代工 业 建筑业理想的多功能装卸搬运机械 建筑型伸缩臂叉 车是为 了适应建 筑领 域使用 的实际需要 在基本型叉 车的基础上 强 化了在 建筑工地定点输运物料 的能力 为 了扩 大伸缩臂 的作业范围 该型叉车设计成 上下 2部分 下部 分为行走底盘 上部分为驾驶操作 与伸缩臂装置 2部分由回转支承连接 这类叉 车既具备 了小型