基于多旋转货架协同作业的拣选路径优化方法.pdf

DOI:10.7493486.2023.03.003Jun.2023JOURNAL OFNAVALUNIVERSITY OF ENGINEERING2023年6 月大No.3Vol.35海第3 5卷报程第3 期军学学基于多旋转货架协同作业的栋选路径优化方法芮万智，段军雨，贾正荣（海军工程大学舰船综合电力技术国防科技重点实验室，武汉430 0 33）摘要：为提升多旋转货架的栋选作业效率，保证军械货品的分类正确率，采取一种并行调度作业方式对货架转运路径进行优化，并提出了一种协同组合优化算法。首先，建立了包含分批货品数量、转运时间间隔等约束的多旋转货架协同栋选模型；其次，通过栋选时间序列化转换提高算法收敛性，引入多模块协同组合策略提升算法执行效率。仿真结果表明：与两种典型启发式算法相比，该算法能快速、有效求解协同栋选次序，使得作业时间最小。研究结果可为多模块特征下的仓储系统栋选路径规划提供参考。关键词：多旋转货架；MCS-OOPP模型；协同栋选；时间序列化；最优路径中图分类号：TP271.2；T P391文献标志码：A文章编号：10 0 9348 6（2 0 2 3)0 30 0 150 7Picking path optimization method based on multi-carouselcollaborative operationRUI Wanzhi,DUAN Junyu,JIA Zhengrong(National Key Laboratory of Science and Technology on Vessel Integrated Power System,Naval Univ.of Engineering,Wuhan 430033,China)Abstract:In order to improve the picking efficiency of multi carousel and ensure the accuracy of goodsclassification,a parallel scheduling operation method was adopted to optimize the shelf transfer path,and a collaborative combinatorial optimization algorithm was proposed.Firstly,a carousel collabora-tive picking model with batch quantity and transshipment time interval constraints was established.Secondly,the convergence of the algorithm was improved by sorting time serialization transforma-tion,and the multi module cooperative combination strategy was introduced to improve the executionefficiency of the algorithm.The simulation results show that compared with the two typical heuristicones,the algorithm can solve the collaborative picking path quickly and effectively,and minimize thecost of operation time.The research results can provide reference for picking path planning of ware-housing system under multi module characteristics.Key words:multi-carousel;MCS-OOPP model;collaborative picking;time serialization;optimal path旋转货架是一种用于存储多类别中小型货品的自动化存储装置，作为高效物流仓储系统的重要组成部分，已适用于军械仓库的货品管理中。优化货品栋选路径对于提升旋转货架作业效率、仓储系统管理效能具有重要意义。旋转货架栋选优化问题近似于动态非闭环旅行商问题 1，按照研究对象可分为单旋转货架和多旋转货架。国内外学者通过建立不同约束条件下的数学模型，利用蚁群算法 2、粒子群算法 3或启发式融合算法 4-5等，研究了单旋转货架栋选收稿日期：2 0 2 2-0 6-10；修回日期：2 0 2 2-0 7-2 0。基金项目：国家自然科学基金资助项目（5197 7 2 18）。作者简介：芮万智（198 4一），男，副研究员，博士，主要研究方向为网络化控制系统、位置检测。通信作者：段军雨（1997 一），男，硕士生，98 6 58 2 6 2 5 。16大第35卷海报程军学学问题，取得了诸多有意义的成果。随着工业领域对货物存储量需求的提高，单旋转货架仓储系统的扩容，出货效率大打折扣，极大限制了此类仓储系统的应用。多数文献侧重于研究单旋转货架转运路径问题，为提升栋选作业效率，对多模块下的协同抹选问题也逐渐开展研究。Park等 6 以最短栋选时间为目标，提出一种轮流分选方法求解双旋转货架的栋货路径；张志强 7 利用图论的方法建立组合分层旋转货架转运优化模型，通过改进的离散粒子群算法求解最短路径；李晓春等 8 在文献 6 模型的基础上考虑降低货品分类出错率，提出了OPPOA启发式算法求解；Shankar等 9将一种元启发式策略引入粒子群算法，减少多旋转货架下的交叉抹选数量进行求解栋选路径；Yan等 10 基于Petri网建立多模块回转装置模型，根据时间响应设计两种启发算法，减少作业时间误差。综上，以往针对多旋转货架下的栋选路径研究，在求取最优栋选路径时仅以提升栋选效率为主要目的，且约束条件单一，如以栋选台数量、货品种类等为约束条件。但在实际栋选作业中，保证大规模货品的分类正确率同样重要，分批次、定间隔的规律作业能够减少货品分类时的差错。另外，大部分研究采用的规划方法随机因素多、时间复杂度较高，难以满足时效性。针对上述问题，本文研究了一种并行调度作业约束下的多旋转货架栋选路径优化问题（optimizationof parallelpic-kingoperationn inmulti-carousel Isystem,MCS-OOPP），即在栋选批次、分批货品数量、转运时间间隔的约束条件下，设计一种协同组合优化算法，求解货品的最优协同抹选路径。1问题概述1.1多旋转货架装置多旋转货架装置由数个并列摆放的旋转货架组合而成，多个抹选台与各个货架一一对应，并且各个货架可包含不同数量、装货配置的储位。储位是指装载货品的托盘货仓单元位置，各个储位对应货品的种类、数量确定（见图1）。旋转货架8 利用传动装置沿顺、逆时针方向任意转动，通过固定数量的托盘货仓混装多种类型的货品，并在固定一端的栋选台实现货品分离、完成出库。在进行栋选作业时，各个货架的传动装置、栋选台工作机制相同且相互独立，托盘与传动装置水平挂接，按照规划次序转运货品，转运路径栋选由栋选次序确定。抹选台传动装置货品托盘货仓储位水平旋转货架1水平旋转货架2水平旋转货架n图1多旋转货架装置示意图Fig.1Schematic diagram of multi-carousel device1.2MCS-OOPP问题描述MCS-OOPP问题是在并行调度作业约束下（即给定货品栋选批次、转运时间间隔、分批货品数量的约束条件），以最小化抹选时间代价为指标，求解各个旋转货架的货品选定、栋选序列以及多旋转货架协同作业的最优栋选次序。为便于问题及模型概述，定义相关参数如下：N为多旋转货架装置的货架数量；n为进行选作业的旋转货架编号，n=(n1，n 2，);M为单个旋转货架储位的最大数量；m为单个旋转货架上选定的货品数量；（，y）为二维坐标，表示储位位置，表示储位所在的旋转货架编号；U为一次栋选任务的货品数量；8 为货架的货品装载率，用以确定各个货架的货品装载数；S为协同栋选作业任务；S，为单个旋转货架栋选任务；t。为转运时间间隔，即货品相邻作业次序间的固定时间值；a。为分批货品数量，即同一时刻运出的货品数量；h为完成任务的抹选批次数，h=m/ao;u为各个旋转货架的转动速度，速度相同且恒定；Tsum为完成栋选任务的时间代价。求解多旋转货架装置的协同抹选次序，需选定各个旋转货架的栋选货品，并规划单个旋转货架的栋选任务Sn，由此可得S,二S，表示为Sn=(Gn(T),Gn(T2),.,Gn(T),.,Gn(T)。(1)式中lh；T 为该栋选次序中第k批次栋选的17第3期芮万智等：基于多旋转货架协同作业的栋选路径优化方法时刻;Gn3（T）为在旋转货架n3上T时刻栋选的储位坐标，时刻相同表示同一批次抹选的货品，且to=Tk+1-Tk。所以，MCS-OOPP问题规划的栋选任务可表示为有序集合（集合中各个元素值排列有序），即S=(Gn(Ti),Gn2(T1),Gn3(T,),Gn4(T,),.,Gnc(Th)。(2)1.3MCS-OOPP问题模型多旋转货架中的各个货架结构参数类似，将其进行环形结构抽象，传动装置、储位抽象为线状和点状得到环形抽象图（见图2）。储位初始储位(栋选台处）待抹选储位抹选台其余储位图2 单个旋转货架环形抽象图Fig.2Circular abstract diagram of single carousel根据旋转货架抽象图，将多旋转货架由各个栋选台处展开成线性状态图进行编号，依据节点的状态、位置，货架能够分为三种类型（见图3）。按照货架系统中货品的基准位置，依次表示储位的序号坐标(,y)l=1,2,M;y=1,2,N），其中r=1与=M均表示该货架上位于栋选台处的初始储位点。yN口口(3,M)(5,N)(6,M)N-1口(2,N-1)(4,N-1)(6,N-1)：1O(2,1)(6,1)(M,1)0MX123456图3多旋转货架线性状态展开图Fig.3Linear state expansion diagram of multi carousel任务S在并行调度作业约束条件下，根据初始抹选时刻t。得到时间集合T=（T i，T 2，T，），各货架依次求得目标类别货品的抹选时刻，对比T中元素值选定货品，即确定G，（T)对应坐标。确定待栋选货品对应的储位，若第k、k 十1次栋选的储位位置为i、j，考虑抹选时间代价包含三个部分：准备时间tpre、等待时间th（k，k 十1）、转运时间t（k，k 十1），其中同批次栋选货物间的等待不进行栋选操作，在此不考虑th（k，k 十1)。考虑货架的顺、逆转动，可得其转运时间为tn(k,k+1)=(i-il/u，i-l M/2;(3)(M-i-jl)/u，i一jlM/2。单个旋转货架n上的货品按照规划次序进行选，可得作业时间代价tsum（n）为mtsum(n)=(t,(k,k+1)+tpre)。(4)k=1所以，多旋转货架协同完成栋选任务的总时间代价为NmNTa(n)=22tmtaum(n)=2Zt,(k,tn=1k=1n=1k=1k+1)+mnotpre。(5)各个旋转货架的待栋选货品坐标选定后，n。、m、t p r e 即为定值，由式（3）可知，需取总作业时间代价Tsum的最小值，即要求规划的栋选次序使得转运时间最小，表达式为Nmmin(Turn)=mint,(k,k+1)。(6)n=1k=1由此，MCS-OOPP问题被简化为求解最小转运时间问题，即任务指定抹选货品的种类、数量，在并行调度作业约束条件（给定h、a o、t。）下求取最优协同栋选次序Sbes，满足min Trurn=Tturn(Sbest)。2协同组合优化算法设计算法实现的基本思想是将进行全局寻优的解集限定在由单个旋转货架所得到的局部最优解中，即根据最优回转路径定理，能够将协同栋选次序集S界定在单旋转货架最优栋选次序Sbest中。由局部最优解进行货品、选序列的确定，再通过各个货架抹选序列的遍历组合以获取最优解，避免在多个旋转货架的作业次序中随机搜寻，以提升全局最优解的搜寻效率。2.1栋选时间序列化抹选时间序列化是指将货品抹选时间集合按照转运时间间隔、分批货品数量进行转化，得到一个能够表示每个时间节点上进行栋选的货品数量的序列。抹选时间序列化方式如下所述。18大第3 5卷海报程军学学根据Sbest计算得到无时间间隔约束的栋选作业时间，记为最短选时间。在栋选作业规划时，顺序相邻的两个货品引人等待时间，将二者之间的栋选时间间隔延长，且不能少于最小时间间隔。基于此特点，在给定时间间隔t后，根据Sbest对应的货品抹选时间，可计算得到一个等间隔的序列E=e1，e 2,e 3，,em,在E中相邻两元素存在间隔均为t，其中第i个元素e表示i一1)t时刻（记为t（e;）)能够栋选的货品数量，有e;0，并且当ei2时，表示该时刻能够进行多货齐运。栋选时间序列化过程如图4所示。I，,ta,tb,tEn:.1001XL图4抹选时间序列化示意图Fig.4Schematic diagram of picking time serialization若某个旋转货架的货品栋选时间集合为I,=(ti,.ta,tb,.,tm),nN,mM。将In转换为元素值为正整数的栋选时间序列E，其中ei对应货品的初始栋选时刻tei），t a t，两相邻时刻间满足给定的t，如果该间隔大于需求的转运时间间隔to，且符合L=（t。一t)/，表示tat。间还能以t。栋选L个货品，因此需要在E，中补充L个0，表示能够与其他旋转货架进行组合来满足协同转运。2.2多模块协同组合策略栋选时间集合I，转换成栋选时间序列E，后，根据给定的to、a o，E，进行协同组合的情况包括：序列间隔tto序列元素值e。a o。由此，多个旋转货架的栋选时间序列进行遍历组合，得到一组协同栋选序列Ecop，记为Ecoop=EiE?En，该序列的长度为选次数，每个元素值大于或等于分批货品数量，通过该方式表示各个旋转货架间的协同作业。以转运时间间隔2 t、分批货品数量2 的货品栋选作业为例，栋选时间序列的一种组合过程如图5所示，间隔为4t 的栋选时间序列E1、E2、E3、E4能够组合成Ecopl。在进行N个旋转货架的遍历组合时，多旋转货架共有立u；种组合结果，其中u；为各个货架可选的栋选次序数量。其中，组合序列中的元素值可能大于分批货品数量，此时能够进行减量栋选，例如时间序列中元素值为4的时刻能够以分批货品数量为2 的方式进行栋选，同样能满足固定的分批货品数量要求。E1一000一00010E2100一0 0田E3000一0 00一00田E4000一000一Ecpl2020202020 2抹选时刻04t2t34t4At54t64t74t84t994t10t图5时间序列组合示意图Fig.5Time series combination diagram2.3算法实现协同组合优化算法分为4个阶段。阶段1习求取单一旋转货架最优选次序。阶段2最优栋选次序下的时间集合进行序列化转换。阶段3依据并行调度作业条件，将时间序列进行协同组合得到总选序列。阶段4选定总栋选序列下各旋转货架的货品，计算转运时间，确定最优协同栋选次序。算法步骤如下所述。输入：各个旋转货架的储位坐标、抹货数量U、分批货品数量ao；转运时间间隔to。输出：协同栋选次序S、时间代价Tturn，对应各个货架的货品选定、栋选转运路径。步骤1由各个旋转货架上需求货品的初始坐标G，搜索确定各个货架的最优抹选次序Sbest=(G(t),Gn(t2),.,G,(tm),nN。步骤2 若有I，根据式(3)计算各个旋转货架的抹选时间集合In，n Turn（S*),则min Tturn=Ttum（S*），从而确定最优协同栋选次序，SbestS*。步骤7更新选任务S，若I(S)U,结束；否则，返回步骤2。3实验与分析3.1实验设置本文算法通过MATLAB2016a编程实现，操作系统为Windows7，运行环境的CPU主频为2.9GHz、内存16 GB。将本文提出的协同组合优化算法并与Matthews5、李晓春 8 提出的时间优先算法、邻近域搜索算法比较，以验证算法性能。1）结构配置参数根据某军用仓库工况配置，货架上随机混装10种军械货品，军械货品的标准储位规格为1X1m，转运速度为0.36 m/s，为适用现存的军用仓库尺寸空间，设置如表1所示的多旋转货架的配置参数。表1多旋转货架配置参数Tab.1Configuration parameters of multi carousel序号货架数量储位数量范围装货率配置16(2050)（50 8 0）80%配置28(2050)(5080)80%配置310(2050)(5080)80%配置412(2050)(5080)80%配置构造方法如下：每个货架储位的最大数量分别在（2 0 50）（50 8 0）之间取值，步长为10，存储的军械货品种类随机，共有8（货架配置数量储位范围数量）组数据，货品编号在储位坐标中随机生成，使目标军械货品的生成数量充足，以保证存在可行解。2）军械货品选指标根据军用仓库中的某次典型协同栋选任务，设定军械货品的输人要求：随机选取一种货品，分批货品数量为2，转运时间间隔为4s，栋选货品批次为16。3）仿真指标完成军械货品栋选指标的平均转运时间；求解栋选任务的计算时间；求解不同规模问题的通用性。3.2结果分析1）评估算法执行效率在8 种货架配置情况下，每组数据测试10 0 次取得最佳协同抹选次序，并求得最优解对应路径下的转运时间Tturmn（i），i 10 0，与平均转运时间100Trum进行对比(Trum=Trurn(i)/100)。8 种配i=1置下不同算法得到的平均转运时间对比如图6 所示。时间优先算法邻近域搜索算法协同组合优化算法9888116060601140S/f88868819881120928100806040200681012货架数量/个(a）2 0 50 个储位的转运时间对比(a)Transfer time comparison of 2050storage locations时间优先算法邻近域搜索算法协同组合优化算法25099261S/2681200150100500681012货架数量/个（b）50 8 0 个储位的转运时间对比(a)Transfer time comparison of 5080storagelocations图6 8 种货架配置下的平均转运时间对比Fig.6Comparison of average transfer time undereight carousel configurations由图6 可见，当储位数量在2 0 50 之间取值时，协同组合优化算法、邻近域搜索算法带来的任务执行效率接近。其中，邻近域搜索算法规划下的作业耗时减少约2 3%，协同组合优化算法减少约30%，但随着储位规模逐渐增大，储位数量介于50 8 0 之间时，协同组合优化算法的抹选作业时间耗时减少约35%，任务执行效率更高，主要是由于算法引人的组合策略能够减少同批次货品转运间的等待时间，使得规划结果更优。考虑到货品均匀分配到各个货架协同栋选能20大第35卷海程报军学学够保证货架的使用寿命，因此在固定旋转货架数量（取货架数为12）、储位数量下，对比各算法求解时的货架调度数量评价算法执行性能，结果如图7 所示。12邻近域搜索算法10时间优先算法/协同组合优化算法86421234齐运货品数量/个(a)时间间隔4 s(a)Atinterval of 4 s10/864邻近域搜索算法2一时间优先算法协同组合优化算法01234齐运货品数量/个(b)时间间隔6 s(b)Atinterval of 6 s1210/864邻近域搜索算法2时间优先算法一协同组合优化算法01234齐运货品数量/个(c）时间间隔8 s(c)At interval of 8 s图7不同抹选任务下的货架调度数量Fig.7Carousel scheduling quantity underdifferent picking tasks通过图7 数据对比分析得，间隔时间在4s时，三种算法在不同分批货品数量下，货架的调度使用情况相差不大，但在间隔时间大于4s时，随着分批货品数量的增加，基于协同组合优化算法的调度货架数量明显增加，使得货品栋选分配更加均衡，优化结果更能保证货架的使用寿命。2）评估算法时效性在协同栋选任务相同时，输入4种不同的货架配置，对比各算法求取最优解的计算时间（见表2)。表2 算算法运行时间测试结果Tab.2Test results of algorithm running timeS货架数量N/个测试算法类别681012时间优先算法0.4820.4880.4930.490邻近域搜索算法0.4450.4350.4550.431协同组合优化算法0.2350.2190.2440.223注：储位数量M为50 8 0 个。由表2 数据可知，设计方法的平均计算时间开销分别节省了0.2 11、0.2 58 S，效率提升了约48%，这是由于算法进行的时间序列化转换能够简化在时间集合中选定货品的过程，使得协同组合优化算法的时效性更具优势。3）评估算法的通用性为了验证协同组合优化算法的通用性，采取异构的方式构建6 种多旋转货架装置的初始状态，即在设定范围内随机生成货架的储位数量（取值范围为 2 0，10 0)、各类军械货品的初始位置、装货率（取值范围为 6 0%，10 0%)，并且军械货品分配数量均匀以保证每次规划都存在可行解。为适用于各种大规模、复杂的货品调度任务，不同栋选任务的输入只调整时间间隔（取值范围为 1，10s）、分批数量（取值范围为 1，3)和选批次（取值范围为 5，15），不限制货品种类，由此保证通用性测试时参数设置的合理性。根据范围内生成的栋选任务，区分对比6 种不同结构配置下的路径规划结果，完成任务的平均货品转运时间以及求解的计算时间分别如图8、图9所示。400r300S/2001000123456结构配置图：6种配置下货品栋选的平均转运时间Fig.8Average transit time of goods pickingunder six configurations由图8 可见，随着货架数量的增加、装货率的减少，完成货品转运的时间增加；由图9可见，在货架数量、货品抹选数量最多的配置下，完成转运21第3期芮万智等：基多旋转货架协同作业的栋选路径优化方法路径规划的计算时间均为秒级（均小于3.5s），求解的时效性较优。装货率10 0%3口装货率6 0%S/真210123分批货品数量图9 7不同装货率、栋选任务下的计算耗时Fig.9Calculation time under different loading rates andpicking methods因此，在大量可行的货架配置输人时，本文提出的协同组合优化算法对于MCS-OOPP问题的求解执行效率更高，计算时间开销更小，具有较好的通用性和扩展性，对仓储调度应用有较好的指导意义。4结束语针对多模块仓储装置中栋选作业高效率、低误差的要求，本文研究了一种并行调度作业约束下的多旋转货架仓储系统的栋选优化问题MCS-OOPP。根据旋转货架实际作业中的需求，建立了MCS-OOPP问题模型，以最小化转运时间代价为目标，设计了一种协同组合优化算法，并在相同实验条件下，与两种算法进行了对比测试，求解了8 种货架配置下的协同转运路径。结果表明：协同组合优化算法可快速、有效地求解典型协同栋选任务下的MCS-OOPP问题，满足了旋转货架系统实际应用中的需求。此外，本文所建立的MCS-OOPP模型能够拓展应用于多模块下的回转型仓储系统调度模型，提出的协同组合优化算法能够评估系统不同仓储配置下的栋选能力，为军械仓储系统的作业性能分析提供依据。参考文献(References)：1ANADEH K,DE KOSTER R,ROY D.Robo-tized and automated warehouse systems:Reviewand recent developments J.TransportationScience,2019,53(4):917-945.2邱雅晶，张润雪，易玉柔.自动化仓储系统优化方法的思考J.中国战略新兴产业，2 0 18（12）：118.QIU Yajing,ZHANG Runxue,YI Yurou.Thin-king about the optimization method of automaticstorage system JJ.China Strategic Emerging In-dustry,2018(12):118.(inChinese)3张志强.单旋转货架最优栋选路径求解 J.北京信息科技大学学报，2 0 18，33（4）：6 8-7 2.ZHANG Zhiqiang.Optimum route picking solu-tion for multi-rotating shelves JJ.Journal of Bei-jing Information Science&Technology Universi-ty,2018,33(4):68-72.(in Chinese)4程全明.洗衣生产线调度与物流配送问题研究D.北京：北京科技大学，2 0 17：6 3-7 1.5MATTHEWS J,VISAGIE S E.SKU arrange-ment on a unidirectional picking line J.Interna-tional Transactions in Operational Research,2019,26(1):100-130.6 PARK B C,PARK J Y,FOLEY R D.Carouselsystem performance J.Journal of Applied Pro-bability，2 0 19,40(3):6 0 2-6 12.7 张志强.组合旋转货架抹选路径规划研究 J.制造业自动化，2 0 18，40（8）：140-143.ZHANG Zhiqiang.The picking route planning re-search on multi-rotating shelves J.Manufactu-ring Automation,2018,40(8):140-143.(in Chi-nese)8李晓春，王国庆，钟雪灵，等.双旋转货架栋货路径优化策略JJ.系统管理学报，2 0 12，2 1（1：7 6-8 2.LI Xiaochun,WANG Guoqing,ZHONG Xueling,et al.Order picking in a double carousel systemJ.Journal of Systems&Management,2012,21(1):76-82.(in Chinese)9SHANKAR R R,JAYSEAL S C.Design and op-timization of loop layout in flexible manufacturingsystem using particle swarm optimization JJ.In-ternational Journal of Advancements in Technolo-gy,2018,9(2):1000202.10YAN Jianying,SHI Lina.Analysis on the alloca-tion optimization of airport baggage turntable J.Journal of Physics:Conference Series,2021,1802(3):032125.