基于STPN的分拣系统通信机制设计

肖 伟，彭汝佳，曹 伟

XIAO Wei1,2,3, PENG Ru-jia2,3, CAO Wei1,3

（1.湖南大学 工商管理学院，长沙 410079 ；2.湖南大学 经济与贸易学院，长沙 410079；3.湖南省物流信息与仿真技术重点实验室，长沙 410079）

0 引言

分拣作业是配送的核心作业，决定了配送中心的工作效率和经营业绩，占配送中心总作业成本的40%以上。随着消费时代的来临，终端客户要求配送中心以高速度完成工作，在短时间内完成大批量、多种类的配送任务，这就提高了分拣作业的难度。特别是快递业务的发展，仓储式配送中心向通过式配送中心发展，优质高效的分拣作业有助于物流企业的竞争力成长。

以往的研究表明，就如何改善分拣作业，提高分拣效率等问题，国内学者做了如下探讨。一类研究认为应从硬件环节改善分拣作业，提高设备自动化水平。李哲峰（2001）提出了在货物识别中使用计算机图像处理技术，替代出错率较高的人工识别方式。朱铮涛（2001）提出了使用PLC现场工业总线连接分拣设备与计算机，实现智能化控制。杨庚（2003）提出了一类分拣控制软件的结构，但执行成本较高，选择在卷烟物流中进行了测试。张君等人（2003）提出使用RS串行总线连接分拣设备与计算机，可降低执行成本，但同时有性能损失。田景贺（2006）提出采用RFID技术，实现分拣系统的无人值守工作方式。

另一类研究则认为应从管理角度出发改善分拣作业，提高分拣方式的效率。谢伟东（2007）提出虚拟容器队列算法，将原有的同步分拣方式改进为异步分拣方式，有效提高了卷烟分拣效率。张贻弓（2008,a）提出了一类订单排序算法，将订单排产作为TSP问题，采用最大最小蚁群算法求解。张贻弓（2008,b）还提出了卷烟分拣系统设备选型的优化原则。李丰（2009）提出了一类异步分拣算法，将分拣时间视作虚拟时间窗口分配给分拣设备，改善了分拣系统性能。李歧强（2001）提出了一类受控时滞PN工具，并证明了描述分拣系统方面的有效性。黄银娣（2006）利用PN工具建立了离散仿真模型，检验了分拣系统性能指标。李暄（2009）利用商业仿真软件Flexsim建立了离散仿真模型，优化了分拣设备数量。

本文的研究与前述研究略有不同，在信息技术和自动化技术高度发达的今天，配送中心大量采用自动化技术与IT技术，作业系统和上位系统之间应保持合理有效的通信机制，才能改善分拣作业效率，避免出现异常流程。因而，以分拣作业系统和上位信息系统之间的通信机制为研究对象，采取有穷自动机建立了通信过程图，并插入了异常流程。建立了基于STPN的通信机制模型。算例仿真表明，该通信机制具有可达性，在性能上较现实系统有明显改善。

1 分拣系统的有穷自动状态机描述

分拣系统是配送中心的主要作业系统，担负着订单切割、货物分选的工作。其内部由三个主要子系统构成，分别为负责补充货物的补货系统，负责分拣工作的分拣线路，负责包装输送的包装线路。

分拣系统在空闲中侦听线路信号，如上位系统发送订单到来消息，则回复一个空闲等待消息。分拣系统在运转状态、检修状态或故障状态时不侦听线路信号，同时也不回复上位系统的订单消息。分拣系统在完成订单作业后，回复上位系统执行完毕消息，并回到空闲状态，继续侦听线路信号，因而根据以上的说明，有如下图所表示。

图1 分拣系统的有穷自动状态机

上图中，为简化讨论采取有穷自动状态机的方式描述了分拣系统的5种状态和状态转换条件。其中，状态P1为空闲状态，且在侦听线路消息。状态P2为工作状态。状态P3为完成状态，且在检修中。状态P4为挂起状态，表明工作中出现故障。状态P5为排查状态，表明分拣系统正在排查隐患。转换条件T1表明线路上无消息传来。条件T2表明线路传来分拣任务。条件T3表明分拣机存在缺货。条件T4为补货系统补货到位。条件T5为分拣任务结束，分拣系统发送停机请求。条件T6为上位系统确认分拣任务完成，分拣系统回到侦听状态。条件T7为分拣系统进入检修。条件T8为分拣系统完成检修。条件T9为分拣系统排查隐患。条件T10为补货系统停顿。条件T11为订单等待超时。根据以上的状态和状态转移条件，设分拣系统的当前状态为P0，转移条件为T0，可得到如下通信机制表达式。

