摘 要

随着我国经济的飞速发展，各类制造业以及电子商务的兴起，对物流行业的需求也越来越高，物流业的市场需求持续扩大，需求推动发展，物流行业得到不断发展，物流体系也越来越规范，随着互联网的应用物流业也更加智能化和迅速化，其中仓储管理是整个物流管理的核心，而自动化立体仓库是现代仓储的重要组成部分，在仓储管理中货物的分拣作业搬运成本占仓储总搬运成本的90%,所用人力约占50%，而且分拣作业时间占整个配送中心作业时间的30%-40%，所以确定一个合适的分拣路径，能够大大缩短拣货时间，进而提高分拣效率，降低物流成本，本文采用遗传算法通过MATLAB软件对最短分拣路径进行求解，并得到了一个非常接近最优解的解。

关键词：自动化立体仓库；分拣作业；路径规划；遗传算法

Abstract

With the rapid development of China's economy, the rise of various manufacturing industries and e-commerce, the demand for the logistics industry is also getting higher and higher. The market demand for the logistics industry continues to expand, and the demand promotes the development. The logistics industry has been developing continuously and the logistics system is becoming more and more standardized. With the application of the Internet, the logistics industry is becoming more intelligent and faster. Warehouse management is the core of the whole logistics management, and automated warehouse is an important part of modern warehouse. In storage management, the handling cost of goods sorting operation accounts for 90% of the total handling cost of storage, and the labor force accounts for about 50%, and the sorting operation time accounts for 30%-40% of the operation time of the whole distribution center. Therefore, determining an appropriate sorting path can greatly shorten the picking time, further improve the sorting efficiency and reduce the logistics cost. In this paper, genetic algorithm is used to solve the shortest sorting path through MATLAB software, and a solution very close to the optimal solution is obtained.

Key words: automated warehouse; Sorting operations; Path planning; Genetic algorithm

目 录

第一章 绪论 1

1.1课题背景及意义 1

1.1.1课题背景 1

1.1.2课题意义 2

1.2国内外研究现状 2

1.3课题研究内容及技术方案 3

1.3.1研究内容 3

1.3.2技术方案 4

第二章 立体仓库的运作策略概述 5

2.1立体仓库概述 5

2.1.1立体仓库定义 5

2.1.2立体仓库的特点 5

2.1.3立体仓库的组成 5

2.1.4立体仓库常见布局 6

2.2仓储作业概述 9

2.2.1概念及内涵 9

2.2.2存储策略的选择 9

2.2.3分拣作业及常见拣选策略 11

2.2.4分拣作业方法 12

2.3分拣作业路径规划概述 12

2.3.1分拣作业原理 12

2.3.2分拣路径优化目标 12

2.3.2分拣路径优化目标 12

2.3.3可用于求解的智能算法 12

2.4仓库综合作业策略 12

第三章 分拣作业路径优化及设计 14

3.1基本假设条件 14

3.2优化模型建立 14

3.2.1建立目标函数 14

3.2.2建立模型 15

3.3基于遗传算法的模型求解 15

3.3.1遗传算法概述 15

3.3.2遗传算法求解方法确定 16

第四章 实证求解 18

4.1初始条件设定 18

4.2MATLAB编程求解 18

4.2.1 遗传算法初次求解 18

4.2.2 最优解验算 20

4.2.3遗传算法改进求解 22

总结与展望 25

参考文献 26

附录 28

附录A 遗传算法MATLAB代码 28

致谢 35

第一章 绪论

1.1课题背景及意义

1.1.1课题背景

