3堆垛机路径优化课程设计

1、3 3 堆垛机路径优化堆垛机路径优化3.13.1 路径优化概述路径优化概述自动化立体仓库有被称为自动存取系统（AS/RS）,采用高层货架以货箱和托盘储存货物，用巷道式堆垛机以及其他机械设备进行作业，有电子计算机管理和控制，不需要人工搬运而实现收发作业的仓库。自动化立体仓库可以节省时间，提高劳动效率，如实现这一点最理想的方案是让货位达到最优的同时，堆垛机路径达到最优。要想让堆垛机的路径达到最优，可以利用最短路径问题解决。由于问题中边的权值往往可以从距离引申为其他沿路径线性积累的度量，如：时间、花费等，所以最短路径问题在实际生活中有着广泛的应用，如：城市规划、交通导航、网络寻优等。在自动化立体仓库

2、中利用最短路的思想，采用一定的数学方法，求得最优的路径，充分利用这一最优路径，节约货物的取送时间，提高工作效率，节省劳动力的费用支出，从而提高仓库的管理水平。3.23.2 堆垛机的选择堆垛机的选择巷道式堆垛机又称为巷道式堆垛起重机，是自动化立体仓库的关键设备之一负责将托盘货物送到货架储存和从货架中取出。它主要有机架 （上下横梁、立柱） 、运行机构、升降机构（载货平台、卷扬机）、取物装置（伸缩货板、伸缩货叉、取物机械手）、电器控制设备（电力控制、检测、安全保护）构成。根据不同仓库的需要，我们对仓库所配备的堆垛机月有所不同，我们可以根据堆垛机的结构，起重量划分为不同的类型。1）按结构形式不同分类：

3、桥式堆垛机、有轨巷道式堆垛机。2）按起重量不同分类：轻型堆垛机、中型堆垛机、重型堆垛机。3.23.2 设计条件设计条件随机从图 2 中的 20 个货格中抽出 8 个货格的货物，分别用节点vl,v2,v3,v4,v5，v6，v7，v8 表示。节点间的距离用公式jXj+,H求解。Vx4(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)图 3.1 最终的货位规划图vy货格大小为 L(长)XW(宽)XH(高)=1mX1mX0.8m，节点间的距离用直角距离公式DV 求解。V、

4、V两个节点的距离随机从图 3.1 中的 25 个货格中212抽出 A、J、W、E、P、Y 个货格的货物，分别用节点 vl,v2,v3,v4,v5,v6 表示。节点间的距离用直角距离公式dj二h-_xixL+imyxH求解。3.23.2 设计要求设计要求(1) 绘出货格和节点相对位置图及节点相对距离表(需要列式详细计算各dij的值)。(2) 详细地写出最近邻点法和最近插入法的每一步骤及计算结果。(3) 分析两种方法的结果。(4) 利用熟悉的计算机语言编程实现最近邻点法和最近插入法，打出源程序代码及结果，要求与手工计算的结果一致。(5) 设计结束后，谈谈自己的看法。3.33.3 设计方法设计方法分

5、别用最近邻点法和最近插入法找出堆垛机存取 6 个托盘货物的合理路线。在堆垛机开始拣选之前，由于设备及系统根据实际情况每台堆垛机分配一定数量的货位，被分配的货位用阴影的小方格表示，图中的实心小黑点表示堆垛机从货架上取货时，需要在仓库中停留的位置点，可以选用的方法的有最近零点法、最近插入发和遗传算法等。3.43.4 求解过程求解过程3.4.1 初始数据的计算初始数据的计算1.首先根据设计要求，绘出货格和节点相对位置图如图 3.2、3.3 所示。从中选出的八个点分别是 AV（1,1）,DV（1,3）,FV3（2,2）,CV4（2,1）,HV5V图 3.3 货格的相对位置图2.计算所有节点之间的相对距

6、离解：由货格相对位置知，用X，y标示货格 A,D,F,C,H,E,P,Q 的相对位置即AV1（1,1），DV2（1，3），FV3jHV5（3,3），EV6（4,3），PV7计算公式：计算公式：d d=ij计算两点之间的相对距离：dddddddddd353637384546474856572,2)4,1),-y yxHdd14y y 一jidd1213dddd5867CV4QV82,1),(4,5),H二0.9,(1-1)ddddd1516171823242526L L 二1.1dd166878计算过程如下：d=1(1-1)Ix1.1+l(3-1)lx0.9=1.812d=(|2-1)|x1.1

