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

1、目录TOC o 1-4 h z u HYPERLINK l _Toc297814593 引言 PAGEREF _Toc297814593 h 1 HYPERLINK l _Toc297814594 1自动化立体仓仓库 PAGEREF _Toc297814594 h 2 HYPERLINK l _Toc297814595 1.1概述 PAGEREF _Toc297814595 h 22 HYPERLINK l _Toc297814599 2货位优化33 HYPERLINK l _Toc297814600 2.1设计条件件3 HYPERLINK l _Toc297814601 2.2计算系数数矩阵

2、3 HYPERLINK l _Toc297814602 2.2.11符号假设3 HYPERLINK l _Toc297814603 2.2.22已知条件4 HYPERLINK l _Toc297814604 2.2.33公式计算过过程4 HYPERLINK l _Toc297814605 2.3运用匈牙牙利算法求解解6 HYPERLINK l _Toc297814608 2.4总结113 HYPERLINK l _Toc297814609 3堆垛机路径优优化15 HYPERLINK l _Toc297814610 3.1 设计计条件15 HYPERLINK l _Toc297814611 3.

3、2设计要求求16 HYPERLINK l _Toc297814612 3.3设计方法法16 HYPERLINK l _Toc297814613 3.4求解过程程16 HYPERLINK l _Toc297814614 3.4.11最近邻点法法求堆垛机运运行路径19 HYPERLINK l _Toc297814615 3.4.22最近插入法法求堆垛机运运行路径26 HYPERLINK l _Toc297814616 3.5 总结34 HYPERLINK l _Toc297814617 参考文献366 HYPERLINK l _Toc297814619 引言自动化立体仓库库产生和发展展是生产力高高

4、度发展和城城市化进程不不断发展结果果。计算机的的出现和应用用，自动化仓仓库的产生。仓仓库空间向立立体化方向发发展个，货位位向空间延伸伸，高层货架架和与之配套套的新型装卸卸搬运机械与与周边设备出出现，立体仓仓库产生。自动化立体仓库库是指在高层层货架用货箱箱或托盘储存存货物，用电电子计算机管管理和控制巷巷道式堆垛机机及其它机械械，不需要人人工作业而实实现收发作业业的仓库。自动化立体仓库库是一种集信信息、储存、管管理于一体的的高技术密集集型机电化产产品，堆垛机机和高层货架架是其关键设设备。随着电电子技术与控控制理论的发发展，各种控控制方法被引引入堆垛机的的控制。货位位优化和巷道道式堆垛机的的路径优化

5、成成为自动化立立体仓库的必必要工作，因因此本次课程程设计针对这这两点做出了了详细的介绍绍。货位优化是用来来确定每一品品规的恰当储储存方式，在在恰当的储存存方式下的空空间储位分配配。货位优化化追求不同设设备和货架类类型特征、货货品分组、货货位规划、人人工成本内置置等因素以实实现最佳的 HYPERLINK /view/727829.htm 货货位布局，能能有效掌握商商品变化，将将成本节约最最大化。货位优化为正在在营运的仓库库挖掘效率和和成本，并为为一个建设中中的 HYPERLINK /view/397401.htm 配送中心心或仓库提供供营运前的关关键管理作准准备。1自动化立体仓仓库1.1概述自动

6、化立体仓库库作为 HYPERLINK /dangdai/ 现代化物流系系统中的重要要组成部分,是一种多层层存放货物的的高架仓库系系统,主要由由高层货架、巷巷道堆垛机、出出入库输送设设备、自动控控制与管理系系统所组成。出出入库辅助设设备及巷道堆堆垛机能够在在 HYPERLINK /pc/ 计算机管理下下，完成货物物的出入库作作业、实施综综合库房管理理并与上级管管理系统联网网，可以实现现管理现代化化、存取自动动化，能按指指令自动完成成货物的存取取作业,并能能对库存的货货物进行自动动化管理,是是企业实现现现代化管理的的重要手段。自自动立体仓库库在工厂自动动化，弹性制制造系统及电电脑整合制造造系统的物

7、流流中占非常重重要的位置。其其目的不仅是是为了储存物物料、零件、半半成品、成品品的仓储，更更是密切配合合制造工厂的的产销计划与与物料需求计计划，妥善安安排生产所需需合理数量的的物料、零件件，并尽量缩缩短其库存时时间及避免了了发生缺料、滞滞料，籍高架架搬运车、输输送机、无人人搬运车等，然然后保管成品品而依销售预预定准进正确确出货，提升升服务水平，事事合了计划、库库存、生产、出出入物流的功功能与管理，降降低了生产成成本。 其组成部分：（1） HYPERLINK /view/167019.htm 货架:用用于存储货物物的钢结构。主主要有焊接式式货架和组合合式货架两种种基本形式。（2）托盘（货货箱）：

