自动化立体仓库系统课程设计样本

目录TOC\o"1-4"\h\z\u引言 11自动化立体仓库 21.1概述 22货位优化 32.1设计条件 32.2计算系数矩阵 32.2.1符号假设 32.2.2已知条件 42.2.3公式计算过程 42.3运用匈牙利算法求解 62.4总结 133堆垛机途径优化 153.1设计条件 153.2设计规定 163.3设计办法 163.4求解过程 163.4.1近来邻点法求堆垛机运营途径 193.4.2近来插入法求堆垛机运营途径 263.5总结 34参照文献 36

引言自动化立体仓库产生和发展是生产力高度发展和都市化进程不断发展成果。计算机浮现和应用，自动化仓库产生。仓库空间向立体化方向发展个，货位向空间延伸，高层货架和与之配套新型装卸搬运机械与周边设备浮现，立体仓库产生。自动化立体仓库是指在高层货架用货箱或托盘储存货品，用电子计算机管理和控制巷道式堆垛机及其他机械，不需要人工作业而实现收发作业仓库。自动化立体仓库是一种集信息、储存、管理于一体高技术密集型机电化产品，堆垛机和高层货架是其核心设备。随着电子技术与控制理论发展，各种控制办法被引入堆垛机控制。货位优化和巷道式堆垛机途径优化成为自动化立体仓库必要工作，因而本次课程设计针对这两点做出了详细简介。货位优化是用来拟定每一品规恰当储存方式，在恰当储存方式下空间储位分派。货位优化追求不同设备和货架类型特性、货品分组、货位规划、人工成本内置等因素以实现最佳货位布局，能有效掌握商品变化，将成本节约最大化。货位优化为正在营运仓库挖掘效率和成本，并为一种建设中配送中心或仓库提供营运前核心管理作准备。

1自动化立体仓库1.1概述自动化立体仓库作为当代化物流系统中重要构成某些,是一种多层存储货品高架仓库系统,重要由高层货架、巷道堆垛机、出入库输送设备、自动控制与管理系统所构成。出入库辅助设备及巷道堆垛机可以在计算机管理下，完毕货品出入库作业、实行综合库房管理并与上级管理系统联网，可以实现管理当代化、存取自动化，能按指令自动完毕货品存取作业,并能对库存货品进行自动化管理,是公司实现当代化管理重要手段。自动立体仓库在工厂自动化，弹性制造系统及电脑整合制造系统物流中占非常重要位置。其目不但是为了储存物料、零件、半成品、成品仓储，更是密切配合制造工厂产销筹划与物料需求筹划，妥善安排生产所需合理数量物料、零件，并尽量缩短其库存时间及避免了发生缺料、滞料，籍高架搬运车、输送机、无人搬运车等，然后保管成品而依销售预定准进对的出货，提高服务水平，事合了筹划、库存、生产、出入物流功能与管理，减少了生产成本。其构成某些：（1）货架:用于存储货品钢构造。重要有焊接式货架和组合式货架两种基本形式。（2）托盘（货箱）：用于承载货品器具，亦称工位器具。（3）巷道堆垛机:用于自动存取货品设备。按构造形式分为单立柱和双立柱两种基本形式；按服务方式分为直道、弯道和转移车三种基本形式。（4）输送机系统:立体库重要外围设备，负责将货品运送到堆垛机或从堆垛机将货品移走。输送机种类非常多，常用有辊道输送机，链条输送机，升降台，分派车，提高机，皮带机等。（5）AGV系统:即自动导向小车。依照其导向方式分为感应式导向小车和激光导向小车。（6）自动控制系统:驱动自动化立体库系统各设备自动控制系统。以采用现场总线方式为控制模式为主。（7）储存信息管理系统:亦称中央计算机管理系统。是全自动化立体库系统核心。典型自动化立体库系统均采用大型数据库系统（如ORACLE，SYBASE等）构筑典型客户机/服务器体系，可以与其她系统（如ERP系统等）联网或集成。

2.货位优化