7、+(|2-1)|x0.9=213ddd272834d=1(1-1)丨xl.l+l(l-l)lx0.9=1.114d=l(3-1)lx1.1+l(1-1)lx0.9二415d=l(4-1)lx1.1+l(3-1)lx0.9二5.216d=l(4-1)lx1.1+l(1-1)lx0.9二3.317d=l(5-1)lx1.1+l(4-1)lx0.9二7.118d=l(2-1)lx1.1+l(3-2)lx0.9二223d=l(2-1)lx1.1+l(1-3)lx0.9=2.924d=l(3-1)lx1.1+l(3-3)lx0.9二2.225d=l(4-1)lx1.1+l(3-3)lx0.9二3.326

8、d=l(4-1)lx1.1+l(1-3)lx0.9二5.127d=l(5-1)lx1.1+l(4-3)lx0.9二5.328d=l(2-2)lx1.1+l(1-2)lx0.9二0.934d=l(3-2)lx1.1+l(3-2)lx0.9二235d=l(4-2)lx1.1+l(3-2)lx0.9二3.136d=l(4-2)lx1.1+l(1-2)lx0.9二3.137d=l(5-2)lx1.1+l(4-2)lx0.9二5.138d=l(3-2)lx1.1+l(3-1)1x0.9二2,945d=l(4-2)1x1.1+l(3-1)1x0.9二446d=l(4-2)lx1.1+l(1-1)1x0.9

9、二2.247d=l(5-2)lx1.1+l(4-1)lx0.9二648d=l(4-3)lx1.1+l(3-3)lx0.9二1.156d=l(4-3)1x1.1+l(3-1)1x0.9二2.957d=l(5-3)lx1.1+l(4-3)lx0.9二3.158d=l(4-4)lx1.1+l(1-3)lx0.9二1.867d=l(5-4)lx1.1+l(4-3)lx0.9二268d=l(5-4)1x1.1+l(4-1)1x0.9二3.8783.根据两节点的相对距离绘制节点相对距离表 3.1：表 3.1 节点相对距离表VVVVVVVV元素元素V1.87.1V5

10、.15.3V0.9V_2.942.26VV1.82V3.8V3.4.2 最近邻点法求堆垛机运行路径最近邻点法求堆垛机运行路径1、最近邻点法的思路从零点开始，作为整个回路的起点。找到刚刚加入到回路中的顶点最近的一个顶点，并将其加入到回路当中。重复步骤，直到所有顶点都加入到回路中。最后，将最后一个的顶点和起点连接起来。2、应用过程如下：先将节点V加入到回路中，TV。如图 3.4 所示。11V(2) 从节点V出发，比较节点 2、3、4、5、6、7、8 的距离，选择其最小1值，加入到回路中。mind|iGN,1i8，且i工1二d二1.1将v加1i144(3) 从节

11、点V出发，在节点 5、6、7、8 中，找出离V最近的节点。44mind|iGN,1i8二d二09ji34V3-VV图 3.6V加入回路V3这样就可以将V加入到回路中，T二3V，V，V，如图 3.6 所示。143V图 3.4 加入节点VV4入到回路中，如图 3.5 所示。V图 3.5V4加入回路V（4）从节点v出发，观察离v最近的节点。mind|i；N,1i8,二dd=2二2(5)从节点V出发，观察V最近的节点。22mind|iGN,1i8,d2.22i25从节点v出发，观察v最近的节点。mind|iGN,V1i8,d1.15i56选V加入到回路中，TV,V,V,V,V,V，如图 3.8 所示。

12、6143256如图 3.9 所示。V 图 3.9v加入到回路 V6(7)从节点V出发，观察V最近的节点。mind|i；N,1iN8,二d二1.86iV67选V加入到回路中，T=V,V,V,V,V,V,V，如图 3.971432567V图T3.12 最近邻点法求得的最终结果VVVVVVVV8VVV7(8)从节点V出发，观察V最近的节点。发现V是最近的节点，也是最后一个节点，所以将将VV和V以及V和V直接相连。得到最后的解为 TV7881V,V,V,V,V,V,V,V,V,如图 3.11 所示3.用最近邻点发求的结果所以堆垛机的运行路线为：1T5T6T3T11T15T13T20即取送货物的顺序为：

