自动化存取系统下的货位动态分配数学模型构建

成均孝

(陕西国防工业职业技术学院 基础课部， 西安 710300)

0 引言

自动化存取系统是基于普通货架系统基础实现多载具货物存取装置创建的全新自动化存储系统，其具备多个载具，在一次行程中能够存放或者取出多个货物单元。其具有较高的灵活性、较大的存储量及较高的空间使用率，能够有效满足未来制造配送环境中高柔性、多货种、高密度动态货物存取的需求。货物动态分配的分配数学模型创建是解决自动化存取系统的高效运行基础问题，自动化存货系统和传统货物分配模型创建的目标相同，都是实现货物出入库移动时间距离的最小化，使存取货物效率得到有效的提高。本文对存货货位分配及取货货位选择两方面进行了全面的优化，将存取或时间距离最小化作为目标，创建组合优化模型，使用启发式算法的结合实现算法的求解，利用数值实验对算法有效性进行了全面的验证。

1 货物的出入库作业

1.1 货架的系统结构

自动化存取系统主要包括穿梭板、货架及垂直提升机构成，如图1所示。

系统货架包括多层，各层之间的存储巷道相互平行及密集排列，利用主轨道实现连接。主轨道相互连接成为主轨道网，垂直提升机和各个货架层主轨道网相互连接成为货架系统主干交通网，存储巷道轨道利用主轨道与货架主干交通网相互连接。在自动化存取系统中，为了能够有效避免多个穿梭板相互运行出现路径冲突的情况，利用主轨道只允许穿梭板单向运行的设置实现。

图1 自动化存取系统货架机构和设备

在自动化存取系统中，每个存储巷道都是货道，其中包括多货位。基于密集存储条件中，为了使物资出入库的效率得到进一步的提高，就要降低倒库作业的机率，每条货道中只允许同类托盘物资的存储。为了能够避免多台穿梭板在同时运行过程中出现路径死锁的情况，实现货道穿梭板容量的设置，为1。

1.2 出入库作业

自动化存取系统的主要功能就是实现物资的出入库作业，其作业流程通过管理系统实现统一调度及监控。在物资入库上架作业过程中，托盘物资就从货架的端口进入到货架中，管理系统能够实现穿梭板的调度，使其到货架端口托盘物资，将物资运输到管理系统制定货位中。在物资下架出库的过程中，穿梭板就会通过管理系统的制定货位将货物装盘，实现下架出库。所以，托盘物资入库上架及下架出库简单来说就是系统对货架端口和存储货位的往返控制，在每次入库上架作业过程中，将货架端口作为起点，将存储货位作为重点。在每次下架过程中，出库货位属于起点，货架端口属于终点。如果托盘物资存储货位为货架的一层，那么穿梭板就能够自动实现托盘物资转载运输。如果托盘物资存储货位不处于货架一层，那么穿梭板在运行过程中需要根据垂直提升机实现换层[1]。

2 数学模型的创建

2.1 基本的假设

航空货站的散货区自动化存取系统都是同端出入式结构，其存取单元为网箱，网箱利用货架坐下端出入口进入并且离开自动存取系统。货架中的每个货位尺寸相同，每个网箱能够存储所有货位，每个货位只能够存储同个网箱。巷道中具有一台堆垛机，堆垛机能够在垂直及水平的运动。假如堆垛机在水平及垂直两个方向进行匀速运动，并且负载空载速度相同。

2.2 符号的定义

为了方便系统模型的创建，就要对模型中使用的符号进行定义：入库指令集合表示为Cs，入库指令索引表示为i，出库指令集合表示为Cr，出库指令索引表示为k。空货位集合表示为Le，空货位索引表示为k。货位列表示为W，货位层表示为H，货架宽度表示P，货架高度表示为Q。决策变量表示为Xik={0,1}。

2.3 数学模型的创建

因为堆垛机不仅有水平方向的运动，还具有垂直方向的运动，取垂直及水平的最大完成时间为运行之间，那么入库指令i存货时间就是：

堆垛机因为存货和取货的位置中间时间为：

堆垛机取货的时间表示为：

其中指令序列完工的时间为：

自动化存活系统货位动态分配的数学优化模型为式(1)～式(4)。

(1)

(2)

(3)

(4)

其中式(1)中属于目标函数，其能够缩短堆垛机指令序列的完工时间，式(2)能够保证每个入库的指令指令实现空货位，式(3)和式(4)能够保证每隔入库指令都实现一个空货位的分配。以上模型能够在指令序列规模及空货位规模不断增加的过程中，可行货位分配方案也会增加，无法利用精确算法实现模型求解，本文使用单亲遗传算法实现问题求解[2]。

3 算法的求解

