基于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.