2.1设计条件某自动化立体仓库采用2行3列单元货格式货架存储货品，一共有6个货格，每个货格存储一种托盘货品。货格以按列编码形式进行编号，如图2.1所示。已知其他参数假定如下：假设堆垛机在水平方向行驶速度Vx=3.0m/s，在垂直方向行驶速度Vy=2m/s；货格大小为L（长）×W（宽）×H（高）=1m×1m×0.8m；堆垛机初始状态在原点0处；货格j横坐标和纵坐标就是其所在列和行，如货格6坐标为（3，2）。既有6个托盘货品需要存储到货架上，货品出入库频率如表2.1所示。VyVy24613500Vx图2.1原始货格图Vx表2.1托盘货品出入库频率表货品频率货品频率货品频率A9C18E7B39D14F25依照以上条件，运用匈牙利算法合理安排各托盘货品存储位置。2.2计算系数矩阵2.2.1符号假设1.为第i种货品出入库频率（次数），i=A，B，C，D，E，F；2．，分别为货格j横坐标和纵坐标，即货格j所在列和行（距离巷道口近来列记为第1列，最底层记为第1层），j=1，2，3，4，5，6；3．为水平方向行驶速度；4.为垂直方向行驶速度；5.L为货格长；6.W为货格宽；7.H为货格高；8.为堆垛机运营之货格j所用时间，该时间是堆垛机行进过程中水平方向和垂直方向所用时间最大值，j=1，2，3，4，5，6；9.为堆垛机将货品i向货格j存取时所耗费时间。10.公式为=max（2.1）11.计算系数矩阵中系数：=（2.2）2.2.2已知条件=9，=39，=18，=14，=7，=25；=3.0m/s，=2.0m/s；L×W×H=1m×1m×0.8m；货格1坐标为（，）=(1,1)；货格2货格为（，）=（1，2）；货格3坐标为（，）=（2，1）；货格4坐标为（，）=（2，2）；货格5坐标为（，）=（3，1）；货格6坐标为（，）=（3，2）。2.2.3公式计算过程1.计算：=max=max=1/3=max=max=2/5=max=max=2/3=max=max=2/3=max=max=1=max=max=12.计算系数矩阵中系数：==9×1/3=3，==39×1/3=13，==18×1/3=6，==14×1/3=14/3，==7×1/3=7/3，==25×1/3=25/3；==9×2/5=18/5，==39×2/5=78/5，==18×2/5=36/5，==14×2/5=28/5，==7×2/5=14/5，==25×2/5=10；==9×2/3=6，==39×2/3=26，==18×2/3=12，==14×2/3=28/3，==7×2/3=14/3，==25×2/3=50/3；==9×2/3=6，==39×2/3=26，==18×2/3=12，==14×2/3=28/3，==7×2/3=14/3，==25×2/3=50/3；==9×1=9，==39×1=39，==18×1=18，==14×1=14，==7×1=7，==25×1=25；==9×1=9，==39×1=39，==18×1=18，==14×1=14，==7×1=7，==25×1=25；得到系数矩阵表：货品表2.2系数矩阵表货品货格货格ABCDEF1313614/37/325/3218/578/536/528/514/51036261228/314/350/346261228/314/350/359391814725693918147252.3运用匈牙利算法求解1.匈牙利算法环节第一步：建等效矩阵。（1）从系数矩阵每行元素中减去该行最小元素。（2）再从所得系数矩阵每列元素中减去该列最小元素。第二步：找独立0元素，进行试指派。（1）从只有一种0元素行（或列）开始，给这个0元素加括号（0），表达这行所代表货格已有一种货品分派。然后划去（0）所在列（或行）其他0元素，记作“”，表达这列所代表货品已指派。（2）对只有一种0元素列（或行）0元素加括号（0），然后划去（0）所在行（或列）0元素，记作“”。如果在（1），（2）两步中，遇到每一行和每一列均有两个或两个以上0元素，可任选一种加括号，同步把其所在行和列0元素都划去。（3）重复（1），（2）两步，直到所有0元素都被加括号或打叉。（4）加括号0元素即为独立0元素，若其个数m等于矩阵阶数n，则已得到问题最优解。若m<n，则转入第三步。第三步：用至少直线覆盖所有0元素。（1）对没有独立0元素行打“√”。（2）对以打“√”行中所含0元素列打“√”。（3）再对（2），（3），直到得不到新打“√”行、列为止。（4）将没有打“√”行和以打“√”列用直线覆盖，且直线数目一定等于独立0元素个数。转第四步。第四步：增长0元素。从没有被直线覆盖元素中找出最小元素。未被覆盖元素都减去该最小元素，而被两条线覆盖元素都加上该最小元素，其他元素不变。这样得到新系数矩阵，转第二步，重新拟定独立0元素。2.应用过程(1)给系数矩阵表乘以15，从系数矩阵每行元素中减去该行最小元素35、42、70、70、105、105．再从所得系数矩阵每列元素中减去该列最小元素，得到等效矩阵。（2）①从只有一种0元素第2行开始，给这个0元素加括号（0），表达这行所代表货格已有一种货品分派。然后划去（0）所在列其他0元素，记作“”，表达这列所代表货品已指派。②对只有一种0元素第1列0元素加括号（0），然后划去（0）所在行0元素，记作“”。独立0元素个数m=2<矩阵阶数n=6，转入下一步。（3）用至少直线覆盖所有0元素。①对第3、4、5、6行打“√”。②对第5列打“√”。③得不到新打“√”行、列，停止。④将没有打“√”行和已打“√”列用直线覆盖，且直线数目一定等于独立0元素个数。√√√√√√√√√√√√（4）增长0元素①从没有被直线覆盖元素中找出最小元素2。未被覆盖元素都减去该最小元素，而被两条线覆盖元素都加上该最小元素，其他元素不变。这样得到新系数矩阵，然后重新拟定独立0元素。 ②矩阵中独立0元素个数m=3＜n=6，用至少直线覆盖所有0元素。√√（5）增长0元素①从未被直线覆盖元素中找出一种最小元素８，未被覆盖元素都减去该最小元素，而被两条线覆盖元素都加上该最小元素，其他元素不变。这样得到新系数矩阵，然后重新拟定独立0元素。②矩阵中独立0元素个数m=3＜n=6，用至少直线覆盖所有0元素.√√√√（6）增长0元素①从未被直线覆盖元素中找出一种最小元素5，未被覆盖元素都减去该最小元素，而被两条线覆盖元素都加上该最小元素，其他元素不变。这样得到新系数矩阵，然后重新拟定独立0元素。√√②矩阵中独立0元素个数m=4＜n=6，用至少直线覆盖所有0元素。√√②矩阵中独立0元素个数m=4＜n=6，用至少直线覆盖所有0元素。 （7）增长0元素①从未被直线覆盖元素中找出一种最小元素20，未被覆盖元素都减去该最小元素，而被两条线覆盖元素都加上该最小元素，其他元素不变。这样得到新系数矩阵，然后重新拟定独立0元素。②矩阵中独立0元素个数m=4＜n=6，用至少直线覆盖所有0元素。√√√√√√（8）增长0元素①从未被直线覆盖元素中找出一种最小元素4，未被覆盖元素都减去该最小元素，而被两条线覆盖元素都加上该最小元素，其他元素不变。这样得到新系数矩阵，然后重新拟定独立0元素。②矩阵中独立0元素个数m=5＜n=6，用至少直线覆盖所有0元素。√√（9）增长0元素①从未被直线覆盖元素中找出一种最小元素10，未被覆盖元素都减去该最小元素，而被两条线覆盖元素都加上该最小元素，其他元素不变。这样得到新系数矩阵，然后重新拟定独立0元素。②矩阵中独立0元素个数m=5＜n=6，用至少直线覆盖所有0元素。√√√√√√√√ （9）增长0元素①即从未被直线覆盖元素中找出一种最小元素7，未被覆盖元素都减去该最小元素，而被两条线覆盖元素都加上该最小元素，其他元素不变。这样得到新系数矩阵，然后重新拟定独立0元素。②矩阵中独立0元素个数m=5＜n=6，用至少直线覆盖所有0元素。√√√√√√(10）增长0元素①从未被直线覆盖元素中找出一种最小元素16，未被覆盖元素都减去该最小元素，而被两条线覆盖元素都加上该最小元素，其他元素不变。这样得到新系数矩阵，然后重新拟定独立0元素。②m=n=6,因此可以得到优化方案，将矩阵中非0元素变为0，将独立0元素变为1.由解可得最优分派方案：A货品放5货格，B货品放1货格，C货品放4货格，D货品放3货格，E货品放6货格，F货品放2货格。可以将得出最优分派方案绘制成图2.2所示：VyVy2货品F4货品C6货品E1货品B3货品D5货品A图2.2货品安放规划图0Vx图2.2货品安放规划图0Vx2.4总结面对成千上万货格，立体仓库货位存储优化已成为提高存取效率、减少成本核心，这需要对不同货品在仓库中存储位置进行合理分派，这可通过运用匈牙利算法来达到此目。通过匈牙利算法得到货位分派，可以对仓库中货品储位进行进行整合，使得货品在货格中存储位置最优、取放途径最优，从而达到进货和出货时既经济又省时，同步可使物品破损率达到最低，这对于提高公司品牌起重要作用。通过这次课程设计我也结识到了货位优化对于一种仓库重要性，这次学习使得我也学习到了诸多物流知识，对于教师解说过程中关于自动化立体仓库某些问题也得到了充分理解，这次课程设计过程中也让我学到诸多，以及在设计过程中咱们应当要认真积极态度，以及在整顿课题任务时要仔细，只有这样才干保证咱们在做事情过程中会减少误差。

3堆垛机途径优化最短途径问题是图论中一种典型问题。由于问题中边权值往往可以从距离引申为其她沿途径线性积累度量，如：时间、耗费等，因此最短途径问题在实际生活中有着广泛应用。分层思想作为一种重要思想，也有着许多应用，特别在是某些高效办法中，如：动态规划中阶段划分、图论中基于求阻塞流最大流算法等。将分层思想应用到最短途径问题中，正是分层思想和最短途径问题强强联合。因而正是基于此问题，将最短路途径用于堆垛机途径优化，如下便用近来邻点法和插入法进行堆垛机途径优化。3.1设计条件VyVy4(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)01(A)05(C)9(M)13(P)17(L)VxVx图3.1最后货位规划图随机从图3.1中20个货格中抽出10个货格货品，分别用节点V，V，V，V，V，V，V，V，V，V表达。节点间距离用直角距离公式:式(3.1）。3.2设计规定（1）绘出货格和节点相对位置图及节点相对距离表（需先列式计算各值）；（2）详细地写出近来邻点法和近来插入法每一环节及计算成果。（3）分析两种办法成果。（4）设计结束后，谈谈自己看法。3.3设计办法分别用近来邻点法和近来插入法找出堆垛机存取10个托盘货品合理路线。在堆垛机开始拣选之前，由于设备及系统依照实际状况每台堆垛机分派一定数量货位，被分派货位用阴影小方格表达，图中实心小黑点表达堆垛机从货架上取货时，需要在仓库中停留位置点，可以选用办法有近来零点法、近来插入发和遗传算法等。3.4求解过程一方面依照设计规定，绘出货格和节点相对位置图如图3.2、3.3所示：VyVy 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)VxoVxo图3.2货格相对位置图V10V10V9V8V7V6V5V4V3V2V1图3.3节点相对位置引用d=|x-x|×L+|y-y|×H式(3.1）计算节点间距离dv1v2=|xv2-xv1|×L+|yv2-yv1|×H=|1-1|×1+|3-1|×0.8=0.8dv1v3=|xv3-xv1|×L+|yv3-yv1|×H=|2-1|×1+|1-1|×0.8=1.8dv1v4=|xv4-xv1|×L+|yv4-yv1|×H=|2-1|×1+|4-1|×0.8=3.4dv1v5=|xv5-xv1|×L+|yv5-yv1|×H=|3-1|×1+|2-1|×0.8=2.8dv1v6=|xv6-xv1|×L+|yv6-yv1|×H=|3-1|×1+|4-1|×0.8=3.6dv1v7=|xv7-xv1|×L+|yv7-yv1|×H=|4-1|×1+|2-1|×0.8=3dv1v8=|xv8-xv1|×L+|yv8-yv1|×H=|4-1|×1+|3-1|×0.8=4.6dv1v9=|xv9-xv1|×L+|yv9-yv1|×H=|5-1|×1+|1-1|×0.8=4dv1v10=|xv10-xv1|×L+|yv10-yv1|×H=|5-1|×1+|3-1|×0.8=5.6dv2v3=|xv3-xv2|×L+|yv3-yv2|×H=|2-1|×1+|1-3|×0.8=1dv2v4=|xv4-xv2|×L+|yv4-yv2|×H=|2-1|×1+|4-3|×0.8=2.6dv2v5=|xv5-xv2|×L+|yv5-yv2|×H=|3-1|×1+|2-3|×0.8=2dv2v6=|xv6-xv2|×L+|yv6-yv2|×H=|3-1|×1+|4-3|×0.8=2.8dv2v7=|xv7-xv2|×L+|yv7-yv2|×H=|4-1|×1+|2-3|×0.8=3.8dv2v8=|xv8-xv2|×L+|yv8-yv2|×H=|4-1|×1+|3-3|×0.8=3.8dv2v9=|xv9-xv2|×L+|yv9-yv2|×H=|5-1|×1+|1-3|×0.8=4.8dv2v10=|xv10-xv2|×L+|yv10-yv2|×H=|5-1|×1+|3-3|×0.8=4.8dv3v4=|xv4-xv3|×L+|yv4-yv3|×H=|2-2|×1+|4-1|×0.8=1.6dv3v5=|xv5-xv3|×L+|yv5-yv3|×H=|3-2|×1+|2-1|×0.8=1dv3v6=|xv6-xv3|×L+|yv6-yv3|×H=|3-2|×1+|4-1|×0.8=1.8dv3v7=|xv7-xv3|×L+|yv7-yv3|×H=|4-2|×1+|2-1|×0.8=2.8dv3v8=|xv8-xv3|×L+|yv8-yv3|×H=|4-2|×1+|3-1|×0.8=2.8dv3v9=|xv9-xv3|×L+|yv9-yv3|×H=|5-2|×1+|1-1|×0.8=3.8dv3v10=|xv10-xv3|×L+|yv10-yv3|×H=|5-2|×1+|3-1|×0.8=3.8dv4v5=|xv5-xv4|×L+|yv5-yv4|×H=|3-2|×1+|2-4|×0.8=2.6dv4v6=|xv6-xv4|×L+|yv6-yv4|×H=|3-2|×1+|4-4|×0.8=1.8dv4v7=|xv7-xv4|×L+|yv7-yv4|×H=|4-2|×1+|2-4|×0.8=4.4dv4v8=|xv8-xv4|×L+|yv8-yv4|×H=|4-2|×1+|3-4|×0.8=2.8dv4v9=|xv9-xv4|×L+|yv9-yv4|×H=|5-2|×1+|1-4|×0.8=5.4dv4v10=|xv10-xv4|×L+|yv10-yv4|×H=|5-2|×1+|3-4|×0.8=3.8dv5v6=|xv6-xv5|×L+|yv6-yv5|×H=|3-3|×1+|4-2|×0.8=0.8dv5v7=|xv7-xv5|×L+|yv7-yv5|×H=|4-3|×1+|2-2|×0.8=1.8dv5v8=|xv8-xv5|×L+|yv8-yv5|×H=|4-3|×1+|3-2|×0.8=1.8dv5v9=|xv9-xv5|×L+|yv9-yv5|×H=|5-3|×1+|1-2|×0.8=2.8dv5v10=|xv10-xv5|×L+|yv10-yv5|×H=|5-3|×1+|3-2|×0.8=2.8dv6v7=|xv7-xv6|×L+|yv7-yv6|×H=|4-3|×1+|2-4|×0.8=2.6dv6v8=|xv8-xv6|×L+|yv8-yv6|×H=|4-3|×1+|3-4|×0.8=1dv6v9=|xv9-xv6|×L+|yv9-yv6|×H=|5-3|×1+|1-4|×0.8=3.6dv6v10=|xv10-xv6|×L+|yv10-yv6|×H=|5-3|×1+|3-4|×0.8=2dv7v8=|xv8-xv7|×L+|yv8-yv7|×H=|4-4|×1+|3-2|×0.8=1.6dv7v9=|xv9-xv7|×L+|yv9-yv7|×H=|5-4|×1+|1-2|×0.8=1dv7v10=|xv10-xv7|×L+|yv10-yv7|×H=|5-4|×1+|3-2|×0.8=2.6dv8v9=|xv9-xv8|×L+|yv9-yv8|×H=|5-4|×1+|1-3|×0.8=2.6dv8v10=|xv10-xv8|×L+|yv10-yv8|×H=|5-4|×1+|3-3|×0.8=1dv9v10=|xv10-xv9|×L+|yv10-yv9|×H=|5-5|×1+|3-1|×0.8=1.6依照两节点相对距离绘制节点相对距离表3.1：表3.1节点相对距离表节点VVVVVVVVVVV—0.81.83.42.83.634.645.6V—12.622.83.83.84.84.8V—1.611.82.82.83.83.8V—2.61.84.42.85.43.8V—0.81.81.82.82.8V—2.613.62V—1.612.6V—2.61V—1.6V—3.4.1近来邻点法求堆垛机运营途径1近来邻点法1.1近来邻点法思路从零点开始，作为整个回路起点。找到离刚刚加入到回路顶点近来一种顶点，并将其加入到回路中。重复环节（2），直到所有顶点都加入到回路中。最后，将最后一种加入顶点和起点连接起来。应用过程V1（1）先将节点v1加入到回路中，T={v1}。V1 图3.4加入节点v（2）从节点v1出发，在节点2、3、4、5、6、7、8、9、10中，找出离v1近来节点。Min因而将节点v2加入到回路中，T1={v1,v2}。V10V10V9V8V7V6V5V4V3V2V1图3.5运营路线（3）从节点v2出发，在节点3、4、5、6、7、8、9、10中，找出离v2近来节点。Min因而就可以将v3加入到回路中，T2={v1,v2,v3}。V10V10V9V8V7V6V5V4V3V2V1图3.6运营路线（4）从节点v3出发，在节点4、5、6、7、8、9、10中，找出离v3近来节点。Min因而就可以将v5加入到回路中，T3={v1,v2,v3,v5}V10V10V9V8V7V6V5V4V3V2V1图3.7运营路线（5）从节点v5出发，在节点4、6、7、8、9、10中，找出离v5近来节点。Min因而就可以将v6加入到回路中，T4={v1,v2,v3,v5,v6}V10V10V9V8V7V6V5V4V3V2V1图3.8运营路线 （6）从节点v6出发，在节点4、7、8、9、10中，找出离v6近来节点。Min因而就可以将v8加入到回路中，T5={v1,v2,v3,v5,v6,v8}V10V10V9V8V7V6V5V4V3V2V1图3.9运营路线（7）从节点v8出发，在节点4、7、9、10中，找出离v8近来节点。Min因而就可以将v10加入到回路中，T6={v1,v2,v3,v5,,v6，v8，v10}V10V10V9V8V7V6V5V4V3V2V1图3.10运营路线(8)从节点v10出发，在节点4、7、9中，找出离v10近来节点。Min因而就可以将v9加入到回路中，T7={v1,v2,v3,v5,v6,v8，v10,v9}形成如图3.11所示运营路线V10V10V9V8V7V6V5V4V3V2V1图3.11运营路线(9)从节点v9出发，在节点4、7中，找出离v9近来节点。Min因而就可以将v7加入到回路中，T8={v1,v2,v3,v5,v6,v8，v10,v9,v7}形成如图3.12所示运营路线V10V10V9V8V7V6V5V4V3V2V1图3.12运营路线(10)将最后点v4，,v1连接起来得到最后运营路线图,T9={v1,v2,v3,v5,v6,v8，v10,v9,v7,v4,v1}V10V10V9V8V7V6V5V4V3V2V1图3.13最后运营线路图因此堆垛机运营路线为：1→2→6→10→11→15→19→17→13→8即取送货品顺序为：A→B→F→I→H→E→S→L→P→K堆垛机总行驶距离为：Z=0.8+1+1+0.8+1+1+1.6+1+4.4+3.4=163.4.2近来插入法求堆垛机运营途径2近来插入法2.1近来插入法思路（1）先将节点v1加入到回路中，找到d1k最小节点vk，形成一种子回路，T={v1,vk,v1}。（2）在剩余节点中，寻找一种离子回路中某一节点近来节点vk。（3）在子回路中找到一条弧（i,j）,使得里程增量最小。如果有多条满足条件，任选一条，然后将节点vk插入到节点vi和vj之间，用两条新弧（i,k）和（k,j）代替本来弧（i,j）,并将节点vk加入到子回路中。（4）重复环节（2）和（3），直到所有节点都加入到子回路中。2.2应用过程（1）比较货格相对距离表中从v1出发所有途径大小 Min这样就由节点v1和v2构成子回路，T={v1,v2,v1}V10V10V9V8V7V6V5V4V3V2V1图3.14由v1和v2构成子回路（2）然后考虑剩余节点、、、、、、，到和中某一种节点最小距离；Min由于对称性，无论将3插入到1和2之间来回途径中，成果都是同样，任选其一,这样构成一种新子回路T={v1,v2，v3,v1}V10V10V8V7V6V5V4V3V2V1V9图3.15由v1,v2和v3构成子回路（3）接着考虑剩余节点、、、、、，到、和中某一种节点最小距离；Min（4）由图3.15可知，节点有3个位置（条弧线）可以插入。当前分析将加入到哪里适当：①插入到（1,2）间，△=d15+d52-d12=2.8+2-0.8=4②插入到（2,3）间，△=d25+d53-d23=2+1-1=2③插入到（3,1）间，△=d35+d51-d31=1+2.8-1.8=2比较上面3种状况增量，插入（2,3）或（3,1）之间增量最小，任选其一，将节点加入到（2,3），因此成果为：T={v1,v2,v5v3，v1}其子回路V10V10V9V8V7V6V5V4V3V2V1图3.16由v1,v2,v3和v5构成字回路（5）接着考虑剩余节点、、、、，到、、和中某一节点最小距离；Min（6）由图3.16可知，节点有4个位置（条弧线）可以插入。当前分析将加入到哪里适当：①插入到（1,2）间，△=d16+d-d12=3.6+2.8-0.8=5.6②插入到（2,5）间，△=d+d-d=2.8+0.8-2=1.6③插入到（3,5）间，△=d+d-d=1.8+0.8-1=1.6④插入到（3,1）间，△=d+d-d=1.8+3.6-1.8=3.6比较上面4种状况增量，将插入（2,5）或（3,5）之间增量最小，任选其一，将v5插入（2,5）之间，则成果为：T={v1,v2,v,v，v，v1}其子回路则变为如图3.17所示：V10V10V9V8V7V6V5V4V3V2V1图3.17由v1,v2,v,v，v构成子回路(7)接着考虑剩余节点、、、，到、、、、中某一节点最小距离Min（8）由图3.17可知，节点有5个位置（条弧线）可以插入。当前分析将加入到哪里适当：①插入到（1,2）间，△=d18+d-d12=4.6+3.8-0.8=7.6②插入到（2,6）间，△=d+d-d=3.8+1-2.8=2③插入到（6,5）间，△=d+d-d=1+1.8-0.8=2④插入到（5,3）间，△=d+d-d=1.8+2.8-1=3.6⑤插入到（3,1）间，△=d+d-d=2.8+4.6-1.8=5.6比较上面5种状况增量，可将插入（6,5）或（2,6）之间增量最小，任选其一，若将插入（6,5）之间，则成果为：T={、、、、、、}其子回路则变为图3.18所示：V10V10V9V8V7V6V5V4V3V2V1图3.18由、、、、、构成子回路（9）接着剩余节点、、，到、、、、、中某一节点最小距离Min（10）由图3.18可知有6个位置（条弧线）可以插入。当前分析将加入到哪里适当：①插入到（1,2）间，△=d+d-d12=5.6+4.8-0.8=9.6②插入到（2,6）间，△=d+d-d=4.8+2-2.8=4③插入到（6,8）间，△=d+d-d=2+1-1=2④插入到（8,5）间，△=d+d-d=1+2.8-1.8=2⑤插入到（5,3）间，△=d+d-d=2.8+3.8-1=5.6⑥插入到（3,1）间，△=d+d-d=3.8+5.6-1.8=7.6比较上面6种状况增量，插入到（6,8）或（8,5）之间增量最小，任选其一，因此将节点加入到（8,5）间，成果为：T={、、、、、、、}其子回路则变为图3.19所示：V10V10V9V8V7V6V5V4V3V2V1图3.19、、、、、、构成子回路（11）接着考虑剩余节点、、到、、、、、、中某一节点最小距离；Min（12）由图3.19可知有7个位置（条弧线）可以插入。当前分析将加入到哪里适当：①插入到（1,2）间，△=d+d-d12=3.4+2.6-0.8=5.2②插入到（2,6）间，△=d+d-d=2.6+1.8-2.8=1.6③插入到（6,8）间，△=d+d-d=1.8+2.8-1=3.6④插入到（8,10）间，△=d+d-d=2.8+3.8-1=5.6⑤插入到（10，5）间，△=d+d-d=3.8+2.6-2.8=3.6⑥插入到（5,3）间，△=d+d-d=2.6+1.6-1=3.2⑦插入到(3，1)间，△=d+d-d=1.6+3.4-1.8=3.2比较上面7种状况增量，插入到（2,6）之间增量最小，因此将节点加入到（2,6）间，成果为：T={、、、、、、、、}其子回路则变图3.20所示：V10V10V9V8V7V6V5V4V3V2V1图3.20、、、、、、、构成子回路（13）接着考虑剩余节点、到、、、、、、、中某一节点最小距离；Min（14）由图3.20可知有8个位置（条弧线）可以插入。当前分析将加入到哪里适当：①插入到（1,2）间，△=d+d-d12=4+4.8-0.8=8②插入到（2,4）间，△=d+d-d=4.8+5.4-2.6=7.6③插入到（4,6）间，△=d+d-d=5.4+3.6-1.8=7.2④插入到（6,8）间，△=d+d-d=3.6+2.6-1=5.2⑤插入到（8，10）间，△=d+d-d=1+1.6-1=1.6⑥插入到（10,5）间，△=d+d-d=1.6+2.8-2.8=1.6⑦插入到(5，3)间，△=d+d-d=2.8+3.8-1=5.6⑧插入到(3，1)间，△=d+d-d=3.8+4-1.8=6比较上面8种状况增量，插入到（8,10）和（10,5）之间增量最小，任选其一，因此将节点加入到（10，5）间，成果为：T={、、、、、、、、、}其子回路如图3.21所示：V10V10V9V8V7V6V5V4V3V2V1图3.21、、、、、、、、构成子回路（15）最后考虑剩余节点到、、、、、、、、中某一节点最小距离；Min（16）有9个位置（条弧线）可以插入。当前分析将加入到哪里适当：①插入到（1,2）