8、用于于承载货物的的器具，亦称称工位器具。（3）巷道堆垛垛机:用于自自动存取货物物的设备。按按结构形式分分为单立柱和和双立柱两种种基本形式；按服务方式式分为直道、弯弯道和转移车车三种基本形形式。（4）输送机系系统:立体库库的主要外围围设备，负责责将货物运送送到堆垛机或或从堆垛机将将货物移走。输输送机种类非非常多，常见见的有辊道输输送机，链条条输送机，升升降台，分配配车，提升机机，皮带机等等。（5）AGV系系统:即自动动导向小车。根根据其导向方方式分为感应应式导向小车车和激光导向向小车。（6）自动控制制系统:驱动动自动化立体体库系统各设设备的自动控控制系统。以以采用现场总总线方式为控控制模式为主主

9、。（7）储存 HYPERLINK /view/45136.htm 信息息管理系统:亦称中央计计算机管理系系统。是全自自动化立体库库系统的核心心。典型的自自动化立体库库系统均采用用大型的 HYPERLINK /view/7809.htm 数据据库系统（如如ORACLLE，SYBBASE等）构构筑典型的客客户机/服务务器体系，可可以与其他系系统（如 HYPERLINK /view/86915.htm ERRP系统等）联联网或集成。 2.货位优化 2.1设计条件件某自动化立体仓仓库采用2行行3列的单元元货格式货架架存放货物，一一共有6个货货格，每个货货格存放一个个托盘货物。货货格以按列编编码的形式进

10、进行编号，如如图2.1所示。已已知其它参数数假定如下：假设堆垛机机在水平方向向的行驶速度度Vx=3.0m/s，在在垂直方向的的行驶速度VVy=2m/s；货货格大小为LL（长）W（宽）H（高）=1m1m0.8m；堆堆垛机初始状状态在原点00处；货格jj的横坐标和和纵坐标就是是其所在的列列和行，如货货格6的坐标标为（3，22）。现有66个托盘货物物需要存放到到货架上，货货物的出入库库频率如表22.1所示。VyVy24613500Vx图2.1原始货货格图Vx表2.1 托盘盘货物出入库库频率表货物频率货物频率货物频率A9C18E7B39D14F25根据以上条件，利利用匈牙利算算法合理安排排各托盘货物物

11、的存放位置置。2.2计算系数数矩阵2.2.1符号号假设1.为第i种货货物的出入库库频率（次数数），i=A，B，CC，D，E，FF；2，分别为货货格j的横坐坐标和纵坐标标，即货格jj所在的列和和行（距离巷巷道口最近的的列记为第11列，最底层层记为第1层层），j=11，2，3，44，5，6；3为水平方向向的行驶速度度；4.为垂直方向向的行驶速度度；5.L为货格的的长；6.W为货格的的宽；7.H为货格的的高；8.为堆垛机运运行之货格jj所用时间，该时间是堆垛机行进过程中水平方向和垂直方向所用时间的最大值，j=1，2，3，4，5，6；9. 为堆垛机机将货物i向向货格j存取取时所花费的的时间。10. 公

12、公式为=maax （2.1）11. 计算系系数矩阵中的的系数： = （22.2）2.2.2已知知条件=9，=39，=18，=14，=7，=25；=3.0m/ss, =2.0m/ss；LWH=1m1m0.8m；货格1的坐标为为（，）=(1,1)；货格格2的货格为为（，）=（1，22）；货格33的坐标为（，）=（2，1）；货格4的坐标为（，）=（2，2）；货格5的坐标为（，）=（3，1）；货格6的坐标为（，）=（3，2）。2.2.3公式式计算过程1.计算： =max=maax=1/3=max=maax=2/5=max=maax=2/3=max=maax=2/3=max=maax=1=max=maa

13、x=12.计算系数矩矩阵中的系数数： =91/33=3, =391/3=113, =181/3=6, =141/3=114/3, =71/33=7/3， =251/3=25/3；=92/55=18/55， =392/5=778/5，=182/5=36/5， =142/5=228/5，=72/55=14/55， =252/5=110；=92/33=6， =392/3=226，=182/3=12， =142/3=28/3，=72/33=14/33， =252/3=550/3；=92/33=6， =392/3=226，=182/3=12， =142/3=28/3，=72/33=14/33， =252