步骤1，如分拣系统当前状态为P1，同时分拣系统在侦听线路消息，如无消息传来，则分拣系统保持当前状态P1。如有消息传来，则进入步骤2。

步骤2，分拣系统置当前状态为P2，进入工作状态，如各项工作条件满足，则工作完毕后，分拣系统置当前状态为P3，同时发送完成消息给上位系统。

步骤3，如分拣系统当前状态为P2，进入工作状态，如各项工作条件有未满足条件，如补货条件不满足，则分拣系统置当前状态为P4，系统中的作业流程被挂起。直到各项工作条件满足后，分拣系统置当前状态为P2，进入工作状态，解除作业流程的挂起状态。

步骤4，如分拣系统当前状态为P3，且已收到上位系统停机指令，则分拣系统转入状态P5，进入检修状态。分拣系统进入检修状态后不响应上位系统指令，亦不侦听线路消息，所有线路消息挂起。

步骤5，如分拣系统完成检修，则置分拣系统当前状态为P3，如收到上位系统归位指令，则分拣系统置当前状态为P1，开始侦听线路消息，所有线路消息挂起状态解除，返回步骤1。

2 上位信息系统的有穷自动状态机描述

上位信息系统是配送中心的订单处理机构，负责订单的接受、确认、切割排序和退回处理。在结构上，上位信息系统由三个队列组成，分别为等待订单队列、处理订单队列、完成订单队列。上位信息系统具有几类状态，工作状态、等待状态、挂起状态、侦听状态等。

上位信息系统的等待订单队列如存在等待订单，则进入侦听状态。如分拣系统发来请求消息，则上位信息系统将等待订单队列中的订单取出后发送副本，并将订单置入处理订单队列。上位信息系统处于等待状态。如分拣系统结束作业并发送完毕消息，则上位信息系统转出等待状态，转入等待状态。如上位信息系统等待队列已满，则挂起呼叫中心传来的订单。如上位信息系统内订单为空，则进行侦听状态，侦听线路传来的订单。根据以上的说明，有如下图所表示。

图2 上位信息系统的有穷自动状态机

上图中，为简化讨论，采取有穷自动状态机的方式描述了上位信息系统的5种状态和状态转换条件。其中，状态B1为空闲状态，且未在侦听线路消息。状态B2为等待状态，上位信息系统在线等待分拣系统的申请消息。状态B3为工作状态，上位信息系统发出订单副本，并等待接收来自分拣系统的完成回执。状态B4为上位系统处于侦听状态。状态B5为挂起状态，表明各个消息队列已满，不满足继续执行条件。转换条件K1表明线路上无消息传来。条件K2和条件K3表明线路持续传来订单任务。条件K4、条件K7和条件K10为分拣系统持续发出申请消息。条件K5为分拣系统处于离线维修状态，线路无应答。条件K6为分拣系统发回任务完成回执。条件K8和条件K12为上位信息系统接到分拣系统发送的故障停机请求。条件K9为上位信息系统接到分拣系统发送的复位请求。条件K11为上位信息系统挂起超时。设上位信息系统的当前状态为B0，转移条件为K0，可得到如下通信机制表达式。

步骤1，如上位信息系统当前状态为B1，且未侦听线路，如呼叫中心传来订单副本消息，则上位信息系统置当前状态为B2，侦听下位作业系统申请消息；

步骤2，如上位信息系统当前状态为B2，且线路完好，侦听到下位作业系统发来的申请消息，则上位信息系统从等待订单队列中取出订单副本，下发给下位作业系统，并上位信息系统置当前状态为B3。上位信息系统侦听下位作业系统线路消息，如此时有呼叫中心发来订单副本，则订单副本入上位信息系统等待订单队列。

步骤3，如上位信息系统当前状态为B3，且下位作业系统发来任务完成回执，则上位信息系统置当前状态为B4。上位信息系统重整等待订单队列，已发出订单副本进入完成订单队列。在下位作业系统未发送申请消息之前，上位信息系统处在B4状态。

步骤4，如上位信息系统当前状态为B3，且下位作业系统发来条件不满足消息、故障消息、停机消息，则上位信息系统转入状态B5，挂起当前已发送的订单副本，并开始计时。

步骤5，如上位信息系统当前状态为B5，且计时器已超过订单副本时间标识上限，则上位信息系统取消已发送的订单副本，并将订单副本归位到等待订单队列队尾。处理完毕后，上位信息系统置当前状态为B2，回到步骤2。

