李 琿，肖海寧,王雨軒,顧海航,陸俊曦

(鹽城工學院機械工程學院，江蘇 鹽城 224051)

近年來，隨著我國電子商務的發(fā)展進入井噴時期，快遞包裹量逐年上升，使得快遞分揀及配送壓力日益增大，多數(shù)快遞公司在“雙十一”“雙十二”期間會出現(xiàn)配送延誤甚至包裹丟失現(xiàn)象[1]。造成這一現(xiàn)象的根源在于國內快遞包裹分揀工作依然依賴于人工，不僅分揀準確性及效率低，且易造成包裹的損壞。為了提升快遞包裹分揀的自動化程度和效率，國內外在新型分揀系統(tǒng)開發(fā)、分揀作業(yè)流程及方法優(yōu)化等方面開展了一系列的探索工作。如：李明等[1]針對貨物品相分配優(yōu)化問題，研究了設備通道配比優(yōu)化數(shù)學模型和啟發(fā)式求解算法；許丹[2]根據(jù)A公司分撥中心布局和采用的分揀技術，探索了一種多路并行分揀模式；楊敏[3]設計了一種垂直輸送分揀設備，并從增強平穩(wěn)性、提高效率、降低成本的角度對其結構進行了優(yōu)化；韓興[4]開發(fā)了一種應用于交叉帶分揀機入口的自動化分揀系統(tǒng)，并研究了快遞分揀算法；李昭等[5]設計了一種包括分揀執(zhí)行機構和承接軌道的分揀裝置，并對關鍵結構的設計方法進行了研究；黃夢濤等[6]為了提高快遞分揀系統(tǒng)的效率和自動化程度，研究了用于快遞分揀的二維碼定位與校正方法；王立平[7]為了提升分揀系統(tǒng)的柔性及可擴展性，對某基于柔性分揀單元的高效智能分揀系統(tǒng)中的分揀信息識別技術、分揀優(yōu)化策略等進行了研究；德國不萊梅大學生產(chǎn)與物流研究所開發(fā)了一款模塊化的智能物流系統(tǒng) Celluveyor，在一些工業(yè)場合的應用已證明其具有靈活性好、魯棒性強、擴容方便等優(yōu)勢，具備廣闊的應用前景[8]。然而，目前國內分揀系統(tǒng)依然基于滾筒、皮帶等較為落后的輸送技術，在分揀效率及靈活性上難以取得重大突破，此外，國內外針對如何降低包裹分揀破損率的研究較少，導致包裹在分揀過程中易發(fā)生相互碰撞而損壞，不利于易破損包裹的分揀。為了提高包裹分揀的靈活性與系統(tǒng)魯棒性，本文設計了一款基于全方位輪的新型模塊化包裹智能分揀系統(tǒng)。

1 包裹智能分揀系統(tǒng)簡介

圖1為本文設計的包裹智能分揀系統(tǒng)示意圖，中間為分揀區(qū)域，四周分布有入口傳送帶與出口傳送帶，各出口傳送帶用于輸出各自指定地區(qū)的包裹。待分揀包裹自入口傳送帶依次進入分揀區(qū)域。整個分揀區(qū)域由分揀模塊整齊填充。各分揀模塊安裝有可識別包裹信息的數(shù)據(jù)采集裝置，可根據(jù)各包裹信息確定其輸送方向。通過多個相鄰分揀模塊的接力輸送可將包裹輸送至對應地區(qū)的出口傳送帶。

1—快遞包裹；2—入口傳送帶；3—分揀區(qū)域；4—分揀區(qū)域出口傳送帶；5—分揀模塊

分揀區(qū)域分揀作業(yè)整體調控流程如圖2所示,由路徑規(guī)劃與交通管控兩大功能模塊組成，當新包裹進入分揀區(qū)域時，路徑規(guī)劃功能模塊根據(jù)包裹所處的入口傳送帶和所需送達的地區(qū)，為其規(guī)劃一條分揀路徑——完成分揀所需途徑的分揀模塊序列。路徑規(guī)劃算法可采用Dijkstra算法[9]，本文不作討論。然而，由于包裹間的分揀路徑重疊在所難免，交通管控功能模塊必須協(xié)調各包裹按照各自分揀路徑依次進入各分揀模塊，以避免包裹間發(fā)生碰撞及環(huán)形死鎖。有必要針對分揀系統(tǒng)中可能出現(xiàn)的路徑?jīng)_突及環(huán)形死鎖，設計對應的提效降損交通管控方法。