相比于西方国家，由于历史进程的原因，我国的物流行业开始发展的时间较晚，但是随着改革开放的开始，我们的国民经济得到了又好又快的发展，市场不断扩大完善，市场对于物流业的发展需求也越来越迫切。新世纪以来，在国家的政策支持以及引导下，物流行业得到了稳步发展，整个物流体系越来越成熟，运行也越来越规范。现代物流是将运输、仓储、库存、信息、装卸搬运以及包装等物流活动结合起来的集成管理，其中仓储管理是整个物流管理的重要组成部分，成为供应链管理的核心环节，这是因为仓储存在于整个物流的各个环节中，比如原料采购与产品生产中，产品的生产与销售中，批发与零售中，不同运输方式的转换之中等。日本早稻田大学的西泽修教授提出了“第三利润源”的学说，其含义是：第三利润源即物流领域，随着市场竞争日益激烈。企业能够占有的市场份额也是有一定限度的，当达到一定限度不能再扩大利润的时候，如何寻找新的利润增长点，这时候发现如果能有效降低在企业成本中占据相当高比例的物流费用，就等于说提高了企业的利润。所以这时候我们就把物流管理称为第三利润源泉^[1]。于是各种企业都开始尝试应用现代化的物流管理方式, 也因此取得了不错的收益。在整个仓储管理中, 其中一个重要组成就是自动化立体仓库系统。自动化立体仓库主要是利用立体仓库设备, 实现仓库的高层货架的合理化 ，操作简便化以及存取的自动化,很大程度上减少了物流行业中的人力消耗。自动化立体仓库主要是由货架、巷道式堆垛机、运输设备以及计算机控制系统组成。在物流行业中, 大多数仓库都发挥着存储货物的功能, 这也是物流行业中仓库的最重要的功能, 当应用了自动化立体仓库系统以后, 能够实现货物进、出库, 以及存储与摆放的有序管理, 降低了人工劳动强度, 减少了管理成本, 也提高了管理效果。

近些年随着经济全球化以及电子商务的迅速发展，人们对于物流的速度要求越来越高，各类企业也在不断提高仓库的作业效率，一定程度上刺激了自动化立体仓库管理的发展。自动化立体仓库管理中的货品的分拣问题也成为国内许多外学者的研究热点。一些算法的运用使得自动化立体仓库货物出入库作业调度得到不断优化。

常见的智能算法有模拟退火，遗传算法，粒子群算法，蚁群算法，禁忌搜索，神经网络等，其中遗传算法，模拟退火算法，蚁群算法，粒子群算法是解决旅行商问题的主要手段，然而遗传算法存在早熟，过早收敛，编码所占储存空间可能较大，爬山能力差等问题，因此在解决实际问题时，很多学者将其与模拟退火算法或者粒子群算法相结合，得到一种新的适应该问题的算法。常见改进方法有：改进初始种群、混合算法即将两种算法合理的结合、改进变异策略或操作算子、并行算法的研究等。合适的算法可以很大程度减少计算机对比较复杂的问题或者对大量数据问题的运算时间，且能保证不错的精度。

1.1.2课题意义

在自动化立体仓库的管理中，分拣作业是很重要的一环，分拣是将货物按种类、出入库顺序进行分类堆放的操作过程，是送货的提前准备，是配送企业在竞争和提高利润的主要改进点。因此分拣是送货作业高级化的重要一环，同样分拣是使配送区别于普通送货和其他物流形式的重要工作, 是配送中心作业系统的核心。在配送中心搬运成本中,分拣作业搬运成本约占90%;在劳动密集型配送中心,与分拣作业直接相关的人力占50%;分拣作业时间约占整个配送中心作业时间的30%-40%^[2]，所以设计出合适的分拣路径尤为重要，可以大大缩短操作时间，同时提高分拣效率降低成本。

本文将针对分拣路线规划问题，运用遗传算法进行求解，然后分析所得解是否为最优解，若果不是，则改进算法直至求得最优解，并分析此算法在解决实际问题的特点。

1.2国内外研究现状