13、ATCTFTDTHTETPTQ堆垛机总行驶距离为：F F 二1.1+0.9+2+2.2+1.1+1.8+7.1二3.4.3 最近插入法求堆垛机运行路线最近插入法求堆垛机运行路线1、最近插入法的思路vdvT卫）先将节点1加入到回路中，找到1k最小的节点k，形成一个子回路，1k1。v在剩下的节点中，寻找一个离子回路中某一节点最近的节点k。在子回路中找到一条弧c訂，使得里程增量d+d-d最小。如果i,jvikvkjij有多条满足条件， 任选一条， 然后将节点k插入到节点和vj 之间， 用两条新的弧C,k）和 Ck,丿）代替原来的弧C,j），并将节点v加入到子回路中。重复步骤和，直到

14、所有的节点都加入到子回路中。2、应用过程v比较货格相对距离表中从1出发的所有路径的大小Vmind|ieN,1i8,且i畀=d=1.1这样就由节点v和v构成的子回路，T=然后考虑剩下的节点v、v、v、235节点的最小距离mind|ieN,1i8,且iij这样就由节点v，v，v，构成的子回路,143v，v、v、v到v和v中某一个67814畀=d=0.9T=v，v14v,v如图31V14v，v如图 3.13 所示。mind|ieNV,1i8,且i畀=d=1.8ij12由图可知， 节点V有 3 个位置(条弧线)可以插入。 现在分析将V加入到哪合适： (1)插入到(1,4)间二 d d12+d d24+

15、d d14二1.8+2.9-1.1二4.7(2) 插入至【Q,3)间，A二 d d42+d d23+d d43二2.9+2-0.9二2(3) 插入至【6,3)间，&二d32+d d21+d31=2+1.8-2二1.8比较上面 3 种情况增量，插入到(3,1)之间的增量最小，所以将2节点插入到(3,1)(4)接着考虑剩下的节点V、V、V、V到V,V,V和V，某个节56781342点的最小距离：Vmind|ieN,1i8,且i1=d=2ij35由图可知，节点V有 4 个位置(条弧线)可以插入。现在分析将V加入到哪里55合适：V8VVVV256V3VVVVV74V图 3.15 由V1；V4,

16、V3,V2,构成的子回路所以结果为：T=(V1,V4,V3,V2,V1其子回路变为如图 3.15 所示的最小距离：(1)插入至【6.4)间，A二 d d15+d d54+d d14二4+2.9-1.1二6.8（2）插入至【（4,3）间，A二 C C45+C C53+C C43二2.9+2-0.9二4（3）插入至【（3,2）间，A=C C35+C C52+C C32二2+2.2-2二2.2（2）插入至【 （2,1）间，A=C C25+C C51+C C21=2.2+4-1.8二4.4比较上面 4 种情况增量，将V5插 入 到（3 , 2）间 增 量 最 小 ， 所 以 将 节 点V5节 点 加

17、入（5）接着考虑剩下的节点V、V、V到V,V，V，V和V，某个节67813452点的最小距离：Vmind|ieN,1i8,且iH1=d=1.1ijV56由图可知，节点V有 4 个位置（条弧线）可以插入。现在分析将V加入到哪里66合适：（1）插入至【（1.4）间，&二d d16+d d64+d d14二5.2+4-1.1二8.1（2）插入至【（4,3）间，二 d d46+d d63+C C43二4+3.1-0.9二6.2466343（3）插入至【（3,2）间，&二d36+d d65+d d35二3.1+1.1-2二2.2366535（4）插入到（2,1）间，&二d“+d“

18、+d“二1.1+3.32.2二2.2566252（5）插入至【（2,1）间，&二d26+d d61+d d二3.3+5.21.8二6.7266121比较上面 5 种情况增量，将V插入到（3,5）间增量最小，所以将节点V节点加66入到（3,5）间，结果为：T=V1,V4,V3,V2,V5,V6,V1）其子回路则变为如图 3.17 所示（6）接着考虑剩下的节点V、V到V,V,V,V,V和V，某个节78134562点的最小距离：Vmind|ieN,1i8,且i舁=d=1.8ijV67V由图可知，节点V有 4 个位置（条弧线）可以插入。现在分析将V加入到哪77里合适：（1）插入至【（1.4）间