14、/3=550/3；=91=99， =391=39，=181=18， =141=14，=71=77， =251=25；=91=99， =391=39，=181=18， =141=14，=71=77， =251=25；得到系数矩阵表表：货物 表2.2系数矩矩阵表货物货格货格ABCDEF1313614/37/325/3218/578/536/528/514/51036261228/314/350/346261228/314/350/359391814725693918147252.3运用匈牙牙利算法求解解1. 匈牙利算算法的步骤第一步：建等效效矩阵。（1）从系数矩矩阵的每行元元素中减去该该行的最小元

15、元素。（2）再从所得得系数矩阵的的每列元素中中减去该列的的最小元素。第二步：找独立立0元素，进进行试指派。（1）从只有一一个0元素的的行（或列）开开始，给这个个0元素加括括号（0），表表示这行所代代表的货格已已有一种货物物分配。然后后划去（0）所所在列（或行行）的其它00元素，记作作“”，表示这列列所代表的货货物已指派。（2）对只有一一个0元素的的列（或行）的的0元素加括括号（0），然然后划去（00）所在行（或或列）的0元元素，记作“”。如果在（1），（22）两步中，遇遇到每一行和和每一列都有有两个或两个个以上的0元元素，可任选选一个加括号号，同时把其其所在行和列列的0元素都都划去。（3）重复

16、（11），（2）两两步，直到所所有0元素都都被加括号或或打叉。（4）加括号的的0元素即为为独立0元素素，若其个数数m等于矩阵阵的阶数n，则则已得到问题题的最优解。若若mn，则则转入第三步步。第三步：用最少少的直线覆盖盖所有0元素素。（1）对没有独独立0元素的的行打“”。（2）对以打“”的行中所所含0元素的的列打“”。（3）再对（22），（3），直直到得不到新新的打“”的行、列列为止。（4）将没有打打“”的行和和以打“”的列用用直线覆盖，且且直线的数目目一定等于独独立0元素的的个数。转第第四步。第四步：增加00元素。 从没有被直线线覆盖的元素素中找出最小小元素。未被被覆盖的元素素都减去该最最小元

17、素，而而被两条线覆覆盖的元素都都加上该最小小元素，其它它元素不变。这这样得到新系系数矩阵，转转第二步，重重新确定独立立0元素。2.应用过程(1)给系数矩矩阵表乘以115， 从系数矩阵阵的每行元素素中减去该行行的最小元素素35、422、70、770、1055、105再从所得系系数矩阵的每每列元素中减减去该列的最最小元素，得得到等效矩阵阵。 （2）从只有有一个0元素素的第2行开开始，给这个个0元素加括括号（0），表表示这行所代代表的货格已已有一种货物物分配。然后后划去（0）所所在列的其它它0元素，记记作“”，表示这列列所代表的货货物已指派。对只有一个0元素的第1列的0元素加括号（0），然后划去（0

18、）所在行的0元素，记作“”。独立0元素的个个数m=2矩阵的阶数数n=6，转转入下一步。（3）用最少的的直线覆盖所所有0元素。对第3、4、55、6行打“”。对第5列打“”。得不到新的打打“”的行、列，停停止。将没有打“”的行和已打打“”的列用直线线覆盖，且直直线的数目一一定等于独立立0元素的个个数。 （4）增加0元元素从没有被直线线覆盖的元素素中找出最小小元素2。未未被覆盖的元元素都减去该该最小元素，而而被两条线覆覆盖的元素都都加上该最小小元素，其它它元素不变。这这样得到新系系数矩阵，然然后重新确定定独立0元素素。 矩阵中独立00元素的个数数m=3nn=6，用最最少的直线覆覆盖所有0元元素。（5

19、）增加0元元素从未被直线覆覆盖的元素中中找出一个最最小元素，未被覆盖盖的元素都减减去该最小元元素，而被两两条线覆盖的的元素都加上上该最小元素素，其它元素素不变。这样样得到新系数数矩阵，然后后重新确定独独立0元素。 矩阵中独立00元素的个数数m=3nn=6，用最最少的直线覆覆盖所有0元元素.（6）增加0元元素从未被直线覆覆盖的元素中中找出一个最最小元素5，未被覆盖盖的元素都减减去该最小元元素，而被两两条线覆盖的的元素都加上上该最小元素素，其它元素素不变。这样样得到新系数数矩阵，然后后重新确定独独立0元素。矩阵中独立0元素的个数m=4n=6，用最少的直线覆盖所有0元素。矩阵中独立0元素的个数m=4