对于分拣作业路径规划问题的求解，国内外学者进行了许多研究，以下是我查阅一些文献内容。杨玮，李程等人将模拟退火算法与粒子群算法结合成一个混合算法，初始化种群改用粒子群算法,优化效率得到提高,搜索时间缩短;迭代过程采用模拟退火算法,因为它具有的概率突跳能力,能有效减少局部最优和早熟。相比于基本粒子群算法，迭代更少、速度更快计算机所用时间自然也更短^[3]。谢树新将遗传算法和粒子群算法结合，初始种群使用粒子群算法得出，遗传算法进行进一步优化，可以得到优于基本算法的结果^[4]。方彦军,谢宜净构建含装箱约束条件的堆垛机拣选作业路径最短的数学模型, 分别采用基本蚁群算法和最大最小蚁群算法进行求解，得出结论：与基本蚁群算法相比, 最大最小蚁群算法所求得的解性能更优, 能有效提高自动化仓库拣选作业的工作效率^[5]。庞龙,陆金桂将初始种群用蚁群算法产生，后用遗传算法求解，经实例计算发现新的混合算法求解精度更高，求解速度也更快^[6]。刘增晓, 冯占营, 吴建等考虑到货架的实际结构,将分拣作业的模型与之结合，设计了一个编程简单而且实用性更强的算法，特点是所求路径为环形，实际求解结果也证明该算法能有提高系统的工作效率^[7]。陈荣虎，何运杰改进了粗粒度遗传算法，他们将一种单程序多数据流(简称SPMD)的并行结构用到其中,对分拣路径进行了优化求解，又分别结算了串行和并行两种解，发现并行结构对算法的优化效率有着不错的提升,同时还缩短了计算机的计算时间^[8]。曾强, 张泽斌, 杨龙飞等人考虑到了堆垛机的容量，将有限容量堆垛机分拣路径优化问题化成多个tsp问题的组合,并以出库时间最短为目标函数，采用整数编码,采用分段交叉和单点交换变异实现遗传进化,使用改进的遗传算法对模型加以求解，发现虽然与就近顺序下的出库方案相比,优化程度较小,但是在实际生产中,立体仓库出库量大而且频繁,即便是较小的优化程度,也会产生累积效应,随着时间的增长,优化效果越来越明显,节约的成本和产生的经济利益越来越多^[9]。蔺媛媛, 刘云改进了蚁群算法,利用蚁群算法的节点选择策略、信息素取值范围策略、信息素的局部更新以及整体更新策略、精英策略与局部更新等方法,收敛速度得以提高, 搜索空间也变的更广, 在实际应用中提高了仓库的使用效率^[10]。刘臣奇,李梅娟,陈雪波改进了蚁群算法,用了三个不同的改进措施,分别是改善搜索能力；候选节点集合策略；算法参数的合理改变；搜索速度得以提高,所求解也因为合适的选择算子能够保持最优，对于求解规模比较大的问题也能保证不错的求解效果^[11]。倪虹,李发强将堆垛机进行分拣作业时经过的路径最短为目标函数,通过对货位点所在的坐标进行计算进而产生新的拣选点。编程也采用了顺序遗传基因编码方式,对拣选路径进行优化求解。结果表明该算法能较快找到最优解,系统法运行效率得到了明显提高^[12]。岳嵚采用的是粗粒度并行遗传算法，对同一组数据进行很多次的重复计算,为了将分析的准确性和可信度尽量提高。并对所求最优解进行了数学处理，用平均值和方差的大小反映结果的稳定性和收敛性，通过实际求解证明该算法具有不错的能力^[13]。常发亮，刘增晓等人对分拣作业进行了分析,对立体仓库的分拣作业设定了新的模型,其中新包含了装箱约束条件，并用遗传算法进行求解,并用不可行程度和作业次数对算法进行了改进，实际求解也证明了此算法的有效性^[14]。Ma等人为了缩短自动化立体仓库作业时间,建立了一个多目标的路径规划数学模型,考虑了作业载重和行驶距离，开发了一种基于集成学习的优化算法, 降低了仓库的作业时间^[15]。Meneghetti等人对立体仓库中的货位分配问题进行了研究,同时还考虑到了耗能问题，建立了一个耗能模型，他们的思路是存取频率高的货物分配到能耗低的货位中去,从而缩短了拣货时间并且减少了能耗^[16]。Sarker等提出了一种混合算法方法,考虑到了控制和调度系统，有效解决了立体仓库分拣作业路径规划问题^[17]。

以上文献中学者们运用了许多不同的方法，如粒子群算法与遗传算法的结合，模拟退火算法与遗传算法的结合，改进初始种群，并行结构的采用等多种算法，均取得了不错的效果。

1.3课题研究内容及技术方案

1.3.1研究内容

本文的重点是采用遗传算法对分拣作业路径规划问题进行编程求解，得到结果后，分析是否为最优解，分析原因，然后改变算法中的一些参数继续求解，分析所得结果，比如是否缩短运算时间，提升求解精度等。本文第一章主要介绍本文研究背景及意义、分拣路径规划问题国内外研究现状、采取的技术方案等。第二章主介绍立体仓库的运作策略，介绍了立体仓库的相关知识，分析了整个仓储作业的内容，突出存储及分拣作业的重要性，并且介绍有关存储策略和拣选作业的常见策略。第三章主要是分拣作业路径规划的优化与设计，包括路径规划问题的目标函数确定，建模和算法确定。第四章主要是给定了初始数据，根据所确定的算法，利用MATLAB软件进行求解，并分析结果是否为最优，若不是最优解如何进一步确定最优解，得出结论。最后对本次毕业设计进行总结。

