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

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

0 引言

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

貨到人系統(tǒng)主要由三個(gè)部分組成，分別是存儲系統(tǒng)、配送系統(tǒng)以及分揀系統(tǒng)。存儲系統(tǒng)的研究重點(diǎn)在于如何根據(jù)SKU使用的頻率合理安排其存儲區(qū)域，從而達(dá)到出庫頻次最高的SKU出庫時(shí)間最短的目標(biāo)。在配送系統(tǒng)中，從庫端到達(dá)分揀站臺的最短路徑以及流量控制等問題一直是業(yè)界所關(guān)注的重點(diǎn)。而對于貨到人分揀系統(tǒng)，針對分揀策略的研究相對較少。而對于整個(gè)系統(tǒng)效率而言，分揀策略的優(yōu)劣，直接關(guān)系到系統(tǒng)整體的運(yùn)行效率。

1 背景介紹

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

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

對于貨到人系統(tǒng)訂單吞吐量以及設(shè)備利用率進(jìn)行效率分析常用的方法是使用開環(huán)排隊(duì)模型對其進(jìn)行建模。通過對排隊(duì)模型的分解可獲得各個(gè)環(huán)節(jié)的指標(biāo)，可以實(shí)現(xiàn)對系統(tǒng)效率的估算，發(fā)現(xiàn)系統(tǒng)瓶頸，并有針對性的對系統(tǒng)進(jìn)行優(yōu)化，從而達(dá)到系統(tǒng)效率最大化。因此使用開環(huán)排隊(duì)網(wǎng)絡(luò)分析貨到人分揀系統(tǒng)是系統(tǒng)優(yōu)化過程中重要的一個(gè)環(huán)節(jié)。

2 系統(tǒng)建模分析

2.1 建立系統(tǒng)模型

根據(jù)文獻(xiàn)[3]所闡述的使用排隊(duì)網(wǎng)絡(luò)對自動化系統(tǒng)建模的方法對本案例的自動化貨到人分揀系統(tǒng)進(jìn)行建模。針對系統(tǒng)訂單可以隨時(shí)加入，每個(gè)子系統(tǒng)在繁忙狀態(tài)下，新的任務(wù)均需要加入其隊(duì)列進(jìn)行等待的情況，本文使用開環(huán)排隊(duì)網(wǎng)絡(luò)對其業(yè)務(wù)場景進(jìn)行建模，并基于該模型對系統(tǒng)整體效率進(jìn)行分析。

建模基于如下若干條系統(tǒng)特征：

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

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

3）設(shè)備的服務(wù)規(guī)則為先到先服務(wù)，即：先到達(dá)的庫存箱先對其進(jìn)行相應(yīng)的操作，后到達(dá)的庫存箱將會在其服務(wù)隊(duì)列中進(jìn)行等待。

圖1 系統(tǒng)模型圖

4）堆垛機(jī)完成操作后的停止地點(diǎn)為上一條作業(yè)的目的地址。由于提升機(jī)為連續(xù)提升機(jī)，在一個(gè)隔板到達(dá)1層時(shí)，另一個(gè)隔板會自動到達(dá)2層，因此不需要考慮提升機(jī)系統(tǒng)的這一時(shí)間損耗。

5）堆垛機(jī)任務(wù)的到達(dá)時(shí)間滿足以λ為參數(shù)的泊松分布。

6）各堆垛機(jī)的在同一時(shí)間段只進(jìn)行一種作業(yè)類型。