步骤6，如上位信息系统当前状态为B5，且收到下位作业系统的条件满足消息、故障排除消息、重启消息后，则上位信息系统置当前状态为B3，重新发送已发送订单副本。

步骤7，如上位信息系统当前状态为B4，如接受到下位作业系统的申请消息，则上位信息系统置当前状态为B3，从等待订单队列中取出下一订单副本发送。如未接受到下位作业系统消息，或接受到下位作业系统的条件不满足消息、故障消息、停机消息，则维持当前状态不变。

步骤8，回到步骤1，直到等待订单队列为空，或已到工作时间上限，上位信息系统关闭侦听端口。

3 基于STPN的通信机制仿真

假设存在一个五元组{ti,pi,bi,ki,mi}，其中ti表示分拣作业系统的状态变迁条件集合，pi为分拣作业系统的状态库所集合。bi表示上位信息系统的状态库所集合，ki为上位信息系统的状态变迁条件集合。mi为上位信息系统和下位作业系统所构成的整体系统的全部状态集合。根据图1和图2中有穷自动状态机的结构，可以采用随机事件Petri net构建整体系统的仿真模型如下。

图3 基于STPN的上位信息系统与作业系统通信机制

图3为采用STPN建立的通信机制仿真模型，模型参数选取为如下形式。仿真周期为1000个周期，设下位作业系统和上位信息系统的工作节拍均为1个节拍。上位信息系统挂起10个周期后返回初始状态，上位信息系统故障后5个周期后重新启动返回初始状态。下位作业系统条件不满后10个周期返回初始状态，或5个周期后条件满足返回工作状态。下位作业系统在停机检修状态20个周期后返回初始状态。

在1000个仿真周期中，上位信息系统共有783个周期内处在工作状态，下位作业系统共有744个周期内处在工作状态。使用率较我们在实际当中对白沙物流长沙站的平均观察数据高9%。在仿真过程中，未发现有令牌死锁情况，表明通信机制具有一致性和各状态可达性，证明基于状态机构建的通信机制具有可行性。但在冲突检测中表明，下位作业系统存在工作状态和故障状态之间的争用问题，因而导致上位信息系统存在工作状态和挂起状态之间的争用问题，需要进一步设计机制解决令牌争用问题，避免可能存在的令牌无效循环。

4 结论

消费时代加快了包装的发展和通过型配送中心的产生，对分拣作业提出了高速度、低成本、大批量、多种类、多目的地的特殊要求。以往的研究方式以改进分拣设备，提高分拣性能为主。区别于以往的研究，以分拣系统与上位信息系统之间的通信机制为研究对象，建立了通讯过程的有穷自动机。在建模过程中，考虑了上位信息系统和下位作业系统可能存在的异常状态，如挂起状态、停机状态、条件不具备状态等。采用STPN工具，将分别建立的有穷自动机组成算例仿真。仿真结果证明采用有穷自动机建模，STPN仿真的方式能够有效描述通信机制，并能在仿真中检验通信机制的可达性和一致性，能够判断通信机制的效率。但在不同状态之间还存在令牌争用，不能避免令牌的无效循环，因而需进一步设计新的通信机制以避免该问题。

[1]李哲峰.智能控制分拣系统的研制[J],现代制造工程,2001,11.

[2]朱铮涛.基于计算机控制的自动分拣智能系统设计[J].组合机床与自动化加工技术,2001,03.

[3]杨庚.分拣系统的软件结构与应用研究[J].计算机应用研究,2003,05.

[4]张君.基于RS-485及UDP的邮包自动分拣与邮单自动生成系统的设计——条码扫描仪与原分拣控制系统的连接[J].计算机应用与软件,2003,07.

[5]田景贺.基于RFID的烟草物流分拣系统设计[J].仪器仪表学报,2006.

[6]谢伟东.条烟自动分拣的异步法及其装置[J].工程设仪仪学报,2007,02.

[7]张贻弓.可合流的自动分拣系统订单排序优化[J],山东大学学报(工学版),2008,05 .

[8]张贻弓.卷烟分拣设备选型与优化[J].物流技术与应用,2008,09.

[9]李丰.基于虚拟空间的烟草自动分拣算法的分析[J].物流科技,2009,01.

[10]李歧强.基于受控计时扩展Petri网的分拣系统建模[J].计算机仿真,2001,05.

[11]黄银娣.基于Petri网的物流分拣系统的建模与仿真[J],物流技术,2006,03,

[12]李暄.Flexsim系统仿真软件在配送中心分拣系统设计的应用[J],物流工程与管理,2009,01.