基于排队网络队列模糊控制的自动小车立体仓库出入库任务的分配方法

    摘要： 考虑平均单位时间内自动小车存取系统（AVS／RS）的出入库货物总个数一定的情况，现有的将存取指令随机分配给不同存储区域的方式，会造成指令分配不均，使得一些区域等待服务的货物大量堆积，同时另一些区域闲置，从而导致整个仓库系统的效率和能力不能得到充分发挥。对此，提出了基于排队网络模糊控制的AVS／RS的出入库任务分配方法，其首先建立AVS／RS排队系统并通过模糊控制来进行指令的准入决策，由于引入成本和收益分析，可以实现分配的最佳化。最后设计了Matlab仿真程序，并进行了仿真研究，通过对指令运行周期（P1），AGV利用率（P2）及升降机利用率（P3）的分析，验证了方法的有效性。

 

    关键词：AVS／RS，排队网络，模糊排队控制系统

 

 

    自动化仓库系统是现代物流系统的一个重要组成部分，广泛地运用于各行各业中。自治小车存取系统（AutonomousVehicleStorageandRetrievalSystems，AVS／RS）是利用自治小车（AutomaticGuidedVehicles，AGV）在立体仓库货位间的轨道上作水平运动实现货物的出入库操作，其垂直运动依靠安置在仓库边缘的升降机系统完成，即AGV在立体仓库中作三维运动实现货物的存取操作，AVS／RS示意图如图1。

 

    图1AVS／RS示意图

 

    AVS／RS的研究还处于起步阶段，集中在AVS／RS的优化设计上。Ekren、Soyaslan等人基于仿真软件搭建仿真平台，综合配置AGV利用率、升降机利用率和指令周期等参数来建立最优的AVS／RS模型。这些工作推动了对AVS／RS最优化模型的研究。大多学者在解决AVS／RS货物出入库问题上还是基于AS／RS货物出入库调度的解决方案。国内外AS／RS出入库调度问题的研究主要集中在宏观物流系统优化上，成果主要是不同存储原则下的货物分配模型，比如Tompkins提出入库的货物可以存放在任意的可存取货位上的随机存储原则［6］，罗来仪提出按货物级别不同存放到预先指定的不同区域内的分级存储原则等。这些原则宏观角度上解决了出入库的货位分配问题，然而在微观动态下出入库货位的分配存在着严重不足。随着技术与理论的发展，在微观上仓库货物出入库研究出现新的理论与方法，如韩国的Lim应用遗传算法和计算机模拟对系统进行入库计划控制，这些算法是对模型进行前期预测，在面对过于复杂系统就很难应用。Heragu等人使用排队论方法，根据AGV和升降机的运行时间和利用率的概率分布，提出了一种有效的概念模型。AVS／RS的排队网络模型的建立给评估AVS／RS性能带来了非常大的便利，但主要用于AVS／RS最优化设计上。张润彤等人提出了模糊排队控制系统［3］，建立了串行队列的客户的最优化准入策略，能动态地确定顾客最优准入策略。由此，我们提出利用模糊排队控制对AVS／RS出入库进行平衡控制。这不仅能有效的对AVS／RS进行动态控制，而且对提高AGV和升降机的利用率有很大的帮助。

 

    1模糊排队网络建模

 

    排队网络模型是用来估计离散事件，多级服务系统重要性能指标的强有力工具。本文通过对AVS／RS模型建立排队网络模型，利用排队网络解决AVS／RS出入库控制最优化。本文对AVS／RS模型进行有效的简化，建立的排队网络模型如图2。此排队网络是由若干个并联的仓库区域i（i＝1，2，…，n）简表1AVS／RS模型参数

 

    化的排队网络组合而来，每个区域有自己的服务队列且服务队列能容纳无限的存取指令。不同区域服从泊松分布的到达存取货物指令速率不同，每个存取指令被AGV进行存取操作后离开系统。假定i类货物存取指令遵循泊松过程以速度i到达仓库区域i，在区域i内AGV的连续存取货物的周期相互独立并服从均值为1／μi的指数分布，并与货物无关。一个货物存取指令到达指定区域后可以被拒绝也可以被接受进入该区域的服务队列里等待AGV服务。设货物存取指令准入决策的时刻定为在新的存取指令的到达时刻。在决策时刻系统的状态可表示为xi＝0，1，

 

    2，3，…，i＝1，2，…，n，其中xi表示进入区域i正在排队或正在被n服务的存取货物指令的个数。所以Σxi是表示AVS／RS的存取 i＝1

 

    货物指令的总数。假设停止到服务将获得固定收益ri，指令k由j区域服务将损失w•｜j－i｜，w是一个固定值，它代表相邻区域代为存取货物的成本，｜j－i｜就代表相隔多少区域，单位时间内在区域i服务队列中的单个指令的占位费为hi。问题是根据系统的状态动态地确定最优的准入策略以保证系统的期望利润最大。

 

    图2AVS／RS排队网络模型

 

    2排队网络的模糊控制器的设计

 

    模糊控制方法是以模糊集合论、模糊语言变量和模糊逻辑推理为基础的一种有效的最优控制方法。在排队网络的基础上加上模糊控制器，在每个决策时刻让控制器能做出最优决策。具体地说，根据当前系统的状态，一个装备着模糊规则库的推理机实时地确定出一个在线决策用以调整系统的行为，并以此保证这个系统每次操作最优。

 

    本文建立的模糊排队控制系统如图3。其中模糊推论模型用Mamdani型［1］，Mamdani型模糊推理算法采用极小运算规则定义模糊蕴含表达的模糊关系，如规则R:IfxisAthenyis

 

    B，式中：x为输入语言变量，A为推理前件的模糊集合，y为输出语言变量，B为模糊规则的后件。用Rc表示模糊关系：μRc（x）＝min（μA（x），μB（x））。为了更好实现动态性在非模糊化处理时采用最简单快速的最大隶属度法。

 

    图3模糊排队控制系统

 

    根据模型选择作为模糊输入的参数：在区域i服务队列中等待的存取货物指令数si＝0，1，…，i＝1，2，…，n，j类存取货物指令的到达速度λj∈［0，＋∞），j＝1，2，…，n。用表示一个正到达的i类存取货物指令k是否被服务队列i接受的决定dk，i∈｛0，1｝作为模糊输出。模糊输入si、λj和输出dk，i的隶属函数见图4。

 

    图4隶属函数

 

    2．1模糊控制策略与规则的建立

 

    AVS／RS有n个区域，故模糊控制系统有2n个输入且每一个输入都有4个模糊集合，所以模糊规则库共包含了42n条规则。由于规则数太多不易建立模糊库，把算法分两级来做简化处理。设定一个i类存取指令的k到达系统，Ⅰ级：判断服务队列i是否接受指令k，若接受，指令k就进服务队列i，拒绝接受指令k后，再根据区域i与区域j（j＝1，2，…，n，j≠i）相互关系来确定服务队列j是否接受指令k；经过Ⅱ级后可能产生几个服务队列同时允许指令k进入，指令k就进入这些队列中获得利润最大的服务队列j＇中等待服务，从在全局上达到最优。假如所有的服务队列都拒绝接受指令k，系统将默认进入服务队列i。通过两级模糊控制会使模糊规则条数大大减小，有利于实现控制的实时性，算法流程

 

    图5两级模糊控制策略图如图5。

 

    2．1．1Ⅰ级模糊控制的构造针对一个i类存取指令k建立的级模糊控制规则：

 

    1）区域i服务队列中有很多等待存取的指令时，将对正到达的k指令说“YES”可能性会变得很小，由于已堆积的存取指令已带来了很高的占位费；

 

    《工业控制计算机》2014年第27卷第7期

 

    2）在区域i内i类存取指令有较高到达速率时，服务队列i将削弱对正到达的k指令作“YES”的决定，增加超额的存取指令会导致占位费比例增加。

 

    根据上述规则，建立dk，i的模糊规则库如表2，其中“YES”表示一个到达的i类存取指令k被服务队列i接收并进入服务队列等待AGV对其服务，“NO”表示不被接收。

 

    表2Ⅰ级模糊规则库

 

    针对区域i的排队网络分析模糊输出dk，i与模糊输入si，λi之间的定量关系，确定si、λi的隶属度函数中PB到底有多大。

 

    定理1：当一个i类存取指令k以很慢的速度（λi→0）到达区域i，服务队列i若接受指令k的占位费超过所获得的固定收益时，此时si达到PB的最大值。

 

    证明：考虑区域i服务队列中排队等候的指令个数si时，假设每个i类指令以非常慢的速度到达区域i，这保证指令的到达速率不对si有的影响。当服务队列i中si达到一定值后，接下来的一个i类指令k被服务队列i接受的占位费刚好超过其所获得的固定收益，使得服务队列i拒绝接受指令k，此时si达到服务队列i可接受指令个数的最大值，即认为si达到隶属度函数中PB的最大值。

 

    根据定理1推出在指令k以很慢的速度（λi→0）到达区域i，当si满足式2服务队列i将会拒绝指令k进入。

 

    （si＋1）•hi

 

    ri＜（2）μi整理得：

 

    μi•ri

 

    si＞－1（3）hi

 

    由Mamdani型模糊推理算法，当λi是ZO，si＞μi•ri－1即sihi达到PB的最大值时，dk，i将输出NO。

 

    定理2：在区域i中有且仅有一个在服务中的指令，即xi＝0，si＝0，一个正到达的i类存取指令k若被服务队列i拒绝进入所节省的成本超过其被接受所获得的期望利润时，此时λi达到PB的最大值。

 

    证明：区域i中xi＝0，si＝1表明服务队列i没有等待服务的指令，此时服务队列i接受或拒绝一个到达的指令k系统都会获得利润，但到达速率λi会影响服务队列i是否接受指令。服务队列i拒绝指令k所节省的成本超过接受它所获得的期望利润时，服务队列i会拒绝接受指令k，此时λi达到服务队列i可接受指令的最大速度，即认为λi达到隶属度函数中PB的最大值。

 

    在区域i中有且仅有一个在服务中的指令情况下，服务队列i拒绝指令k系统将节省成本是单位时间的利润（ri－）除以μi直到下一个指令到达的期望时间间隔，于是拒绝指令k将节省成本是（ri－hi）／（1＋λi•1）；如果服务队列i接收指令k，区μiμiλi＋μiλi 域i在给指令k服务时间1内获得一份收益ri，同时它在一个时μi 间内也带来了占位费，这个时间是2＋λi•1，因此服务队列μiλi＋μiλi i接收指令k获得利润变为→ri－hi（2＋λi•1）→／1。在区域iμiλi＋μiλiμi内有且只有一个在服务中的指令情况下，λi满足式（4）时服务队列i将会拒绝指令k进入。λi＞2h(μi)i（μiri－3hi＋姨μi(2)ri(2)－2μirihi＋5hi(2)）（4）由Mamdani型模糊推理算法，当si是ZO，λi＞μi（μiri－3hi2hi＋姨μ2ir2i－2μirihi＋5h2i）即λi达到PB最大值时，dk，i将输出NO。

 

    2．1．2Ⅱ级模糊控制的构造针对一个正在到来的i类存取指令k建立的Ⅱ级模糊控制规则：

 

    1）区域i的服务队列中有很多等待存取的指令时，将强化

 

    服务队列j（j＝1，2，…，n，j≠i）对指令k说“YES”；

 

    2）区域j的服务队列中有很多等待存取的指令时，将以很小的机率对指令k说“YES”；

 

    3）区域i有较高的存取指令到达速率时，同样将强化服务队列j对指令k说“YES”；

 

    4）区域j有较高的存取指令到达速率时，同样也将以很小的机率对指令k说“YES”。

 

    根据上述规则，建立dk，j的模糊规则库跟表1类似。

 

    一个i类存取指令k需要借助区域j内AGV来完成存取操作，说明服务队列i已经拒绝了该指令，所以在模糊控制中的模糊输入si，λi对模糊输出dk，j与模糊输出dk，i的影响是相对的；然而模糊规则库中模糊输入si，λi对模糊输出dk，j与模糊输出dk，i的作用相反。综上s＞μi•ri－1时si达到PB的最大值，λi＞

 

    2h(μi)iiii姨μi(2)ri(2)－2μirihi＋5hi(2)）时λi达到PB的最大值。

 

    （μr－3h＋

 

    定理3：一个i类指令k被服务队列i拒绝进入后并以很慢的速度（λj→0）到达区域，若服务队列接受指令k所付的占位费超过所获的固定收益时，sj达到隶属函数中PB的最大值。

 

    定理3的证明类似定理1，省略证明过程。一个i类指令k被服务队列i拒绝进入后并以很慢的速度（λj→0）到达区域情况

 

    下，当sj满足式（5）服务队列j将会拒绝指令k进入。

 

    μj•（ri－w•j－i）

 

    sj＞－1（5）hj

 

    定理4：一个i类指令k被服务队列i拒绝进入后并且区域j中有且仅有一个正在接受服务的指令，xj＝1，sj＝0，若指令k被服务队列j拒绝所节省的成本大于其被接受所获得的期望利润时，λi达到隶属函数图中PB的最大值。

 

    定理4的证明类似定理2，省略证明过程。在服务队列i拒绝让指令k进入后并且区域j内有且仅有一个在服务中的指令情况下，当λi满足式（6）服务队列j将会拒绝指令进入。

 

    μj222

 

    λj＞［（ri－w•j－i）μj－3hj＋姨（ri－w•j－i）μj－2（ri－w•j－i）μjhj＋5hj］（6）

 

    2Hj

 

    2．2服务区域的优选

 

    服务队列i拒绝指令k进入后，可能有多个区域同时满足Ⅱ级模糊控制可以给指令k提供服务，从这些区域中选择获得利润最多的区域j′，从而使AVS／RS在运行中达到整体最优。假设在指令k到达区域j时，服务队列j中已有m个正在排队的指令个数，那么服务队列j接受指令k将获得利润为：

 

    p（j）＝ri＋（ri－（m＋1）•hj－wj－i）／（1＋λj•1）－m•hjsμjμjλj＋μjλjμj

 

    44基于排队网络队列模糊控制的自动小车立体仓库出入库任务的分配方法

 

    －ri－wj－i－hj（m＋2＋λj•1）／1（7）μjλj＋μjλjμj

 

    AVS／RS在运行中优选的原则为：

 

    p（j′）＝min（p（j）），j′∈j（8）

 

    3仿真实验设计

 

    基于Matlab的AVS／RS仿真流程图［5］如图6、图7所示。

 

    实验假设如下：

 

    图6储存流程图

 

    图7提取流程图

 

    4案例分析

 

    本课题设计的AVS／RS包含A＝42个巷道和T＝7层货架，货架B＝27个货仓，每个货仓能存储3个货物，因此这个仓库容

 

    量为47，628，其中D＝1，H＝0．6，W＝1．5，BL＝2．15，Yx＝0．5。系统

 

    包含V＝21个AGV和L＝7个升降机，仓库分为7个区域，每个区域1个升降机和与之相适应的3个AGV，其中vv＝2，vL＝1，TT＝TL／U＝14。排队模糊控制系统涉及的参数：各区域服务速度相等μ1＝μ2＝…＝μn＝3．5，服务每类指令获得的固定收益相等r1＝r2＝…＝rn＝16，不同区域单位时间里需付的占位费相等h1＝h2＝…＝hn＝0．13。通过对运用排队模糊逻辑的方法的AVS／RS进行仿真，得到指令运行周期（P1），AGV利用率（P2）及升降机利用率（P3）与没有运用模糊逻辑方法的AVS／RS对比图8，可以得出运用排队模糊逻辑的方法后指令运行周期变短，AGV与升降机的利用率有明显的提升。

    参考文献：

 

    ［1］张润彤，朱晓敏．串联排队网络顾客准入的模糊控制［J］．自动化学报，2009，26（2）

    ［2］SundereshS．Heragu，XiaoCai,Luo,J．AnalysisofAutonomousVehicleStorageandRetrievalSystembyOpenQueueingNetwork[J]5thAnnualIEEEConferenceonAutomationScienceandEngineeringBangalore,India,August22－25,2009

    ［3］GinoMarchet,MarcoMelacini,SaraPerottiandElenaTappia．Analyticalmodeltoestimateperformancesofautonomousvehiclestorageandretrievalsystemsforproducttotes[J]InternationalJournalofProductionResearchVol．50,No．24,15December2012,7134－7148

    ［4］BanuY．Ekren,SundereshS．Heragu,AnanthKrishnamurthy．AnApproximateSolutionforSemi－OpenQueueingNetworkModelofanAutonomousVehicleStorageandRetrievalSystem[J]．TransactionsonAutomationScienceAndEngineering,Vol．10,No．1,January2013

    ［5］Tompkins．Facilitiesplanning[M]．Wiley．com．

    ［6］罗来仪，王智强．现代物流知识回答［M］．北京：对外经济贸易大学出版社，2002

    注:本文由笔耕文化传播（www.bigengculture.com)整理，文章版权归原作者所有，转载请注明出处！