基于以上約束，針對該系統(tǒng)建立的模型如圖1所示，堆垛機(jī)任務(wù)的到達(dá)率服從以λ為參數(shù)的泊松分布。該模型包含三個(gè)子系統(tǒng)：雙工位miniload堆垛機(jī)系統(tǒng)，連續(xù)提升機(jī)系統(tǒng)和2對4模式下分揀工作臺系統(tǒng)。在堆垛機(jī)系統(tǒng)中，將到達(dá)該巷道的任務(wù)視為等待服務(wù)的顧客，miniload堆垛機(jī)作為服務(wù)者將完成將庫存箱送至輸送機(jī)的任務(wù)。在堆垛機(jī)子系統(tǒng)中，λis（i=1…7）標(biāo)識第i個(gè)巷道的任務(wù)到達(dá)率，μiS（i=1…7）表示第i巷道堆垛機(jī)的服務(wù)率?；谪浳坏刂冯S機(jī)分配的約束，任務(wù)由每臺miniload堆垛機(jī)執(zhí)行的概率均為1/7，因此λis（i=1…7）的值為λ/7。輸送線將庫存箱送至連續(xù)提升機(jī)，提升機(jī)作為服務(wù)者為庫存箱提供服務(wù)。在模型中λT為連續(xù)提升機(jī)的任務(wù)到達(dá)率，其值應(yīng)該為∑μiS（i=1…7），μT即為連續(xù)提升機(jī)系統(tǒng)的服務(wù)率。在分揀工位系統(tǒng)中，λjw（j=1…6）表示揀選工作臺系統(tǒng)的任務(wù)到達(dá)率。由于分揀工位相對于連續(xù)提升機(jī)的位置從1號工位到6號工位由近到遠(yuǎn)的均勻排列，則各個(gè)工位的任務(wù)到達(dá)率與其距離成反比，由連續(xù)提升機(jī)只有一臺，故其任務(wù)到達(dá)率即為μT/（6*k）（k=1…6）。μkw（k=1…6）即為分揀站臺系統(tǒng)第k個(gè)工位的服務(wù)率。

2.2 系統(tǒng)模型分析

對于開環(huán)排隊(duì)網(wǎng)絡(luò)來說，求解的方式一般為將其拆分成若干M/M/1模型的子系統(tǒng)，并對子系統(tǒng)進(jìn)行求解。通過式(1)可計(jì)算出每個(gè)子系統(tǒng)的隊(duì)列的平均隊(duì)列長度NQ。

其中ρ=λ/μ，λ表示各系統(tǒng)的任務(wù)到達(dá)率，μ表示各個(gè)系統(tǒng)的服務(wù)率。

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

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

從以上模型可以看出，在堆垛機(jī)系統(tǒng)以及提升機(jī)系統(tǒng)達(dá)到最優(yōu)效率的情況下，揀選工位的任務(wù)等待時(shí)間以及揀選任務(wù)的執(zhí)行時(shí)間對系統(tǒng)效率有很大影響。而在實(shí)際的分揀業(yè)務(wù)場景下，揀選任務(wù)的揀選時(shí)間取決于工人的揀選速度，而等待時(shí)間取決于庫存箱命中率。因此系統(tǒng)在進(jìn)行揀選方案的設(shè)計(jì)時(shí)，從提高庫存箱命中率出發(fā)，針對不同類型的物品，設(shè)計(jì)的裝箱策略有所不同。

3 分揀策略設(shè)計(jì)

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

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

在本案例中，貨到人分揀系統(tǒng)設(shè)備構(gòu)成如圖2所示，6個(gè)貨到人揀選站臺，分為上層庫存箱輸送系統(tǒng)與下層訂單箱輸送系統(tǒng)，屬于二對四分揀方式。根據(jù)縮短tPSW的目標(biāo)，針對上述兩種情況分別設(shè)計(jì)了離線計(jì)算動態(tài)綁定策略和在線計(jì)算裝箱策略。離線計(jì)算與在線計(jì)算為裝箱算法的兩種形式。在該項(xiàng)目案例中，某一SKU存放至相應(yīng)客戶箱的數(shù)量，由相關(guān)部門提供并導(dǎo)入到系統(tǒng)中。

3.1 場景一分揀策略設(shè)計(jì)

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

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

3.2 場景二分揀策略設(shè)計(jì)

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

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

4 系統(tǒng)運(yùn)行結(jié)果分析

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

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

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

通過對比數(shù)據(jù)可以看出，對照組的分揀時(shí)間明顯大于實(shí)際的訂單執(zhí)行時(shí)間。結(jié)果說明，基于庫存箱的動態(tài)綁定策略效果優(yōu)于基于訂單箱的綁定策略。

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

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

通過對比數(shù)據(jù)可以看出，對照組的分揀時(shí)間明顯大于實(shí)際的訂單執(zhí)行時(shí)間。結(jié)果說明，針對場景二，在線裝箱的分揀策略明顯優(yōu)于離線的分揀策略。

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

5 結(jié)語

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