貨到人系統中分揀策略的設計與應用

郭 麗，楊騰飛，吳 雙，王 祥，武明虎

（北自所（北京）科技發展有限公司，北京 100120）

0 引言

隨著倉儲物流自動化程度加深，越來越多的企業希望通過全自動化方式實現貨物的分揀，提高企業的配送效率，從而產生更大的效益。

貨到人系統主要由三個部分組成，分別是存儲系統、配送系統以及分揀系統。存儲系統的研究重點在于如何根據SKU使用的頻率合理安排其存儲區域，從而達到出庫頻次最高的SKU出庫時間最短的目標。在配送系統中，從庫端到達分揀站臺的最短路徑以及流量控制等問題一直是業界所關注的重點。而對于貨到人分揀系統，針對分揀策略的研究相對較少。而對于整個系統效率而言，分揀策略的優劣，直接關系到系統整體的運行效率。

1 背景介紹

裝箱問題是經典的NP問題，解決裝箱問題是設計分揀系統中的一個重要環節。針對裝箱問題的經典算法在研究過程中相繼涌現。解決裝箱問題的算法主要分為離線算法和在線算法。離線算法是指已知所有SKU的信息，提前計算出其分配序列，并根據此序列進行裝箱。在線算法是指根據SKU到達的順序，在保證固定數量箱子打開的情況下，對到達的物料進行裝箱操作。從理論的角度看，在線裝箱中所使用的算法在解決離線裝箱問題均同樣適用，但結合實際的業務生產過程，離線算法和在線算法各有優劣。

本文以某大型海外食品加工企業配送中心為研究案例，其客戶分為大型超市以及個體零售商兩種類型。這兩種客戶對于同一SKU需求的數量有著巨大差異。大型商超對同一SKU的需求數量大，一張訂單所涉及的SKU數量較少。而對于零售個體，其訂單需要SKU數量龐大，但每種SKU所需數量很小。在這種情況下，分揀策略的設計中使用離線裝箱還是在線裝箱，對分揀效率有著很大的影響。

對于貨到人系統訂單吞吐量以及設備利用率進行效率分析常用的方法是使用開環排隊模型對其進行建模。通過對排隊模型的分解可獲得各個環節的指標，可以實現對系統效率的估算，發現系統瓶頸，并有針對性的對系統進行優化，從而達到系統效率最大化。因此使用開環排隊網絡分析貨到人分揀系統是系統優化過程中重要的一個環節。

2 系統建模分析

2.1 建立系統模型

根據文獻[3]所闡述的使用排隊網絡對自動化系統建模的方法對本案例的自動化貨到人分揀系統進行建模。針對系統訂單可以隨時加入，每個子系統在繁忙狀態下，新的任務均需要加入其隊列進行等待的情況，本文使用開環排隊網絡對其業務場景進行建模，并基于該模型對系統整體效率進行分析。

建模基于如下若干條系統特征：

1）貨物的存儲方式為隨機存儲，倉儲區域沒有進行分區，貨物使用某貨位的概率為1/N（N為貨位的總數量，由巷道數*層數*列數*排數計算得出）。

2）訂單的所需SKU的貨位地址為隨機選擇。

3）設備的服務規則為先到先服務，即：先到達的庫存箱先對其進行相應的操作，后到達的庫存箱將會在其服務隊列中進行等待。

圖1 系統模型圖

4）堆垛機完成操作后的停止地點為上一條作業的目的地址。由于提升機為連續提升機，在一個隔板到達1層時，另一個隔板會自動到達2層，因此不需要考慮提升機系統的這一時間損耗。

5）堆垛機任務的到達時間滿足以λ為參數的泊松分布。

6）各堆垛機的在同一時間段只進行一種作業類型。

基于以上約束，針對該系統建立的模型如圖1所示，堆垛機任務的到達率服從以λ為參數的泊松分布。該模型包含三個子系統：雙工位miniload堆垛機系統，連續提升機系統和2對4模式下分揀工作臺系統。在堆垛機系統中，將到達該巷道的任務視為等待服務的顧客，miniload堆垛機作為服務者將完成將庫存箱送至輸送機的任務。在堆垛機子系統中，λis（i=1…7）標識第i個巷道的任務到達率，μiS（i=1…7）表示第i巷道堆垛機的服務率。基于貨位地址隨機分配的約束，任務由每臺miniload堆垛機執行的概率均為1/7，因此λis（i=1…7）的值為λ/7。輸送線將庫存箱送至連續提升機，提升機作為服務者為庫存箱提供服務。在模型中λT為連續提升機的任務到達率，其值應該為∑μiS（i=1…7），μT即為連續提升機系統的服務率。在分揀工位系統中，λjw（j=1…6）表示揀選工作臺系統的任務到達率。由于分揀工位相對于連續提升機的位置從1號工位到6號工位由近到遠的均勻排列，則各個工位的任務到達率與其距離成反比，由連續提升機只有一臺，故其任務到達率即為μT/（6*k）（k=1…6）。μkw（k=1…6）即為分揀站臺系統第k個工位的服務率。