遗传算法是根据生物进化规律实现的计算技术，能够利用种群进行自动获取及调整优化搜索空间的操作，并且实现空间多解的搜索，并且以不同解之间性能的差别实现自适应搜索方向的调整。对自动化存货系统大规模货位分配的问题，要全面考虑问题特殊性及遗传算法随机性，假如继续使用基本的遗传算法，就会使迭代次数及不可行解可能性得到增加，以此就不能够产生满意解。那么针对此问题，本文就基于多种方式实现模型解。

3.1 染色体编码

染色体编码属于遗传算法编码空间中的模型解空间映射，其属于遗传算法最基本的工作，编码能够对交叉、选择及变异的过程造成影响。本文所研究的染色体使用备选货位集合耦合映射二进制编码的方式，使编码能够分割成为多个片段，使用空货位和取货货位相互结合的顺序进行排列，编码主要通过两层构成。上层属于备选货位集合编码，下层属于是否选择相应货位码值。编码长度指的是指令周期中空货位数量与需要取货物的占有数量集合。需要存取的货物数量及载具数与货位数量具有密切的联系。图2为染色体编码的设计，其中A、B、C指的是需要取的货物，为了能够有效满足货物存取的约束，就要保证空货位中能够具有三个空货位，在货物中选择货位，实现货物的取出[3]。

图2 染色体编码的设计

3.2 生成初始种群

因为以上所描述的编码结构和值具有特殊的约束，所以初始种群无法按使用随机方式生成，要不然会产生不可行的解，无法继续实现算法。所以针对自动化存取系统中的货位分配，可以使用基于分片段货位数量限制随机的方法实现初始种群的生成。在选择种群规模中，一般表示越多越好，但是要全面考虑计算代价及后续选择交配操作便捷性，可以选择编码程度2或者4等一系列的偶数倍作为种群规模[4]。

3.3 种群及适应度函数

遗传算法通过对生物遗传进化过程中的优胜劣汰模拟实现问题求解，其中的适应度函数属于对个体优劣进行衡量的指标。本文所使用的使用度函数指的是使用原本模型中改进策略实现目标函数的生成，并且以经典轮盘赌的方式选择种群个体，根据相应的概率分布到下一代实现染色体的遗传。为了能够促进算法收敛，使用精英保存策略，是每代数量最有个体到下一代遗传，从而提高父体选择压力，使选择最优个体概率得到进一步的提高。

3.4 变异算子及交叉算子

自然界中的生物交配之后后代属于种群进化核心步骤，遗传算法利用交叉算法相互配对的方式实现其中基因片段的交换，从而形成全新个体。交叉算子能够对遗传算法的全局搜索能力决定，一般常见的交叉规则包括单亲遗传、双亲双子及多位交配。为了能够避免出现不可行解的情况，本文就使用基于固定交配位双亲双子方式实现交叉，交叉操作，如图3所示。

为了能够避免出现早熟情况，遗传算法就利用变异算法使个体染色体中的某个位置基因使用其他等位基因进行替换，以此形成全新的个体，提高遍历性。本文使用倒位变异方式，随机选择1-t之间的某基因片段，之后将相应片段中的基因值实现逆序倒位排列，不仅能够保证个体可行，还能够进行变异操作。

4 算法使用

将所收集的数据以以上所描述，使用Matlb软件，实现货位分配数学模型的求解。现在需要对一批货物进行入库作业，在实现货物ABC分类之后得到各种货物在货架中需要的入库数量，并且利用基础专家知识库数据的调用，能够有效得到各种货物出入库频率，实验数据，如表1所示。

表1 实验数据

在迭代次数不断增加的过程中，时间函数及适应度值在不断的降低，在迭代为150的时候，适应度的值不变，时间函数值从原本7 500降低为4 300。在迭代为200次的时候，虽然适应度值不发生变化，时间函数也会不断降低成为4 100,而且不发生变化，在满足收敛条件的过程中，就结束迭代。因为货位分配数学模型中已经实现了均衡作业，也就是每个巷道需要作业的次数相同，选择其中的一排货架货位分配优化如表2所示。

表2 货架1-10的分配优化结果

通过优化结果表示，货物1在货架1-4行中，其属于A类货物，利用货物编码创建基础专家知识库用户界面，能够搜索知识库数据，查询待入库类别及存储区域，通过以上结果表式，自学习粒子群算法得到的货物分类及货位分区结果和基础专家知识库相同，表示本文所设计的算法求解结果可行[5]。

5 总结

本文对货位分配进行了分析，根据货位分配的原则，将企业年数据作为根据创建了自动化存取系统中货位动态分配的数学模型。通过某烟草配送中心为例，实现货物动态分类及分区。全面考虑均衡作业约束条件，实现货位动态分配。通过模型求解结果表示，本文所设计的数学模型能够有效解决库容量较大的时候自动化立体仓库系统能力问题，满足实际需求。