集成 自动 导引 车 路径 规划 的 智能 制造 数字化 车间 设备 布局 优化 方法
葛华辉 ， 冯毅雄 ， 密尚华 ， 谭建荣 ， 王云
（ １ ． 浙江大学 浙江省 先进 制造 技术 重点 研究 实验室 ， 浙江 杭州 ３１００２７ ； ２ ． 浙江大学 流体动力 与 机电 系统 国家 重点 实验室 ， 浙江 杭州 ３１００２７ ）
摘要 ： 智能 制造 数字化 车间 具有 自动 导引 车 （ ＡＧＶ ） 、 加工 设备 高度 集成 的 特点 。 针对 智能 制造 数字化 车间 布局 和 ＡＧＶ 路径 规划 分开 优化 ， 使得 某 Ｋ 域 的 物料 搬运 过于 集中 ， 导致 该 区域 ＡＧＶ 搬运 工作量 繁重 ， 影响 ＡＧＶ 路径 规划 的 问题 ， 建立 了 以 物流 运输量 最小 ， 物料 搬运 时长 最 短 以及 ＡＧＶ 数量 最少 为 目标 的 智能 制造 数字化 车间 布局 和 ＡＧＶ 路径 规划 集成 优化 模型 。 提出 一种 改进 的 带 精英 策略 的 快速 非 支配 排序 遗传算法 ， 采用 系统化 布置 设计 法来 生成 部分 初始 种群 ， 增加 初始 种群 分布 ， 防止 陷入 局部 最优 ； 将 不 等 长 的 双链 染色体 与 疫苗 接种 策略 引人非 支配 排序 遗传算法 ， 提 髙 了 算法 的 寻优 速度 和 精度 ； 最后 求解 得到 一组 Ｐａｒｅｔｏ 解集 ， 供 决策者 优 中选优 。 通过 实例 验证 了 所 提 方法 的 有效性 。
关键词 ： 智能 制造 ； 车间 布局 ； 自动 导引 车 路径 规划 ； 改进 的 带 精英 策略 的 快速 非 支配 排序 遗传算法 ； 疫苗 接种 策略
〇 引言
制造业 是 国民经济 的 基础 ， 是 科技进步 、 技术创新 的 主战场 ， 是 供给 侧 结构性 改革 的 关键 领域 。 随着 科技 创新 进步 和 信息技术 发展 ， 制造业 与 互联网 等 新 技术 的 融合 发展 日趋 紧密 ， 并 向 智能化 、 信息化 、 自动化 转型 ， 智能 制造 成为 制造业 未来 发展 的 主要 方向 。 智能 制造 数字化 车间 高度 融合 了 机械设备 、 传感器 设备 等 硬件 、 边缘 计算 、 控制 、 数据 采集 与 操作系统 。 然而 ， 现在 有些 传统 车间 还 主要 依靠 人工 驾驶 叉车 进行 物料 运输 ， 效率 不高 。 为 推进 智能 制造 ， 智能 制造 数字化 车间 改造 刻不容缓 ， 采用 自动 导引 小车 （ Ａｕｔｏｍａｔｅｄ Ｇｕｉｄｅｄ Ｖｅｈｉｃｌｅ ， ＡＧＶ ） 来 代替 传统 人工 叉车 进行 物料 运输 从而 实现 车间 自动化 。 ＡＧＶ 应 具备 自动 呼叫 、 信息 传感 、 节拍 控制 等 功能 ， 以 达到 提高 生产 效率 的 目的 。 ＡＧＶ 的 路径 规划 与 设备 布局 情况 有 密切关系 ， 设计 智能 制造 数字化 车间 设备 布局 和 ＡＧＶ 路径 规划 方案 对 制造 生产 实现 智能化 至关重要 。 智能 制造 数字化 车间 下 的 设备 布局 问题 （ Ｆａｃｉｌｉｔｙ Ｌａｙｏｕｔ Ｐｒｏｂｌｅｍ ， ＦＬＰ ） 是 指 车间 内 设备 的 布置 ， 根据 某些 约束条件 ， 确定 最 有效 的 安排 ， 使得 物流 运输 距离 短 、 物流 运输成本 或者 设备 所 占 空间 尽可能 小 。 车间 设备 布局 是否 科学 、 合理 ， 直接 影响 ＡＧＶ 路径 规划 。
目前 ， 国内外 很多 学者 为 解决 不同 类型 的 ＦＬＰ 问题 ， 做 了 大量 的 研究 。 ＭａｒｃｅｌｌｏＢｒａｇｌｉａ 等 在 对 车间 单行 设备 布局 问题 研究 中 ， 以 搬运 费用 和 机器 安装 费用 最小 为 优化 目标 ， 建立 车间 布局 模型 ； ３１１ 〇 等 研究 了 在 半圆 布局 、 Ｕ 型 布局 等 单排 布局 下 ， 以 物料 运输成本 、 面积 利用率 、 设备 和 劳动力 利用率 为 目标 的 求解 ； ？ 明 １１ 化等 在 设备 的 长度 和 宽度 不 确定 的 条件 下 进行 建模 ， 根据 决策者 的 需求 ， 提出 一种 自 适应 的 算法 来 确定 健壮 布局 ； Ａｍａｒ 等 提出 一种 用于 设施 布局 设计 的 双 目标 分辨率 模型 ， 目标 是 设计 一个 平衡 环境 限制 和 生产 效率 要求 的 制造 系统 ； Ｓａｆａｒｚａｄｅｈ 等 提出 了 一种 具有 模糊 约束 的 非线性 多 整数 规划 模型 ， 使用 ３ 种 不同 的 交叉 的 遗传算法 求解 多行 设备 布局 问题 ； 李聪波 等
针对 再 制造 工艺 过程 的 不确定性 问题 ， 以 再 制造 物流 成本 和 再 制造 工艺 单元 重 布置 成本 最小 为 目标 ， 建立 了 再 制造 车间 设施 动态 布局 模型 。 针对 不同 约束条件 下 的 车间 布局 模型 ， Ｅｌ－Ｂａｚ 等 利用 改进 的 遗传算法 ， 以 物流 运输成本 为 目标 函数 ， 解决 了 制造 系统 设计 中多 产品 、 多线 布局 、 循环 布局 等 不同 生产 环境 下 的 设备 布局 问题 ； Ｍａｔａｉ 等 提出 一种 改进 的 模拟退火 方法 ， 利用 决策者 生成 的 不同 目标 权重 来 解决 多 目标 设施 布局 问题 ； Ａｍａｒａｌ 等 提出 一个 分支 一 剪切 算法 来 求解 单行 设施 布置 问题 ； Ｇｏｎｃａｌｖｅｓ 等 针对 用于 不 等 面积 设施 布局 问题 ， 提出 一种 具有 偏差 的 随机 密钥 遗传算法 ； Ｍａｌｌｉｋａｒｊｕｎａ 等 提出 一种 结合 遗传算法 和 模拟退火 算法 来 优化 柔性 制造 环境 下 的 环形 布局 ； 郭 源源 等 将 粒子 群 优化 算法 结合 系统化 布置 设计 法 ， 求解 面向 车间 布局 的 连续 空间 优化 问题 ； 张屹 等 针对 多 约束 、 多 变量 、 非线性 的 模型 ， 分别 运用 差分 元胞 多 目标 遗传算法 、 经典 元胞 多 目标 遗传算法 和 带 精英 策略 的 快速 非 支配 排序 遗传算法 （ ｆａｓｔｅｌｉｔｉｓｔ Ｎｏｎ－ｄｏｍｉｎａｔｅｄ Ｓｏｒｔｉｎｇ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ， ＮＳＧＡ－ｎ ） 对 测试函数 及 车间 设备 布局 模型 进行 求解 ； 何坤 等 以 物流 运输 费用 最小 和 车间 面积 利用率 最大 为 目标 ， 结合 模拟退火 算法 中 的 并行性 和 遗传算法 中 收敛 速度 快 的 特点 ， 提出 一种 新 的 算法 ； 刘琼 等 设计 了 一种 多 目标 果蝇 优化 算法 来 求解 车间 布局 和 调度 集成 优化 模型 ； 刘琼 等 提出 一种 改进 蛙跳 算法 求解 以 车间 物料 搬运 费用 和 面积 费用 最小化 为 目标 的 多 目标 鲁棒性 布局 优化 模型 。
综上所述 ， 目前 学术界 在 设备 布局 问题 的 建模 上 考虑 的 因素 和 约束条件 越来越 多 ， 如 考虑 车间 制造 过程 碳 排放 、 再 制造 工艺 过程 不确定性 或 车间 布局 和 车间 调度 集成 优化 等 。 近些年 ， 求解 设备 布局 问题 的 方法 基本 采用 智能 优化 算法 ， 但 综合 考虑 智能 制造 数字化 车间 设备 布局 和 ＡＧＶ 路径 规划 问题 的 相关 研究 还 较 少 ， 何 永乐 以 禁忌 搜索算法 进行 求解 设备 环形 布局 和 路径 规划 二者 集成 优化 问题 ； 刘庄成 提出 一类 柔性 车间 设备 布局 和 ＡＧＶ 系统 规划 集成 的 协同 设计 模型 。 在 智能 制造 中 ， ＡＧＶ 物料 运输 将 代替 传统 的 人工 叉车 搬运 ， ＡＧＶ 的 应用 不仅 能够 实现 智能 制造 车间 的 自动化 管理 ， 还 能 提高 系统 柔性 、 灵活性 以及 生产 效率 。 智能 制造 数字化 车间 布局 和 ＡＧＶ 路径 规划 都 将 影响 智能 制造 数字化 车间 的 生产 效率 和 改造 成本 。 本文 针对 考虑 ＡＧＶ 的 智能 制造 数字化 车间 设备 布局 问题 ， 建立 了 智能 制造 数字化 车间 布局 与 ＡＧＶ 路径 规划 集成化 模型 ， 结合 系统化 布置 设计 （ Ｓｙｓｔｅｍ Ｌａｙｏｕｔ Ｐｌａｎｎｉｎｇ ， ＳＬＰ ） 法 与 免疫 接种 策略 ， 提出 一种 改进 的 ＮＳＧＡ－ＩＩ ， 以 快速 求解 集成 模型 。 通过 建立 数字化 模型 ， 模拟 物理 系统 中 发生 的 情况 ， 在 物理 系统 与 数字化 模型 间 的 双向 信息 传输 ， 快速 优化 和 调整 设备组 之间 的 物料 运输 、 ＡＧＶ 的 路径 规划 等 ， 提高 智能 制造 数字化 车间 的 生产 效率 。
１ 智能 制造 数字化 车间 布局 和 ＡＧＶ 路径 规划 集成 模型
１．１ 问题 描述 及 相关 假设
为 方便 问题 的 研究 ， 智能 制造 数字化 车间 布局 和 ＡＧＶ 路径 规划 做 以下 假设 ： ① 布局 的 设备组 ， 忽略 其 形状 细节 ， 假定 都 为 矩形 结构 且 尺寸 大小 相同 ； ② 各 设备组 按 多行 线性 布局 ， 当 车间 宽度 不够 时 ， 采取 自动 换行 布局 ； ③ ＡＧＶ 物料 运输 路径 只能 为 水平 或 垂直 方向 ； ④ 设备组 之间 的 物料 搬运 无 优先级 之分 ； ⑤ 物料 存放 在 设备组 的 中心 处 ； ⑥ 中转 缓存 区 位置 均 设置 在 相邻 两 设备组 中间 ； ⑦ ＡＧＶ 物料 运输 时 忽略 中转 缓存 区 的 尺寸 ； ⑧ ＡＧＶ — 次 运输 一批 物料 。
智能 制造 数字化 车间 布局 和 ＡＧＶ 路径 规划 模型 如图 １ 所示 。 图中 为 车间 的 水平 方向 ； ｙ 为 车间 的 垂直 方向 ； 工厂 车间 有 ｎ 组 设备 ， 分别 表示 为 ｅｑｕａｔｉｏｎ ； ｌ 和 Ｗ 分别 为 设备组 Ｍ 水平 方向 和 垂直 方向 上 的 长度 ； ｘ 和 ｙ 分别 表示 设备组 或 中转 缓存 区 的 中心点 在 水平 方向 和 垂直 方向 上 的 位置 坐标 ； Ｓ 表示 中转 缓存 区 ； 为 中转 缓存 区 和 相邻 设备组 在 水平 方向 上 的 间距 ； ＾ 为 中转 缓存 区 和 相邻 设备组 在 垂直 方向 上 的 间距 ； 虚线 、 点画 线 和 双点 画线 为 不同 区段 的 ＡＧＶ 路径 规划 示意图 。
１．２ 目标 函数 的 建立
（ １ ） 智能 制造 数字化 车间 内 设备组 之间 物流 运输量 最小
ｅｑｕａｔｉｏｎ 式 中 ： Ｃ 为 智能 制造 数字化 车间 内 设备组 之间 物流 运输 总量 ； ？ 为 在 生产 过程 中 从 设备组 ？ 搬到 设备组 的 物料 搬运 量 ； 为 车间 布局 中 设备组 Ｍ ， ？ 和 设备组 Ｍ ， 之间 的 距离 。
当 ＡＧＶ 的 数量 为 １ 时 ， ＡＧＶ 物料 运输 每次 都 能 以 最 短 路径 运输 物料 。 按照 曼哈顿 距离 来 计算 设备组 之间 的 最 短距离 。 当 运输 任务 繁重 时 ， 在 规定 时间 内 ， 一辆 ＡＧＶ 不能 满足 运输 要求 ， 需要 采用 多辆 ＡＧＶ 进行 物料 运输 。 这时 要 防止 ＡＧＶ 出现 碰撞 、 死锁 和 长时间 滞留 现象 。 本文 采用 改进 的 区段 式 ＡＧＶ 系统 来 防止 车辆 碰撞 现象 。 区段 式 系统 是 在 Ｓｉｎｒｉｅｃｈ 等 提出 的 区段 式 轨道 设计 方式 基础 上 产生 的 系统 ， 该 系统 将 ＡＧＶ 的 轨道 分成 许多 互不 交错 的 区段 ， 如图 ２ 所示 ， ％ 代表 第 ６ 段 区段 的 区段 号 。 传统 区段 式 系统 ， 先 用 一条线 将 设备组 依次 连接 ， 设备组 位置 按 连接线 依次 编号 ， 在 两个 设备组 之间 的 连线 上 可以 设置 中转 缓存 区 。
一个 区段 间 的 设备组 数量 应 大于 等于 ２ ， — 个 区段 只有 一台 ＡＧＶ ， ＡＧＶ 可以 在 轨道 线上 双向 行驶 。 当 物料 需要 在 区段 间 运输 时 ， 如 设备组 Ｍ ， — 设备组 叫 ， 先 用 区段 ＆ 上 工作 的 ＡＧＶ 将 物料 从 设备组 Ｍ ， 运输 到 区段 ｗ 和 区段 ９２ 之间 的 中转 缓存 站 Ｓ ， 再 通过 区段 仍上 工作 的 ＡＧＶ 将 物料 从中 转缓 图 １ 智能 制造 数字化 车间 布局 和 ＡＧＶ 路径 规划 示意图 存站 Ｓ！ 搬运 至 设备组 Ｍ ； 。 这种 区段 式 ＡＧＶ 系统 可以 有效 地 防止 ＡＧＶ 之间 发生 干涉 ， 增加 设备组 数目 和 中转 缓存 区 数目 对 整个 系统 影响 不 大 ， 系统 具有 很强 的 弹性 ， 但是 设备组 — 设备组 ｉＷ ， 的 运输 路径 长度 变 大 。
根据 区段 式 ＡＧＶ 系统 划分 得到 的 区段 ， 为了 优化 区段 中 的 ＡＧＶ 物料 运输 路径 ， 改进 后 的 设备组 ？ 设备组 Ｍ ， ？ 路径 示意 如图 ３ 所示 。 两段 ＡＧＶ 物料 运输 路径 互不 干扰 。 则 Ｍ ， — Ｍ ， 物料 运输 路径 为 ： ｅｑｕａｔｉｏｎ 式 中 ： ？ 表示 在 车间 布局 中 设备组 Ｍｆ 和 中转 缓存 区 ５ ： 之间 的 距离 ， ＤＳｖ 表示 设备组 Ｍ ， 和 中转 缓存 区 ５ ？ 之间 的 距离 ， ＤＳＡ＋Ｉ 表示 转 缓存 区 Ｓ ， 和 中转 缓存 区 ？＋１ 之间 的 距离 。
（ ２ ） 物料 搬运 时长 最 短
车间 中 设备组 之间 的 物料 搬运 主要 考虑 人工 辅助 上下 物料 与 ＡＧＶ 运输 ， 其中 由于 操作 工人 技能 差异 ， 体能 差异 等 多种 因素 的 影响 ， 工人 参与 上下 料 是 车间 物流 中 存在 的 一类 不 确定 因素 。 假设 工人 一次 装载 所用 时间 大致 呈 右 偏 分布 ， 实验 可 得 工人 完成 一次 装载 的 最 乐观 时间 为 Ｇ 、 最 可能 时间 ｉｃ 、 最 悲观 时间 化 。 本文 采用 三时 估计 法将 不确定性 问题 转换 为 确定性 问题 来 计算 ， 则 工人 完成 一次 装载 的 平均 时间 ｅｑｕａｔｉｏｎ ， 方差 ｅｑｕａｔｉｏｎ 由 中心 极限 定理 可知 ， 工人 一次 装载 物料 的 时间 乃应 服从 正态分布 ： ｅｑｕａｔｉｏｎ 。 同理 可 求得 工人 一次 卸载 物料 的 时间 Ｔ ？
。 物料 搬运 时长 由 区段 中 最长 的 物料 搬运 时 长 决定 ， 每个 区段 中 的 物料 搬运 时长 由 三 部分 组成 ， 如图 ４ 所示 。 以图 ４ 区段 ％ 为例 ： 第一 部分 时间 为 区段 ９ ＊ 中 设备组 之间 的 物流 搬运 时 长 ； 第二 部分 为 中转 缓存 区 之间 的 物流 搬运 时 长 ， 即 中转 缓存 区民 ＾ 与 中转 缓存 区次 之间 的 物料 搬运 时 长 ， 这段 时长 由 区段 办 ？ 中 的 设备组 和 区段 中 的 设备组 之间 的 物料 运输量 决定 ； 第三 部分 为 区段 中 设备组 与 中转 缓存 区 ？， ？ 区段 ％ 中 设备组 与 中转 缓存 区 ＆ 之间 的 物流 搬运 时长 之 和 。