2.2 系統模型分析

對于開環排隊網絡來說，求解的方式一般為將其拆分成若干M/M/1模型的子系統，并對子系統進行求解。通過式(1)可計算出每個子系統的隊列的平均隊列長度NQ。

其中ρ=λ/μ，λ表示各系統的任務到達率，μ表示各個系統的服務率。

由圖2可知，完整的分揀系統由堆垛機系統、連續提升機系統以及分揀站臺系統構成，因此完成對三個子系統求解，即可得到整個系統的解。根據上述對系統的劃分，訂單的等待時間為任務在各個系統中的等待時間以及執行時間的綜合，如式(2)所示。

在式(1)中，tod為訂單從到達到結束所需要的時間，tsw表示堆垛機系統的平均等待時間，tSE表示堆垛機系統任務的平均執行時間，tc1表示從miniload堆垛機到連續提升機的輸送時間，該時間為常量；tTW表示任務在連續提升機中的等待時間，tTE表示連續提升機執行任務的時間，tc2是連續提升機配送到分揀站臺的時間，該時間與分揀站臺與連續提升機之間的距離成正比；tPSW表示任務在分揀站臺的等待時間，tPSE表示任務在分揀站臺的執行時間。根據利特爾公式(3)，將使用式(1)求得的各系統隊列的平均長度以及其服務率和到達率代入式(3)中，即可求得個系統的平均等待時間。系統的平均執行時間由一定時間內的實際數據的平均值得出。

從以上模型可以看出，在堆垛機系統以及提升機系統達到最優效率的情況下，揀選工位的任務等待時間以及揀選任務的執行時間對系統效率有很大影響。而在實際的分揀業務場景下，揀選任務的揀選時間取決于工人的揀選速度，而等待時間取決于庫存箱命中率。因此系統在進行揀選方案的設計時，從提高庫存箱命中率出發，針對不同類型的物品，設計的裝箱策略有所不同。

3 分揀策略設計

在通過第一節中對其業務場景的描述可以將分揀過程中的會出現的任務場景劃分為兩種。第一種場景是針對大型商超。其要求訂單箱中均為同一種物料且不同訂單的物料不能放入相同的訂單箱。而且這種類型的客戶，每張訂單的需求數量較大，訂單箱幾乎沒有空箱。第二種場景針對小型的零散客戶。其訂單模式通常支持混裝，且需求的SKU中類型多單數量少，因此完成一個客戶箱所需的庫存箱數量較大。

從第二節中建立的訂單完成時間模型中可以看出，在決定訂單從到達到結束所需要的時間構成中，分揀工位的服務時間和任務等待時間起到很重要的因素。從上述兩種任務場景分析，在第一種業務場景中，tPSE分揀任務的執行時間對整個分揀系統的效率影響較大，而tPSW對系統效率影響較小；在第二種業務場景中，tPSW分揀任務的等待時間對整個分揀系統的效率影響較大，而tPSE對系統效率影響較小。在優化tPSE方面，可以通過改善包裝方式的方法進行。如針對采購的形式，將散裝的單個物料以一定數量為單元進行二次打包，這樣可以有效的縮短每次分揀的執行時間。在這種管理方式下，兩種場景中tPSE值的差異性大大縮小。解決了tPSE的差異性之后，分揀策略設計的目標將集中在縮短tPSW，也就是分揀系統的任務等待時間上。

在本案例中，貨到人分揀系統設備構成如圖2所示，6個貨到人揀選站臺，分為上層庫存箱輸送系統與下層訂單箱輸送系統，屬于二對四分揀方式。根據縮短tPSW的目標，針對上述兩種情況分別設計了離線計算動態綁定策略和在線計算裝箱策略。離線計算與在線計算為裝箱算法的兩種形式。在該項目案例中，某一SKU存放至相應客戶箱的數量，由相關部門提供并導入到系統中。

3.1 場景一分揀策略設計