19、，&二d d17+d74+d14=3.3+3.1-1.1二5.3（2）插入至【（4,3）间，A二 d d47+d d73+C C43二2.2+3.1-0.9二4.4（3）插入到（3,6）间，&二d37+d d73+d d43二3.1+1.8-3.1二1.8（4）插入至【（6,5）间，&二d67+d d75+d d65二1.8+2.9-1.1二3.6677565（5）插入至【（5.2）间，A二 d d57+d d72+d d52二2.9+5.1-2.2二5.9（6）插入到（2,1）间，A二d27+d71+d21二5.1+3.31,8二6.6比较上面 6 种情况增量，将V7

20、插入到（3,6）间增量最小，所以将节点V7节点加入到（3,6）间，结果为：TfVJJfVJ 其子回路则变为如图 3.18（7）最后考虑剩下的节V到V,V，V，V,V，V、和V中某一节点的81345672jk.VVVVV2VVVVV4VV图必 17 由构成的子回路最小距离：Vmind|ieN,1i8,且iH1=d=2ij68有 7 个位置（条弧线）可以插入。现在分析将v&加入到哪里最合适：（1）插入至【6.4）间，&二叽+dA+d“二7.1+61.1二12188414（2）插入至【（4,3）间，二 d d48+d d83+C C43二6+5.10.9二10.2488343（3）插

21、入至【（3,6）间，A=d d38+d d86+d d365.1+23.1=4（4）插入至 0（6,7）间，Ad d68+d d87+d d752+688775（5）插入至【（5,2）间，Ad d55+d d82+d“3.1+558252（6）插入至【（2,1）间，Ad“+九+d“5.3+7.11.810.6288121（6）插入至【（7.5）间，A几+d d 輕+d”3.8+788575所以堆垛机的运行路线为1T5T6T13T20T15T11T3T1几取送货物次序为：ATCTFTPTQTETHTDTA总距离为： F F+1.1+0.9+3

22、.1+3.8+2+1.1+2.2+1.816利用最近邻点法所得的解所以堆垛机的运行路线为:1T5T6T3T11T15T13T20即取送货物的顺序为：ATCTFTDTHTETPTQ堆垛机总行驶距离为：F F1.1+0.9+2+2.2+1.1+1.8+7.116.2节省路线：比较上面 7 种情况增量，将V插入到（6,7）间增量最小，所以将节点V节点入到（6,7）间，结果为：T仝mmm 其子回路则变为如图 3.193.计算结果对比利用最近插入法所得的解 T-罗，VJf16.2160.2通过最终的结果对比，可得知，最近插入法所求得结果要优于最近邻点法所求得的结果。程序运行的最后结果如图 3.19 所示

23、。3.53.5 总结总结通过这次的了解了什么是自动化立体仓库货位规划和堆垛机路径优化问题，我所做的是堆垛机路径优化问题。通过这次的课程设计我懂得了堆垛机路线优化的一些方法，并且通过使用不同的方法就行了堆垛机的线路优化。是我印象深刻的是，当我最近邻点法最近插入法来就行路线优化是，的出来的结果完全不同。在堆垛机路线优化问题上，最近插入法优于最近邻点法，但是过程比最近邻点法复杂。堆垛机径路的优化是为了找到最佳的路线，提高拣货效率，缩短拣货距离、充分利用仓库等作业效率改善指标来评定优化的效果，要以最节省值的观念来建立模型，在实际生活中，常常有最近邻点法和最近插入法两种方法。最近邻点法是一种构造性启发式算法。由于最近邻点法能够产生较优解，所以可以利用它来构造禁忌搜索算法的初始解，从而更易于搜索到优化问题的最优解。最近邻点法首先是从零点开始，作为整个回路的起点，再运用邻点法的步骤，以距离最短的点为下一个点，依次将各点连起来，得到一条最短的路线。最近插入法是选取第一个点作为线路的种子点，再根据最近插入法