智能化立体仓库

1 问题阐述

某智能仓库，有两个巷道，4排货架，中间两排货架并排在一起，每排货架有200货格，其中长20个，高10个，每个货格尺寸为300cm*300cm，堆垛机行进速度与升降为0~1.6米/秒，行进过程可以升降，堆垛机存取货物时只有一个出口，智能仓库存放10类物品，这10类物品需求量不同，假设不同需求，设计这10类物品如何存放，占多少货格，取货速度能达到最优。

2 自动化立体仓库简介

自动化立体仓库是机械、电气与信息技术相结合的产品。它主要由货物储存系统、货物存取和传送系统、控制和管理等三大系统组成，还有与之配套的供电系统、空调系统、消防报警系统、称重系统、信息系统等。 2.1 自动化立体仓库的构成

一个比较完善的自动化立体仓库主要由货物储存系统、货物存取和传送系统、控制和管理等三大系统组成：(1)货物储存系统，用于货物存放和周转的货物储存的系统，如高层货架及托盘、货箱；(2)货物存取和传送系统，用于出入库作业的货物存取和传送，如堆垛机、输送带、装卸机；(3)入出库分配系统，进行货物的出入库分配，如辊式、链式输送机、分配车、升降机等。除此之外，一个自动化立体仓库需有与之配套的辅助系统：(1)自控系统，由计算机控制的入出库设备、分配系统以及各种检测、保险机构的全部电控装置组成；(2)计算机管理系统，用来管理仓库的信息管理、数据分析、合理管理货位、设备运行、库存情况等；(3)入出库频率不高的立体仓库几个巷道可共用一台堆垛机，此时应配备堆垛机转轨设备，如转轨车。 2.2 自动化立体仓库的分类

自动化立体仓库是一个复杂的综合自动化系统，作为一种特定的仓库形式，一般有以下几种分类形式。 1．按建筑形式分类

按建筑形式可以分为整体式和分离式。整体式指货架除了储存货物外，还可以作为建筑物的支撑结构，构成建筑物的一个部分，即库房货架形成一体化结构。分离式是指储存货物的货架存在，建在建筑物内部，它可以将现有的建筑物改造为自动化仓库，也可以将货架拆除，使建筑物用于其他目的。

1

2．按货物存取形式分类

按货物存取形式分为单元货架式、拣选货架式。单元货架式是一种常见的结构。货物放在标准容器中或托盘上存储，出入库都以整个单元进行。所用的物料搬运机械式适用于整个单元搬运的，例如带伸缩货叉的巷道堆垛机、高架叉车等。 3．按货架构造形式分类

按货架构造形式分类可分为单元货格式、贯通式、阁楼式、屏挂式、移动式、旋转式、驶入式和悬臂式货架仓库。单元货格式仓库是使用最广、适用性较强的一种仓库形式。其特点是货架沿仓库的宽度方向分成若干排，每两排货架为一组，期间有一条巷道供堆垛机或其他起重机作业，每排货架沿着仓库纵长方向分为数列，沿垂直方向又分为若干层，从而形成大量货格，用以存储货物。 4．按在生产和流通中的作用分类

按在生产和流通中的作用可以分为生产性仓库和流通性仓库。生产性仓库是指工厂内部为了协调工序和工序、车间和车间、外购件和自制件间物流的不平衡而建立的仓库，它能保证各生产工序间进行有节奏的生产；流通性仓库是一种服务性仓库，它是企业为了调节生产厂家和用户间的供需平衡而建立的仓库。 3 自动化立体仓库货位优化管理

