0 引言
随着智能制造在全球的不断推进，物流的重要性日益凸显，作为现代物流系统核心和枢纽的自动化立体仓库受到企业界和学术界的高度关注。自动化立体仓库可提高仓储作业效率，实现智能化、无人化。实现仓储高效作业和智能化的关键在于能否实现货位优化，而自动仓储系统(automated storage and retrieval system,AS/RS)的货位优化属于NP难问题，一方面，工程上不断将新技术应用于AS/RS以实现智能化；另一方面，学术界采用智能优化理论对AS/RS的研究相当丰富。对AS/RS的研究从起初的硬件结构研究转向库位优化及出入库调度等软件方面。HESKETT等[1]提出了COI索引值的货位分配方法，主要思想是某种货物的最大在库量和周转率的比值越小，该货物的货位就越应靠近入口；LEE等[2]在一直固定取货指令的前提下，对存取指令进行排序，以所有存取任务的时间最短为目标，结果表明对提高立体仓库的存取效率有明显作用；SARKER等[3]采用贪婪排序算法对比双载位立体仓库的吞吐量和单载位立体仓库的吞吐量，结果表明双载位立体仓库的吞吐量比单载位高40%左右；KIM等[4-5]对立体仓库的拣选作业进行研究分析，将其归纳为旅行商问题，以行程最短为目标建立模型，并采用改进启发式算法进行求解；KHOJASTEH-GHAMARI等[6]对多巷道立体仓库的货物拣选作业进行分析，建立以最短拣选时间为目标的数学模型，并采用遗传算法对模型进行求解；BYUNG等[7]提出根据货物周转率的高低划分货位存储分区，方便货物的管理；THOMSON等[8]通过对立体仓库的货物拣选作业进行详细分析，提出路径协调规划方法进行求解；EKREN等[9]提出利用矩阵几何方法和半开放式排队网络，对立体仓库的主要性能进行分析。
国内对自动化立体仓库的研究也相当丰富，李诗珍等[10]研究了拣货方式、路径策略、存储策略对人工拣选效率的协同作用，并确定各策略的适用场合；唐江峰[11]分析了板式定制家具生产的工艺特点，改造并设计满足板材生产自动分拣工艺的立体仓库，并对加入分拣约束的立体仓库货位分配进行分析；王进业等[12]对旁通式自动化立体仓库的拣选作业和复合作业的运动路径和出入口选择进行分析，以堆垛机运行时间最短和运行次数最少为优化目标建立数学模型，分别采用遗传算法和单亲遗传算法来求解，结果表明该模型可明显提高旁通式立体仓库运行效率；薛婷等[13]采用组态软件和可编程控制器设计了立体仓库的自动控制系统软件和上位机控制软件；泮家丽等[14]采用物流仿真方法对立体仓库进行优化；刘欣[15]在货物质量数据缺失的情况下，对立体仓库拣选作业进行优化，并采用数据仿真方法进行验证。
综上，当前学术界对AS/RS的研究方向主要集中在立体仓的拣选作业、单一作业及复合作业三大方面的货位优化和调度问题上，主要目标是缩短存取时间，减少能耗，提高效率。研究对象主要集中在单元货格式立体仓库，其特点是货架由同一尺寸的货格组成；而对悬臂式货架立体仓库的研究几乎没有，悬臂式货架是由在立柱上装设悬臂梁构成的，在悬臂梁上加搁板后，则适合空间小和高度低的库房，管理方便，视野宽阔，比普通搁板式货架利用率高。悬臂式货架立体仓库没有固定的货位，每个位置都可能是货位，从理论上分析，其平面利用率可达100%。当前因为悬臂式货架立体仓库的自动化程度较低，货位最主要是根据经验分配。本文采用智能算法对悬臂式货架立体仓库的货位优化进行分析，研究结论为悬臂式货架立体仓库的货位分配提供参考。
1 问题描述
有一批矩形货物集合{G1,G2,…,Gn}，货物具有{形状，质量，材料，密度}等多种属性，现将其全部装入一个2n层的单轨双货架立体仓库中，在保证仓库平稳的情况下实现货位利用率最大化。为了方便建立立体仓库的入库库位分配模型，对问题论述的前提作以下规定：①立体仓库的货架左边编号为单数，右边编号为双数，最低层分别为第1层、第2层，从下往上递增；②入库作业时堆垛机为单一作业模式，堆垛机只进行入库作业，整个作业期间无货物出库；③为了保证货物安全出入库，货物与货架两端以及货物与货物之间的间隔设为10 cm，货物的高必须比所在货架高度低10 cm；④一个大的货位段允许分配成多个货位给多个货物，货位段内的货物顺序不做排序；⑤已被利用的货物段一旦不能再被分配货位，则剩下的货位段将被视为浪费;⑥由于影响货物在立体仓库中货位的主要因素是货物的形状和质量，故忽略货物的其他属性。
为了保证货架的安全性以及货位分配的合理性，要求满足下列约束条件：①每个货位段中装载的货物不超出装载空间的边界；②所装货物的质量之和不超过货架允许载质量。
2 数学建模
记G={G1,G2,…,Gn}为n个矩形货物集合；T={T1,T2,…,Tm}为m个货位段集合；li、wi、hi、ki分别为货物Gi的长、宽、高、质量；Lj、Wj、Hj、Nj、Xj分别为货位段Tj的长、宽、高、所在货架层号以及货位段起始点距离本层货架起始端点的距离，空货架所包含的货位段X值为0；aij=1或0，若货物Gi分配给货位段Tj，则aij取1，否则取0；M为货架的最大载质量；D1为货物与货架两端以及货物与货物之间的间隔；D2为货物顶部与上层货架挡板之间的最小安全距离。根据上述设定，建立约束条件的数学模型：
(1)
wi<Wj
(2)
hi+D2<Hj
(3)
(4)
(5)
约束条件中，式(1)～式(3)分别表示货位段所装载的货物在保证安全间隔的情况下不超出货位段的装载空间；式(4)表示每个货架装载货物的质量之和不超过货架的最大载质量；式(5)表示一个货物只能分配给一个货位段。
立体仓库的仓储利用率是评判立体仓库优劣的基础指标，提高仓库的空间利用率是提高立体仓库使用效率、降低成本的有效手段。为提高悬臂式货架立体仓库的利用率，实现最大的存储，需保证货位段在分配完货位之后货位浪费最少,则其目标函数为
(6)
为了保证整个立体仓库的稳定性，并考虑作业安全和节约能源，货物分配需遵循下重上轻的存储原则，即要求所有货物的质量与所在货架层的乘积之和最小，使货架的重心最低，提高整个货架的稳定性，则其目标函数表示为
(7)
显然，这是一个多目标的优化问题，采用加权重的方法将多目标转化为单目标，将代表目标在多目标优化问题中的权重系数u1和u2分别赋予对应的目标函数S和Q，权重的大小表示相应的目标函数的重要程度。采用权重自适应方法确定各目标函数的权重，能根据种群的当前信息实时调整权重，提高模型的柔性和适用范围，有
(8)
式中，Smax、Smin分别为当前种群中最大利用率目标函数的最大值和最小值；Qmax、Qmin分别为当前种群中平衡性目标函数的最大值和最小值;S、Q分别为当前种群中当前个体的最大利用率目标函数值和平衡性目标函数值。
3 多种群遗传算法求解货位分配优化问题
3.1 多种群遗传算法
标准遗传算法(standard genetic algorithm， SGA)是通过模拟自然界优胜劣汰的进化过程而形成的一种搜索全局最优解的方法。遗传算法在解决组合优化问题上有操作简单、鲁棒性强和全局搜索性强等优点。对于悬臂式货架立体仓库的货位优化问题也可以用SGA进行求解，但SGA存在早熟和因初始种群不合理而易陷入局部最优等问题。而多种群遗传算法(muti-population genetic algorithm， MPGA)具有初始种群多样性和多种群协调进化的特性，并配合参数的自适应控制方法和对适应度函数进行缩放，可提高遗传算法的自适应能力和搜索能力。本文采用MPGA进行求解，有效地避免了早熟和陷入局部最优解等问题，明显提高了收敛速度。
3.1.1 移民算子
多种群遗传算法中各种群保持相对独立性，为避免多种群遗传算法变成简单的多次遗传算法实验，需加强种群之间的联系。因此，引入移民算子，可加强各种群间联系，丰富种群多样性，防止未成熟和早熟现象。移民算子是将源种群中的最优个体代替目标种群中的最差个体，达到多种群协同进化的目的，见图1。
3.1.2 精华种群
精华种群大小决定了多种群遗传算法的迭代代数，而精华种群的提取需人工选择每一代中每一个种群的最优个体，并将其放入精华种群加以保存，保证各种群产生的最优个体不被破坏和丢失，见图2。
图1 移民算子操作
Fig.1 Operation of Immigrant operator
图2 人工选择精华种群
Fig.2 Artificial selection of the elite population
3.1.3 控制参数
遗传算法中的交叉概率和变异概率参数的选择是影响遗传算法收敛性和性能的关键所在，交叉概率影响全局搜索能力，变异概率影响局部搜索能力，而目前没有具体可行的方法选择参数，通常随机选择交叉概率Px为0.7～0.9，变异概率Pm取0.001～0.05，具有相当大的盲目性。为避免发散和陷入局部最优问题,在适应度值高时需减小Px和Pm的值，加快收敛；适应度值低时需提高Px和Pm的值，防止陷入局部最优：
其中，avg(f)表示当前种群中平均适应度；max(f)表示当前种群中最大适应度；f表示当前种群中交叉个体的最大适应度；f′表示当前种群中变异个体的适应度；参数v1，v2∈(0.7,0.9)且v1<v2；参数v3，v4∈(0.001,0.05)且v3<v4。
3.2 算法实现
3.2.1 编码设计
编码的目的是确定各个货位段的货物分配状况。由于货物在货位段中的摆放顺序不影响整体的货位优化结果，故每个货位段只需知道有哪些货物分配在该货位段中即可。本文采用二进制编码来表示货位分配状况，其所包含的信息如下：
aji∈{0,1}
由于每一个货物只能分配一个货位，所以A的每个行向量bi=(a1i,a2i,…,ani)中只能有一个值为1。已知某个j货位段的货物分配状况时，根据货位短信息和货物信息就可求得该货位段中分配的所有货物的货位信息。
3.2.2 初始种群
初始种群的质量、规模都会影响最优解的搜索，通常初始种群采用随机方式生成，会生成满足约束条件的可行个体和不满足约束的非可行个体，导致种群的质量无法保证。初始种群加入强约束会增大初始种群的复杂度，延长初始种群的生成时间。采用弱约束的方式生成初始种群，即在所有约束条件中选取少数约束，既保证初始种群的生成时间不至于过长，又能提高初始种群的质量，保证算法的尽快搜索最优解。考虑到多种群的初始种群量较大，初始种群时只满足每一个货物只能分配一个货位和一个约束条件。
3.2.3 适应度函数
适应度函数是用来区分群体中个体优劣的标准，是进行遗传算法进化选择的唯一标准，通常情况下由目标函数变换得来。采用轮盘赌进行选择操作的最大问题如下：前期当适应度比较分散时，容易产生超级个体，出现早熟；后期当适应度比较集中时，又不易选出适应度高的个体，出现爬山能力不足。对适应度进行放缩，能快速聚集种群，提高适应度值。由于本文中的目标函数是求最小值，首先需要对目标值求倒数：
其中，avg(1/f)表示当前种群中目标函数倒数的平均值；max(1/f)表示当前种群中目标函数倒数的最大值；c表示放缩控制参数，c取值越小，放缩程度越大，此处取1.5。
3.2.4 多种群操作
提取出每一代各种群中适应度最好和最差的个体，通过移民算子实现各种群间优秀个体的传播，丰富种群的多样性，提高算法的全局搜索能力。另外，人工选择每一代各种群的最优个体并保存到精华种群，直到精华种群的规模达到设计要求便结束算法。
4 仿真实验及分析
分别采用SGA和MPGA对7组数据进行优化，结果见表1。图3和图4分别为其中第6组数据采用SGA和MPGA适应度函数随进化代数的收敛情况。SGA各参数值如下：种群规模p=40，交叉概率Px=0.7，变异概率Pm=0.01，最大遗传代数Gmax=200。MPGA各参数值如下：种群规模p=40，种群数量GNum=3，交叉概率Px为0.7～0.9，变异概率Pm为0.001～0.05，最大精华种群规模Gmax=200。
表1 SGA和MPGA性能对比
Tab.1 Performance comparison between SGA and MPGA
第1组第2组第3组第4组第5组第6组第7组MPGA平均计算时间(s)4.768 95.649 26.437 26.533 67.263 47.687 78.763 7迭代代数39363628453141最佳适应度16 85117 67821 77215 10522 36022 05515 655SGA平均计算时间(s)4.272 54.780 65.071 25.914 05.794 26.561 97.293 3迭代代数45364431486543最佳适应度21 78625 97822 90729 88036 31029 88038 430
对比两种算法对货位优化的结果可知，单从SGA和MPGA都收敛并且最佳适应度相同的数据结果来看，SGA在平均计算时间方面比MPGA表现稍好，这主要是因为MPGA的整体运算规模比SGA大。虽然SGA在运算时间上比MPGS有优势，但SGA却存在致命的早熟问题和不收敛问题。对比图3和图4可以看出，多种群遗传算法在运行到第31代就已经收敛，且目标函数值为22 055；而简单遗传算法运行到第65代才收敛，其目标函数值为29 880，可见MPGA的全局搜索能力明显优于简单遗传算法。
MPGA相比SGA在悬臂式货架立体仓库货位优化中具有更好的全局搜索能力，且能较好地解决SGA存在的早熟和不收敛等问题。本文对两种优化策略采用等值处理，在实际应用中可以根据具体问题调整权重，以得到更合理、更高效的分配方案。
图3 SGA适应度函数值变化曲线
Fig.3 Fitness function value change curve of SGA
图4 MPGA适应度函数值变化曲线
Fig.4 Fitness function value change curve of MPGA
5 结论
本文详细介绍了悬臂式货架立体仓库的结构和货位分配特点，提出仓库最大利用率和货架稳定性的策略实现货位智能优化，并建立多目标数学模型，采用智能算法对模型进行优化分析。最后采用MATLAB仿真实验，从平均计算时间、适应度函数变化方面对比MPGA和SGA，结果表明MPGA在解决悬臂式货架立体仓库货位优化问题上比SGA更优异高效。本文只考虑仓库最大利用率和稳定性两个衡量指标，下一步将在此基础上研究如何构建数字孪生系统[16-18],以提高立体仓库的运行效率。
[1] HESKETTJ L.Cube-per-order Index-a Key to Warehouse Stock Location[J].Transportation and Distribution Management,1963,1(3):27-31.
[2] LEE H F,SCHAEFER S K.Retrievel Sequencing for Unit Load Automated Storage and Retrieval Systems with Multiple Openings[J].Intertional Journal of Production Research,1996,34(10):2943-2962.
[3] SARKER B R,SABAPATHY A,LAL A M.Performance Evaluation of a Double Shuttle Auomated Storage and Retriveal System[J].Production Planning & Control:The Managenment of Operation,1991,2(3):207-213.
[4] KIM B, HERAGU S S, GRAVES R J,et al. Clustering-based Order-picking Sequence Algorithm for an Automated Warehouse[J]. International Journal of Production Research, 2003, 41(15):3445-3460.
[5] KIM B, HERAGU S S,GRAVES R J,et al. A Hybrid Scheduling and Control System Architecture for Warehouse Management[J]. IEEE Transactions on Robotics & Automation, 2003, 19(6):991-1001.
[6] KHOJASTEH-GHAMARI Y, SON J D, KOREA J. Order Picking Problem in a Multi-aisle Automated Warehouse Served by a Single Storage/Retrieval Machine [J]. International Journal of Information and Management Sciences Chang C T, 2008, 19(4):651-665.
[7] BYUNG C P, ROBERT D F, EDWARD E. Performance of Mini-load System with Two-class Storage[J].European Journal of Operational Research,2006,17(1):144-155.
[8] THOMSON J J. Efficient Scheduling for Multiple Automated Non-holonomic Vehicles Using a Coordinated Path Planner[C]//IEEE International Conference on Robotics and Automation. Shanghai,2011:1-4.
[9] EKREN BY , HERAGU S S , KRISHNAMURTHY A , et al. Matrix-geometric Solution for Semi-open Queuing Network Model of Autonomous Vehicle Storage and Retrieval System[J]. Computers & Industrial Engineering, 2014, 68:78-86.
[10] 李诗珍.拣货方式、存储策略与路径策略协同研究[J].工业工程,2011,14(2):37-43.
LI Shizhen. Synergistic Effect Study on Picking,Storing and Routing Policies[J]. Industrial Engineering Journal, 2011,14(2):37-43.
[11] 唐江峰. 定制家具板材分拣系统自动化立体仓库研究与设计[D].衡阳:南华大学,2016.
TANG Jiangfeng. Research and Dessign of AutoMatic Solid Warehouse of Sorting System for Custom Furniture Board[D]. Hengyang:University of South China,2016.
[12] 王进业.旁通式自动化立体仓库堆垛机作业的优化调度研究[D].兰州:兰州交通大学,2015.
WANG Jinye.Study on Optimization of Stacker Working Dispatching in Bypass Type Automated Warehouse[D]. Lanzhou:Lanzhou Jiaotong University,2015.
[13] 薛婷，苏晓峰，闫起源，等.立体仓库自动仓储控制系统的设计[J].机械制造,2017,55(7):33-36.
XUE Ting, SU Xiaofeng, YAN Qiyuan,et al. Design of Automatic Warehouse Storage Control Sys-tem for Three-dimensional Warehouse[J].Machinery manufacture,2017,55(7):33-36.
[14] 泮家丽，王勇，曹一凡,等.基于虚拟仿真的立体仓库优化设计及“无纸化作业”推进[J].物流技术,2017,36(6):165-169.
PAN Jiali, WANG Yong,CAO Yifan,et al. Optimization of AS/RS and Promotion of Paperless Operarion Based on Virtual Simulation[J]. Logistics Teschnology,2017,36(6):165-169.
[15] 刘欣.立体仓库储位优化研究[J].价值工程,2015,34(36):239-241.
LIU Xin. Research on the Storage Position Optimization for Stereoscopic Warehouse[J]. Value Engineering,2015,34(36):239-241.
[16] LENG Jiewu, ZHANG Hao, YAN Douxi,et al.Digital Twin-driven Manufacturing Cyber-physical System for Parallel Controlling of Smart Workshop[J].Journal of Ambient Intelligence and Humanized Computing,2018:1-12.
[17] LIU Qiang, ZHANG Hao, LENG Jiewu, et al. Digital Twin-driven Rapid Individualised Designing of Automated Flow-shop Manufacturing System[J].International Journal of Production Research, 2018.
[18] ZHANG Hao, LIU Qiang, CHEN Xin, et al. A Digital Twin-based Approach for Designing and Multi-objective Optimization of Hollow Glass Production Line[J].IEEE Access, 2017,5: 26901-26911.
