仓储课程设计.doc

交通运输学院课程设计1、自动化立体仓库1.1自动化立体仓库的概述仓库的产生和发展是第二次世界大战之后生产和技术发展的结果。50年代初，美国出现了采用桥式堆垛起重机的立体仓库；50年代末60年代初出现了司机操作的巷道式堆垛起重机立体仓库；1963年美国率先在高架仓库中采用计算机控制技术，建立了第一座计算机控制的立体仓库。此后，自动化立体仓库在美国和欧洲得到迅速发展，并形成了专门的学科。60年代中期，日本开始兴建立体仓库，并且发展速度越来越快，成为当今世界上拥有自动化立体仓库最多的国家之一。对立体仓库及其物料搬运设备的研制开始并不晚，1963年研制成第一台桥式堆垛起重机（机械部北京起重运输机械研究所），1973年开始研制我国第一座由计算机控制的自动化立体仓库（高15米，机械部起重所负责），该库1980年投入运行。到2003年为止，我国自动化立体仓库数量已超过200座。立体仓库由于具有很高的空间利用率、很强的入出库能力、采用计算机进行控制管理而利于企业实施现代化管理等特点，已成为企业物流和生产管理不可缺少的仓储技术，越来越受到企业的重视。自动化立体仓库（AS/RS）是由立体货架、有轨巷道堆垛机、出入库托盘输送机系统、尺寸检测条码阅读系统、通讯系统、自动控制系统、计算机监控系统、计算机管理系统以及其他如电线电缆桥架配电柜、托盘、调节平台、钢结构平台等辅助设备组成的复杂的自动化系统。运用一流的集成化物流理念，采用先进的控制、总线、通讯和信息技术，通过以上设备的协调动作，按照用户的需要完成指定货物的自动有序、快速准确、高效的入库出库作业。1.2自动化立体仓库的分类一按照建筑物形式分类按建筑形式可分为整体式和分离式两种：（1）整体式：是指货架除了存储货物以外，还作为建筑物的支撑结构，构成建筑物的一部分，即库房货架一体化结构，一般整体式高度在12米以上。这种仓库结构重量轻，整体性好，抗震好。（2）分离式：分离式中存货物的货架在建筑物内部独立存在。分离式高度在12米以下，但也有15米至20米的。适用于利用原有建筑物作库房，或在厂房和仓库内单建一个高货架的场所。二按照货物存取形式分类按照货物存取形式分为单元货架式、移动货架式和拣选货架式。（1）单元货架式：单元货架式是常见的仓库形式。货物先放在托盘或集装箱内，再装入单元货架的货位上。（2）移动货架式：移动货架式由电动货架组成，货架可以在轨道上行走，由控制装置控制货架合拢和分离。作业时货架分开，在巷道中可进行作业；不作业时可将货架合拢，只留一条作业巷道，从而提高空间的利用率。（3）拣选货架式：拣选货架式中分拣机构是其核心部分，分为巷道内分拣和巷道外分拣两种方式。“人到货前拣选”是拣选人员乘拣选式堆垛机到货格前，从货格中拣选所需数量的货物出库。“货到人处拣选”是将存有所需货物的托盘或货箱由堆垛机至拣选区，拣选人员按提货单的要求拣出所需货物，再将剩余的货物送回原地。三按照货架构造形式分类可分为单元货格式、贯通式、水平旋转式和垂直旋转式。（1）单元货格式仓库：类似单元货架式，巷道占去了三分之一左右的面积。（2）贯通式：为了提高仓库利用率，可以取消位于各排货架之间的巷道，将个体货架合并在一起，使每一层、同一列的货物互相贯通，形成能一次存放多货物单元的通道，而在另一端由出库起重机取货，成为贯通式仓库。根据货物单元在通道内的移动方式，贯通式仓库又可分为重力式货架仓库和穿梭小车式货架仓库。重力式货架仓库每个存货通道只能存放同一种货物，所以它适用于货物品种不太多而数量又相对较大的仓库。梭式小车可以由起重机从一个存货通道搬运到另一通道。（3）水平旋转式仓库的货架：这类仓库本身可以在水平面内沿环形路线来回运行。每组货架由若干独立的货柜组成，用一台链式传送机将这些货柜串连起来。每个货柜下方有支撑滚轮，上部有导向滚轮。传送机运转时，货柜便相应运动。需要提取某种货物时，只需在操作台上给予出库指令。当装有所需货物的货柜转到出货口时，货架停止运转。这种货架对于小件物品的拣选作业十分合适。它简便实用，充分利用空间，适用于作业频率要求不太高的场合。（4）垂直旋转货架式仓库：与水平旋转货架式仓库相似，只是把水平面内的旋转改为垂直面内的旋转。这种货架特别适用于存放长卷状货物，如地毯、地板革、胶片卷、电缆卷等1.3自动化立体仓库的相关设备1.3.1自动化立体仓库的组成部分（1）货架：用于存储货物的钢结构。主要有焊接式货架和组合式货架两种基本形式。（2）托盘(货箱）：用于承载货物的器具，亦称工位器具。（3）巷道堆垛机：用于自动存取货物的设备。按结构形式分为单立柱和双立柱两种基本形式；按服务方式分为直道、弯道和转移车三种基本形式。（4）输送机系统：立体库的主要外围设备，负责将货物运送到堆垛机或从堆垛机将货物移走。输送机种类非常多，常见的有辊道输送机，链条输送机，升降台，分配车，提升机，皮带机等。（5）AGV系统：即自动导向小车。根据其导向方式分为感应式导向小车和激光导向小车。（6）自动控制系统：驱动自动化立体库系统各设备的自动控制系统。以采用现场总线方式为控制模式为主。（7）储存信息管理系统：亦称中央计算机管理系统。是全自动化立体库系统的核心。典型的自动化立体库系统均采用大型的数据库系统（如ORACLE，SYBASE等）构筑典型的客户机/服务器体系，可以与其他系统（如ERP系统等）联网或集成。1.3.2自动化立体仓库的主要设备（1）货架货架的设计是立体仓库设计的一项重要内容，它直接影响到立体仓库面积和空间的利用率。货架形式：货架的形式有很多，而用在自动化立体仓库的货架一般有：横梁式货架、牛腿式货架、流动式货架等。设计时，可根据货物单元的外形尺寸、重量及其它相关因素来合理选取。货格的尺寸：货格的尺寸取决于货物单元与货架立柱、横梁（牛腿）之间的间隙大小，同对，在一定程度上也受到货架结构型式及其它因素的影响。（2）有轨巷道堆垛机有轨巷道堆垛机是立体仓库成套设备中的主机，是一种在轨道上运行的起重机械，它能在三维空间上(行走、升降、两侧向伸缩)按照一定的顺序组合进行往复运动，以完成对集装单元或拣选货物的出入库业。本产品采用单立柱结构形式。自动小型堆垛机采用一批新技术，在寻址技术上采用脉冲式红外测距仪其体积小、重量轻，采用数字测相脉冲展宽细分技术，测量精度达到毫米级，且能快速准确地直接显示距离。该堆垛机应用变频调速技术，根据堆垛机运行的目标要求由PLC对变频器的速度进行切换变频调速，达到调速和停准的目的。特点：堆垛机高速运行、换速平稳、低速停准的调速控制要求。实际应用表明，该方案能对电机转矩实行精准控制、低速运行性能好、调速范围广。此外该堆垛机还应用了以下新技术如：远红外通讯，条码识别、编码识别、实时监控等。先进的技术及优异的性能使该设备在欧美等发达国家运用比较广泛.该自动小型堆垛机主要结构由铝合金型材空中轨道（天轨），及铝合金型材地面轨道(地轨)，铝合金立柱，平移小车装置，升降系统，货叉装置，滑触线，电控装置等组成。（3）堆垛机控制：堆垛机控制设计为手动、半自动和全自动控制 3 种。全自动控制是由监控机发送作业命令和地址给堆垛机，而后堆垛机响应执行。运行中，监控机对堆垛机运行状态实时监控。手动、半自动控制是由操作员直接在堆垛机操作面板上设定作业命令和地址。在实际运行中以全自动控制为主，手动、半自动控制作为维修和调试的辅助手段。（4）堆垛机特点： 整机结构紧凑，运行在与单一轨道上，由后轮驱动，前后轮有水平导向轮，运行平稳，上部有水平尼龙导向夹轮夹在天轨上，防止堆垛机倾翻。取货采用三级差动式滑义，结构先进，伸缩行程为500mm。起升采用链条传动，起降平稳，停准可靠。采用用三相交流电机变频调速，光电认址，有较好的调速性能和停准精度高的特点。电气控制具有手动、单机自动和全自动功能。采用安全滑接输电装置供电，安全可靠。2、货位优化传统的仓储作业管理常常把货品放在货品到达时最近的可用空间或不考虑商品动态变化的需求和变化了的客户需求模式，沿袭多年习惯和经验来放置物品。传统型货品布局造成流程速度慢、效率低以及空间利用不足。然而，现代物流尤其是在供应链管理模式下的新目标是：用同样的劳动力或成本来做更多的工作；利用增值服务把仓库由资金密集转化成劳动力密集的行业；减少定单履行时间，提供更快捷，更周到的服务。这就涉及到货位优化问题。2.1货位优化的原则事先确定储存策略是仓库入库作业控制的重要内容，只有配合货位分配原则才能决定储存作业的实际运作模型。为了货物安排货位应遵循的原则可归纳如下：(1)可与随机储存，共同储存策略相配合的原则。即靠近出入口原则，指将刚到达的货物分配到离出入口最近的空货位上。(2)可与定位储存，分类（随机）储存策略相配合的原则。以周转率为基础原则。即将货品按周转率由大到小排序，再将此序分为若干段（通常分为三至五段），同属于一段中的货品列为同一级，依照定位或分类存储法的原则，指定存储区域给每一级货品，周转率越高应离出入口越近。产品相关性原则。这样可以减短提取路程，减少工作人员疲劳，简化清点工作。产品的相关性大小可以利用历史订单数据做分析。产品同一性原则。所谓同一性的原则，指把同一物品储放于同一保管位置的原则。产品互补性原则。互补性高的货品也应存放于邻近位置，以便缺货时可迅速以另一品项替代。产品相容性原则。相容性低的产品不可放置在一起，以免损害品质。产品尺寸原则。在仓库布置时，我们同时考虑物品单位大小以及由于相同的一群物品所造成的整批形状，以便能供应适当的空间满足某一特定要求。所以在存储物品时，必须要有不同大小位置的变化，用以容纳不同大小的物品和不同的容积。此原则可以使物品存储数量和位置适当，使得拣货迅速，搬运工作及时间都能减少。一旦未考虑存储物品单位大小，将可能造成存储空间太大而浪费空间，或存储空间太小而无法存放；未考虑存储物品整批形状亦可能造成整批形状太大无法同处存放。重量特性原则。所谓重量特性的原则，是指按照物品重量不同来决定储放物品于货位的高低位置。一般而言，重物应保管于地面上或料架的下层位置，而重量轻的物品则保管于料架的上层位置；若是以人手进行搬运作业时，人腰部以下的高度用于保管重物或大型物品，而腰部以上的高度则用来保管重量轻的物品或小型物品。产品特性原则。物品特性不仅涉及物品本身的危险及易腐蚀，同时也可能影响其他的物品，因此在物流中心布局时应考虑。2.2货位优化的目的理想的解决方案、先进的设施设备与完善的经营理念是物流企业为了适应当今社会发展应当具备的重要条件。货位优化则是必不可少的。（1）货位优化的目的：货位优化的目的就是为了保证货位分布处在较为合理的状态，如何合理安排货物的存放次序或空间，减少货物搬运的成本、降低货物在存储过程及搬运过程中的损耗，来达到提高作业效率、降低仓库操作成本和充分利用仓容的最大化。正确的货位可以节约时间，合理的对仓库进行货位优化，来可以缩短出入库移动的距离、作业时间，充分发挥仓库的利用率，这有利于物流企业在日后的发展。（2）货位优化基本功能：根据内置货品属性或自定义属性将货品分组；评估建议每一货品的最佳货位和可用货位；在货品分类及属性发生变化的情况下调整设施的状态；将仓库从低效率状态转化为功能性优化状态所需的移动执行配置；（3）货位优化的意义：便于补货。根据商品不同的特性来存放。相似的产品应该分开，提高拣货的准确性。互补性高的货品应存放于临近的位置，以便缺货时可迅速以另一品项替代。拣货频率最高的区域应该位于最便于拣货的区域，这样能缩短拣选作业中的移动时间，加快拣货作业流程，提高订单的处理效率。将拣货量大的货品平均分配在不同拣货区域，避免某区域内的拣货作业拥挤，改善工作流程，缩短对一批订单的总反应时间。a.根据内置货品属性或自定义属性将货品分组；b.评估建议每一货品的最佳货位和可用货位；c.在货品分类及属性发生变化的情况下调整设施的状态；d.将仓库从低效率状态转化为功能性优化状态所需的移动执行配置；e.三维图形化或数字化的分析结果输出。2.3自动化立体仓库货位优化实现2.3.1设计条件某自动化立体仓库采用2行3列的单元货格式货架存放货物，一共有6个货格，每个货格存放一个托盘货物。货格以按列编码的形式进行编号，如图1所示。已知其它参数假定如下：假设堆垛机在水平方向的行驶速度，在垂直方向的行驶速度；货格大小为L（长）W（宽）H（高）=1.3m1.3m1.1m；堆垛机初始状态在原点0处；货格的横坐标和纵坐标就是其所在的列和行，如货格6的坐标为（3，2）；叉车运行至货格所用时间。现有6个托盘货物需要存放到货架上，货物的出入库频率如表2.1所示。 246135 图2.1 原始货位图表2.1 托盘货物出入库频率表货物频率货物频率货物频率A14C27E10B29D18F37根据以上条件，利用匈牙利算法合理安排各托盘货物的存放位置。2.3.2设计要求（1）根据已知条件，计算出系数矩阵（先列式详细计算的值）；（2）详细地写出匈牙利算法的每一步骤及计算结果；（3）绘出最终的货位规划图。（4）设计结束后，谈谈自己的看法。2.3.3设计步骤第一步：建等效矩阵。（1）从系数矩阵的每行元素中减去该行的最小元素；（2）再从所得系数矩阵的每列元素中减去该列的最小元素。第二步：找独立0元素，进行试指派。（3）从只有一个0元素的行（或列）开始，给这个0元素加括号(0)，表示这行所代表的货格已有一种货物分配。然后划去(0)所在列（或行）的其它0元素，记作“”，表示这列所代表的货物已指派。（2）对只有一个0元素的列（或行）的0元素加括号(0)，然后划去(0)所在行（或列）的0元素，记作“”。如果在(1)，(2)两步中，遇到每一行和每一列都有两个或两个以上的0元素，可任选一个加括号，同时把其所在行和列的0元素都划去。（3）重复(1)，(2)两步，直到所有0元素都被加括号或打叉。（4）加括号的0元素即为独立0元素，若其个数m等于矩阵的阶数n，则已得到问题的最优解。若mn，则转入第三步。第三步：用最少的直线覆盖所有0元素。（1）对没有独立0元素的行打“”。（2）对已打“”的行中所有含0元素的列打“”。（3）再对(2)中打“”的列中含有独立0元素的行打“”。（4）重复(2)，(3)，直到得不到新的打“”的行、列为止。（5）将没有打“”的行和已打“”的列用直线覆盖，且直线的数目一定等于独立0元素的个数。转第四步。第四步：增加0元素。从没有被直线覆盖的元素中找出最小元素。未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到的新系数矩阵，转第二步，重新确定独立0元素。2.4求解过程2.4.1计算系数矩阵一参数假设：（1）为种货物的出入库频率，=1,2,3,4,5,6，分别表示货物A,B,C,D,E,F（2），分别为货格的横坐标和纵坐标，即货格所在的行和列(距离巷道口最近的列记为第1列，最底层记为第1层)，=1,2,3；（3）为水平方向的行驶速度；（4）为垂直方向的行驶速度；（5）L，W，H分别为货格的长宽高；（6）为堆垛机运行到货格所用的时间，该时间是堆垛机行进过程中水平方向和垂直方向所用时间的最大值，=1,2,3,4,5,6；（7）为堆垛机将货物向货格存取所花费的时间。二已知条件：（1） ，（2） ， (2-1) (2-2)三具体计算：根据公式(2-1)，计算的值=根据公式(2-2),计算的值对于货物A： 对于货物B： 对于货物C： 对于货物D： 对于货物E： 对于货物F： 进而得到系数矩阵表：表2.2系数矩阵表货格货物ABCDEF123456由上表得出系数矩阵如下：为方便后续的计算，对上面得到的系数矩阵全部乘以120，得到如下系数矩阵： 2.4.2匈牙利算法的应用（1）建立等效矩阵。从该系数矩阵的每行元素中减去该行的最小元素，即从第一行开始，每行分别减去390，440,780,780,1170,1170得如下矩阵：再从所得系数矩阵的每列元素中减去该列的最小元素，即从第一列开始，每列分别减去156,741,663,312,0,1053，得到等效矩阵：（2）找独立0元素，进行试指派。如下所示：由于，转入第三步，用最少的直线覆盖所有0元素。对没有独立0元素的行打“”。即对第三，四，五，六行打“”。对已打“”的行中所有含0元素的列打“”。即对第五列打“”。再对第五列中含有独立0元素的行打“”。即对第二行打“”。 将没有打“”的行和已打“”的列用直线覆盖，且直线的数目一定等于独立0元素的个数。 （3）转第四步，增加0元素。从没有被直线覆盖的元素中找出最小元素。未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到的新系数矩阵，转第二步，重新确定独立0元素。最小元素为20，得到如下矩阵：（4）再转第二步，找独立0元素，进行试指派。（一直重复上面的过程，直到停止）如下所示：由于，转入第三步，用最少的直线覆盖所有0元素。对没有独立0元素的行打“”。即对第四，五，六行打“”。对已打“”的行中所有含0元素的列打“”。即对第五列打“”。再对第五列中含有独立0元素的行打“”。即对第三行打“”。 将没有打“”的行和已打“”的列用直线覆盖，且直线的数目一定等于独立0元素的个数。 转第四步，增加0元素。从没有被直线覆盖的元素中找出最小元素。未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到的新系数矩阵，转第二步，重新确定独立0元素。最小元素为136，得到如下矩阵：再转第二步，找独立0元素，进行试指派。如下所示：由于，转入第三步，用最少的直线覆盖所有0元素。对没有独立0元素的行打“”。即对第三，四，六行打“”。对已打“”的行中所有含0元素的列打“”。即对第一，五列打“”。再对第一，五列中含有独立0元素的行打“”。即对第二，五行打“”。 将没有打“”的行和已打“”的列用直线覆盖，且直线的数目一定等于独立0元素的个数。 转第四步，增加0元素。从没有被直线覆盖的元素中找出最小元素。未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到的新系数矩阵，转第二步，重新确定独立0元素。最小元素为20，得到如下矩阵：再转第二步，找独立0元素，进行试指派。如下所示：由于，转入第三步，用最少的直线覆盖所有0元素。对没有独立0元素的行打“”。即对第四，六行打“”。对已打“”的行中所有含0元素的列打“”。即对第一，五列打“”。再对第一，五列中含有独立0元素的行打“”。即对第三，五行打“”。 将没有打“”的行和已打“”的列用直线覆盖，且直线的数目一定等于独立0元素的个数。 转第四步，增加0元素。从没有被直线覆盖的元素中找出最小元素。未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到的新系数矩阵，转第二步，重新确定独立0元素。最小元素为136，得到如下矩阵：再转第二步，找独立0元素，进行试指派。如下所示：由于，转入第三步，用最少的直线覆盖所有0元素。对没有独立0元素的行打“”。即对第三，五行打“”。对已打“”的行中所有含0元素的列打“”。即对第一，四，五列打“”。再对第一，四，五列中含有独立0元素的行打“”。即对第二，四，六行打“”。 将没有打“”的行和已打“”的列用直线覆盖，且直线的数目一定等于独立0元素的个数。 转第四步，增加0元素。从没有被直线覆盖的元素中找出最小元素。未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到的新系数矩阵，转第二步，重新确定独立0元素。最小元素为45，得到如下矩阵：再转第二步，找独立0元素，进行试指派。如下所示：由于，转入第三步，用最少的直线覆盖所有0元素。对没有独立0元素的行打“”。即对第五行打“”。对已打“”的行中所有含0元素的列打“”。即对第五列打“”。再对第五列中含有独立0元素的行打“”。即对第六行打“”。 将没有打“”的行和已打“”的列用直线覆盖，且直线的数目一定等于独立0元素的个数。 转第四步，增加0元素。从没有被直线覆盖的元素中找出最小元素。未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到的新系数矩阵，转第二步，重新确定独立0元素。最小元素为156，得到如下矩阵：再转第二步，找独立0元素，进行试指派。如下所示：由于，转入第三步，用最少的直线覆盖所有0元素。对没有独立0元素的行打“”。即对第六行打“”。对已打“”的行中所有含0元素的列打“”。即对第一，五列打“”。再对第一，五列中含有独立0元素的行打“”。即对第四，五行打“”。对已打“”的四，五行中所有含0元素的列打“”。即对第四列打“”。 将没有打“”的行和已打“”的列用直线覆盖，且直线的数目一定等于独立0元素的个数。 转第四步，增加0元素。从没有被直线覆盖的元素中找出最小元素。未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到的新系数矩阵，转第二步，重新确定独立0元素。最小元素为306，得到如下矩阵：再转第二步，找独立0元素，进行试指派。如下所示：由于，转入第三步，用最少的直线覆盖所有0元素。对没有独立0元素的行打“”。即对第五行打“”。对已打“”的行中所有含0元素的列打“”。即对第一，五列打“”。再对第一，五列中含有独立0元素的行打“”。即对第四，六行打“”。再对四，六行中所有含0元素的列打“”。即对第三，四列打“”。 将没有打“”的行和已打“”的列用直线覆盖，且直线的数目一定等于独立0元素的个数。 转第四步，增加0元素。从没有被直线覆盖的元素中找出最小元素。未被覆盖的元素都减去该最小元素，而被两条线覆盖的元素都加上该最小元素，其它元素不变。这样得到的新系数矩阵，转第二步，重新确定独立0元素。最小元素为10，得到如下矩阵：由于，所以停止计算，得出最优解。 （5）转化为01矩阵。在不改变其相对位置条件下，将独立0元素，转化为1，其他元素写成0，就得到最终的指派矩阵，如下所示：2.5最终的货位规划图由01矩阵得到如下货位规划图：2(B)4(C)6(E)1(F)3(D)5(A) 图2.2 最终货位规划图最优分配方案为：货物A放在货格5，货物B放在货格2，货物C放在货格4，货物D放在货格3，货物E放在货格6，货物F放在货格1。2.6设计总结刚开始做这个题目的时候，总觉得无从下手。感觉很复杂，后来我先把主要的计算步骤都写在草稿本上，但和同学讨论的时候才发现有几个地方出现了问题，只能重新计算。来来回回算了好几遍，保证正确、合适的前提下，才敲到电脑上，当把大体框架写好之后，真有的很有成就感。就是在排版上遇到很多问题，最主要的就是目录页码和正文的页码发生冲突，试了很多次才达到老师的要求。总体来说，我学到了许多知识，不仅是专业课知识，还有计算机基础知识。对专业课而言，让我掌握了如何选择更有的货位去存放货位，这是我们在上课的过程中没有得到的东西。从这次的货位优化中，我明白最终货位规划图不是唯一的，只要它符合条件即可，不同的存放位置，将获得不一样的效果，但我们最终的目的都是存取货物达到最优。这次的课程设计让我有很多的体会，同时我也感受到认真做好一件事的重要性。通过这次课程设计，使我学会了很多东西，也知道了学习的重要性，知道了自己的不足，对以前所学过的知识没有做到学以致用，掌握地不够牢固。我会在以后的学习过程中再接再励，使自己的生活更加充实，对知识的掌握更加全面。3、堆垛机径路优化3.1货格和节点位置确定5(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)VY VY 图3.1最终的货位规划 VY从图3.1中随机抽取10个货格的货物，O、U、K、T、H、E、V、R、A、C，分别用节点V1，V2，V3，V4，V5，V6，V7，V8，V9，V10表示,货格和节点的相对位置分别如图3.2和3.3所示：5(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)VY 图3.2 货格相对位置图 VXV1V4V8V6V3V9v10000090000000V7V5V2 图3.3 节点相对位置图3.2节点间距离计算3.2.1节点间距离公式货格大小为L（长）W（宽）H（高）=1.3m1.3m1.1m，两货格相对距离相等，则根据直角距离公式（3-1）可以计算出所有节点之间的距离。 （3-1）3.2.2具体计算如下 由以上计算可得表3-1货格相对距离表：表3-1货格相对距离表元素V1V2V3V4V5V6V7V8V9V10V13.33.52.67.05.07.25.27.49.6V22.45.93.76.13.98.56.36.3V33.53.53.73.76.13.96.1V44.42.44.62.64.87.0V54.62.47.04.82.6V62.22.42.44.6V74.62.42.4V82.24.4V92.2V103.3最近零点法优化3.1.1最近零点法一最近零点法的思路：（1）从零点开始，作为整个回路的起点。（2）找离到刚刚加入到回路中的顶点最近的一个顶点，并将其加入到回路中。（3）重复步骤（2），直到所有顶点都加入到回路中。（4）最后，将最后一个加入的顶点和起点连接起来。3.1.2最近零点法优化过程（1）步骤一：将节点V1加入到回路中。T1= V1V1图3.4（2）步骤二：从节点V1出发，比较其到节点2、3、4、5、6、7、8、9、10的距离，选择其最小的加入到回路中。因此将节点V4加入到回路中。 T2=V1。V4V1V4图3.5（3）步骤三：从节点V4出发，比较其到节点2、3、5、6、7、8、9、10的距离，选择其最小的加入到回路中。故将节点V6加入到回路中。T3=V1，V4，V6。V1V4V6图3.6（4）步骤四：从节点V6出发，比较其到节点2、3、5、7、8、9、10的距离，选择其最小的加入到回路中。故将节点V7加入到回路中。T4=V1， V4， V6， V7。V1V4V6V7图3.7（5）步骤五：从节点V7出发，比较其到节点2、3、5、8、9、10的距离，选择其最小的加入到回路中。min3.9,3.7,2.4,4.6,2.4,2.4=2.4 T5=V1， V4， V6， V7 ， V5。 故将节点V5加入到回路中。V1V4V6V7V5图3.8（6）步骤六：从节点V5出发，比较其到节点2、3、8、9、10的距离，选择其最小的加入到回路中。min3.7,3.5,7.0,4.8,2.6=2.6 T6=V1， V4， V6， V7 ， V5， V10。故将节点V10加入到回路中。V1V4V6V7V5v10000090000000图3.9（7）步骤七：从节点V10出发，比较其到节点2、3、8、9的距离，选择其最小的加入到回路中。min6.3,6.1,4.4,2.2=2.2 T7=V1， V4， V6， V7 ， V5， V10 V9。故将节点V9加入到回路中。V1V4V6V7V9v10000090000000V5图3.10（8）步骤八：从节点V9出发，比较其到节点2、3、8的距离，选择其最小的加入到回路中。min6.3,3.9,2.2=2.2 T8=V1， V4， V6， V7 ， V5， V10 ，V9， V8。 故将节点V8加入到回路中。V1V4V6V7V8V9v10000090000000V5图3.11（9）步骤九：从节点V9出发，比较其到节点2、3的距离，选择其最小的加入到回路中。min8.5,6.1=6.1 T9=V1， V4， V6， V7 ， V5， V10 ，V9， V8， V3。故将节点V3加入到回路中。V1V4V6V7V3V8V9v10000090000000V5图3.12（10）步骤十：从节点V3出发，节点V2是最后一个点，将节点V2加入到回路中，并连接V1 。最后得到的解为V1 , V4 , V6, V7, V5 , V10 , V9, V8 , V3, V2V1V4V8V6V3V9v10000090000000V7V5V2图3.13 最近零点法求解结果因此，堆垛机运行路线为：V1 V4 V6 V7 V5 V10 V9 V8 V3 V2 即取送货物次序为：O W N V M L S Y J B 堆垛机的行驶总距离为：2.6+2.4+2.2+2.4+2.6+2.2+2.2+6.1+2.4+3.3=28.43.4最近插入法优化3.4.1最近插入法思路（1）先将节点V1加入到回路中，找到d1k最小的节点Vk，形成一个子回路，T=V1，Vk，V1。（2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点VK（3）在子回路中找到一条弧（i,j），使得里程增量Cik+Ckj+Cij最小。（4）重复步骤(2)和步骤(3)，直到所有的节点都加入到子回路中。3.4.2最近插入法过程（1）步骤一：比较表3-1货格相对距离表中从V1出发的所有路径的大小，将所有Cij改成dij 这样就由节点V1和V4构成的子回路,T=V1，V4，V1如图3.14所示：V1V4V8V6V3V9v10000090000000V7V5V2图 3.14（2）步骤二：比较剩下的节点V2，V3,V5,V6,V7,V8,V9,V10到V1,V4中某一节点的最小距离：，由于对称性，无论将V6插入到1和4之间往返路径中，结果都是一样的，这样构成一个新的子回路，T=V1，V4，V6，V1其结果如图3.15所示：V1V4V8V6V3V9v10000090000000V7V5V2图3.15（3）步骤三：比较剩下的节点V2，V3,V5, V7,V8,V9,V10到V1,V4，V6中某一节点的最小距离：,将节点V7插入V1, V4 ,V6的往返路径中。由图3.15可知V7有三个位置可以插入，现在分析将V7插入到哪里合适：插入到（1，4）间： 插入到（4，6）间： 插入到（1，6）间：比较上面三种情况增量，可将V7插入到（4，6），（1，6）的增量最小，现选其一，这里将V7节点加入到（1，6）间，结果为T=V1，V4，V6，V7，V1这样构成了一个新的子回路如图3.16所示：V1V4V8V6V3V9v10000090000000V7V5V2图3.16（4）步骤四：比较剩下的节点V2，V3,V5, V8,V9,V10到V1,V4，V6，V7中某一节点的最小距离：，将节点V5插入V1, V4 ,V6 ,V7的往返路径中，由图3.16可知V5有4个位置可以插入，现在分析将V5插入到哪里合适：插入到（1，4）间： 插入到（4，6）间： 插入到（6，7）间：插入到（1，7）间：比较上面四种情况增量，将V5插入到（1，7）的增量最小，将V5节点加入到（1，7）间，结果为T=V1，V4，V6，V7，V5，V1这样构成了一个新的子回路如图3.17所示：V1V4V8V6V3V9v10000090000000V7V5V2图 3.17（5）步骤五：比较剩下的节点V2，V3, V8,V9,V10到V1,V4，V6，V7，V5中某一节点的最小距离：在节点V8,V9,V10中任选一个节点加入到V1, V4 ,V6 ,V7 ,V5中，这里将节点V10插入V1, V4 ,V6 ,V7 ,V5的往返路径中，由图3.17可知V10有5个位置可以插入，现在分析将V10插入到哪里合适：插入到（1，4）间： 插入到（4，6）间： 插入到（6，7）间：插入到（7，5）间：插入到（5，1）间：比较上面五种情况增量，将V10插入到（7，5）的增量最小，将V10节点加入到（7，5）间，结果为T=V1，V4，V6，V7，V5，V10，V1，这样构成了一个新的子回路如图3.18所示：V1V4V8V6V3V9v10000090000000V7V5V2V7图3.18（6）步骤六：比较剩下的节点V2，V3, V8,V9到V1,V4，V6，V7，V5,V10中某一节点的最小距离：将节点V9插入V1, V4 ,V6 ,V7 ,V5,V10的往返路径中，由图3.18可知V9有6个位置可以插入，现在分析将V9插入到哪里合适：插入到（1，4）间： 插入到（4，6）间：插入到（6，7）间：插入到（7，10）间：插入到（10，5）间：插入到（5，1）间：比较上面六种情况增量，将V9插入到（7，10）的增量最小，将V9节点加入到（7，10）间，结果为T=V1，V4，V6，V7，V5，V10，V9,V1，这样构成了一个新的子回路如图3.19所示：V1V4V8V6V3V9v10000090000000V7V5V2图3.19（7）步骤七：比较剩下的节点V2，V3, V8到V1,V4，V6，V7，V5,V10,V9中某一节点的最小距离：将节点V8插入V1, V4 ,V6 ,V7 ,V5,V10,V9的往返路径中,由图3.19可知V8有7个位置可以插入，现在分析将V8插入到哪里合适：插入到（1，4）间： 插入到（4，6）间： 插入到（6，7）间：插入到（7，9）间：插入到（9，10）间：插入到（10，5）间：插入到（5，1）间：比较上面七种情况增量，将V8插入到（7，10）的增量最小，将V8节点加入到（4，6）间，结果为T=V1，V4，V8，V6，V7，V9，V10,V5,V1，这样构成了一个新的子回路如图3.20所示：V1V4V8V6V3V9v100000