为了适应当今客户快速和频繁的配送要求，物流中心的拣选作业必须比以前更快而且更有效率，理想的拣选作业的解决方案，是将恰当的设备和～种拣选方法相结合。但是，为了更加有效地拣选，我们同时也一定要把存放单元放入正确的地方——即货位优化。将货品位置最优化，可以减少货物搬运的成本，降低货物在存储过程及搬运过程中的损耗，从而降低物流业务本身的成本，提高收益。随着现代物流技术的发展，一种与所谓的“仓库关键业绩指标(Warehouse Key PerformanceIndicator)’’，即生产率、运送精度、库存周转、入库时间、订单履行时间和存储密度紧密关联的货位优化(Slotting Optimization)已经被提出。货位优化追求不同设备和货架类型特征、货品分组、货位规划、人工成本等因素以实现最佳的货位布局，能有效掌握商品变化，将成本节约最大化。货位优化管理为正在营运的仓库挖掘效率和成本，并为一个建设中的配送中心或仓库提供营运前的关键管理做准备。由于很少的仓库管理系统(WMS)和计算机系统能够支持储位优化管理，因此当前大约80％的配送中心或仓库不能够进行正确的货位

2

优化。

3 自动化立体仓库的布局

自动化立体仓库的出现是物流技术的一个划时代的革新。它不仅彻底改变了仓储行业劳动密集、效率低下的落后面貌，而且大大拓展了仓库功能，使之从单纯的保管型向综合的流通型方向发展。自动化立体仓库具有普通仓库无法比拟的优越性。首先是节约空间、节约劳动力。据国际仓库自动化会议资料：以库存11000托盘、月吞吐10000托盘的冷库为例，自动化立体仓库与普通仓库比较情况为：用地面积为13％、工作人员为21．9％、吞吐成本为55．7％；立体仓库的单位面积存储量为普通仓库的4到7倍；其次是提高仓库管理水平，减少货损，优化、降低库存，缩短周转期，节约资金。 3.1 自动化立体仓库分类简介

(1)按货格内的货位数进行分类。以这种分类方式，自动化立体仓库可以分为单货位式货架和多货位式货架两种。单货位式货架对货物单元的外形结构要求较低，单面和双面托盘均适用，有的货物也可以直接放入货格；多货位式货架不适用于双面托盘，而且要求托盘叉孔高度能满足堆垛机的升降要求，这种货架对货格利用较好，能比单货位式货架存储更多的货位。

(2)按货架高度分类。按这种分类原则，自动化立体仓库可以分为高层立体货架(>12米)、中层立体货架(5—12米)、底层立体货架(<5米)三种。 3.2 货位存储策略

良好的存储策略可以减少出入库移动的距离、缩短作业时间，甚至能够充分利用存储空间。一般自动化立体仓库常见的存储策略有定位存放、随机储放、分类储放、分类随机储放与共享储放等五种。 1．定位存放

在这种储放策略下，每一个存储的货物都有其固定的储位，货物之间不能互用储位。因此须规定每一项货位的储位容量必大于其可能的最大在库量。定位储放的优点：货物的储位可按照周转率大小或出货频率来安排，以缩短出入库的搬运距离。可针对各种货品的特性作储位的安排调整，将不同货品特性间的相互影响减到最小。缺点是储位必须按各项货品的最大在库量来设计自动化立体仓库。总之，定位储放易管理、需时少，但费空间。所以该种策略适用于厂房空间大或

3

者多种少量商品的存放。 2．随机储放

以这种存储策略，每一个货品被指派存放的位置都是经由随机过程所产生的，而且可以随机改变。即任何物品可以被存放在任何可以利用的位置。随机存放原则通常按货品入库的时间顺序储放于靠近出入口的位置。优点：由于储位可共享，因此只需要按所有库存货品最大在库量设计即可，存储空间的使用效率较高。缺点：货品的出入库管理以及盘点工作的进行比较困难。 3．分类储放

所有的储放货品按照一定的特性加以分类，每一类货品都有固定存放的位置，而同属一类的不同货品又可以按一定的法则来分配货位。分类存储通常按产品相关性、流动性、产品尺寸、重量或产品特性来分类。优点：便于畅销品的存取，具有定位储放的各项优点。各分类的储存区域可以根据货品特性再作设计，有助于货品的储放管理。缺点：储位必须按各项货品最大在库量设计，一次存储空间平均使用率较低。该类存储策略适用于产品相关性大、周转率差别大、产品尺寸相差大的情况。 4．分类随机储放