20、n=6，用最少的直线覆盖所有0元素。（7）增加0元元素从未被直线覆覆盖的元素中中找出一个最最小元素200，未被覆盖盖的元素都减减去该最小元元素，而被两两条线覆盖的的元素都加上上该最小元素素，其它元素素不变。这样样得到新系数数矩阵，然后后重新确定独独立0元素。 矩阵中独立00元素的个数数m=4nn=6，用最最少的直线覆覆盖所有0元元素。（8）增加0元元素从未被直线覆覆盖的元素中中找出一个最最小元素4，未被覆盖盖的元素都减减去该最小元元素，而被两两条线覆盖的的元素都加上上该最小元素素，其它元素素不变。这样样得到新系数数矩阵，然后后重新确定独独立0元素。 矩阵中独立00元素的个数数m=5n=6，用最

21、少少的直线覆盖盖所有0元素素。（9）增加0元元素从未被直线覆覆盖的元素中中找出一个最最小元素100，未被覆盖盖的元素都减减去该最小元元素，而被两两条线覆盖的的元素都加上上该最小元素素，其它元素素不变。这样样得到新系数数矩阵，然后后重新确定独独立0元素。 矩阵中独立00元素的个数数m=5nn=6，用最最少的直线覆覆盖所有0元元素。 （9）增加0元元素即从未被直线线覆盖的元素素中找出一个个最小元素77，未被覆盖盖的元素都减减去该最小元元素，而被两两条线覆盖的的元素都加上上该最小元素素，其它元素素不变。这样样得到新系数数矩阵，然后后重新确定独独立0元素。 矩阵中独立00元素的个数数m=5nn=6，用