圖2 分揀作業(yè)整體流程

2 路徑?jīng)_突及對應的避碰策略

2.1 主要符號簡介

首先定義本文中使用的主要符號：

ΩM={Mi|1≤i≤NM}，為分揀區(qū)域分揀模塊集合，其中Mi為第i個分揀模塊，NM為分揀模塊數(shù)。

G(Mi)為當前正占用Mi的包裹。

2.2 沖突及對應的避碰策略

圖3 包裹路徑?jīng)_突示例

為了避免包裹間發(fā)生碰撞，設計了基于互斥型信號量的避碰策略，通過信號量的“申請—阻塞—授權—占用—釋放”機制避免系統(tǒng)中的各包裹發(fā)生碰撞，具體步驟如下：

其中，I(Mi) 定義為：

(1)

(2)

(3)

①循環(huán)初始化，設置m=1，進入②。

步驟3，所有包裹均已完成分揀，結束。

通過上述流程可保證任一分揀模塊在任意時刻至多僅會授權給一個包裹，從而避免包裹間發(fā)生碰撞。

3 環(huán)形死鎖檢測與避免算法

3.1 環(huán)形死鎖及其檢測方法

圖4 環(huán)形死鎖現(xiàn)象示意圖

首先，基于有向圖理論建立包裹阻塞圖模型。

定義1：包裹阻塞圖ΛQ(VQ，EQ)。該圖為有向圖，其中頂點集VQ定義為：

VQ={Mi|Mi∈ΩM且I(Mi)=1}

(4)

邊集EQ定義為：

(5)

式中：Mi為邊ei,j的起點；Mj為邊ei,j的終點，Mj也稱為Mi的前向相鄰節(jié)點，記Adj(Mi)=Mj。

定理1：在阻塞圖中的一個有向環(huán)路即為環(huán)形死鎖。該環(huán)形死鎖可采用阻塞圖中的有向節(jié)點序列表示，即環(huán)形死鎖LP={Mi,…,Mj,…,Mn}。

證明：根據(jù)阻塞圖的定義，LP中的任一分揀模塊Mi均已被包裹占用，則環(huán)路中的所有包裹均無法移動，因此LP是環(huán)形死鎖。

步驟2,檢測MC是否存在前向相鄰節(jié)點Adj(MC)，若Adj(MC)=?，則不會引發(fā)環(huán)形死鎖，轉步驟4；否則，轉步驟3。

步驟4,輸出檢測結果，結束。

3.2 環(huán)形死鎖臨界狀態(tài)及對應的死鎖避免算法

若檢測到環(huán)形死鎖，則說明分揀系統(tǒng)此時處于環(huán)形死鎖臨界狀態(tài)。下面根據(jù)環(huán)形死鎖臨界狀態(tài)的類型，設計對應的死鎖避免算法。

圖5 單環(huán)形死鎖臨界狀態(tài)示例

4 方法驗證

4.1 包裹智能分揀系統(tǒng)仿真平臺的開發(fā)

圖6 多環(huán)形死鎖臨界狀態(tài)示例

圖7 包裹智能分揀系統(tǒng)仿真平臺

4.2 實驗及分析

利用該仿真模型比較3種交通管控方法。

方法1(Method 1，M1)：本文所設計的提效降損交通管控方法。

方法2(Method 2，M2)：僅采用本文所設計的避碰策略，不采用環(huán)形死鎖檢測與避免算法。

方法3(Method 3，M3)：全程獨占法，即包裹只有在一次性獲得路徑全程所有分揀模塊的使用權后才進入分揀區(qū)域。

圖8 系統(tǒng)單位小時平均分揀包裹數(shù)

圖9 所有包裹平均分揀耗時

圖10 環(huán)形死鎖臨界狀態(tài)出現(xiàn)次數(shù)

5 結束語

本文針對新型包裹智能分揀系統(tǒng)設計的提效降損交通管控方法，能夠避免包裹間發(fā)生碰撞及環(huán)形死鎖現(xiàn)象，有利于易破損包裹的分揀。但受試驗條件限制，本文所設計的提效降損交通管控方法僅通過仿真進行了分析，沒有經(jīng)過實際工程試驗驗證，有一定的局限性，后續(xù)將盡可能和相關企業(yè)聯(lián)合進行試驗驗證，以進一步完善所設計的提效降損交通管控方法。