1.3.2技术方案

1.对于立体仓库分拣作业过程进行分析，确定约束条件及目标。

2.确定立体仓库的布局设施，综合仓储策略及分拣设备数目等初始条件。

3.选择一种合适的基本算法，如遗传算法，针对已知条件进行建模。

4.运用MATLAB软件对确定的算法模型进行求解，对求解结果进行分析。

第二章 立体仓库的运作策略概述

2.1立体仓库概述

2.1.1立体仓库定义

自动化立体仓库,又被称作自动化立体仓储，物流仓储的一个新概念，在立体仓库设备的使用下，仓库高层空间得到更加充分合理的利用，存取具有自动化的特点，操作也变得更简单；自动化立体仓库，是技术水平发展的产物。自动化立体仓库的主体包括货架，巷道式堆垛机、入(出)库工作台和主动运进(出)及操作控制系统。货架的材料种类有钢材和钢筋混凝土两种，具有各种标准尺寸的货位空间就存在于货架内部，巷道式堆垛机机主要运行区域为各货架之间的巷道，堆垛机的主要任务是完成货物的存取，立体仓库在管理上采用计算机控制系统，条形码技术也得到应用，在这两项技术的加持下，仓库内货物的详细信息一目了然 ^[18]。

2.1.2立体仓库的特点

1.立体仓库一般都较高。其高度范围一般在5-40米，目前行业中主流的立体仓库高度范围基本在7-25米^[18]。

2.立体仓库一定是具有较高机械化程度的。因为即使是最矮的货架也都在5米以上，不可能采用人力进行存取货物的工作，就必须采用合适的机械设备。其中自动化立体仓库就是机械化程度和智能程度更高的仓库类型^[18]。

3.立体仓库中货架都为多层。而且货架高度较高，因此又被称为高层货架仓库^[18]。

2.1.3立体仓库的组成

1.货架：自动化立体仓库采用的货架是高层货架，使得仓库内的高度空间也得到充分利用，进而仓库的面积也可以缩小，减少占地成本，货架材料有钢材和钢筋混凝土两种，其中钢货架具有构件尺寸小、空间利用率高、容易建造、安装建设快速等特点，钢筋混凝土货架具有更好的防火及抗腐蚀能力、并且日常维护和保养简单，但是其结构不易改变、造价高、工期长，因此目前更受欢迎的还是钢材货架^[18]。

2.托盘与货箱：为了方立体仓库内的机械设备存取货物，大部分立体仓库中的货物使用托盘或者货箱装载，这样能有效提高拣货速度,托盘和货箱的主要职能是装载货物，又有利于堆垛机和叉车等机械设备的叉取，是工位器具的一种^[18]。

3.巷道堆垛机：负责存取货物，根据结构的不同，常见的基本形式有单立柱和双立柱；根据行驶场合的不同又有直道、弯道还有转移车这几种类型^[18]在调度中心发出指令以后，堆垛机便从起始位到到达指定位置完成存取作业。

4.运输系统：立体仓库的外围设备之一，主要负责货物的运输，常见的有输送机和AGV（Automated Guided Vehicle）小车也叫自动导引车两种,输送机有很多类型，主要有辊道输送机、链条输送机、皮带输送机、升降台和提升机等,AGV小车装备有自动导引装置，一般为光学和电磁式，小车能够按照导引路线行驶，还具有安全保护装置，主要由电脑进行控制^[18]。

5.计算机控制系统：计算机控制系统是实现立体仓库自动化的核心，计算机通过互联网或局域网与仓库内的自动化设备进行连接，操作人员只需要在计算机上输入相应指令便能实现作业,主要结构有集中控制系统和分层分布式控制系统；集中式控制系统所使用的硬件设备少，物理上容易实现，但是设备必须具有较高的可靠性,分层分布式控制系统的全部系统功能不集中在少数几台设备上，类似于一种并行结构，可以用于控制规模较大的情况；现场总线是一种新的分布式控制系统，它使控制设备和系统实现了信息网络化，系统可靠性更高，用户有了更好的系统集成权^[18]。

6.储存信息管理系统：是全自动化立体仓库的核心，典型的自动化立体仓库系统均采用大型的数据库系统（如ORACLE,SYBASE等）构筑典型的客户机/服务器体系，可以与其他系统（如ERP系统等）联网或集成^[18]。