22、最最少的直线覆覆盖所有0元元素。 (10）增加加0元素从未被直线覆覆盖的元素中中找出一个最最小元素166，未被覆盖盖的元素都减减去该最小元元素，而被两两条线覆盖的的元素都加上上该最小元素素，其它元素素不变。这样样得到新系数数矩阵，然后后重新确定独独立0元素。 m=n=6,所以可以得得到优化方案案，将矩阵中中的非0元素素变为0，将将独立0元素素变为1. 由解可可得最优分配配方案：A货货物放5货格格，B货物放放1货格，CC货物放4货货格，D货物物放3货格，EE货物放6货货格，F货物物放2货格。可以将得出的最优分配方案绘制成图2.2所示：VyVy2货物F4货物C6货物E1货物B3货物D5货物A图2.

23、2货物安放规划图0Vx图2.2货物安放规划图0Vx2.4总结面对成千上万的的货格，立体体仓库的货位位存储优化已已成为提高存存取效率、降降低成本的关关键，这需要要对不同货物物在仓库中的的存放位置进进行合理分配配，这可通过过利用匈牙利利算法来达到到此目的。通通过匈牙利算算法得到的货货位分配，可可以对仓库中中的货物储位位进行进行整整合，使得货货物的在货格格中的存放位位置最优、取取放路径最优优，从而达到到进货和出货货时既经济又又省时，同时时可使物品的的破损率达到到最低，这对对于提高企业业的品牌起重重要作用。通过这次课程设设计我也认识识到了货位优优化对于一个个仓库的重要要性，这次学学习使得我也也学习到了

24、很很多的物流知知识，对于老老师讲解过程程中的关于自自动化立体仓仓库的一些问问题也得到了了充分理解，这这次的课程设设计过程中也也让我学到很很多，以及在在设计过程中中我们应该要要认真的积极极态度，以及及在整理课题题任务时要仔仔细，只有这这样才能保证证我们在做事事情的过程中中会减少误差差。3堆垛机路径优优化最短路径问题是是图论中的一一个经典问题题。由于问题题中边的权值值往往可以从从距离引申为为其他沿路径径线性积累的的度量，如：时间、花费费等，所以最最短路径问题题在实际生活活中有着广泛泛的应用。分层思想作为一一个重要的思思想，也有着着许多应用，特特别在是某些些高效的方法法中，如：动动态规划中的的阶段划

25、分、图图论中基于求求阻塞流的最最大流算法等等。将分层思思想应用到最最短路径问题题中，正是分分层思想和最最短路径问题题的强强联合合。因此正是是基于此问题题，将最短路路路径用于堆堆垛机的路径径优化，以下下便用最近邻邻点法和插入入法进行堆垛垛机的路径优优化。 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.11中的20个个货格中抽出出10个货格格的货

26、物，分分别用节点VV，V，V，V，V，V，V，V，V，V表示。节点点间的距离用用直角距离公公式: 式(3.1）。3.2设计要求求（1）绘出货格格和节点相对对位置图及节节点相对距离离表（需先列列式计算各的的值）；（2）详细地写写出最近邻点点法和最近插插入法的每一一步骤及计算算结果。（3）分析两种种方法的结果果。（4）设计结束束后，谈谈自自己的看法。 3.3设计方法法分别用最近邻点点法和最近插插入法找出堆堆垛机存取110个托盘货货物的合理路路线。在堆垛垛机开始拣选选之前，由于于设备及系统统根据实际情情况每台堆垛垛机分配一定定数量的货位位，被分配的的货位用阴影影的小方格表表示，图中的的实心小黑点点表

27、示堆垛机机从货架上取取货时，需要要在仓库中停停留的位置点点，可以选用用的方法的有有最近零点法法、最近插入入发和遗传算算法等。3.4求解过程程首先根据设计要要求，绘出货货格和节点相相对位置图如如图3.2、33.3所示：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)1 (A)5 (C)9 (M)13 (P)17 (L)VxoVxo图3.2 货格格的相对位置置图V10V10V9V8V7V6V5V4V3V2V1 图33.3 节点点的相对位置置引用d=|x-x|L+|y-yy

28、|H 式(3.1）计算算节点间距离离dv1v2=|xv2-xv1|L+|yv22-yv1|H=|1-11|1+|3-1|0.8=0.8 dv1v33=|xv3-xv1|L+|yv33-yv1|H=|2-11|1+|1-1|0.8=1.8dv1v4=|xv4-xv1|L+|yv44-yv1|H=|2-11|1+|4-11|0.8=33.4dv1v5=|xv5-xv1|L+|yv55-yv1|H=|3-11|1+|2-11|0.8=2.8dv1v6=|xv6-xv1|L+|yv66-yv1|H=|3-1|1+|4-11|0.8=3.6dv1v7=|xv7-xv1|L+|yv77-yv1|H=|4-

29、11|1+|2-11|0.8=33dv1v8=|xv8-xv1|L+|yv88-yv1|H=|4-11|1+|3-11|0.8=44.6 dv1v99=|xv9-xv1|L+|yv99-yv1|H=|5-11|1+|1-11|0.8=4 dv1v110=|xv100-xv1|L+|yv110-yv1|H=|5-11|1+|3-11|0.8=55.6dv2v3=|xv3-xv2|L+|yv33-yv2|H=|2-1|1+|1-3|0.8=11dv2v4=|xv4-xv2|L+|yv44-yv2|H=|2-1|1+|4-33|0.8=2.6dv2v5=|xv5-xv2|L+|yv55-yv2|H=

30、|3-1|1+|2-3|0.8=22dv2v6=|xv6-xv2|L+|yv66-yv2|H=|3-11|1+|4-33|0.8=22.8dv2v7=|xv7-xv2|L+|yv77-yv2|H=|4-1|1+|2-33|0.8=33.8 dv2v88=|xv8-xv2|L+|yv88-yv2|H=|4-1|1+|3-33|0.8=33.8dv2v9=|xv9-xv2|L+|yv99-yv2|H=|5-1|1+|1-33|0.8=44.8dv2v10=|xv100-xv2|L+|yv110-yv2|H=|5-1|1+|3-33|0.8=44.8dv3v4=|xv4-xv3|L+|yv44-yv

31、3|H=|2-2|1+|4-11|0.8=1.6dv3v5=|xv5-xv3|L+|yv55-yv3|H=|3-2|1+|2-11|0.8=1dv3v6=|xv6-xv3|L+|yv66-yv3|H=|3-22|1+|4-11|0.8=1.8dv3v7=|xv7-xv3|L+|yv77-yv3|H=|4-2|1+|2-11|0.8=2.8dv3v8=|xv8-xv3|L+|yv88-yv3|H=|4-2|1+|3-11|0.8=2.8 dv3v99=|xv9-xv3|L+|yv99-yv3|H=|5-2|1+|1-11|0.8=3.8dv3v10=|xv100-xv3|L+|yv110-yv3

32、|H=|5-2|1+|3-11|0.8=3.8 dv4v55=|xv5-xv4|L+|yv55-yv4|H=|3-2|1+|2-44|0.8=2.6 dv4v66=|xv6-xv4|L+|yv66-yv4|H=|3-22|1+|4-44|0.8=1.8 dv4v77=|xv7-xv4|L+|yv77-yv4|H=|4-2|1+|2-44|0.8=44.4 dv4v88=|xv8-xv4|L+|yv8-yv4|H=|4-2|1+|3-44|0.8=2.8 dv4v99=|xv9-xv4|L+|yv9-yv4|H=|5-22|1+|1-44|0.8=5.4 dv4v110=|xv10-xv4|L+

33、|yv10-yv4|H=|5-2|1+|3-44|0.8=33.8 dv5v66=|xv6-xv5|L+|yv66-yv5|H=|3-33|1+|4-22|0.8=0.8 dv5v77=|xv7-xv5|L+|yv77-yv5|H=|4-3|1+|2-22|0.8=1.8 dv5v88=|xv8-xv5|L+|yv8-yv5|H=|4-3|1+|3-22|0.8=11.8 dv5v99=|xv9-xv5|L+|yv9-yv5|H=|5-3|1+|1-22|0.8=2.8 dv5v110=|xv10-xv5|L+|yv10-yv5|H=|5-3|1+|3-22|0.8=2.8 dv6v77=|x

34、v7-xv6|L+|yv77-yv6|H=|4-3|1+|2-44|0.8=2.6 dv6v88=|xv8-xv6|L+|yv8-yv6|H=|4-3|1+|3-44|0.8=11 dv6v99=|xv9-xv6|L+|yv9-yv6|H=|5-3|1+|1-4|0.8=3.6 dv6v110=|xv10-xv6|L+|yv10-yv6|H=|5-3|1+|3-44|0.8=22 dv7v88=|xv8-xv7|L+|yv8-yv7|H=|4-44|1+|3-22|0.8=11.6 dv7v99=|xv9-xv7|L+|yv99-yv7|H=|5-44|1+|1-22|0.8=1 dv7v11

35、0=|xv10-xv7|L+|yv10-yv7|H=|5-44|1+|3-22|0.8=2.6 dv8v99=|xv9-xv8|L+|yv9-yv8|H=|5-44|1+|1-33|0.8=2.6 dv8v110=|xv10-xv8|L+|yv10-yv8|H=|5-44|1+|3-33|0.8=1 dv9v10=|xv10-xv9|L+|yv10-yv9|H=|5-5|1+|3-11|0.8=1.6根据两节点的相相对距离绘制制节点相对距距离表3.11：表3.1 节点点相对距离表表节点VVVVVVVVVVV2.83.634.645.6V12.64.84.8V1.63.83.8VV2.82.8V

36、2.613.62V1.612.6V2.61V1.6V3.4.1最近近邻点法求堆堆垛机运行路路径1 最近邻点法法1.1 最近邻邻点法的思路路从零点开始，作作为整个回路路的起点。找到离刚刚加入入到回路的顶顶点最近的一一个顶点，并并将其加入到到回路中。重复步骤（2），直直到所有顶点点都加入到回回路中。最后，将最后一一个加入的顶顶点和起点连连接起来。 应用过程V1（1）先将节点点v1加入到回路路中，T=v1。V1图3.4 加入入节点v（2） 从节点点v1出发，在节点点2、3、44、5、6、77、8、9、110中，找出出离v1 最近的节点。Min 因此将节点vv2加入到回路路中，T1=v1,v2。V10

37、V10V9V8V7V6V5V4V3V2V1图 3.5 运运行路线（3）从节点vv2出发，在节节点3、4、55、6、7、88、9、100中，找出离离v2最近的节点点。Min因此就可以将vv3加入到回路路中，T2=v1,v2,v3。V10V10V9V8V7V6V5V4V3V2V1图 3.6 运运行路线（4）从节点vv3出发，在节节点4、5、66、7、8、99、10中，找找出离v3最近的节点点。Min因此就可以将vv5加入到回路路中，T3=v1,v2,v3,v5V10V10V9V8V7V6V5V4V3V2V1图 3.7 运运行路线（5）从节点vv5出发，在节节点4、6、7、88、9、100中，找出离

38、离v5最近的节点点。Min因此就可以将vv6加入到回路路中，T4=v1,v2,v3,v5,v6V10V10V9V8V7V6V5V4V3V2V1图 3.8 运运行路线（6） 从节点点v6出发，在节节点4、7、8、99、10中，找找出离v6最近的节点点。Min因此就可以将vv8加入到回路路中，T5=v1,v2,v3,v5,v6,v8V10V10V9V8V7V6V5V4V3V2V1图 3.9 运运行路线（7） 从节点点v8出发，在节节点4、7、9、100中，找出离离v8最近的节点点。Min因此就可以将vv10加入到回回路中，T66=v1,v2,v3,v5,v6，v8，v10V10V10V9V8V7V

39、6V5V4V3V2V1图 3.10 运行路线(8)从节点vv10出发，在在节点4、77、9中，找出离离v10最近的节节点。Min因此就可以将vv9加入到回路路中，T7=v1,v2,v3,v5,v6,v8，v10,v9形成如图33.11所示示的运行路线线V10V10V9V8V7V6V5V4V3V2V1图 3.11 运行路线(9)从节点vv9出发，在节节点4、7中，找找出离v9最近的节点点。Min因此就可以将vv7加入到回路路中，T8=v1,v2,v3,v5,v6,v8，v10,v9,v7形成如图33.12所示示的运行路线线V10V10V9V8V7V6V5V4V3V2V1图 3.12 运行路线(1

40、0)将最后后的点v4, ,v1连接起来得得到最后的运运行路线图,T9=vv1,v2,v3,v5,v6,v8，v10,v9,v7 ,v4,v1V10V10V9V8V7V6V5V4V3V2V1图 3.13 最终运行线线路图所以堆垛机运行行路线为：11261011151917138即取送货物次序序为：ABFIHESLPK堆垛机总行驶距距离为：Z=0.8+11+1+0.8+1+11+1.6+1+4.44+3.4=163.4.2最近近插入法求堆堆垛机运行路路径2 最近插入法法2.1 最近插插入法的思路路（1）先将节点点v1加入到回路路中，找到dd1k最小的节节点vk ，形成一一个子回路，TT=v1 ,v

41、k ,v1。（2）在剩下的的节点中，寻寻找一个离子子回路中某一一节点最近的的节点vk 。（3）在子回路路中找到一条条弧（i,jj）,使得里里程增量最小小。如果有多多条满足条件件，任选一条条，然后将节节点vk插入到节点点vi和vj之间，用两两条新的弧（ii,k）和（k,jj）代替原来的的弧（i,jj）,并将节点点vk加入到子回回路中。（4）重复步骤骤（2）和（33），直到所所有的节点都都加入到子回回路中。2.2 应用过过程（1）比较货格格相对距离表表中从v1出发的所有有路径的大小小Minn这样就由节点vv1和v2构成的子回回路，T=v1,v2,v1V10V10V9V8V7V6V5V4V3V2V1

42、图3.14 由由v1和v2构成的子回回路（2）然后考虑虑剩下的节点点、 ，到和中某一个节节点的最小距距离；Min由于对称性，无无论将3插入入到1和2之之间往返路径径中，结果都都是一样的，任选其一,这样构成一个新的子回路T=v1,v2, v3,v1V10V10V8V7V6V5V4V3V2V1V9图3.15 由由v1,v2和v3构成的子回回路（3）接着考虑虑剩下的节点点、 ，到、和中 某一一个节点的最最小距离； Min（4）由图3.15可知，节节点有3个位位置（条弧线线）可以插入入。现在分析析将加入到哪哪里合适：插入到（1,2）间，=d15+d52-d12=2.88+2-0.8=4插入到（2,3）

43、间，= d25+d53-d23=2+1-11=2插入到（3,1）间，= d35+d51-d31=1+22.8-1.8=2比较上面3种情情况增量，插插入（2,33）或（3,1）之间的的增量最小，任选其 一，将节点加入到（22,3），所所以结果为：T=v11,v2,v5 v3，v1其子回路路V10V10V9V8V7V6V5V4V3V2V1图3.16 由由v1,v2,v3和v5构成成的字回路（5）接着考虑虑剩下的节点点、 ，到、和中某一节点的的最小距离；Min（6）由图3.16可知，节节点有4个位位置（条弧线线）可以插入入。现在分析析将加入到哪哪里合适：插入到（1,2）间，= d16+d-d12=3

44、.6+22.8-0.8=5.66插入到（2,5）间，= d+d-d=2.8+00.8-2=1.6插入到（3,5）间，= d+d-d=1.88+0.8-1=1.66插入到（3,1）间，= d+d-d=1.88+3.6-1.8=33.6比较上面4种情情况增量，将将插入（2,5）或（3,55）之间的增增量最小，任任选其一，将将v5插入（2,5）之间，则则结果为：TT= v1,v2,v,v，v，v1其子回路则则变为如图33.17所示示：V10V10V9V8V7V6V5V4V3V2V1图3.17 由由v1,v2,v,v，v构成的子子回路(7) 接着考考虑剩下的节节点、 ，到、中某一节点点的最小距离离Mi

45、n（8）由图3.17可知，节节点有5个位位置（条弧线线）可以插入入。现在分析析将加入到哪哪里合适：插入到（1,2）间，= d18+d-d12=4.6+33.8-0.8=7.66插入到（2,6）间，= d+d-d=3.8+11-2.8=2插入到（6,5）间，= d+d-d=1+1.88-0.8=2插入到（5,3）间，= d+d-d=1.8+22.8-1=3.6插入到（3,1）间，= d+d-d=2.8+44.6-1.8=5.66比较上面5种情情况增量，可可将插入（6,5）或（22,6）之间的增增量最小，任任选其一，若若将插入（6,5）之间，则则结果为：TT=、其子回路则则变为图3.18所所示：V

46、10V10V9V8V7V6V5V4V3V2V1图3.18 由由、构成的子回回路（9）接着剩下下的节点、，到、中某一节点点的最小距离离Min（10）由图33.18可知知有6个位置置（条弧线）可可以插入。现现在分析将加加入到哪里合合适： 插入到（1,2）间，= d+d-d12=5.6+44.8-0.8=9.66插入到（2,6）间，= d+d-d=4.88+2-2.8=4插入到（6,8）间，= d+d-d=2+11-1=2插入到（8,5）间，= d+d-d=1+22.8-1.8=2插入到（5,3）间，= d+d-d=2.88+3.8-1=5.66插入到（3,1）间，= d+d-d=3.88+5.6-

47、1.8=77.6比较上面6种情情况增量，插插入到（6,8）或（8,5）之间的增增量最小，任任选其一，所所以将节点加加入到（8,5）间，结果果为：T=、其子回路则则变为图3.19所所示：V10V10V9V8V7V6V5V4V3V2V1图3.19 、构成的子回回路 （111）接着考虑虑剩下的节点点、到、中某一节点点的最小距离离；Min（12）由图33.19可知知有7个位置（条条弧线）可以以插入。现在在分析将加入入到哪里合适适： 插入到（1,2）间，= d+d-d12=3.44+2.6-0.8=55.2插入到（2,6）间，= d+d-d=2.66+1.8-2.8=11.6插入到（6,8）间，= d+

48、d-d=1.88+2.8-1=3.66插入到（8,10）间，= d+d-d=2.88+3.8-1=5.66插入到（100，5）间，= d+d-d=3.88+2.6-2.8=33.6插入到（5,3）间，= d+d-d=2.66+1.6-1=3.22插入到(3，11)间，= d+d-d=1.66+3.4-1.8=33.2比较上面7种情情况增量，插插入到（2,6）之间的的增量最小，所以将节点加入到（2,6）间，结果为：T=、其子回路则变图3.20所示：V10V10V9V8V7V6V5V4V3V2V1图3.20 、构成的子回回路（13）接着考考虑剩下的节节点、到、中某一节点点的最小距离离；Min（14

49、）由图33.20可知知有8个位置（条条弧线）可以以插入。现在在分析将加入入到哪里合适适： 插入到（1,2）间，= d+d-d12=4+44.8-0.8=8插入到（2,4）间，= d+d-d=4.88+5.4-2.6=77.6插入到（4,6）间，= d+d-d=5.44+3.6-1.8=77.2插入到（6,8）间，= d+d-d=3.66+2.6-1=5.22插入到（8，110）间，= d+d-d=1+11.6-1=1.6插入到（100,5）间，= d+d-d=1.66+2.8-2.8=11.6插入到(5，33)间，= d+d-d=2.88+3.8-1=5.66插入到(3，11)间，= d+d-d=3.88+4-1.8=6比较上面8种情情况增量，插插入到（8,10）和（110,5）之之间的增量最最小，任选其其一，所以将将节点加入到到（10，55）间，结果果为：T=、其子回路路如图3.21所所示：V10V10V9V8V7V6V5V4V3V2V1图3.21 、构成的子回回路（15）最后考考虑剩下的节节点到、中某