自动化立体仓库系统设计.doc

交通运输学院课程设计交通运输学院自动化立体仓库系统 课程设计学院 交通运输学院 班级 物流1201姓名 周达东 学号 201200602 成绩 指导老师 赵小柠2014年 12月17日2指导教师评语及成绩任务分配表序号学号姓名设计任务成绩1201200602周达东货位优化2201200603徐高贵堆垛机径路优化指导教师评语：导师签字： 年 月 日兰州交通大学交通运输学院课程设计任务书1所在系： 物流管理系 课程名称： 仓储管理 指导教师（签名）： 赵小柠 专业班级： 物流管理1201 学生姓名： 学号： 一、课程设计题目自动化立体仓库系统设计二、课程设计的目的 通过本课程设计可以使学生深入了解什么是自动化立体仓库货位规划和堆垛机径路优化问题，并掌握解决问题的基本方法，为今后走上工作岗位从事相关工作打下一定基础，使理论和实践有效结合。 三、课程设计的主要内容和要求（包括原始数据、技术参数、设计要求、工作量要求等） 一、货位规划1、设计条件某自动化立体仓库采用2行3列的单元货格式货架存放货物，一共有6个货格，每个货格存放一个托盘货物。货格以按列编码的形式进行编号，如图1所示。已知其它参数假定如下：假设堆垛机在水平方向的行驶速度Vx=3.0m/s，在垂直方向的行驶速度Vy=2m/s；货格大小为L（长）W（宽）H（高）=1m1m0.8m；堆垛机初始状态在原点0处；货格j的横坐标和纵坐标就是其所在的列和行，如货格6的坐标为（3，2）；叉车运行至货格j所用时间。现有6个托盘货物需要存放到货架上，货物的出入库频率如表1所示。Vy246135Vx0图1原始货格图表1 托盘货物出入库频率表货物频率货物频率货物频率A8C17E6B32D11F222、设计任务根据以上条件，利用匈牙利算法合理安排各托盘货物的存放位置。3、设计要求（1）根据已知条件，计算出系数矩阵（先列式详细计算的值）；（2）详细地写出匈牙利算法的每一步骤及计算结果；（3）绘出最终的货位规划图； （4）设计结束后，谈谈自己的看法。二、堆垛机径路规划1、设计条件随机从图2中的25个货格中抽出11个货格的货物，分别用节点v1，v2，v3，v4，v5，v6，v7，v8 ，v9，v10，v11表示。节点间的距离用直角距离公式求解。5 (O)10 (U)15 (W)20 (X)25 (Y)4 (G)9 (K)14 (T)19 (N)24 (Q)3 (D)8 (J)13 (H)18 (E)23 (S)2 (B)7 (F)12 (I)17 (V)22 (R)1 (A)6 (C)11 (M)16 (P)21 (L)VyoVx图2 最终的货位规划图2、设计任务分别用最近邻点法和最近插入法找出堆垛机存取11个托盘货物的合理路线。3、设计要求（1）绘出货格和节点相对位置图及节点相对距离表（需要先列式计算各的值）；（2）详细地写出最近邻点法和最近插入法的每一步骤及计算结果。（3）分析两种方法的结果。（4）设计结束后，谈谈自己的看法。四、工作进度安排 17周前期完成货位规划和堆垛机径路规划的设计任务；17周后期完成货位规划和堆垛机径路规划的文档整理任务。五、主要参考文献【1】李引珍.管理运筹学. 北京：科学出版社，2012年9月 【2】蔡临宁.物流系统规划建模及实例分析. 北京：机械工业出版社, 2013年7月 审核批准意见系主任（签字） 年月日一、货位规划- 1 -1.设计条件- 1 -2.设计任务- 1 -3.设计要求- 1 -4.设计过程- 2 -4.1计算各货物与货位对应的系数矩阵：- 2 -4.3找独立0元素，进行试指派：- 3 -4.4用最少的直线覆盖所有0元素：- 4 -4.5增加0元素：- 4 -5.设计总结- 7 -二、堆垛机径路规划- 9 -1.设计条件- 9 -2.设计过程- 10 -2.1选取货格计算相对距离- 10 -2.2最近邻点法- 12 -2.3最近插入法- 18 -2.4分析两种方法的结果- 25 -3设计总结- 25 -参考文献- 27 -2一、货位规划1.设计条件某自动化立体仓库采用2行3列的单元货格式货架存放货物，一共有6个货格，每个货格存放一个托盘货物。货格以按列编码的形式进行编号，如图1所示。已知其它参数假定如下：假设堆垛机在水平方向的行驶速度Vx=3.0m/s，在垂直方向的行驶速度Vy=2m/s；货格大小为L（长）W（宽）H（高）=1m1m0.8m；堆垛机初始状态在原点0处；货格j的横坐标和纵坐标就是其所在的列和行，如货格6的坐标为（3，2）；叉车运行至货格j所用时间。现有6个托盘货物需要存放到货架上，货物的出入库频率如表1所示。Vy246135Vx0图1原始货格图表1 托盘货物出入库频率表货物频率货物频率货物频率A8C17E6B32D11F222.设计任务根据以上条件，利用匈牙利算法合理安排各托盘货物的存放位置。3.设计要求（1）根据已知条件，计算出系数矩阵（先列式详细计算的值）；（2）详细地写出匈牙利算法的每一步骤及计算结果；（3）绘出最终的货位规划图； （4）设计结束后，谈谈自己的看法。4.设计过程 4.1计算各货物与货位对应的系数矩阵：已知：L=1，H=0.8，Vx=3.0，Vy=2.0；公式1各货位坐标：1(1,1);2(1,2);3(2,1);4(2,2);5(3,1);6(3,2);t1=max(11/3,(1-1)0.8/2)=1/3t2=max(11/3,(2-1)0.8/2)=2/5t3=max(21/3,(1-1)0.8/2)=2/3t4=max(21/3,(2-1)0.8/2)=2/3t5=max(31/3,(1-1)0.8/2)=1t6=max(31/3,(2-1)0.8/2)=1又，实例给出各货物出入库频率fi：fA=8，fB=32，fC=17，fD=11，fE=6，fF=22根据系数ci=fiti既得：对于货物B：c1B=fBt1=321/3=32/3c2B=fBt2=322/5=64/5c3B=fBt3=322/3=64/3c4B=fBt4=322/3=64/3c5B=fBt5=321=32c6B=fBt6=321=32对于货物A：c1A=fAt1=81/3=8/3c2A=fAt2=82/5=16/5c3A=fAt3=82/3=16/3c4A=fAt4=82/3=16/3c5A=fAt5=81=8c6A=fAt6=81=8对于货物C：c1C=fCt1=171/3=17/3c2C=fCt2=172/5=34/5c3C=fCt3=172/3=34/3c4C=fCt4=172/3=34/3c5C=fCt5=171=17c6C=fCt6=171=17对于货物D：c1D=fDt1=111/3=11/3c2D=fDt2=112/5=22/5c3D=fDt3=112/3=22/3c4D=fDt4=112/3=22/3c5D=fDt5=111=22c6D=fDt6=111=22对于货物E：c1E=fEt1=61/3=2c2E=fEt2=62/5=12/5c3E=fEt3=62/3=4c4E=fEt4=62/3=4c5E=fEt5=61=6c6E=fEt6=61=6对于货物F：c1F=fFt1=221/3=22/3c2F=fFt2=222/5=44/5c3F=fFt3=222/3=44/3c4F=fFt4=222/3=44/3c5F=fFt5=221=22c6F=fFt6=221=22由于是分数不便于计算，同乘以其最小公倍数整15即得出系数矩阵如表1.2所示：表1.2各货物货位对应系数矩阵货位货格ABCDEF140160855530110248192102663613238032017011060220480320170110602205120480255165903306120480255165903304.2根据匈牙利算法求指派结果：根据系数矩阵建立等效矩阵(系数矩阵中每行各元素减去该行最小元素)：40 160 85 55 30 110 48 192 102 66 36 132 80 320 170 110 60 220 80 320 170 110 60 220 120 480 255 165 90 330 120 480 255 165 90 330 10130552508012156663009620260110500160202601105001603039016575024030390165750240再从所得系数矩阵的每列元素中减去该列最小元素：1013055250801215666300962026011050016020260110500160303901657502403039016575024000000022611501610130552508010130552508020260110500160202601105001604.3找独立0元素，进行试指派：从只有一个0元素的行(或列)开始，给这个0元素加括号，记作(0)，表示行行所代表的货格已有一种货物分配。然后划去(0)所在列(或行)的其他0元素，记作“0”，表示该列所代表的货物已指派。对只有一个0元素的列(或行)的0元素加括号，然后划去该0所在行(或列)的0元素。（如果、两步中，遇到每一行和每一列都有两个或两个以上0元素，可任选一个加括号，把其所在行或列的0元素划掉。）重复、两步，直到所有0元素都被 括号或 划掉。加括号的0即为独立0元素，若其个数m等于矩阵阶数n(本例中n=6)，则已得到问题的最优解。若mn，则转入第三步。0(0)00002261150161013055250801013055250802026011050(0)16020260110500160其中独立0元素m的个数2小于阶数n=6，转入第(4)步。4.4用最少的直线覆盖所有0元素：对没有独立0元素的行打“”对已打“”的行所有含0元素的列打“”在对 中打“”的列中含独立0元素的行打“”重复 直到得不到新的打“”的行、列为止将没有“”的行和已打“”的列用直线覆盖，且直线的数目一定等于独立0元素的个数。转第(5)步0(0)00000(0)0000226115016226115016 1013055250801013055250801013055250801013055250802026011050(0)1602026011050(0)16020260110500160202601105001604.5增加0元素：从没有被直线覆盖的元素中找出最小元素。未被覆盖的元素都减去该最小元素，而没被两条线覆盖的元素都加上该最小元素，其他元素不变。这样，得到新系数矩阵，再转第(3)步，重新找独立0元素。0(0)0020000020(0)249301402493014812853230788128532307881285323078812853230781825810848015818258108480158182581084801581825810848015800002000(0)01000249301402493814812853230780120451507081285323078(0)1204515070182581084801581025010040(0)1501825810848015810250100400150按照这一程序直到独立0元素达6个为止，各过程如下：最小元素12 最小元素6300013(0)150(0)02500216(0)81112216(0)201101174212067(0)105300055(0)11742120670105300055102479737(0)147102358525(0)1351024797370147102358525013521006310210064101215002051215003050992400490992401049099240049099240104910229792501290219691501191022979250129021969150119最小元素10 最小元素24最小元素5最小元素204500306505005357003615024545361002454007500102507000102007500102507000102001954515095019045150900195451509501904515090独立0元素已达6个，当前分配是最有情况。即得最优解如表1.3示：70(0)25552005610204474(0)050(0)01000500(0)10001704515(0)70(0)1704515070表1.3 最优解方案1ABCDEF613452最优方案耗时表1.4 所有最优方案 由于最后一个系数矩阵选取独立0元素时，有多种可能，因此实例最优解有多组如表1.4所示：货物ABCDEF货位方案1613452方案2614352方案3513462方案4514362最终画在货格中如图1.2图1.5所示2F4D6A1B3C5E图1.2方案一货位安排2F4C6A1B3D5E 图1.3方案二货位安排2F4D6E1B3C5A图1.4方案三货位安排2F4C6E1B3D5A图1.5方案四货位安排5.设计总结通过这次设计我了解到一个自动化立体仓库效率的高低主要取决于库区和货位的分配策略，使用好的优化策略能大大提高出入库频率，提高堆垛机的存取操作效率，减少时间及能耗。并且怎样将各种先进的数学，运筹学计算方法应用到实际的物流问题的解决中的能力得以提高，熟悉了各种方法的细节注意点随着现代工业的快速发展，传统的仓储方式日益不能满足生产和流通的需要，自动化立体仓库得到越来越多的应用。面对成千上万的货格，立体仓库的货位存储优化已成为提高存取效率、降低成本的关键。 本文根据立体仓库基本特征，建立了自动化立体仓库三维数学坐标系，把立体仓库中的货格转换成为了三维坐标系中坐标点的形式，实现了通过两点距离来表示堆垛机的实际运行距离。随后，以堆垛机运行参数为基础，分别提出基于堆垛机运行距离的距离参数算法和基于堆垛机运行时间的最大时间算法。距离参数算法通过参数把垂直方向和水平方向上不同维度的速度统一到同一速度单位上，从而实现了不同方向上距离的比较，进而取得每个货位进行出入库操作所需要运行距离的大小；最大时间算法通过取堆垛机在水平方向和垂直方向上运行时间进行比较，得出的最大时间也就是每次入库或出库所花费时间的多少，从而确定每个货位到出、入库点所花费时间的大小。这样就实现了通过距离和时间两个数值参数大小来表示堆垛机运行效率高低的方法。自动化立体仓库是现代物流系统中迅速发展的一个重要组成部分, 它具有节约用地、减轻劳动强度、消除差错、提高仓储自动化水平及管理水平、提高管理和操作人员素质、降低储运损耗、有效地减少流动资金的积压、提高物流效率等诸多优点。与厂级计算机管理信息系统联网以及与生产线紧密相连的自动化立体仓库更是当今CIMS( 计算机集成制造系统)及FMS( 柔性制造系统)必不可少的关键环节。 自动化所围绕自动化仓储系统开发了多种自动化系统硬件设备及软件产品, 如: 不同类型的库存管理软件、系统仿真软件、图形监控及调度软件、堆垛机输送机控制软件、条形码识别跟踪系统、搬运机器人、码垛机械手、自动运行小车、货物分选系统、堆垛机认址检测系统、堆垛机控制系统、货位探测器、高度检测器、输送系统、码垛系统、自动输送小车等产品。采用现场控制总线直接通讯的方式，真正做到计算机只监不控，所有的决策、作业调度和现场信息等均由堆垛机、出入库输送机等现场设备通过相互间的通讯来协调完成。堆垛机有自动召回原点的功能，即无论任何情况，只要货叉居中且水平运行正常时，可按照下达的命令自动返回原点。这意味着操作人员和维护人员可以尽量不进入巷道。 堆垛机是整个自动化立体仓库的核心设备，通过手动操作、半自动操作或全自动操作实现把货物从一处搬运到另一处。它由机架（上横梁、下横梁、立柱）、水平行走机构、提升机构、载货台、货叉及电气控制系统构成。 自动化立体仓库的主要优点有：（1）仓库作业全部实现机械化和自动化（2）采用高层货架、立体储存，能有效地利用空间，减少占地面积，降低土地购置费用。（3）采用托盘或货箱储存货物，货物的破损率显著降低。（4）货位集中，便于控制与管理，特别是使用电子计算机，不但能够实现作业过程的自动控制，而且能够进行信息处理。二、堆垛机径路规划1.设计条件随机从图2中的25个货格中抽出11个货格的货物，分别用节点v1，v2，v3，v4，v5，v6，v7，v8 ，v9，v10，v11表示。节点间的距离用直角距离公式 求解。5 (O)10 (U)15 (W)20 (X)25 (Y)4 (G)9 (K)14 (T)19 (N)24 (Q)3 (D)8 (J)13 (H)18 (E)23 (S)2 (B)7 (F)12 (I)17 (V)22 (R)1 (A)6 (C)11 (M)16 (P)21 (L)oVxVy图2 最终的货位规划图2、设计任务分别用最近邻点法和最近插入法找出堆垛机存取11个托盘货物的合理路线。3、设计要求（1）绘出货格和节点相对位置图及节点相对距离表（需要先列式计算各的值）；（2）详细地写出最近邻点法和最近插入法的每一步骤及计算结果。（3）分析两种方法的结果。（4）设计结束后，谈谈自己的看法。2.设计过程 2.1选取货格计算相对距离随机从图2.1中的25个货格中抽出个货格的货物A、G、J、I、W、V、E、N、L、R、Y，分别用节点v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11表示。货格和节点的相对位置图如图2.2、图2.3所示。5 (O)10 (U)15 (W)20 (X)25 (Y)4 (G)9 (K)14 (T)19 (N)24 (Q)3 (D)8 (J)13 (H)18 (E)23 (S)2 (B)7 (F)12 (I)17 (V)22 (R)1 (A)6 (C)11 (M)16 (P)21 (L)Vy oVxo 图2.2 货格相对位置图V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1图2.3 节点相对位置图现找出堆垛机存取7个托盘货物的合理路线。如果货格大小为L（长）W（宽）H（高）=1m1m0.8m,两货格相对距离相等，则根据直角距离公式可计算出所有节点的距离。d12=x2-x1L+y2-y1H=1-11+4-10.8=2.4d13=x3-x1L+y3-y1H=2-11+3-10.8=2.6d14=x4-x1L+y4-y1H=3-11+2-10.8=2.8d15=x5-x1L+y5-y1H=3-11+5-10.8=5.2d16=x6-x1L+y6-y1H=4-11+2-10.8=3.8d17=x7-x1L+y7-y1H=4-11+3-10.8=4.6d18=x8-x1L+y8-y1H=4-11+4-10.8=5.4d19=x9-x1L+y9-y1H=5-11+1-10.8=4d1 10=x10-x1L+y10-y1H=5-11+2-10.8=4.8d1 11=x11-x1L+y11-y1H=5-11+5-10.8=7.2d23=x3-x2L+y3-y2H=2-11+3-40.8=1.8d24=x4-x2L+y4-y2H=3-11+2-40.8=3.6d25=x5-x2L+y5-y2H=3-11+5-40.8=2.8d26=x6-x2L+y6-y2H=4-11+2-40.8=4.6d27=x7-x2L+y7-y2H=4-11+3-40.8=3.8d28=x8-x2L+y8-y2H=2-11+4-40.8=3d29=x9-x2L+y9-y2H=5-11+1-40.8=7.4d2 10=x10-x2L+y10-y2H=5-11+2-40.8=4.6d2 11=x11-x2L+y11-y2H=5-11+5-40.8=4.8d34=x4-x3L+y4-y3H=3-21+2-30.8=1.8d35=x5-x3L+y5-y3H=3-21+2-30.8=2.6d36=x6-x3L+y6-y3H=4-21+2-30.8=2.8d37=x7-x3L+y7-y3H=4-21+3-30.8=2d38=x8-x3L+y8-y3H=4-21+4-30.8=2.8d39=x9-x3L+y9-y3H=5-21+1-30.8=4.6d3 10=x10-x3L+y10-y3H=5-21+2-30.8=3.8d3 11=x11-x3L+y11-y3H=5-21+5-30.8=4.6d45=x5-x4L+y5-y4H=3-31+5-20.8=2.4d46=x6-x4L+y6-y4H=4-31+2-20.8=1d47=x7-x4L+y7-y4H=4-31+3-20.8=1.6d48=x8-x4L+y8-y4H=4-31+4-20.8=2.6d49=x9-x4L+y9-y4H=5-31+1-20.8=2.8 d4 10=x10-x4L+y10-y4H=5-31+2-20.8=2d4 11=x11-x4L+y11-y4H=5-31+5-20.8=4.4 d56=x6-x5L+y6-y5H=4-31+2-50.8=3.4d57=x7-x5L+y7-y5H=4-31+3-50.8=2.6d58=x8-x5L+y8-y5H=4-31+4-50.8=1.8d59=x9-x5L+y9-y5H=5-31+1-50.8=5.2d5 10=x10-x5L+y10-y5H=5-31+2-50.8=4.4d5 11=x11-x5L+y11-y5H=5-31+5-50.8=2d67=x7-x6L+y7-y6H=4-41+3-20.8=0.8d68=x8-x6L+y8-y6H=4-41+4-20.8=1.6d69=x9-x6L+y9-y6H=5-41+1-20.8=1.8d6 10=x10-x6L+y10-y6H=5-41+2-20.8=1d6 11=x11-x6L+y11-y6H=5-41+5-20.8=3.4D78 =x8-x7L+y8-y7H=4-41+4-30.8=0.8D79 =x9-x7L+y9-y7H=5-41+1-30.8=2.6D7 10=x10-x7L+y10-y7H=5-41+2-30.8=1.8D7 11=x11-x7L+y11-y7H=5-41+5-30.8=2.6D89 =x7-x8L+y7-y8H=5-41+1-40.8=3.4D8 10=x10-x8L+y10-y8H=5-41+2-40.8=2.6D8 11=x11-x8L+y11-y8H=5-41+5-40.8=1.8D9 10=x10-x9L+y10-y9H=5-51+2-10.8=0.8D9 11=x11-x9L+y11-y9H=5-51+5-10.8=3.2D10 11=x11-x10L+y11-y10H=5-51+5-20.8=2.4计算结果见表2.1：表2.1 节点相对距离表元素V1V2V3V4V5V6V7V8V9V10V11V1_2.42.62.85.23.84.65.444.87.2V2_1.83.62.84.63.837.44.64.8V3_1.82.62.822.84.63.84.6V4_2.411.82.62.824.4V5_3.42.61.85.24.42V6_0.81.61.813.4V7_0.82.61.82.6V8_3.42.61.8V9_0.83.2V10_2.4V11_2.2最近邻点法最近邻点法的思路(1)从零点开始，作为整个回路的起点。(2)找到离刚刚加入到回路中的顶点最近的一个顶点，并将其加入到回路中。(3)重复步骤（2），直到所有的顶点都加入到回路中。(4)最后，将最后一个加入的顶点和起点连接起来。 2.应用过程 (1)将V1设为起始点(2)先将节点V1加入到回路中，T=V1。(3)从节点V1出发，比较其到其他节点的距离，选择其最小值，加入到回路中。mind1iiN,1i11,且i1=d12=2.4因此将节点V2加入到回路中，T=V1,V2，见图2.4：V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1图2.4 由V1、V2构成的回路V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1(3)从节点V2出发，在剩下的节点中，找出离V2最近的节点。mind2iiN,1i11,且i1,2=d23=1.8这样就可以将V3节点加入到回路中，T=V1,V2,V3。图2.5 由V1，V2和V3构成的回路(4)从节点V3出发，观察离V3最近的节点。mind3iiN,1i11,且i1,2,3=d34=1.8这样V4是最近的点，将V4加入到回路中，T=V1,V2,V3,V4。V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1图2.6 由V1，V2，V3和V4构成的回路(5)从节点V4出发，观察离V4最近的节点mind4iiN,1i11,且i1,2,3,4=d46=1这样V6是最近的点，将V6加入到回路中，T=V1,V2,V3,V4,V6。V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1图2.7 由V1，V2，V3，V4和V6构成的回路(6)从节点V6出发，观察离V6最近的节点mindi6iN,1i11,且i1,2,3,4,6=d67=0.8这样V7是最近的点，将V7加入到回路中，T=V1,V2,V3,V4,V6,V7V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1图2.8 由V1,V2,V3,V4,V6和V7构成的回路(7) 从节点V7出发，观察离V7最近的节点mindi7iN,1i11,且i1,2,3,4,6，7=d78=0.8这样V8是最近的点，将V8加入到回路中，T=V1,V2,V3,V4,V6,V7，V8V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1图2.9 由V1,V2,V3,V4,V6,V7和V8构成的回路(8) 从节点V8出发，观察离V8最近的节点mindi8iN,1i11,且i1,2,3,4,6，7，8=d58=1.8这样V5是最近的点，将V5加入到回路中，T=V1,V2,V3,V4,V6,V7，V8，V5如图2.10V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1图2.10 由V1,V2,V3,V4,V6,V7，V8和v5构成的回路(9) 从节点V5出发，观察离V5最近的节点mindi5iN,1i11,且i=9，10，11=d11 5=2这样V11是最近的点，将V11加入到回路中，T=V1,V2,V3,V4,V6,V7，V8，V5，v11V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1图2.11 由V1,V2,V3,V4,V6,V7，V8，v5和v11构成的回路(10) 从节点V11出发，观察离V11最近的节点mindi11iN,1i11,且i=9，10=d10 11=2.4这样V10是最近的点，将V10加入到回路中，T=V1,V2,V3,V4,V6,V7，V8，V5，v11，v10如图2.12V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1图2.12 由V1,V2,V3,V4,V6,V7，V8，v5，v11，和v10构成的回路（11）从节点V10出发，V9是最后一个节点，直接加入就可以了。然后，将V9和V1相连。得到最后的解为T=V1,V2,V3,V4,V6,V7，V8，V5，v11，v10，v9V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1图2.13 最近邻点法求解结果所以堆垛机运行路线为：1481217181915252221即取送货物次序为：AGJIVENWYRL堆垛机总行驶距离为：f=2.4+1.8+1.8+1+0.8+0.8+1.8+2+2.4+0.8+4=19.62.3最近插入法 1.最近插入法的思路 (1)先将节点V1加入到回路中，找到最小的节点，形成一个子回路，T=V1,VK,V1。(2)在剩下的节点中，寻找一个离子回路中某一节点最近的节点。(3)在子回路中找到一条弧（i,j），使得里程增量最小。如果有多条满足条件，任选一条，然后将节点插入到节点和之间，用两条新的弧（i,k）和(k,j)代替原来的弧（i,j），并将节点加入到子回路中。(4)重复步骤（2）和（3），直到所有的节点都加入到子回路中。2.应用过程(1)比较货格相对距离表中从V1出发的所有路径的大小minc1iiN,1i11,且i1=c12=2.4这样就由节点V1和V2构成的子回路，T=V1,V2,V1如图2.14所示。V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1图2.14 由V1，V2构成的子回路(2)然后考虑剩下的节点V3、V4、V5、V6、V7,V8,V9,V10,V11到V1和V2中某一个节点的最小距离：minc1i,c2iiN,1i11,且i1,2=c23=1.8(3)由于对称性，无论将3插入到1和2之间往返路径中，结果都一样的，这样，构成一个新的子回路T=V1,V2,V3,V1，其结果如图2.15所示。V2V3V5V8V7v10V9V6vvvvvvvvvvvv6V4v11V1图2.15 由V1，V2和V3构成的子回路(4)接着考虑剩下的节点V4,V5,V6,V7,V8,V9,V10,V11到V1，V2和