基于混合粒子群算法的仓储系统优化研究.doc

签字日期：沁辍月“日本学位论文作者完全了解云洼王些太堂有关保留、使用学位论文的规定。特授权云洼王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。艿难宦畚脑诮饷芎笫视帽臼谌得导师签名：签字日期：翧日 学位论文的主要创新点 关键词：自动化仓储、混合粒子群算法、多目标优化、路径优化、货位优化 。 畂 畂琣 目录 人类历史上出现两大利润领域，即资源领域、人力领域。但在原材料、人工、制造成本等日益趋同的今天，物流业己经成为企业的“第三利润泉”，是国民经济发展的动脉之一。而在物流活动中，仓储是物流业的重要组成部分，也是社会生产的必要环节之一。仓储体系是从事对物流活动中暂时处于停滞状态的物资进行保管、存放活动的物流体系，它与运输系统并列为物流活动的两大重要支柱，是商品流通的重要环节之一，同时它也是物流及供应链系统中的调控中心和重要节点。仓储业在现代物流行业中占有的独特地位决定了其的发展对优化物流与供应链系统、转变国民经济的增长方式、提高国民经济的运行质量都具有重大意义，因此自动化仓储系统 图物流业的各基础环节问题提出的背景和意义 货位图管理；货位盘点、组盘；报表查询；基础信息管理等组成。货位管理包括入库货位分配、出库货位分配、电子货位图、货位组盘、货位调整等。路径管理包含于出入库指令、盘点指令等。货位、路径管理是自动化仓储信息管理系统的一个重要组成部分，自动化仓储的作业路径及货位优化是提高自动化仓储工作效率的一个主要突破口。图自动化仓储信息管理系统选人员的经验来制定拣选作业的路径明显不能满足现代物流的发展要求。综上在精确、及时完成拣选任务的基础上，如何通过优化拣选路径来降低仓储运行成本是自动化仓储所要面临的重要问题之一。因此需要设计出一套适合自动化仓储拣选作业路径的优化算法，应用于计算机控制系统中来实现自动化仓储路径优化。设计优化算法也是提高自动化仓储运行效率和科学决策的必然要求。 近年来，随着计算技术的发展，一些新的智能算法，如遗传算法、模拟退火算法、禁忌搜索算法得到了迅速发展和广泛应用。遗传算法是由美国的瓾教授年首先提出的，它是一种通过模拟自然进化过程搜索最优解的方法，广泛运用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。蚁群算法是一种群智能优化算法，应用该算法求解侍狻峙湮侍狻甹法，解决此问题的优化算法有启发式算法、蚁群算法、遗传算法、弹性网算法和路径代数算法等等，其中启发式算法包括邻近启发式、最邻近插入启发式、几何启发式等。求解小规模问题时，具有很好局部寻优能力的遗传算法效果最好。但是启发式算法所需的计算时间较少，规则简单、易于理解，在大多数情况下也都能满足要求，有时会存在解质量很差的情况，需要研究者综合考虑。当问题解的规模较大时，遗传算法的性能会大幅降低不如启发式算法。此外作为一种求解旅行商问题的弹性网算法，由于其是一种递推算法，可以用于求解各种规模问题，一般情况下其得到解的质量优于启发式算法，但是其所需的计算时间较长。最后 行入库或者仓储盘库操作前给货物分配最合适的货位，保证货位分布于较合理的位置达到仓储作业效率和成本最优化。货位优化的众多原则决定其是个多目标优化问题，和传统的数学规划法相比，智能优化算法更适合求解多目标优化问题。目前智能算法作为一类启发式搜索算法，己被成功应用于多目标优化领域，出现了一些研究成果。 将设计一种基于粒子群算法的多目标混合粒子群算法对仓储货位进行优化求解。自动化仓储的简介自动化立体仓库又称“自动存储自动检索系统疪货架存放或送到入库站台备用。 针对仓储系统而言，自动化仓储系统由货架、存取输送机械、现场控制装置合循环式等。当前，自动化仓储已经发展到集成化和智能化阶段，该部分成为现代集成制 定期合理地对库存的货位进行优化，使货物存储位置达到最优，能缩短出入库运行距离和作业时间，充分利用存储空间，降低仓储操作成本，提高企业效益。但是实际货位优化过程中有诸多问题，比如对于高层固定货架来说，由于存在一些不定因素，如货架、货物本身的一些特性，若货物在入库时存储货位分配不当，会大大降低出入库的工作效率，还会造成货架的不稳定，增加仓库安全隐患等。 第二章混合粒子群算法粒子群算法的简介理论，简称为主体，如果研究鸟群系统，则而是通过追随、逼近当前种群找到的最优解来搜索全局最优解。考或依据以往迭代所搜索的最优解。每个粒子都有反应其适应度的目标函数，具 翔”。在每个具体的时刻，每个粒子都有一个位置和速度。每个粒子的位置矢量 标准粒子群算法具体流程【】如下：公式是粒子速度的调整【】，主要由自身惯性、认知及学习等三部分组成。第一部分为粒子的自身惯性，表示粒子对自身状态的肯定，用权值系数乘以自身速度来进行加速，也是对自身当前进行的惯性运动；认知部分就是指粒子自身学习的过程，通过自身的思考不断增大强化随机行为出现的概率，表示粒子行为认知：最后一部分即社会部分，通过前面两部分粒子的自身信任及学习之后， 上保持协调一致，尽量试图向自己所认为的群体中靠近。粒子群算法遵循的五个俳：粒子群中粒子应该能够进行简单的时空计算。窄的范围，要能在全局空间自由活动。栽：粒子群应该对自身有肯定性，不轻易随环境改变自境的变化，适当修改自身的行为。 第二章混合粒子群算法口眵口一，篬貽粁 緓衯】数辞笕函数广泛运用于神经网络中，其表达式为：算法中解的质量，因为基于连续空间的连续解及整数规划和目标函数值之间是一对多的映射关系。算法中进行离散化处理会导致出现大量冗余空间，然后出现冗余搜索，影响算法的速度，但是由于算法的矢量计算较简单，耗时少，总体来说连续空间运行速度较快。因此建立它们之间的合理映射如近似取整、松弛法等是研究连续空间算法的关键。畁等针对规划问题，提出的离散算法。 被表示为这些城市所以可能的排列组合。并引入交换子和交换序列概念：一个交 计的离散其他几种常见的智能算法遗传算法是着眼于生物进化及遗传进程的模拟的一种随机算法，同时也是一种迭代算法，从初始解不断更新、改进到收敛于最优解或满意解，提供了求解复杂问题的通用框架，具有较强的鲁棒性。其基本思想来源于达尔文的生物进化论和孟德尔的遗传学说。进化论的基本理论就是适者生存，一个种群能够自发的逐渐去适应环境，是因为个体中能够很好适应环境的特征被保存下来，反之不适应环境的个体特征逐步被淘汰。种群通过一代代的进化最终能够生存下来。遗传学说主要认为基因决定个体的特征及其对环境的适应度。子代通过继承父代基因片段或者基因突变两种途径来获取更加适应环境的基因，因此可适应基因就更容易保存下来，通过代代相传，最终使此基因片段保存下来。 第二章混合粒子群算法的基本流程图 基因填入子代个体校玫糠钟成浣徊鍼优先保存交叉 第二章混合粒子群算法上，循环由前三位基因组成，则子代个体第一、即维持种群的多样性，预防算法早熟。遗传算法最大的缺点就是性能比较依赖种群的规模、交叉及变异算子，因为遗传算法是一个不断搜索、迭代的过程，由于种群的规模是一定的，规模小则种群中含有的有用信息过少，起不到遗传寻优的作用：相反规模过大时，种群中含有的信息量太大，算法的复杂程度会几何性增加，阻碍算法进一步实用。不适的交叉算子能使群体染色体局部高度相似，同时也能减小群体之间交换染色体的信息 进行间接通信。 第二章混合粒子群算法综上所述，禁忌搜索算法主要有算法程序直观、简单、易于实现，算法运行速度快、改进方便，具有灵活的记忆功能及藐视原则等优点。算法主要缺点就是严重依赖领域结构、禁忌特性、禁忌表及藐视原则，如选取不当算法的性能很差，且禁忌表和禁忌特性的设置没有一个固定规则。此外算法的特性决定其在搜索最优解的过程仍存在早熟现象，很可能陷入局部最优解等。混合粒子群算法张雪东【】等人提出了基于遗传算法思想的混合粒子群算法和结合禁忌搜索综上本文提出一种新的混合粒子群算法，具体如下：首先通过充分比较几种智能算法的优缺点，一方面由于粒子群算法实现较简单、全局寻优性能好且能有效解决问题己经广泛应用到很多领域。但在实际应用过程中，还有些方面不尽人意。如传统粒子群算法不能解决离散优化问题、容易陷入局部最优、局部搜索能力比较差、搜索精度不够高和搜索性能对参数的依赖性较强等，另一方面神经网络、蚁群算法、爬山法、直接搜索法和模拟退火等优化算法都广泛运用于离散优化问题、具有很强的的局部搜索能力。将粒子群算法和其他算法混合能够更好的解决具体问题。框架下，引入其他智能算法，具体通过重新定义粒子群的离散表示方式及操作算 由货位优化的模型及优化原则可知，货位优化是个多目标组合优化问题。实舡，琻即所有最优解的集合。厂每。瑇尾撼伲贰识 第二章混合粒子群算法非劣最优解集。通过以上转换，任何不同形式的多目标组合优化问题都可以转化为统一的表 最优解，首先需要不断的调整将多目标转化为单目标采用方法的具体参数，然后多次重复运行算法得到可能的最优解，最后还要比较每次程序运行的结果，人为找出最合适的多个解，这样的优化过程过于繁琐，不适合信息化的管理。此外传统算法仅得到一个最优解，对前沿面的形状特别敏感。线性加权法就不能处理前沿面的非凸区域。自从在磕晔状翁岢鲆恢侄嗄勘暧呕惴向量估计遗传算法獠康蛋肝纬蒒蔽C扛隽友。 第二章混合粒子群算法忍岢鲇肦、和等三种方法确定全局最最优位置，即随机从档案中取全局最好位置，是前面两种方法 瑀。】中的硎镜趂个目标函数的网格宽度，整个 离为无穷大。图拥挤距离计算本章小结 究求解。仓储作业的流程 堆垛机运行路径就是其一次作业时往返运动所经过路径。堆垛机所经过的货位能构成一条回路。对这条回路进行优化就是路径优化问题。自动化仓储中堆垛机有单元出库、单元入库、拣选出库、拣选入库、盘库、倒库等拣选工作模式，这些工作模式中都需要面临运行路径优化。因此合理确定作业路径，不仅能使堆垛机拣选作业所花费的时间最小，而且能大大缩短堆垛机所有工作模式下的运行时间。当前仓储堆垛机对小批量、少品种货物进行出入库拣选作业时效率比较高，但是对于批量大、品种繁多的货物进行拣选操作时效率较低。一般一台巷道堆垛机负责多排货架的拣选任务。若每条巷道内都配备一台巷道堆 第三章路径优化问题的研究选货位的总数。约束函数：， ， 产生新个体。线路和其对应的编码，算法终止。遗传算法优化，最优路径线路为：鸬阋一 雹墅 蚁群算法路径优化，最短工作时间为图混合粒子群算法流程图 置更好将其作为当前位置，否则粒子位置保持不变。舸锏皆璧木然蛘叩问惴梗鼻癵为最优解，否则表交叉、变异算子测试逆序土邮呕肪都笆樟睬咄所示：混合粒子群算法优化，最优路径线路为：鸬阋 混合粒子群算法适应值变化曲线 平均值的立体仓储路径优化问题效果优于传统蚁群算法、遗传算法。 第四章货位优化问题的研究固定货架的货位分配问题主要包含为入库货物分配适当的货位和动态适时调整货位等两方面。其中为入库货物进行货位分配是自动化仓储作业中的首要任务，且在仓储运行和管理中占有重要的地位。随着货位存储的动态变化，加上货物存取频繁的不同，使用合适的库区和货位分配策略周期性地为货物分配最佳存储位置，能大大提高仓储的出入库效率，方便仓储的日常盘库、移库等操作，进而为有效地进行拣选作业创造条件。仓储的货位信息管理是货位动态调整的过程。一般仓储会定期根据货架当前的存储状态及货物的分散程度对货位进行相应的调整，如何对货位进行分配及动态调整就是仓储的货位优化，仓储的货位优化需要综合考虑货品的周转率、货架稳定性、系统工作量及准确率等。众多优化原则决定货位优化是一个多目标组合优化问题。 货位的随机存储模式是指系统对每个货物随机地产生其存储货位，具有随机性且可随机更改。其随机存储原则是将先入库货物优先安排存储在靠近出入口的位置，而不考虑货物的周转率及出入库频率。此存储模式即最原始的存储策略几乎不能对其进行货位优化、出入库管理及盘点工作。优点就是货位可以共享，适用于存储量较小的小型仓库。点就是对信息技术的要求较高。 在仓储活动中，存在很多不便规划预测的因素决定要对货位进行调整，这就是货位优化的外因。不便预测的因素包括货物的品种、数量、使用频率等。在仓储频繁存取活动中，随着这些因素的变化要求对仓储的货位进行实时再优化，因此仓储货位分配不应一成不变，仓储会定期进行货位整理。此外仓储货位优化也是实现高效优化管理仓储的需要。在仓储货位优化过程中，需要遵循一定的优化原则，具体如下：成本最小化。所谓的黄金区域就是指对此区域的货位进行操作时极其方便，多因素决定黄金区域的位置它一般由货架以下区域和靠近出入口的位置组成。处理相关性货物时，要尽可能分配在批量区域，能简化作业路径、减少作业时间等。轻物尽可能分配在高层货位，重物应该存放于货架低层位置，做到“上轻下重”是重心合适的基本要求，也助于货架的稳定性。 针对单排固定货架，如图所示，定义参数如下：图籌单排货架重心示意图，为整个货架的重心坐标；琀为每个货位的长度和高度；瑅。分别表示堆垛机的水平、垂直运行速度： 设定荷韪鞲龌跷坏母叨取榷嘉5。约束条件主要是货架能够承受货物的总重量空心圆表示单个货物重心。货架重心为：目标函数：猧三啤！一，窜簃一兰约束条件：能力。货位优化实验仿真 支配档案械娜魏谓猓虻蛋妇芫陆獾募尤耄髁拥膅不变：最后具备终止条件时结束。 表货物重量及使用频率 。 嗄勘昊旌狭尤核惴隢实验结果对比为验证本文多目标混合粒子群算法的搜索性能，将其运用于中，表