自动或立体仓库货位规划匈牙利算法,堆垛机路径优化.doc

交通运输学院自动化立体仓库系统课程设计学 院 运输学院 班 级 物流 姓 名 * 学 号 * QQ 297252509 如果还需要相关学习资料联系本人成 绩 指导老师 2011 年 月 日指导教师评语及成绩任务分配表序号学号姓名所做任务成绩1货位优化2堆垛机径路优化导师签字： 年 月 日交通运输学院课程设计任务书1所在系： 课程名称： 指导教师（签名）： 专业班级： 学生姓名： 学号： 一、课程设计题目自动化立体仓库系统设计二、课程设计的目的 通过本课程设计可以使学生深入了解什么是自动化立体仓库货位规划和堆垛机径路优化问题，并掌握解决问题的基本方法，为今后走上工作岗位从事相关工作打下一定基础，使理论和实践有效结合。 三、课程设计的主要内容和要求（包括原始数据、技术参数、设计要求、工作量要求等） 一、货位规划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所示。Vy2460135Vx图1原始货格图表1 托盘货物出入库频率表货物频率货物频率货物频率A6C15E4B30D9F202、设计任务根据以上条件，利用匈牙利算法合理安排各托盘货物的存放位置。3、设计要求（1）根据已知条件，计算出系数矩阵（列式详细计算的值）；（2）详细地写出匈牙利算法的每一步骤及计算结果；（3）绘出最终的货位规划图。（4）利用熟悉的计算机语言编程实现匈牙利算法，打出源程序代码及结果，要求与手工计算的结果一致。（5）设计结束后，谈谈自己的看法。二、堆垛机径路规划1、设计条件Vy5 (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)Vxo图2 最终的货位规划图随机从图2中的25个货格中抽出7个货格的货物，分别用节点v1,v2,v3,v4,v5,v6,v7表示。节点间的距离用直角距离公式求解。2、设计任务分别用最近邻点法和最近插入法找出堆垛机存取7个托盘货物的合理路线。3、设计要求（1）绘出货格和节点相对位置图及节点相对距离表（需要列式详细计算各的值）；（2）详细地写出最近邻点法和最近插入法的每一步骤及计算结果。（3）分析两种方法的结果。（4）利用熟悉的计算机语言编程实现最近邻点法和最近插入法，打出源程序代码及结果，要求与手工计算的结果一致。（5）设计结束后，谈谈自己的看法。四、工作进度安排 18周完成货位规划任务；19周完成堆垛机径路规划任务。五、主要参考文献【1】焦永兰.管理运筹学. 北京：中国铁道出版社，2000年3月 【2】蔡临宁.物流系统规划建模及实例分析. 北京：机械工业出版社, 审核批准意见系主任（签字） 年月日上传这篇文档的主要原因 出于我们的经验, 咱的课程设计评分标准 一共两条 ： 1、完成稿的厚度： 2、排版整齐程度.一下午就可以把我们花半个月做完的60页的120份设计成绩全给出来对于word基础好的同学来说 这种设计纯粹是浪费时间因此 上传这篇文档 希望给学弟学妹们带来一些方便，节省出更多时间用在真正想学的东西上目录目录I引言1正文11货位规划11.1、设计条件11.2、设计任务11.3、设计要求11.4、设计过程21.4.1计算各货物与货位对应的系数矩阵：21.4.2根据匈牙利算法求指派结果：31.4.3找独立0元素，进行试指派：31.4.4用最少的直线覆盖所有0元素：41.5、方法的计算机实现71.6、设计总结92堆垛机径路规划112.1、设计条件112.2、设计任务112.3、设计要求112.4、设计过程112.4.1选取货格计算相对距离112.4.2最近邻点法和最近插入法解题132.5 路径优化的计算机实现212.6设计总结21参考文献24附录25货位优化代码：25堆垛机路径优化39引言自动化立体仓储，物流仓储中出现的新概念，利用立体仓库设备可实现仓库高层合理化，存取自动化，操作简便化，是当前仓储技术水平较高的形式。自动化立体仓库的主体由货架，巷道式堆垛起重机、入(出)库工作台和自动运进(出)及操作控制系统组成。货架是钢结构或钢筋混凝土结构的建筑物或结构体，货架内是标准尺寸的货位空间，巷道堆垛起重机穿行于货架之间的巷道中，完成存、取货的工作。管理上采用计算机及条形码技术。一个自动化立体仓库效率的高低主要取决于库区和货位的分配策略，使用好的优化策略能大大提高出入库频率，提高堆垛机的存取操作效率，减少时间及能耗。巷道堆垛机是自动化立体仓库系统的核心部件，是实现整个仓储系统功能 的关键设备，其性能及操作路径直接影响整个仓储系统的快速性、安全性和准确性。本文根据相关自动化立体仓库的资料及实际情况， 着重介绍自动化立体仓库系统中的货位规划及堆垛机路径规划问题并编写出相应的及计算机执行程序。该程序经过调试，运行良好，可以正确得出结果，与手算结果相同 正文1货位规划1.1、设计条件某自动化立体仓库采用2行3列的单元货格式货架存放货物，一共有6个货格，每个货格存放一个托盘货物。货格以按列编码的形式进行编号，如图1所示。已知其它参数假定如下：假设堆垛机在水平方向的行驶速度Vx=3.0m/s，在垂直方向的行驶速度Vy=2m/s；货格大小为L（长）W（宽）H（高）=1m1m0.8m；堆垛机初始状态在原点0处；货格j的横坐标和纵坐标就是其所在的列和行，如货格6的坐标为（3，2）；叉车运行至货格j所用时间公式1现有6个托盘货物需要存放到货架上，货物的出入库频率如表1所示。246135Vy0图1.1原始货格图Vx表1.1 托盘货物出入库频率表货物频率货物频率货物频率A6C15E4B30D9F201.2、设计任务根据以上条件，利用匈牙利算法合理安排各托盘货物的存放位置。1.3、设计要求（1）根据已知条件，计算出系数矩阵（列式详细计算t1t6的值）；（2）详细地写出匈牙利算法的每一步骤及计算结果；（3）绘出最终的货位规划图。（4）利用熟悉的计算机语言编程实现匈牙利算法，打出源程序代码及结果，要求与手工计算的结果一致。（5）设计结束后，谈谈自己的看法。1.4、设计过程1.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=6，fB=30，fC=15，fD=9，fE=4，fF=20根据系数ci=fiti既得：对于货物A：c1A=fAt1=61/3=2c2A=fAt2=62/5=12/5c3A=fAt3=62/3=4c4A=fAt4=62/3=4c5A=fAt5=61=6c6A=fAt6=61=6对于货物B：c1B=fBt1=301/3=10c2B=fBt2=302/5=12c3B=fBt3=302/3=20c4B=fBt4=302/3=20c5B=fBt5=301=30c6B=fBt6=301=30对于货物C：c1C=fCt1=151/3=5c2C=fCt2=152/5=6c3C=fCt3=152/3=10c4C=fCt4=152/3=10c5C=fCt5=151=15c6C=fCt6=151=15对于货物F：c1F=fFt1=201/3=20/3c2F=fFt2=202/5=8c3F=fFt3=202/3=40/3c4F=fFt4=202/3=40/3c5F=fFt5=201=20c6F=fFt6=201=20对于货物D：c1D=fDt1=91/3=3c2D=fDt2=92/5=18/5c3D=fDt3=92/3=6c4D=fDt4=92/3=6c5D=fDt5=91=9c6D=fDt6=91=9对于货物E：c1E=fEt1=41/3=4/3c2E=fEt2=42/5=8/5c3E=fEt3=42/3=8/3c4E=fEt4=42/3=8/3c5E=fEt5=41=4c6E=fEt6=41=4由于是分数不便于计算，同乘以其最小公倍数整即得出系数矩阵如表1.2所示：表1.2各货物货位对应系数矩阵货位货格ABCDEF1301507545201002361809054241203603001509040200460300150904020059045022513560300690450225135603001.4.2根据匈牙利算法求指派结果：根据系数矩阵建立等效矩阵(系数矩阵中每行各元素减去该行最小元素)：30 150 75 45 20 100 36 180 90 54 24 120 60 300 150 90 40 200 60 300 150 90 40 200 90 450 225 135 60 300 90 450 225 135 60 300 10130552508012156663009620260110500160202601105001603039016575024030390165750240再从所得系数矩阵的每列元素中减去该列最小元素：1013055250801215666300962026011050016020260110500160303901657502403039016575024000000022611501610130552508010130552508020260110500160202601105001601.4.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)步。1.4.4用最少的直线覆盖所有0元素：对没有独立0元素的行打“”对已打“”的行所有含0元素的列打“”在对 中打“”的列中含独立0元素的行打“”重复 直到得不到新的打“”的行、列为止将没有“”的行和已打“”的列用直线覆盖，且直线的数目一定等于独立0元素的个数。转第(5)步0(0)00000(0)0000226115016226115016 1013055250801013055250801013055250801013055250802026011050(0)1602026011050(0)1602026011050016020260110500160(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最优方案耗时: (90+150+150+90+60+120)/15=660/15=44 (小时)表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方案四货位安排1.5、方法的计算机实现对于该指派问题的匈牙利算法，基于Microsoft Visual C+平台，编写程序，依照程序提示，1首先输入货格及货位个数2再依次输入各货格于货物对应的系数矩阵3计算结果抓图 如图1.6所示：图1.6 对应货格货物系数矩阵输入及第一最优结果由于本题有多重最优解，在输出结果时，依次回车，程序会依次输出本算例的其他最优解，这四种最优解的总时耗是相等的。依次显示结果如 图1.7：左列货格号相对应的右列货物号，为方便起见程序中分别用数字对应不同字母名号的货物： 123456 ABCDEF图1.7其他最优解情况1.6、设计总结通过这次设计我了解到一个自动化立体仓库效率的高低主要取决于库区和货位的分配策略，使用好的优化策略能大大提高出入库频率，提高堆垛机的存取操作效率，减少时间及能耗。并且怎样将各种先进的数学，运筹学计算方法应用到实际的物流问题的解决中的能力得以提高，熟悉了各种方法的细节注意点随着现代工业的快速发展，传统的仓储方式日益不能满足生产和流通的需要，自动化立体仓库得到越来越多的应用。面对成千上万的货格，立体仓库的货位存储优化已成为提高存取效率、降低成本的关键。 本文根据立体仓库基本特征，建立了自动化立体仓库三维数学坐标系，把立体仓库中的货格转换成为了三维坐标系中坐标点的形式，实现了通过两点距离来表示堆垛机的实际运行距离。随后，以堆垛机运行参数为基础，分别提出基于堆垛机运行距离的距离参数算法和基于堆垛机运行时间的最大时间算法。距离参数算法通过参数把垂直方向和水平方向上不同维度的速度统一到同一速度单位上，从而实现了不同方向上距离的比较，进而取得每个货位进行出入库操作所需要运行距离的大小；最大时间算法通过取堆垛机在水平方向和垂直方向上运行时间进行比较，得出的最大时间也就是每次入库或出库所花费时间的多少，从而确定每个货位到出、入库点所花费时间的大小。这样就实现了通过距离和时间两个数值参数大小来表示堆垛机运行效率高低的方法。自动化立体仓库是现代物流系统中迅速发展的一个重要组成部分, 它具有节约用地、减轻劳动强度、消除差错、提高仓储自动化水平及管理水平、提高管理和操作人员素质、降低储运损耗、有效地减少流动资金的积压、提高物流效率等诸多优点。与厂级计算机管理信息系统联网以及与生产线紧密相连的自动化立体仓库更是当今CIMS( 计算机集成制造系统)及FMS( 柔性制造系统)必不可少的关键环节。 自动化所围绕自动化仓储系统开发了多种自动化系统硬件设备及软件产品, 如: 不同类型的库存管理软件、系统仿真软件、图形监控及调度软件、堆垛机输送机控制软件、条形码识别跟踪系统、搬运机器人、码垛机械手、自动运行小车、货物分选系统、堆垛机认址检测系统、堆垛机控制系统、货位探测器、高度检测器、输送系统、码垛系统、自动输送小车等产品。采用现场控制总线直接通讯的方式，真正做到计算机只监不控，所有的决策、作业调度和现场信息等均由堆垛机、出入库输送机等现场设备通过相互间的通讯来协调完成。堆垛机有自动召回原点的功能，即无论任何情况，只要货叉居中且水平运行正常时，可按照下达的命令自动返回原点。这意味着操作人员和维护人员可以尽量不进入巷道。 堆垛机是整个自动化立体仓库的核心设备，通过手动操作、半自动操作或全自动操作实现把货物从一处搬运到另一处。它由机架（上横梁、下横梁、立柱）、水平行走机构、提升机构、载货台、货叉及电气控制系统构成。 自动化立体仓库的主要优点有：（1）仓库作业全部实现机械化和自动化（2）采用高层货架、立体储存，能有效地利用空间，减少占地面积，降低土地购置费用。（3）采用托盘或货箱储存货物，货物的破损率显著降低。（4）货位集中，便于控制与管理，特别是使用电子计算机，不但能够实现作业过程的自动控制，而且能够进行信息处理。2堆垛机径路规划2.1、设计条件Vy5 (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)Vxo图2.1 最终的货位规划图随机从图2.1中的25个货格中抽出7个货格的货物，分别用节点v1,v2,v3,v4,v5,v6,v7表示。节点间的距离用直角距离公式求解。2.2、设计任务分别用最近邻点法和最近插入法找出堆垛机存取7个托盘货物的合理路线。2.3、设计要求（1）绘出货格和节点相对位置图及节点相对距离表（需要列式详细计算各的值）；（2）详细地写出最近邻点法和最近插入法的每一步骤及计算结果。（3）分析两种方法的结果。（4）利用熟悉的计算机语言编程实现最近邻点法和最近插入法，打出源程序代码及结果，要求与手工计算的结果一致。（5）设计结束后，谈谈自己的看法。2.4、设计过程2.4.1选取货格计算相对距离随机从图2.1中的25个货格中抽出7个货格的货物A、G、J、I、W、L、R，分别用节点，表示。货格和节点的相对位置图如图2.2、图2.3所示。Vy5 (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)OVxV2V5V1V3V4V6V7图2.2 货格相对位置图图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=5-11+1-10.8=4d17=x7-x1L+y7-y1H=5-11+2-10.8=4.8d23=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=5-11+1-40.8=6.4d27=x7-x2L+y7-y2H=5-11+2-40.8=5.6d34=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=5-21+1-30.8=4.6d37=x7-x3L+y7-y3H=5-21+2-30.8=3.8d45=x5-x4L+y5-y4H=3-31+5-20.8=2.4d46=x6-x4L+y6-y4H=5-31+1-20.8=2.8 d47=x7-x4L+y7-y4H=5-31+2-20.8=2d56=x6-x5L+y6-y5H=5-31+1-50.8=5.2d57=x7-x5L+y7-y5H=5-31+2-50.8=4.4d67=x7-x6L+y7-y6H=5-51+2-10.8=0.8计算结果见表2.1：表2.1 节点相对距离表元素V1V2V3V4V5V6V7V1_2.42.62.85.244.8V2_1.83.62.86.45.6V3_1.82.64.63.8V4_2.42.82V5_5.24.4V6_0.8V7_2.4.2最近邻点法和最近插入法解题2.4.2.1最近邻点法：1.最近邻点法的思路(1)从零点开始，作为整个回路的起点。(2)找到离刚刚加入到回路中的顶点最近的一个顶点，并将其加入到回路中。(3)重复步骤（2），直到所有的顶点都加入到回路中。(4)最后，将最后一个加入的顶点和起点连接起来。2.应用过程(1)先将节点V1加入到回路中，T=V1。(2)从节点V1出发，比较其到节点2、3、4、5、6、7的距离，选择其最小值，加入到回路中。mind1iiN,1i7,且i1=d12=2.4因此将节点V2加入到回路中，T=V1,V2，见图2.4：V2V1V3V4V5V6V7图2.4 由V1、V2构成的回路(3)从节点V2出发，在节点3、4、5、6、7中，找出离V2最近的节点。mind2iiN,1i7,且i1,2=d23=1.8这样就可以将V3节点加入到回路中，T=V1,V2,V3。V2V1V3V4V5V6V7图2.5 由V1，V2和V3构成的回路(4)从节点V3出发，观察离V3最近的节点。mind3iiN,1i7,且i1,2,3=d34=1.8这样V4是最近的点，将V4加入到回路中，T=V1,V2,V3,V4。V2V1V3V4V5V6V7图2.6 由V1，V2，V3和V4构成的回路(5)从节点V4出发，观察离V4最近的节点mind4iiN,1i7,且i1,2,3,4=d47=2这样V7是最近的点，将V7加入到回路中，T=V1,V2,V3,V4,V7。V2V1V3V4V5V6V7图2.7 由V1，V2，V3，V4和V7构成的回路(6)从节点V7出发，观察离V7最近的节点mindi7iN,1i7,且i=5,6=d67=0.8V2V1V3V4V5V6V7这样V6是最近的点，将V6加入到回路中，T=V1,V2,V3,V4,V7,V6。图2.8 由V1,V2,V3,V4,V7和V6构成的回路(7)从节点V6出发，V5是最后一个节点，直接加入就可以了。然后，将V5和V1相连。得到最后的解为T=V1,V2,V3,V4,V7,V6,V5，见图2.9。V2V1V3V4V5V6V7图2.9 最近邻点法求解结果所以堆垛机运行路线为取送货物次序为：AGJILRW堆垛机总行驶距离为：f=2.4+1.8+1.8+2+0.8+5.2+5.2=19.22.4.2.2最近插入法： 1.最近插入法的思路(1)先将节点V1加入到回路中，找到最小的节点，形成一个子回路，T=V1,VK,V1。(2)在剩下的节点中，寻找一个离子回路中某一节点最近的节点。(3)在子回路中找到一条弧（i,j），使得里程增量最小。如果有多条满足条件，任选一条，然后将节点插入到节点和之间，用两条新的弧（i,k）和(k,j)代替原来的弧（i,j），并将节点加入到子回路中。(4)重复步骤（2）和（3），直到所有的节点都加入到子回路中。2.应用过程(1)比较货格相对距离表中从V1出发的所有路径的大小minc1iiN,1i7,且i1=c12=2.4这样就由节点V1和V2构成的子回路，T=V1,V2,V1如图2.10所示。V2V5V1V3V4V6V7图2.10 由V1，V2构成的子回路(2)然后考虑剩下的节点V3、V4、V5、V6、V7到V1和V2中某一个节点的最小距离：minc1i,c2iiN,1i7,且i1,2=c23=1.8(3)由于对称性，无论将3插入到1和2之间往返路径中，结果都一样的，这样，构成一个新的子回路T=V1,V2,V3,V1，其结果如图2.11所示。V2V5V1V3V4V6V7图2.11 由V1，V2和V3构成的子回路(4)接着考虑剩下的节点V4、V5、V6、V7到V1，V2和V3中某一个节点的最小距离:minc1i,c2i,c3iiN,1i7,且i1,2,3=c34=1.8(5)由图可知，节点V4有3个位置（条弧线）可以插入。现在分析将V4加入到哪里合适：插入到（1，2）间：=c14 + c42 - c12 =2.8+3.6-2.4=4插入到（2，3）间：=c24 + c43 - c23 =3.6+1.8-1.8=3.6插入到（3，1）间：=c34 + c41 c31 =1.8+2.8-2.6=2比较上面3种情况增量，插入（3,1）之间的增量最小，所以将V4节点加入到（3，1），所以结果为:T=V1,V2,V3,V4,V1其子回路则变为如图2.12所示。V1V2V3V4V5V6V7图2.12 由V1，V2 ,V3和V4构成的子回路(6)接着考虑剩下的点V5,V6,V7到V1,V2,V3,V4中某一节点的最小距离：minc1i,c2i,c3i,c4iiN,1i7,且i1,2,3,4=c47=2由图可知，节点V7有4个位置（条弧线）可以插入。现在分析将V7加入到哪里合适：插入到（1，2）间， =c17 + c72 - c12 =4.8+5.6-2.4=8插入到（2，3）间， =c27 + c73 c23 =5.6+3.8-1.8=7.6插入到（3，4）间， =c37 + c74 c34 =3.8+2-1.8=4插入到（4，1）间， =c47 + c71 c41 = 2+4.8-2.8=4 比较上面4种情况增量，插入（3，4）和（4,1）之间的增量都最小，任选其一，所以将V7节点加入到（3，4），所以结果为：T=V1,V2,V3,V7,V4,V1其子回路则变为如图2.13所示。V1V2V3V4V5V6V7图2.13 由V1，V2 ,V3,V4和V7构成的子回路（7）接着考虑剩下的点V5,V6到V1,V2,V3,V4,V7中某一节点的最小距离：minc1i,c2i,c3i,c4i,c7iiN,1i7,且i1,2,3,4,7=c67=0.8由图可知，节点V6有5个位置（条弧线）可以插入。现在分析将V6加入到哪里合适：插入到（1，2）间， =c16 + c62 - c12 = 4+6.4 -2.4 =8 插入到（2，3）间， =c26 + c63 c23 = 6.4 +4.6 -1.8 =9.2 插入到（3，7）间， =c36 + c67 c37 = 4.6+0.8 -3.8 =1.6 插入到（7，4）间， =c76 + c64 c74 = 0.8+2.8 -2 =1.6 插入到（4，1）间， =c46 + c61 c41 =2.8 +4 -2.8 =4 比较上面5种情况增量，插入（3，7）和(7, 4)之间的增量都最小，所以将V6节点加入到（7，4），所以结果为：T=V1,V2,V3,V7,V6,V4,V1其子回路则变为如图2.14所示。V1V2V3V4V5V6V7图2.14 由V1，V2 ,V3,V4，V6和V7构成的子回路（8）最后考虑剩下的点V5到V1,V2,V3,V4,V6,V7中某一节点的最小距离：minc1i,c2i,c3i,c4i,c6i,c7iiN,1i7,且i1,2,3,4,6,7=c45=2.4由图可知，节点V5有6个位置（条弧线）可以插入。现在分析将V5加入到哪里合适： 插入到（1，2）间， =c15 + c52 - c12 = 5.2 +2.8 -2.4 =5.6 插入到（2，3）间， =c25 + c53 c23 = 2.8 +2.6 -1.8 =3.6 插入到（3，7）间， =c35 + c57 c37 = 2.6 +4.4 -3.8 =3.2 插入到（7，6）间， =c75 + c56 c76 = 4.4 +5.2 -0.8 =8.8 插入到（6，4）间， =c65 + c54 c64 = 5.2 +2.4 -2.8 =4.8插入到（4，1）间， =c45 + c51 c41 = 2.4 +5.2 -2.8 =4.8V1V2V3V4V5V6V7比较上面6种情况增量，插入（3，7）之间的增量最小，所以将V5节点加入到（3，7），所以结果为：T=V1,V2,V3,V5,V7,V6,V4,V1其子回路则变为如图2.15所示。图2.15 最近插入法求得的最终结果利用最插入法所得的解T=V1, V2, V3, V5, V7, V6, V4, V1所以堆垛机运行路线为取送货物次序为：AGJWRLI总距离为：f2= 2.4+1.8+2.6+4.4+0.8+2.8+2.8=17.62.4.2.3分析两种方法的结果通过计算可得出最近插入法比最近邻点法可节省路程为：f1-f2=19.2-17.6=1.6。通过最终的结果比较，可得知，最近插入法所求得的结果要优于最近邻点法所求得的结果。2.5 路径优化的计算机实现对于该指派问题的匈牙利算法，基于Microsoft Visual C+平台，编写程序，依照程序提示，1首先输入各货格坐标2计算结果抓图 如图2.16所示：图2.16 堆垛机路径优化零点法、插入法所得结果图示为计算机计算结果，与手算相同。2.6设计总结通过最终的结果比较，可得知，在堆垛机径路规划中最近插入法所求得的结果要优于最近邻点法所求得的结果。堆垛机出入库调度优化问题是提高自动化立体仓库工作效率的关键技术之一 。自动化立体仓库（AS/RS）是由立体货架、有轨巷道 堆垛机、出入库托盘输送机系统、尺寸检测条码阅读系统、通讯系统、自动控制系统、计算机监控系统、计算机管理系统以及其他如电线电缆桥架配电柜、托盘、调节平台、钢结构平台等辅助设备组成的复杂