每一类货品都有固定的存放位置，但在各类的储区内，每个货物的分配是随机的。分类随机储放优点：具有分类储放的部分优点，又可以节省储位数量，提高储区利用率。缺点：货品出入库管理以及盘点工作的难度较高。分类随机储放兼具分类储放及随机储放的特点，需要的存储空间介于两者之间。 5．共享储放

在确定知道各货品的进出库时刻，不同的货品可共享相同储位的方式称为共享储放。共享储放在管理上虽然较复杂，所需的存储空间及搬运时间却更为经济。本文在研究蒙牛自动化立体仓库的货位优化时，采用了分类储存策略。所有的储存货品按照产品相关性、流动性、产品尺寸、重量或产品特性加以分类，每类货品都有固定存放的位置，而同属一类的不同货品又按一定的法则来分配货位。 3.3 货位分配原则

那么在仓库的初始状态，如何为货品分配货位才合理呢?通常需要将适当的存储策略配合货位分配原则来确定货位的初始位置。对自动化立体仓库的货位进

4

行管理，是要合理的分配和使用货位。即考虑如何提高货位的利用率，又要保证出库效率。货位分配包含两方面的含义，一是为出入库的物料分配最佳货位，即入库货位分配；二是要选择待出库物料的货位，即出库货位分配。货位分配考虑的原则有很多，针对于自动化立体仓库，其货位分配原则有以下几种： (1)货架承重均匀，上轻下重。分散存放，物料分散存放在仓库的不同位置，避免因集中存放，而使得货架受力不均匀。较重的物品存放在下面的货位，较轻的物品存放在高处的货位，使货架承载稳定；

(2)加快周转，先入先出。同种物料出库时，先入先出，以加快物料周转，避免因物料长期积压产生锈蚀、变形、变质及其他损坏造成的损失；

(3)提高可靠性，分巷道存放。自动化立体仓库有多个巷道时，同种物品分散在不同的巷道进行存放，以防止因某巷道堵塞影响某种物料的出库，造成生产中断； (4)提高效率，就近入／出库。在线自动仓库，为保证快速响应出库请求，一般将物料就近放置在出库台附近；

(5)产品相关性。商品相关性大者在订购时经常被同时订购，所以应尽可能存放在相邻位置。

3.4 货位优化管理的基本思路

每个仓库的货架类型、规模、物流动性、存储特性等参数是不同的，合理的货位分配方案就取决于这些参数。对自动化立体仓库实施货位优化是一项艰巨而庞大的工程，但货位优化研究这项工作在提高管理和潜在利润挖掘上有着不可取代的重要作用。在本文中，将货位优化研究的基本思路分为四步：基础数据收集、优化目标和约束的确定、算法设计、仿真试验。

4 遗传算法

