仓库管理-自动化立体仓库系统课程设计教材(doc 37页)

交通运输学院课程设计 I 目录 引言 1 1 自动化立体仓库 .2 1.1 概述 .2 2 货位优化 .3 2.1 设计条件 .3 2.2 计算系数矩阵 .3 2.2.1 符号假设 .3 2.2.2 已知条件 .4 2.2.3 公式计算过程 .4 2.3 运用匈牙利算法求解 .6 2.4 总结 13 3 堆垛机路径优化 15 3.1 设计条件 .15 3.2 设计要求 16 3.3 设计方法 16 3.4 求解过程 16 3.4.1 最近邻点法求堆垛机运行路径 19 3.4.2 最近插入法求堆垛机运行路径 26 3.5 总结 34 参考文献 .36 交通运输学院课程设计 1 引言 自 动 化 立 体 仓 库 产 生 和 发 展 是 生 产 力 高 度 发 展 和 城 市 化 进 程 不 断 发 展 结 果 。 计 算 机 的 出 现 和 应 用 ， 自 动 化 仓 库 的 产 生 。 仓 库 空 间 向 立 体 化 方 向 发 展 个 ， 货 位 向 空 间 延 伸 ， 高 层 货 架 和 与 之 配 套 的 新 型 装 卸 搬 运 机 械 与 周 边 设 备 出 现 ， 立 体 仓 库 产 生 。 自 动 化 立 体 仓 库 是 指 在 高 层 货 架 用 货 箱 或 托 盘 储 存 货 物 ， 用 电 子 计 算 机 管 理 和 控 制 巷 道 式 堆 垛 机 及 其 它 机 械 ， 不 需 要 人 工 作 业 而 实 现 收 发 作 业 的 仓 库 。 自 动 化 立 体 仓 库 是 一 种 集 信 息 、 储 存 、 管 理 于 一 体 的 高 技 术 密 集 型 机 电 化 产 品 ， 堆 垛 机 和 高 层 货 架 是 其 关 键 设 备 。 随 着 电 子 技 术 与 控 制 理 论 的 发 展 ， 各 种 控 制 方 法 被 引 入 堆 垛 机 的 控 制 。 货 位 优 化 和 巷 道 式 堆 垛 机 的 路 径 优 化 成 为 自 动 化 立 体 仓 库 的 必 要 工 作 ， 因 此 本 次 课 程 设 计 针 对 这 两 点 做 出 了 详 细 的 介 绍 。 货 位 优 化 是 用 来 确 定 每 一 品 规 的 恰 当 储 存 方 式 ， 在 恰 当 的 储 存 方 式 下 的 空 间 储 位 分 配 。 货 位 优 化 追 求 不 同 设 备 和 货 架 类 型 特 征 、 货 品 分 组 、 货 位 规 划 、 人 工 成 本 内 置 等 因 素 以 实 现 最 佳 的 货 位 布 局 ， 能 有 效 掌 握 商 品 变 化 ， 将 成 本 节 约 最 大 化 。 货 位 优 化 为 正 在 营 运 的 仓 库 挖 掘 效 率 和 成 本 ， 并 为 一 个 建 设 中 的 配送中心或 仓 库 提 供 营 运 前 的 关 键 管 理 作 准 备 。 交通运输学院课程设计 2 1 自动化立体仓库 1.1 概述 自动化立体仓库作为现代化物流系统中的重要组成部分,是一种多层存放货物的高 架仓库系统,主要由高层货架、巷道堆垛机、出入库输送设备、自动控制与管理系统所 组成。出入库辅助设备及巷道堆垛机能够在计算机管理下，完成货物的出入库作业、 实施综合库房管理并与上级管理系统联网，可以实现管理现代化、存取自动化，能按 指令自动完成货物的存取作业,并能对库存的货物进行自动化管理,是企业实现现代化 管理的重要手段。自动立体仓库在工厂自动化，弹性制造系统及电脑整合制造系统的 物流中占非常重要的位置。其目的不仅是为了储存物料、零件、半成品、成品的仓储， 更是密切配合制造工厂的产销计划与物料需求计划，妥善安排生产所需合理数量的物 料、零件，并尽量缩短其库存时间及避免了发生缺料、滞料，籍高架搬运车、输送机、 无人搬运车等，然后保管成品而依销售预定准进正确出货，提升服务水平，事合了计 划、库存、生产、出入物流的功能与管理，降低了生产成本。 其组成部分： （1）货架:用于存储货物的钢结构。主要有焊接式货架和组合式货架两种基本形式。 （2）托盘（货箱）：用于承载货物的器具，亦称工位器具。 （3）巷道堆垛机:用于自动存取货物的设备。按结构形式分为单立柱和双立柱两种 基本形式；按服务方式分为直道、弯道和转移车三种基本形式。 （4）输送机系统:立体库的主要外围设备，负责将货物运送到堆垛机或从堆垛机将 货物移走。输送机种类非常多，常见的有辊道输送机，链条输送机，升降台，分配车， 提升机，皮带机等。 （5）AGV 系统:即自动导向小车。根据其导向方式分为感应式导向小车和激光导向 小车。 （6）自动控制系统:驱动自动化立体库系统各设备的自动控制系统。以采用现场总 线方式为控制模式为主。 （7）储存信息管理系统:亦称中央计算机管理系统。是全自动化立体库系统的核心。 典型的自动化立体库系统均采用大型的数据库系统（如 ORACLE，SYBASE 等）构筑典型 的客户机/服务器体系，可以与其他系统（如 ERP 系统等）联网或集成。 交通运输学院课程设计 3 2.货位优化 2.1 设计条件 某自动化立体仓库采用 2 行 3 列的单元货格式货架存放货物，一共有 6 个货格， 每个货格存放一个托盘货物。货格以按列编码的形式进行编号，如图 2.1 所示。已知 其它参数假定如下：假设堆垛机在水平方向的行驶速度 Vx=3.0m/s，在垂直方向的行驶 速度 Vy=2m/s；货格大小为 L（长）W（宽）H（高）=1m1m0.8m；堆垛机初始 状态在原点 0 处；货格 j 的横坐标 和纵坐标 就是其所在的列和行，如货格 6 的坐jxjy 标为（3，2） 。现有 6 个托盘货物需要存放到货架上，货物的出入库频率如表 2.1 所示。 2 4 6 1 3 5 图 2.1 原始货格图 表 2.1 托盘货物出入库频率表 货物 频率 货物 频率 货物 频率 A 9 C 18 E 7 B 39 D 14 F 25 根据以上条件，利用匈牙利算法合理安排各托盘货物的存放位置。 2.2 计算系数矩阵 2.2.1 符号假设 1. 为第 i 种货物的出入库频率（次数） ，i=A，B，C，D ，E ，F；fi 2 ， 分别为货格 j 的横坐标和纵坐标，即货格 j 所在的列和行（距离巷道口最xjyj 近的列记为第 1 列，最底层记为第 1 层） ，j=1，2，3，4，5，6； 0 Vx Vy 交通运输学院课程设计 4 3 为水平方向的行驶速度；vx 4. 为垂直方向的行驶速度；y 5.L 为货格的长； 6.W 为货格的宽； 7.H 为货格的高； 8. 为堆垛机运行之货格 j 所用时间，该时间是堆垛机行进过程中水平方向和垂直方tj 向所用时间的最大值，j=1，2，3，4，5，6； 9. 为堆垛机将货物 i 向货格 j 存取时所花费的时间。cij 10. 公式为 =max （2.1）tj vyxjj HL1, 11. 计算系数矩阵中的系数： = （2.2）cijtfji 2.2.2 已知条件 =9， =39， =18， =14， =7， =25；fABfCDfEF =3.0m/s, =2.0m/s；LWH=1m1m0.8m；vxy 货格 1 的坐标为（ ， ）=(1,1)；货格 2 的货格为（ ， ）=（1，2） ；货格 3x1 x2y 的坐标为（ ， ）=（2，1） ；货格 4 的坐标为（ ， ）=（2，2） ；货格 5 的3 4 坐标为（ ， ）=（3，1） ；货格 6 的坐标为（ ， ）=（3，2） 。5y6 2.2.3 公式计算过程 1.计算： =max =max =1/3t1 vyxHL1,1 28.01,3 =max =max =2/5t2yx,22 ., 交通运输学院课程设计 5 =max =max =2/3t3 vyxHL1,33 28.01,3 =max =max =2/3t4yx,44 ., =max =max =1t5 vyxHL1,55 28.0,31 =max =max =1t6yx,66 ., 2.计算系数矩阵中的系数： = =91/3=3, = =391/3=13, cA1tf1cB1tf1 = =181/3=6, = =141/3=14/3, C D = =71/3=7/3， = =251/3=25/3；E1tf1F1tf1 = =92/5=18/5， = =392/5=78/5，cA22cB22 = =182/5=36/5， = =142/5=28/5，Ctf Dtf = =72/5=14/5， = =252/5=10；E22F22 = =92/3=6， = =392/3=26，cA3tf3cB3tf3 = =182/3=12， = =142/3=28/3，CD = =72/3=14/3， = =252/3=50/3；E3tf3F3tf3 = =92/3=6， = =392/3=26，cA44cB44 = =182/3=12， = =142/3=28/3，Ctf Dtf = =72/3=14/3， = =252/3=50/3；E44F44 = =91=9， = =391=39，cA5tfB5cBtf5 交通运输学院课程设计 6 = =181=18， = =141=14，cC5tf5cD5tf5 = =71=7， = =251=25；E F = =91=9， = =391=39，A6tf6B6tf6 = =181=18， = =141=14，cCcD = =71=7， = =251=25；E6tf6F6tf6 得到系数矩阵表： 表 2.2 系数矩阵表 A B C D E F 1 3 13 6 14/3 7/3 25/3 2 18/5 78/5 36/5 28/5 14/5 10 3 6 26 12 28/3 14/3 50/3 4 6 26 12 28/3 14/3 50/3 5 9 39 18 14 7 25 6 9 39 18 14 7 25 2.3 运用匈牙利算法求解 1. 匈牙利算法的步骤 第一步：建等效矩阵。 （1）从系数矩阵的每行元素中减去该行的最小元素。 （2）再从所得系数矩阵的每列元素中减去该列的最小元素。 第二步：找独立 0 元素，进行试指派。 （1）从只有一个 0 元素的行（或列）开始，给这个 0 元素加括号（0） ，表示这行 所代表的货格已有一种货物分配。然后划去（0）所在列（或行）的其它 0 元素，记作 “ ”，表示这列所代表的货物已指派。 （2）对只有一个 0 元素的列（或行）的 0 元素加括号（0） ，然后划去（0）所在 行（或列）的 0 元素，记作“ ”。 如果在（1） ， （2）两步中，遇到每一行和每一列都有两个或两个以上的 0 元素， 可任选一个加括号，同时把其所在行和列的 0 元素都划去。 货格 货物 交通运输学院课程设计 7 （3）重复（1） ， （2）两步，直到所有 0 元素都被加括号或打叉。 （4）加括号的 0 元素即为独立 0 元素，若其个数 m 等于矩阵的阶数 n，则已得到 问题的最优解。若 mn，则转入第三步。 第三步：用最少的直线覆盖所有 0 元素。 （1）对没有独立 0 元素的行打“” 。 （2）对以打“”的行中所含 0 元素的列打“” 。 （3）再对（2） ， （3） ，直到得不到新的打“”的行、列为止。 （4）将没有打“”的行和以打“”的列用直线覆盖，且直线的数目一定等于 独立 0 元素的个数。转第四步。 第四步：增加 0 元素。 从没有被直线覆盖的元素中找出最小元素。未被覆盖的元素都减去该最小元素， 而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩阵，转 第二步，重新确定独立 0 元素。 2.应用过程 (1)给系数矩阵表乘以 15， 从系数矩阵的每行元素中减去该行的最小元素 35、42、70、70、105、105再从所得系数矩阵的每列元素中减去该列的最小元素， 得到等效矩阵。 45190735122384015701537382 0032171865900231718 （2）从只有一个 0 元素的第 2 行开始，给这个 0 元素加括号（0） ，表示这行所 代表的货格已有一种货物分配。然后划去（0）所在列的其它 0 元素，记作“ ”，表 示这列所代表的货物已指派。对只有一个 0 元素的第 1 列的 0 元素加括号（0） ，然 后划去（0）所在行的 0 元素，记作“ ”。 交通运输学院课程设计 8 (0)2317(0)86590 独立 0 元素的个数 m=2矩阵的阶数 n=6，转入下一步。 （3）用最少的直线覆盖所有 0 元素。 对第 3、4、5、6 行打“” 。 对第 5 列打“” 。 得不到新的打“”的行、列，停止。 将没有打“”的行和已打“”的列用直线覆盖，且直线的数目一定等于独 立 0 元素的个数。 (0)2317(0)1865902317018 （4）增加 0 元素 从没有被直线覆盖的元素中找出最小元素 2。未被覆盖的元素都减去该最小元 素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩 阵，然后重新确定独立 0 元素。 03951681807361(0)23951681(0)87361 矩阵中独立 0 元素的个数 m=3n=6，用最少的直线覆盖所有 0 元素。 交通运输学院课程设计 9 (0)23951681(0)87361 （5）增加 0 元素 从未被直线覆盖的元素中找出一个最小元素，未被覆盖的元素都减去该最小 元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩 阵，然后重新确定独立 0 元素。 0139586142001736(0)103958614200()1736 矩阵中独立 0 元素的个数 m=3n=6，用最少的直线覆盖所有 0 元素.(0)173 （6）增加 0 元素 从未被直线覆盖的元素中找出一个最小元素 5，未被覆盖的元素都减去该最小元 素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩阵， 然后重新确定独立 0 元素。 交通运输学院课程设计 10 5(0)1524()8170359(0)165 （7）增加 0 元素 从未被直线覆盖的元素中找出一个最小元素 20，未被覆盖的元素都减去该最小 元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩 阵，然后重新确定独立 0 元素。 2503542811002857345125(0)354()2811028573(0)451 矩阵中独立 0 元素的个数 m=4n=6，用最少的直线覆盖所有 0 元素。2()354(0)28115087()423 5015024817035901655(0)1524()8170359(0)165 矩阵中独立 0 元素的个数 m=4n=6，用最少的直线覆盖所有 0 元素。 交通运输学院课程设计 11 （8）增加 0 元素 从未被直线覆盖的元素中找出一个最小元素 4，未被覆盖的元素都减去该最小元 素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩阵， 然后重新确定独立 0 元素。 2939012876510287341029039128765102873041 矩阵中独立 0 元素的个数 m=5n=6，用最少的直线覆盖所有 0 元素。29()3910287651287()410 （9）增加 0 元素 从未被直线覆盖的元素中找出一个最小元素 10，未被覆盖的元素都减去该最小 元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩 阵，然后重新确定独立 0 元素。 29049138760510271329049138761052713 矩阵中独立 0 元素的个数 m=5n=6，用最少的直线覆盖所有 0 元素。 交通运输学院课程设计 12 29049138761052713 （9）增加 0 元素 即从未被直线覆盖的元素中找出一个最小元素 7，未被覆盖的元素都减去该最小 元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩 阵，然后重新确定独立 0 元素。 290756143814002624829075601438140260248 矩阵中独立 0 元素的个数 m=5n=6，用最少的直线覆盖所有 0 元素。290756143810426248 (10）增加 0 元素 从未被直线覆盖的元素中找出一个最小元素 16，未被覆盖的元素都减去该最小 元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩 阵，然后重新确定独立 0 元素。 交通运输学院课程设计 13 450725036164981802450450725361640981802450 m=n=6,所以可以得到优化方案，将矩阵中的非 0 元素变为 0，将独立 0 元素变 为 1. 01011001 由解可得最优分配方案：A 货物放 5 货格，B 货物放 1 货格，C 货物放 4 货格，D 货 物放 3 货格，E 货物放 6 货格，F 货物放 2 货格。可以将得出的最优分配方案绘制成图 2.2 所示： 2 货物 F 4 货物 C 6 货物 E 1 货物 B 3 货物 D 5 货物 A 2.4 总结 面对成千上万的货格，立体仓库的货位存储优化已成为提高存取效率、降低成本 的关键，这需要对不同货物在仓库中的存放位置进行合理分配，这可通过利用匈牙利 算法来达到此目的。通过匈牙利算法得到的货位分配，可以对仓库中的货物储位进行 进行整合，使得货物的在货格中的存放位置最优、取放路径最优，从而达到进货和出 货时既经济又省时，同时可使物品的破损率达到最低，这对于提高企业的品牌起重要 作用。 0 Vx Vy 图 2.2 货物安放规划图 交通运输学院课程设计 14 通过这次课程设计我也认识到了货位优化对于一个仓库的重要性，这次学习使得 我也学习到了很多的物流知识，对于老师讲解过程中的关于自动化立体仓库的一些问 题也得到了充分理解，这次的课程设计过程中也让我学到很多，以及在设计过程中我 们应该要认真的积极态度，以及在整理课题任务时要仔细，只有这样才能保证我们在 做事情的过程中会减少误差。 交通运输学院课程设计 15 3 堆垛机路径优化 最短路径问题是图论中的一个经典问题。由于问题中边的权值往往可以从距离引 申为其他沿路径线性积累的度量，如：时间、花费等，所以最短路径问题在实际生活 中有着广泛的应用。 分层思想作为一个重要的思想，也有着许多应用，特别在是某些高效的方法中， 如：动态规划中的阶段划分、图论中基于求阻塞流的最大流算法等。将分层思想应用 到最短路径问题中，正是分层思想和最短路径问题的强强联合。因此正是基于此问题， 将最短路路径用于堆垛机的路径优化，以下便用最近邻点法和插入法进行堆垛机的路 径优化。 3.1 设计条件 4 (G) 8 (K) 12 (T) 16 (N) 20 (Q) 3 (D) 7 (J) 11 (H) 15 (E) 19 (S) 2 (B) 6 (F) 10 (I) 14 (V) 18 (R) 1 (A) 5 (C) 9 (M) 13 (P) 17 (L) 图 3.1 最终的货位规划图 随机从图 3.1 中的 20 个货格中抽出 10 个货格的货物，分别用节点 V ，V ，V ， V ，V ，V ，V ，V ，V ，V 表示。节点间的距离用直角距离公式:12345678910 式(3.1） 。HyLxdijijij Vy 0 Vx 交通运输学院课程设计 16 Vy Vx 3.2 设计要求 （1）绘出货格和节点相对位置图及节点相对距离表（需先列式计算各 的值） ；ijd （2）详细地写出最近邻点法和最近插入法的每一步骤及计算结果。 （3）分析两种方法的结果。 （4）设计结束后，谈谈自己的看法。 3.3 设计方法 分别用最近邻点法和最近插入法找出堆垛机存取 10 个托盘货物的合理路线。在堆 垛机开始拣选之前，由于设备及系统根据实际情况每台堆垛机分配一定数量的货位， 被分配的货位用阴影的小方格表示，图中的实心小黑点表示堆垛机从货架上取货时， 需要在仓库中停留的位置点，可以选用的方法的有最近零点法、最近插入发和遗传算 法等。 3.4 求解过程 首先根据设计要求，绘出货格和节点相对位置图如图 3.2、3.3 所示： 4 (G) 8 (K) 12 (T) 16 (N) 20 (Q) 3 (D) 7 (J) 11 (H) 15 (E) 19 (S) 2 (B) 6 (F) 10 (I) 14 (V) 18 (R) 1 (A) 5 (C) 9 (M) 13 (P) 17 (L) 图 3.2 货格的相对位置图 o 交通运输学院课程设计 17 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.3 节点的相对位置 引用 d =|x -x |L+|y -y |H 式(3.1）计算节点间距离ijjiji dv1v2=|xv2-xv1|L+|yv2-yv1|H=|1-1|1+|3-1|0.8=0.8 dv1v3=|xv3-xv1|L+|yv3-yv1|H=|2-1|1+|1-1|0.8=1.8 dv1v4=|xv4-xv1|L+|yv4-yv1|H=|2-1|1+|4-1|0.8=3.4 dv1v5=|xv5-xv1|L+|yv5-yv1|H=|3-1|1+|2-1|0.8=2.8 dv1v6=|xv6-xv1|L+|yv6-yv1|H=|3-1|1+|4-1|0.8=3.6 dv1v7=|xv7-xv1|L+|yv7-yv1|H=|4-1|1+|2-1|0.8=3 dv1v8=|xv8-xv1|L+|yv8-yv1|H=|4-1|1+|3-1|0.8=4.6 dv1v9=|xv9-xv1|L+|yv9-yv1|H=|5-1|1+|1-1|0.8=4 dv1v10=|xv10-xv1|L+|yv10-yv1|H=|5-1|1+|3-1|0.8=5.6 dv2v3=|xv3-xv2|L+|yv3-yv2|H=|2-1|1+|1-3|0.8=1 dv2v4=|xv4-xv2|L+|yv4-yv2|H=|2-1|1+|4-3|0.8=2.6 dv2v5=|xv5-xv2|L+|yv5-yv2|H=|3-1|1+|2-3|0.8=2 dv2v6=|xv6-xv2|L+|yv6-yv2|H=|3-1|1+|4-3|0.8=2.8 交通运输学院课程设计 18 dv2v7=|xv7-xv2|L+|yv7-yv2|H=|4-1|1+|2-3|0.8=3.8 dv2v8=|xv8-xv2|L+|yv8-yv2|H=|4-1|1+|3-3|0.8=3.8 dv2v9=|xv9-xv2|L+|yv9-yv2|H=|5-1|1+|1-3|0.8=4.8 dv2v10=|xv10-xv2|L+|yv10-yv2|H=|5-1|1+|3-3|0.8=4.8 dv3v4=|xv4-xv3|L+|yv4-yv3|H=|2-2|1+|4-1|0.8=1.6 dv3v5=|xv5-xv3|L+|yv5-yv3|H=|3-2|1+|2-1|0.8=1 dv3v6=|xv6-xv3|L+|yv6-yv3|H=|3-2|1+|4-1|0.8=1.8 dv3v7=|xv7-xv3|L+|yv7-yv3|H=|4-2|1+|2-1|0.8=2.8 dv3v8=|xv8-xv3|L+|yv8-yv3|H=|4-2|1+|3-1|0.8=2.8 dv3v9=|xv9-xv3|L+|yv9-yv3|H=|5-2|1+|1-1|0.8=3.8 dv3v10=|xv10-xv3|L+|yv10-yv3|H=|5-2|1+|3-1|0.8=3.8 dv4v5=|xv5-xv4|L+|yv5-yv4|H=|3-2|1+|2-4|0.8=2.6 dv4v6=|xv6-xv4|L+|yv6-yv4|H=|3-2|1+|4-4|0.8=1.8 dv4v7=|xv7-xv4|L+|yv7-yv4|H=|4-2|1+|2-4|0.8=4.4 dv4v8=|xv8-xv4|L+|yv8-yv4|H=|4-2|1+|3-4|0.8=2.8 dv4v9=|xv9-xv4|L+|yv9-yv4|H=|5-2|1+|1-4|0.8=5.4 dv4v10=|xv10-xv4|L+|yv10-yv4|H=|5-2|1+|3-4|0.8=3.8 dv5v6=|xv6-xv5|L+|yv6-yv5|H=|3-3|1+|4-2|0.8=0.8 dv5v7=|xv7-xv5|L+|yv7-yv5|H=|4-3|1+|2-2|0.8=1.8 dv5v8=|xv8-xv5|L+|yv8-yv5|H=|4-3|1+|3-2|0.8=1.8 dv5v9=|xv9-xv5|L+|yv9-yv5|H=|5-3|1+|1-2|0.8=2.8 dv5v10=|xv10-xv5|L+|yv10-yv5|H=|5-3|1+|3-2|0.8=2.8 dv6v7=|xv7-xv6|L+|yv7-yv6|H=|4-3|1+|2-4|0.8=2.6 dv6v8=|xv8-xv6|L+|yv8-yv6|H=|4-3|1+|3-4|0.8=1 dv6v9=|xv9-xv6|L+|yv9-yv6|H=|5-3|1+|1-4|0.8=3.6 dv6v10=|xv10-xv6|L+|yv10-yv6|H=|5-3|1+|3-4|0.8=2 dv7v8=|xv8-xv7|L+|yv8-yv7|H=|4-4|1+|3-2|0.8=1.6 dv7v9=|xv9-xv7|L+|yv9-yv7|H=|5-4|1+|1-2|0.8=1 dv7v10=|xv10-xv7|L+|yv10-yv7|H=|5-4|1+|3-2|0.8=2.6 dv8v9=|xv9-xv8|L+|yv9-yv8|H=|5-4|1+|1-3|0.8=2.6 dv8v10=|xv10-xv8|L+|yv10-yv8|H=|5-4|1+|3-3|0.8=1 交通运输学院课程设计 19 dv9v10=|xv10-xv9|L+|yv10-yv9|H=|5-5|1+|3-1|0.8=1.6 根据两节点的相对距离绘制节点相对距离表 3.1： 表 3.1 节点相对距离表 节点 V1V2V3V4V5V6V7V8V9V10 V1 0.8 1.8 3.4 2.8 3.6 3 4.6 4 5.6 V2 1 2.6 2 2.8 3.8 3.8 4.8 4.8 V3 1.6 1 1.8 2.8 2.8 3.8 3.8 V4 2.6 1.8 4.4 2.8 5.4 3.8 V5 0.8 1.8 1.8 2.8 2.8 V6 2.6 1 3.6 2 V7 1.6 1 2.6 V8 2.6 1 V9 1.6 V10 3.4.1 最近邻点法求堆垛机运行路径 1 最近邻点法 1.1 最近邻点法的思路 （1） 从零点开始，作为整个回路的起点。 （2） 找到离刚刚加入到回路的顶点最近的一个顶点，并将其加入到回路中。 （3） 重复步骤（2） ，直到所有顶点都加入到回路中。 （4） 最后，将最后一个加入的顶点和起点连接起来。 交通运输学院课程设计 20 1.2 应用过程 （1）先将节点 v1加入到回路中，T =v1。0 图 3.4 加入节点 v1 （2） 从节点 v1出发，在节点 2、3、4、5、6、7、8、9、10 中，找出离 v1 最近 的节点。 Min1 12|,10,id0.idN 因此将节点 v2加入到回路中，T1=v 1,v2。 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.5 运行路线 （3）从节点 v2出发，在节点 3、4、5、6、7、8、9、10 中，找出离 v2最近的节 点。 Min2 23|,10,i1didN 因此就可以将 v3加入到回路中，T2=v 1,v2,v3。 V1 交通运输学院课程设计 21 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.6 运行路线 （4）从节点 v3出发，在节点 4、5、6、7、8、9、10 中，找出离 v3最近的节点。 Min35|,10,i2,d1idN 因此就可以将 v5加入到回路中，T3=v 1,v2,v3,v5 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.7 运行路线 交通运输学院课程设计 22 （5）从节点 v5出发，在节点 4、6、7、8、9、10 中，找出离 v5最近的节点。 Min56|,10,i2,3d0.8idN 因此就可以将 v6加入到回路中，T4=v 1,v2,v3,v5,v6 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.8 运行路线 （6） 从节点 v6出发，在节点 4、7、8、9、10 中，找出离 v6最近的节点。 Min68|,10,i2,35d1idN 因此就可以将 v8加入到回路中，T5=v 1,v2,v3,v5,v6,v8 交通运输学院课程设计 23 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.9 运行路线 （7） 从节点 v8出发，在节点 4、7、9、10 中，找出离 v8最近的节点。 Min810|,10,i2,356didN 因此就可以将 v10加入到回路中，T6=v 1,v2,v3,v5,v6， v8， v10 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.10 运行路线 交通运输学院课程设计 24 (8)从节点 v10出发，在节点 4、7、9 中，找出离 v10最近的节点。 Min10 109|,10,i2,3568,d.6idN 因此就可以将 v9加入到回路中，T7=v 1,v2,v3,v5,v6,v8， v10,v9形成如图 3.11 所示的运 行路线 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.11 运行路线 (9)从节点 v9出发，在节点 4、7 中，找出离 v9最近的节点。 Min7|,10,i2,3568,10didN 因此就可以将 v7加入到回路中，T8=v 1,v2,v3,v5,v6,v8， v10,v9,v7形成如图 3.12 所示的 运行路线 交通运输学院课程设计 25 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.12 运行路线 (10)将最后的点 v4, ,v1连接起来得到最后的运行路线图, T9=v1,v2,v3,v5,v6,v8， v10,v9,v7 ,v4,v1 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.13 最终运行线路图 交通运输学院课程设计 26 所以堆垛机运行路线为：1261011151917138 即取送货物次序为：ABFIHESLPK 堆垛机总行驶距离为：Z=0.8+1+1+0.8+1+1+1.6+1+4.4+3.4=16 3.4.2 最近插入法求堆垛机运行路径 2 最近插入法 2.1 最近插入法的思路 （1）先将节点 v1加入到回路中，找到 d1k最小的节点 vk ，形成一个子回路， T=v1 ,vk ,v1。 （2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点 vk 。 （3）在子回路中找到一条弧（i,j）,使得里程增量 最小。如果有多条cikjij+- 满足条件，任选一条，然后将节点 vk插入到节点 vi和 vj之间，用两条新的弧（i,k） 和（k,j）代替原来的弧（i,j）,并将节点 vk加入到子回路中。 （4）重复步骤（2）和（3），直到所有的节点都加入到子回路中。 2.2 应用过程 （1）比较货格相对距离表中从 v1出发的所有路径的大小 Min1 12|,0,0.8icNic 这样就由节点 v1和 v2构成的子回路，T=v 1,v2,v1 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.14 由 v1和 v2构成的子回路 交通运输学院课程设计 27 （2）然后考虑剩下的节点 、 、 、 、 、 、 ， 到 和 中某一3v456v789v10v2 个节点的最小距离；Min 12 23,|,10,icNic 由于对称性，无论将 3 插入到 1 和 2 之间往返路径中，结果都是一样的，任选其一,这 样构成一个新的子回路 T=v1,v2, v3,v1 V10V8 V7 V6 V5 V4 V3V2 V1 V9 图 3.15 由 v1,v2和 v3构成的子回路 （3）接着考虑剩下的节点 、 、 、 、 、 ， 到 、 和 中 456789v10v23 某一个节点的最小距离； Min123 35,|,10,2,1iicNic （4）由图 3.15 可知，节点 有 3 个位置（条弧线）可以插入。现在分析将 加5v 5v 入到哪里合适： 插入到（1,2）间，=d 15+d52-d12=2.8+2-0.8=4 插入到（2,3）间，= d 25+d53-d23=2+1-1=2 插入到（3,1）间，= d 35+d51-d31=1+2.8-1.8=2 比较上面 3 种情况增量，插入（2,3）或（3,1）之间的增量最小，任选其 一， 将节点 加入到（2,3），所以结果为：T=v 1,v2,v5 v3， v1其子回路5v 交通运输学院课程设计 28 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.16 由 v1,v2,v3和 v5 构成的字回路 （5）接着考虑剩下的节点 、 、 、 、 ， 到 、 、 和 中某一4678v910v23v5 节点的最小距离； Min1235 56,|,10,2,3.8iicNic （6）由图 3.16 可知，节点 有 4 个位置（条弧线）可以插入。现在分析将 加6v 6v 入到哪里合适： 插入到（1,2）间，= d 16+d -d12=3.6+2.8-0.8=5.662 插入到（2,5）间，= d +d -d =2.8+0.8-2=1.65 插入到（3,5）间，= d +d -d =1.8+0.8-1=1.6363 插入到（3,1）间，= d +d -d =1.8+3.6-1.8=3.61 比较上面 4 种情况增量，将 插入（2,5）或（3,5）之间的增量最小，任选其一，将6v v5插入（2,5）之间，则结果为：T= v1,v2,v ,v ，v ， v1其子回路则变为如图 3.17653 所示： 交通运输学院课程设计 29 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.17 由 v1,v2,v ,v ，v 构成的子回路653 (7) 接着考虑剩下的节点 、 、 、 ， 到 、 、 、 、 中某一节478910v235v6 点的最小距离 Min12356 68,|,51iiiccNic （8）由图 3.17 可知，节点 有 5 个位置（条弧线）可以插入。现在分析将 加8v 8v 入到哪里合适： 插入到（1,2）间，= d 18+d -d12=4.6+3.8-0.8=7.682 插入到（2,6）间，= d +d -d =3.8+1-2.8=26 插入到（6,5）间，= d +d -d =1+1.8-0.8=285 插入到（5,3）间，= d +d -d =1.8+2.8-1=3.63 插入到（3,1）间，= d +d -d =2.8+4.6-1.8=5.681 比较上面 5 种情况增量，可将 插入（6,5）或（2,6）之间的增量最小，任选其一，v 若将 插入（6,5）之间，则结果为： T= 、 、 、 、 、 、 其子回路则变8v 1v268v531v 为图 3.18 所示： 交通运输学院课程设计 30 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.18 由 、 、 、 、 、 构成的子回路1v268v53 （9）接着剩下的节点 、 、 ， 到 、 、 、 、 、 中某一节点4791026v853v 的最小距离 Min 123568 810,|,3iiiccNi c （10）由图 3.18 可知有 6 个位置（条弧线）可以插入。现在分析将 加入到哪v 里合适： 插入到（1,2）间，= d +d -d12=5.6+4.8-0.8=9.6102 插入到（2,6）间，= d +d -d =4.8+2-2.8=46 插入到（6,8）间，= d +d -d =2+1-1=2108 插入到（8,5）间，= d +d -d =1+2.8-1.8=25 插入到（5,3）间，= d +d -d =2.8+3.8-1=5.6103 插入到（3,1）间，= d +d -d =3.8+5.6-1.8=7.61 比较上面 6 种情况增量，插入到（6,8）或（8,5）之间的增量最小，任选其一，所以 将 节点加入到（ 8,5）间，结果为： T= 、 、 、 、 、 、 、 其子回10v 1v268v1053v1 路则变为图 3.19 所示： 交通运输学院课程设计 31 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.19 、 、 、 、 、 、 构成的子回路1v268v1053v （11）接着考虑剩下的节点 、 、 到 、 、 、 、 、 、 中某一节479268105v3 点的最小距离； Min 12356810 34,|,10,35,.6iiiiccNi c （12）由图 3.19 可知有 7 个位置（条弧线）可以插入。现在分析将 加入到哪v 里合适： 插入到（1,2）间，= d +d -d12=3.4+2.6-0.8=5.2142 插入到（2,6）间，= d +d -d =2.6+1.8-2.8=1.66 插入到（6,8）间，= d +d -d =1.8+2.8-1=3.648 插入到（8,10）间，= d +d -d =2.8+3.8-1=5.610 插入到（10，5）间，= d +d -d =3.8+2.6-2.8=3.645 插入到（5,3）间，= d +d -d =2.6+1.6-1=3.253 插入到(3，1)间，= d +d -d =1.6+3.4-1.8=3.241 比较上面 7 种情况增量，插入到（2,6）之间的增量最小，所以将 节点加入到4v （2,6）间，结果为：T= 、 、 、 、 、 、 、 、 其子回路则变图 3.201v246v8105v31 所示： 交通运输学院课程设计 32 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.20 、 、 、 、 、 、 、 构成的子回路1v246v8105v3 （13）接着考虑剩下的节点 、 到 、 、 、 、 、 、 、 中某一791246810v53 节点的最小距离； Min 123456810 109,|,0,35,.6iiiiccNi c （14）由图 3.20 可知有 8 个位置（条弧线）可以插入。现在分析将 加入到哪4v 里合适： 插入到（1,2）间，= d +d -d12=4+4.8-0.8=8192 插入到（2,4）间，= d +d -d =4.8+5.4-2.6=7.64 插入到（4,6）间，= d +d -d =5.4+3.6-1.8=7.296 插入到（6,8）间，= d +d -d =3.6+2.6-1=5.28 插入到（8，10）间，= d +d -d =1+1.6-1=1.6910 插入到（10,5）间，= d +d -d =1.6+2.8-2.8=1.65 插入到(5，3)间，= d +d -d =2.8+3.8-1=5.6593 插入到(3，1)间，= d +d -d =3.8+4-1.8=61 比较上面 8 种情况增量，插入到（8,10）和（10,5）之间的增量最小，任选其一，所 以将 节点加入到（10，5）间，结果为：9v T= 、 、 、 、 、 、 、 、 、 其子回路如图 3.21 所示：1246v8109v531v 交通运输学院课程设计 33 V10 V9 V8 V7 V6 V5 V4 V3V2 V1 图 3.21 、 、 、 、 、 、 、 、 构成的子回路1v2