自动化立体仓库系统课程设计.docx

目录引言11自动化立体仓库21.1概述22货位优化32.1设计条件32.2计算系数矩阵3 2.2.1符号假设3 2.2.2已知条件4 2.2.3公式计算过程42.3运用匈牙利算法求解62.4总结133堆垛机路径优化153.1 设计条件153.2设计要求163.3设计方法163.4求解过程16 3.4.1最近邻点法求堆垛机运行路径19 3.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所示。Vy2461350Vx图2.1原始货格图表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=3n=6，用最少的直线覆盖所有0元素。（5）增加0元素从未被直线覆盖的元素中找出一个最小元素，未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩阵，然后重新确定独立0元素。 矩阵中独立0元素的个数m=3n=6，用最少的直线覆盖所有0元素.（6）增加0元素从未被直线覆盖的元素中找出一个最小元素5，未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩阵，然后重新确定独立0元素。矩阵中独立0元素的个数m=4n=6，用最少的直线覆盖所有0元素。（7）增加0元素从未被直线覆盖的元素中找出一个最小元素20，未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩阵，然后重新确定独立0元素。 矩阵中独立0元素的个数m=4n=6，用最少的直线覆盖所有0元素。（8）增加0元素从未被直线覆盖的元素中找出一个最小元素4，未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩阵，然后重新确定独立0元素。 矩阵中独立0元素的个数m=5n=6，用最少的直线覆盖所有0元素。（9）增加0元素从未被直线覆盖的元素中找出一个最小元素10，未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩阵，然后重新确定独立0元素。 矩阵中独立0元素的个数m=5n=6，用最少的直线覆盖所有0元素。 （9）增加0元素即从未被直线覆盖的元素中找出一个最小元素7，未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到新系数矩阵，然后重新确定独立0元素。 矩阵中独立0元素的个数m=5n=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所示：Vy2货物F4货物C6货物E1货物B3货物D5货物A图2.2货物安放规划图0Vx2.4总结面对成千上万的货格，立体仓库的货位存储优化已成为提高存取效率、降低成本的关键，这需要对不同货物在仓库中的存放位置进行合理分配，这可通过利用匈牙利算法来达到此目的。通过匈牙利算法得到的货位分配，可以对仓库中的货物储位进行进行整合，使得货物的在货格中的存放位置最优、取放路径最优，从而达到进货和出货时既经济又省时，同时可使物品的破损率达到最低，这对于提高企业的品牌起重要作用。通过这次课程设计我也认识到了货位优化对于一个仓库的重要性，这次学习使得我也学习到了很多的物流知识，对于老师讲解过程中的关于自动化立体仓库的一些问题也得到了充分理解，这次的课程设计过程中也让我学到很多，以及在设计过程中我们应该要认真的积极态度，以及在整理课题任务时要仔细，只有这样才能保证我们在做事情的过程中会减少误差。3堆垛机路径优化最短路径问题是图论中的一个经典问题。由于问题中边的权值往往可以从距离引申为其他沿路径线性积累的度量，如：时间、花费等，所以最短路径问题在实际生活中有着广泛的应用。分层思想作为一个重要的思想，也有着许多应用，特别在是某些高效的方法中，如：动态规划中的阶段划分、图论中基于求阻塞流的最大流算法等。将分层思想应用到最短路径问题中，正是分层思想和最短路径问题的强强联合。因此正是基于此问题，将最短路路径用于堆垛机的路径优化，以下便用最近邻点法和插入法进行堆垛机的路径优化。 3.1 设计条件Vy4 (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)5 (C)9 (M)13 (P)17 (L)Vx图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所示：Vy4 (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)Vxo图3.2 货格的相对位置图V10V9V8V7V6V5V4V3V2V1 图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.8 dv1v3=|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.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.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.8 dv2v8=|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.8 dv3v9=|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.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 dv9v10=|xv10-xv9|×L+|yv10-yv9|×H=|5-5|×1+|3-1|×0.8=1.6根据两节点的相对距离绘制节点相对距离表3.1：表3.1 节点相对距离表节点VVVVVVVVVVV0.81.83.42.83.634.645.6V12.622.83.83.84.84.8V1.611.82.82.83.83.8V2.61.84.42.85.43.8V0.81.81.82.82.8V2.613.62V1.612.6V2.61V1.6V3.4.1最近邻点法求堆垛机运行路径1 最近邻点法1.1 最近邻点法的思路（1） 从零点开始，作为整个回路的起点。（2） 找到离刚刚加入到回路的顶点最近的一个顶点，并将其加入到回路中。（3） 重复步骤（2），直到所有顶点都加入到回路中。（4） 最后，将最后一个加入的顶点和起点连接起来。1.2 应用过程V1（1）先将节点v1加入到回路中，T=v1。图3.4 加入节点v（2） 从节点v1出发，在节点2、3、4、5、6、7、8、9、10中，找出离v1 最近的节点。Min 因此将节点v2加入到回路中，T1=v1,v2。V10V9V8V7V6V5V4V3V2V1图 3.5 运行路线（3）从节点v2出发，在节点3、4、5、6、7、8、9、10中，找出离v2最近的节点。Min因此就可以将v3加入到回路中，T2=v1,v2,v3。V10V9V8V7V6V5V4V3V2V1图 3.6 运行路线（4）从节点v3出发，在节点4、5、6、7、8、9、10中，找出离v3最近的节点。Min因此就可以将v5加入到回路中，T3=v1,v2,v3,v5V10V9V8V7V6V5V4V3V2V1图 3.7 运行路线（5）从节点v5出发，在节点4、6、7、8、9、10中，找出离v5最近的节点。Min因此就可以将v6加入到回路中，T4=v1,v2,v3,v5,v6V10V9V8V7V6V5V4V3V2V1图 3.8 运行路线（6） 从节点v6出发，在节点4、7、8、9、10中，找出离v6最近的节点。Min因此就可以将v8加入到回路中，T5=v1,v2,v3,v5,v6,v8V10V9V8V7V6V5V4V3V2V1图 3.9 运行路线（7） 从节点v8出发，在节点4、7、9、10中，找出离v8最近的节点。Min因此就可以将v10加入到回路中，T6=v1,v2,v3,v5,v6，v8，v10V10V9V8V7V6V5V4V3V2V1图 3.10 运行路线(8)从节点v10出发，在节点4、7、9中，找出离v10最近的节点。Min因此就可以将v9加入到回路中，T7=v1,v2,v3,v5,v6,v8，v10,v9形成如图3.11所示的运行路线V10V9V8V7V6V5V4V3V2V1图 3.11 运行路线(9)从节点v9出发，在节点4、7中，找出离v9最近的节点。Min因此就可以将v7加入到回路中，T8=v1,v2,v3,v5,v6,v8，v10,v9,v7形成如图3.12所示的运行路线V10V9V8V7V6V5V4V3V2V1图 3.12 运行路线(10)将最后的点v4, ,v1连接起来得到最后的运行路线图,T9=v1,v2,v3,v5,v6,v8，v10,v9,v7 ,v4,v1V10V9V8V7V6V5V4V3V2V1图 3.13 最终运行线路图所以堆垛机运行路线为：1261011151917138即取送货物次序为：ABFIHESLPK堆垛机总行驶距离为：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,v1V10V9V8V7V6V5V4V3V2V1图3.14 由v1和v2构成的子回路（2）然后考虑剩下的节点、 ，到和中某一个节点的最小距离；Min由于对称性，无论将3插入到1和2之间往返路径中，结果都是一样的，任选其一,这样构成一个新的子回路T=v1,v2, v3,v1V10V8V7V6V5V4V3V2V1V9图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,v5 v3，v1其子回路V10V9V8V7V6V5V4V3V2V1图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所示：V10V9V8V7V6V5V4V3V2V1图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所示：V10V9V8V7V6V5V4V3V2V1图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所示：V10V9V8V7V6V5V4V3V2V1图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=、