遗传算法(GeneticAlgorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是由美国Michigan大学的J．Holland教授于1975年首先提出的，他在该年发表了著名专著《自然系统和人工系统的适配》该书系统阐述了遗传算法基本理论方法。并提出了著名的模式理论。同年，DeJong发表了《遗传自适应系统的行为分析》，他在该论文中的研究工作可以看作是遗传算法的里程碑，他在该论文中将模式理论与计算试验结合起来，进一步完善和系统化了选择、交叉

5

以及变异操作，并提出了诸如代沟等新技术。进过二十余年的发展，遗传算法的研究取得了丰硕的成果，特别是近年来世界范围形成的进化计算热潮，计算智能已作为人工智能研究的一个重要方向，以及后来人工生命研究兴起，使遗传算法受到广泛的关注。 4.1 遗传算法的基本操作

虽然遗传算法是一个反复的搜索过程，但这一过程并非简单的重复，而是一个带着“记忆”的搜索，它是根据适应度函数来进行搜索的，遗传算法通过这样的操作来改良种群，进而实现寻优。遗传算法具体的操作步骤如下： 步骤一：初始化，设置进化代数计数器t=0；设置最大进化代数T；随机生产M个个体作为初始群体P(0)。

步骤二：个体评价，计算群体P(t)中各个个体的适应度。 步骤三：选择运算，将选择运算算子作用于群体。 步骤四：交叉运算，将交叉运算作用于群体。 步骤五：变异运算，将变异运算作用于群体。

步骤六：终止条件判断t遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法。与传统算法不同的是，大多数遗传算法是以某个单一度量函数的梯度进行统计，以产生一个确定性的试验解序列。遗传算法不依赖梯度信息，而是通过模拟自然进化过程来搜索最优解，它采用某种编码技术，将每种可能出现的解编码为～系列的数字串(称为染色体)，然后模拟由这些串组成的群体的进化过程。遗传算法通过有组织的、随机的信息交换来重新组合那些适应性好的串，生产新的群体。与传统算法相比，遗传算法具有以下特点。 1．以决策变量的编码为运算对象

遗传算法将决策变量按照一定的原则进行编码，这种编码组成的运算对象对应于自然界中的基因和染色体。采用编码的方法可以方便的进行遗传操作运算。从这里可以看出遗传算法与传统的优化方法的不同，传统的方法一般是直接以决策变量来进行优化运算。

6

2．直接以目标函数值同时使用多个搜索点作为搜索信息遗传算法

一般仅需要有一个目标函数就可以确定搜索方向和搜索范围，无需其他目标函数信息。而传统的优化算法不仅需要利用目标函数值，还需要如导数值等其他一些辅助信息才能确定搜索方向。 3．使用多个搜索点的搜索信息

这是由于遗传算法本身所具有的隐含并行性的特点。就是说一个个编码中隐含了多种不用的模式，处理了一个个体，实际上也就并行处理了多种模式。

5 自动化立体仓库的货位优化

5.1 货位优化的目标和约束

所谓货位优化就是根据一定的存储策略和几个货位分配原则对仓库中的初始货位进行调整使之处于最合理的状态(最合理状态指通过货位优化，使得货位达到提高拣选效率和降低仓库操作成本的目的)。货位优化的目标和约束在实施优化过程中是必不可少的。目标决定了优化的方向，而约束则规定了优化的方式。 5.1.1 货位优化的原则

影响自动化立体仓库货位优化的因素有很多，如周转率、货品季节特性、移动距离。自动化立体仓库是为物流系统服务的，所以立体库货位优化的目的应该是在考虑上述因素的基础上满足物流系统的Speed(速度)、Safety(安全)、Surely(可靠)、Low(低费用)的3S1L原则。 5.1.2 货位优化的目的

货位优化是用来确定每一货品的恰当储存方式，在恰当的储存方式下的空间储位分配。货位优化追求不同设备和货架类型特征、货品分组、货位规划、人工成本内置等因素以实现最佳的货位布局，能有效掌握商品变化，将成本节约最大化。因此，货位优化的最终目标就是通过提高生产力和将无用的运动减少到最少来降低成本从而获取最大的效益。对货位优化模型而言，如何判定它的优劣呢?我们采用仓库关键业绩指标来判定，所谓仓库关键业绩指标指的是生产率、运送精度、库存周转、入库时间、订单履行时间、存储密度和自动化程度等七个指标。通过平衡操作者的工作量，提高拣货效率、减少补货工作量、缩短拣货距离等作业效率改善指标来评定所建立的优化模型的效果。 5.1.3 货位优化的约束

7

货位优化并不是随心所欲的优化，必须满足一定的客观约束条件。如：货品重量、货位大小、拣货准确率要求等。一般来说，货位优化的约束条件有如下几条：

1、考虑到承载能力，在存放货品的时候应遵循“货架承重均匀，上轻下重\"原则，即重物放置在货架靠近地面的层位上。

2、根据货物的尺寸规格选择相应的货位：大容量使用大货位，小容量使用小货位；高货物使用高货位的层面储存，低货物使用低货位的层面储存。 3、根据不同的拣货方式选择货品的储存区域：对于人工操作方式应该将易混淆的货品储放于不同的区域；对自动化操作方式则不必要强调易混淆物品的储存区域。

5.2 AS／RS货位优化建模分析

所谓数学建模就是对现实世界的实际研究对象和目的建立模型的过程，也就是对于现实世界的一个特定对象(原始参照物)，为了某种特定的目的，根据该对象特有的内在规律，做出一些必要的简化假设，运用适当的数学工具得到一个数学结构。本文研究的重点就是将立体仓库的货架结构、货品信息等经过抽象建立一个合理的数学模型，并为之求解。 5.2.1 物流系统建模的方法

物流系统的研究已经有较长的历史，其建模与分析设计的方法有很多，简单来说主要有以下几种：

(1)决策系统分析与建模法。该方法以概念参考模型为基础，将系统分解为物理、信息和决策三部分，采用自上而下的分析方法清楚地表明决策系统内部间的决策职能以及在决策和信息上的相互联系。该方法适合于决策功能层的优化，但仿真实现比较困难；

(2)功能模型。该模型结构化地描述了所研究系统的活动和处理进程； (3)信息模型。该模型表达了制造系统环境的信息结构和语义；

(4)仿真模型设计。该模型表述了环境或系统时常变化的行为特征，常用于系统模拟，建立动态模型；

(5)面向对象问题分解法。面向对象设计方法的基本思想就是寻找并处理问题域中的对象以及各对象间的关系，采用分解问题的方法将建模问题分解为“三要素”：

8

初始态、目标态和过程。 5.2.2 货位优化模型的确立

模型的确立在货物优化研究中起关键作用，一个好的模型会给研究工作带来事半功倍的效果。本小节将以模型的设计、问题假设以及模型的确立等三部分内容对货位优化模型的确立过程进行详细的阐述。 5.2.3 模型的设计

通过以上的分析，我们现在已经对货位优化的目的有了很深刻的认识。货位优化的目的就是通过倒库等作业方式对货位进行调整，使得仓库中每一个货位都能处于一个最合理的位置。自动化立体仓库货位分配的运行方式可以简单的描述为：堆垛机根据一定的规则将货品运送到指定的货位。货位优化的执行是指为每一个货物确定一个最有效合理的货位的过程。可见，在整个货位分配优化过程中涉及到三个关键的对象：货品、货位、堆垛机，其中堆垛机在货位优化过程中起到中介的作用，每一个货物通过堆垛机被送达到优化后的货位上。所以货位优化问题的研究对象为货品、堆垛机和货位。 5.2.4 问题假设

模型假设是与问题分析紧密衔接的一个重要步骤。根据对象的特征和建模目的，在问题分析基础上对问题进行必要的、合理的取舍简化，并使用精确的语言做出假设，这是建模至关重要的一步。为了建立一个易求解且符合实际的货位优化模型，我们需要做如下假设。 (1)货位与货品的存放尺寸相适应

假设在为货品进行货位分配时，不存在货品尺寸与货位尺寸不匹配的情况。也就是说，规定将空间大的货位分配给体积大的货品。 (2)假设所有货架上的托盘尺寸规格是相同的。

立体仓库中的托盘分为两种：木托盘与塑木托盘，规格为1200x1200mm承载重量为1500kg。假设在我们建的模型中，所有托盘的尺寸规格与最大承载重量是相同的。但是在承载范围内，托盘上存放的货物重量可以各不相同。 (3)假设货格长宽尺寸相同

相关资料显示，高架立体仓库在设计货格时有两种参数规格：货格长宽比例1：1型与5：3型。为了模型简单起见，设货格长：货格宽：巷道宽比例为1：1：

9

1型。

(4)货位优化区域定义

假设优化区域为l排P列q层的货架区域，将距离巷道口的最近一排记为第1排，最近的列记为第1列，最低一层记为第1层，处于第i排j列k层的货位记为(i, j, k)，出库台位置记为(0，0，1)。 (6)假设货格中货物无混放的情况

不考虑货格上货物混放的情况，即在同一个货格上放的是相同的货品，它们的质量是相同的。 5.2.5 数学模型建立

根据货位分配原则和以上假设，进行货位分配的优化

1、根据货架的承重能力，按照上轻下重的原则，某仓库共有p层q列，设地面层为第一层，离出入口最近的列为第一列，处在第i 列第j 层的货品重量记作Gij，货位分配优化目标是每个托盘上货品的质量与其所在层数的乘积之和Yc最小，即重心最低。得到第一个目标条件：

minf1(Gij*nij*j)

i1j1pqGmax为货架上每个货位所能承受的最大重量，其中Gji2、根据提高效率、就近出入库的原则，出入库频率高的货品离出入库口更近，这样有利于加快货物的出入库时间，提高出入库效率，为了提高自动化立体仓库的出入库效率，通常将经常使用的货物摆放至靠近起始点位置。

minf2(tkij/fkij)

k1i1j1lpqtkij为将k 排 i列 j层货位上的物品搬运到巷道口所用时间，fkij为将k 排 i列j 层货位上的单位物品的存取频率。

该目标函数是对存取效率的要求，目标函数越小，则使用频率高的物品越靠近出入库台。在本文中，使用双排单巷道货格仓库，假设只针对一台堆垛机进行控制，即只研究两排货格，每排货格有10列10层，即i=2，p=20，q=10。

10

假设堆垛机在纵向方向上每次取货都花费相同的时间，那么决定堆垛机的效率的时间只有行进速度与升降速度，这里忽略纵向运行时间对总时间的影响，得到k排i列j层上物品搬运到巷道口所用的时间：

tijkiL0jL0kL0Lj(ik)0 vxvyvz5vxvx、vy分别表示堆垛机行进速度与升降速度，L代表货位的长度，H代表货位的高度。由已知条件知L=H=3m。

6 基于遗传算法的货位分配优化求解

根据上文分析货位分配问题，这是一个多目标优化问题，本文采用遗传算法，结合关联矩阵求得权重系数，将算法的进化分解成若干群体，各子群体分别用不同的权重系数进行不同方向上的搜索获得妥协解。 6.1 关联矩阵求权重系数

现有六名专家对上述两个目标函数权重进行打分，得到如下表 1 2 专家1 0.12 1 0 专家二 0.18 0 1 专家三 0.2 1 0 专家四 0.16 1 0 专家五 0.12 1 0 专家六 0.22 0 1 加权和 0.6 0.4 那么货位分配的目标函数可表示为

minf(x）0.6*f1(x)0.4*f2(x)，

其中X表示货品在货架上的位置。 6.2 多目标遗传算法求解

考虑最小化问题。由于后悔值越小个体越好，因此需要将后悔值转换为适应值从而确保优秀个体具有较大的适应值。设r(x)表示个体x的后悔值，‟戤表示当前代中的最大后悔值，‟表示当前代中的最小后悔值。变换方式如下

eval(x)rmaxr(x)

rmaxrmin其中，γ是正实数，通常被在开区间(0，1)中。该系数有两个作用，

一个是为了避免公式产生被零除错误；另一个是可以将选择方式从适应值比例选择调整到纯粹随机选择。

11

7 算法设计与实现

7.1 确定染色体编码方法

本文所研究的货位优化问除了是多目标优化问题外，还应该是一种组合优化问题，它需要组合两个约束目标来寻找满足约束项目的最佳组合，所以本文决定采用整数排列编码方式对染色体进行编码。采用整数排列编码方式，我们将货物与货位的从属关系进行编码如下。 (1)整个一条染色体代表一种货位分配方案

(2)染色体中基因的个数表示在优化区域内货品的个数(将货位所存放的货物打包视为一个货物)，将每条染色体分为m段，m就表示在该优化区域内货物的总数。

(3)基因的值表示货物存储的货位，基因的位置表示存放在该货位上的货物的编号。每段基因用整数表示要存储的货位坐标(排，列，行)。假设在2排4列3层的优化区域内共有5个物品，其中1号货物存放在坐标(1，1，2)的货位上；2号货物存放在坐标(1，2，1)的货位上；3号货物存放在坐标(2，3，2)的货物上；4号货物存放在坐标(2，4，3)的货位上：5号货物存放在坐标(1，3，3)的货位上。那么染色体“112121 232 243 133”就形成了一个解，表示一种货位分配方案，如图所示。

112 121 232 243 133 „ 7.2 适应度函数的确定

本文研究的是目标函数的最小化问题，孤儿后悔值函数只要去目标函数的倒数就可以变为适应度函数，并通过适应度大小来评价个体优劣程度，为防止溢出，我在目标函数整体上加1，从而得到本文目标函数所对应的后悔值函数如下：

minr(x)1

0.6f1(x)0.4f2(x)1适应度函数如下：

rmaxr(x)

rmaxrmineval(x)其中r是正实数，通常被在开区间(O，1)中，在这里我们令r=O．08。

12

7.3选择、交叉和变异 1、选择算子

比例选择是最基本的选择方式，其中每个个体被选择的期望数量与其适应值 和群体平均适应值的比例有关，通常采用轮盘赌方式实现。这种方式首先计算每 个个体的适应值，然后计算出此适应值在群体适应值总和中所占的比例，表示该 个体在选择过程中被选中的概率。选择过程体现了生物进化过程中“适者生存， 优胜劣汰”的思想，并且保证优良基因遗传给下一代个体。 设种群数为M，个体i的适应度值为fi，则个体i被选择的概率为：

pififk1M

k2、交叉

交叉操作是进化算法中遗传算法具备的原始性的独有特征。GA 交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。在这里使用单点交叉算子，也称为简单交叉，即只有一个交叉点位置，任意挑选经过选择操作后种群中两个个体作为交叉对象，随机产生一个交叉点位置，两个个体在交叉点位置，两个个体在交叉点位置互换部分基因码，形成两个子个体。 3、变异

在生物的遗传和自然进化过程中，细胞复制或者其他一些偶然因素均会造成复制出错，这样就导致了生物的某些基因发生变异，改变了原有的生物特性。变异是生物进化产生新种群的重要因素。 在这里选择基本位突变，即0变成1，1变成0。 7.4 应用遗传算法工具箱进行求解 7.4.1 遗传算法操作过程

第一步，初始化。采用实数编码方案进行染色体编码，确定种群规模为N，应用MATLAB遗传算法工具箱函数crtbp产生种群规模为N的初始种群。初始种群的产生意味着产生了N个初始货位的分配方案，将种群中坐标重复的或者超过优化区域的染色体去掉，并补充新的染色体，使之满足种群的规模为N。 第二步，种群适应度评价。评价初始种群的目标函数值和适应值。

13

第三步，通过选择、交叉、变异操作，产生新一代群体。

第四步，对产生的新种群中的个体进行评价，计算目标函数值和适应值。 第五步，记录本带群体中的最优个体，保留最优解。 第六步，完成预先设定的进化代数后算法停止。 7.4.2 系统仿真

考虑到现在所学知识的，现在只研究单排货架，并且假设堆垛机一直匀速行驶，且其行驶速度和升降速度Vx=Vy=1m/s,现在对这是类货物的出入库频率重量和所占货格数假设如下：

货品编号 1 2 3 4 5 6 7 8 9 10 出入库频率 0.1 0.2 0.16 0.24 0.1 0.05 0.05 0.04 0.03 0.03 重量 100 50 40 80 90 100 60 80 70 60 所占货格数 50 30 20 40 15 5 10 10 6 14 该计算中燃热提供有200个基因位，每个基因长度为，每个基因长度为4，染色体长度为200*4,在计算中假设染色体种群代数为M=400,进化代数为T=400，交叉概率Pc=0.8，变异概率Pm=0.2。 1 产生初始种群

我们应用MATLAB遗传算法工具箱中的crtbase函数与crtbp函数产生初始种群格式如下示： NIND=400；

BaseV=crtbase(800，4)；

Chrom=crtbp(Nnm3，BaseV)+ones(NrYD，800)； 2 计算目标函数和适应度值：

14

ObjV0.6*f1(chrom)0.4*f2(chrom)

适应度变形为：

FitnVeavl(chrom)rmaxr(chrom)0.08

rmaxrmin0.083 选择、交叉

本文采用MATLAB遗传算法工具箱函数中的轮盘选择(rws)函数进行选择操作；采用单点交叉(xovsp)函数进行基因的重组。格式如下所示： SelCh=select('rws’，Chrom，FitnV)； SelCh=recombine('Xovsp’，SelCh，0.8)； 5 变异

FieldDR=rep([1：20]，[1，10])； SelCh=mutbga(SelCh，FieldDR[0.2 1.0])； 6 计算子代目标函数如下：

ObjVSel0.6*f1(SelCh)0.4*f2(SelCh)

7.4.3 仿真优化结果

货位进行优化前，布局不合理，仓库的综合性能比较差。优化后的货位分配及存放的货物重量与出入库频率分别如下表所示： 列层 1 2 3 4 5 6 7 8 9 10 1 80 80 80 80 80 80 80 80 80 80 2 80 80 80 80 80 80 80 80 80 80 3 80 80 80 80 80 80 80 80 80 80 4 80 80 80 80 80 80 80 80 80 80 5 100 100 100 100 100 100 100 100 100 100 6 50 50 50 50 50 50 50 50 50 50 7 50 50 50 50 50 50 50 50 50 50 8 50 50 50 50 40 40 40 40 40 40 9 40 40 40 40 40 40 40 60 60 60 10 80 80 80 80 80 80 80 80 80 80 15

11 12 13 14 15 16 17 18 19 20 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 90 90 90 90 90

50 50 50 40 40 90 90 90 90 90 50 50 50 40 90 90 90 90 90 90 40 40 40 40 60 70 70 70 70 70 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 列层 1 2 3 4 5 6 7 8 9 列层 10 11 12 13 14 15 16

1 2 3 4 5 6 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 6 0.2 0.2 0.2 0.2 7 0.2 0.2 0.2 0.2 8 9 10 0.24 0.24 0.24 0.24 0.1 0.24 0.24 0.24 0.24 0.1 0.24 0.24 0.24 0.24 0.1 0.24 0.24 0.24 0.24 0.1 0.24 0.24 0.24 0.24 0.1 0.24 0.24 0.24 0.24 0.1 0.24 0.24 0.24 0.24 0.1 0.24 0.24 0.24 0.24 0.1 0.24 0.24 0.24 0.24 0.1 1 2 3 4 5 0.2 0.16 0.04 0.2 0.16 0.04 0.2 0.16 0.04 0.2 0.16 0.04 0.2 0.16 0.16 0.04 0.2 0.16 0.16 0.04 0.2 0.16 0.16 0.04 0.2 0.16 0.05 0.04 0.2 0.16 0.05 0.04 7 8 9 10 0.24 0.24 0.24 0.24 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.2 0.16 0.05 0.04 0.2 0.16 0.05 0.05 0.2 0.16 0.05 0.05 0.2 0.16 0.05 0.03 0.1 0.16 0.16 0.16 0.05 0.03 0.1 0.16 0.1 0.05 0.03 0.03 0.1 0.1 0.1 0.03 0.03 0.03 16

17 18 19 20 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.03 0.03 0.03 0.1 0.03 0.03 0.03 0.1 0.03 0.03 0.03 0.1 0.05 0.05 0.1 0.05 0.05 0.05 0.05 0.1 0.1 0.03 0.03 0.03 0.03 8 小结

优化后的货位在满足提高出入库效率的基础上同时也使得货架的重心比较低，符合货架稳定性的要求。由此可见，在具体货位分配优化应用过程中，可能由于仓库规模很大导致需要处理的货物比较多，如果使用传统的求解方法进行货位优化求解时可能导致计算时间成级数增长，从而无法应用到实际问题中。远过上面所示的优化结果，我们可以得到这样一个结论，即应用遗传算法进行货位优化时可以有效地对问题进行求解，且其算法非常简单，虽然无比保证获得最优解，但是由于收敛速度快，则可以在较短的时间段内获得一个令人满意的近似解，所以应用遗传算法对货位优化进行求解具有较大的应用价值。

17