在場景一中，由于訂單中對于某一物料的需求數量較大，通常情況下一個庫存箱所包含的數量可以滿足一至兩個訂單箱。因此采用離線計算的方式能夠消除在線計算所需要的時間。離線計算的步驟如圖3所示，系統根據訂單中的客戶信息找到相應的客戶箱。通過系統維護的訂單物料的基礎數據計算所需的客戶箱總數。根據客戶對物料不同的存儲日期的需要，篩選出滿足條件的庫存箱。根據訂單數量對該物料需求的數量，為每一訂單箱生成對應的唯一任務號，同時生成該訂單箱的揀選任務，并與庫存箱進行綁定。由于庫存箱到達分揀站臺的順序不定，為了避免增加不必要的周轉時間，當庫存箱到達分揀站臺后，再選擇相對應的分揀任務執行分揀作業，而不是在訂單箱到達之后就綁定其對應的分揀任務。這樣的綁定模式可以避免由于庫存箱到達順序的不確定性而導致的tPSW的增加。在計算分揀任務的時候，可能會出現由于零箱所導致的交叉連鎖效應，因此對于零頭箱在生成分揀作業的前需要進行匹配和規整計算。

圖3 場景一分揀策略流程圖

3.2 場景二分揀策略設計

圖4 場景二分揀策略流程圖

在場景二中，由于一個訂單箱的每個分揀任務通常需要最多高達10個左右的庫存箱，多箱周轉的情況勢必會發生。因此降低單箱周轉次數，保證每個庫存箱到達后即可揀選可有效降低tPSW的值。因此，在線裝箱算法更適合于該場景下的分揀任務。在線裝箱算法的流程如圖4所示。在這一階段，場景一與場景二有很大不同，場景二的分揀策略在這一階段不生成任何分揀任務，在完成匹配訂單箱型以及查詢存儲期限后，不進行訂單分解、生成分揀任務以及綁定庫存箱的操作只生成出庫任務。當庫存箱到達之后，根據訂單數量以及訂單箱容量計算揀選數量，生成分揀任務，綁定庫存箱，直到該訂單箱裝滿或者訂單分揀結束。在這種揀選模式下，可以達到使庫存箱到位即可分揀的效果。有效避免了庫存箱的無用周轉，降低了tPSW的值，從而使得訂單的開始時間和結束時間得以降低。

4 系統運行結果分析

針對以上業務場景，本文設計了兩組對照試驗，證明上述兩種優化的方案對于縮短分揀過程中tPSW確實有效。場景一與場景二的試驗中使用本案例中的某大型商超客戶的6張訂單，6張訂單中所需的物料沒有交叉，以排除由于物料交叉對料箱到達時間造成的影響。

場景一的訂單結構如下表所示。由表中可以看出，這一組訂單的特點為SKU需求的數目均在5～8種之間，需求量平均值反映了這一組訂單對于每一種物料的需求數目相對較集中。這一組訂單滿足業務場景一所描述的特征與場景一相符合。對照組使用的分揀策略為客戶箱到達即綁定分揀任務這樣一種離線裝箱策略。在本次分揀過程中，6個分揀工位分別綁定6張訂單，分揀過程同時啟動。

表1 場景一分揀效率對照表

通過對比數據可以看出，對照組的分揀時間明顯大于實際的訂單執行時間。結果說明，基于庫存箱的動態綁定策略效果優于基于訂單箱的綁定策略。

場景二選取得訂單結構入下表。從表2可以看出，場景二的訂單類的基本特征為SKU數量龐大且每一種SKU的數量很小，訂單結構比較分散。對照組使用離線的分揀策略，即在訂單開始分揀前即確定每一訂單箱中所需分揀的物料及數量。本次分揀過程與場景一致，6個工位分別綁定6張訂單，分揀過程同時啟動。

表2 場景二分揀效率對照表

通過對比數據可以看出，對照組的分揀時間明顯大于實際的訂單執行時間。結果說明，針對場景二，在線裝箱的分揀策略明顯優于離線的分揀策略。

兩種分揀策略通過在項目案例現場的實際應用，提高分揀效率在20%以上，縮短了訂單的處理時間，提高了分揀訂單量。

5 結語

本文運用了開環排隊模型，對實際的項目方案進行建模。通過對模型進行分析，確定軟件設計過程中系統的優化方向集中在縮短tPSw上。在確定業務場景后，本文提出了兩種不同優化策略。從數據中可以看出，針對場景一，本文提出的離線計算動態綁定策略相比針對基于客戶箱對訂單進行綁定的策略能夠有效縮短分揀任務的等待時間；針對場景二所使用的在線裝箱策略同樣達到了降低tPSw的效果。該項目實際投產使用超過一年的時間，分揀訂單數量近4萬，項目的實際運行情況也證明了以上兩種策略切實有效的提高了分揀效率，縮短了訂單的流轉周期，為相同業務場景下的分揀策略設計提供了思路。