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

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

0 引言

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

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

1 背景介紹

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

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

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

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

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

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

建?；谌缦氯舾蓷l系統(tǒng)特征：

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

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

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

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

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

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

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

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

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

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

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

由圖2可知，完整的分揀系統(tǒng)由堆垛機(jī)系統(tǒng)、連續(xù)提升機(jī)系統(tǒng)以及分揀站臺(tái)系統(tǒng)構(gòu)成，因此完成對(duì)三個(gè)子系統(tǒng)求解，即可得到整個(gè)系統(tǒng)的解。根據(jù)上述對(duì)系統(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ī)配送到分揀站臺(tái)的時(shí)間，該時(shí)間與分揀站臺(tái)與連續(xù)提升機(jī)之間的距離成正比；tPSW表示任務(wù)在分揀站臺(tái)的等待時(shí)間，tPSE表示任務(wù)在分揀站臺(tái)的執(zhí)行時(shí)間。根據(jù)利特爾公式(3)，將使用式(1)求得的各系統(tǒng)隊(duì)列的平均長(zhǎng)度以及其服務(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í)間對(duì)系統(tǒng)效率有很大影響。而在實(shí)際的分揀業(yè)務(wù)場(chǎng)景下，揀選任務(wù)的揀選時(shí)間取決于工人的揀選速度，而等待時(shí)間取決于庫(kù)存箱命中率。因此系統(tǒng)在進(jìn)行揀選方案的設(shè)計(jì)時(shí)，從提高庫(kù)存箱命中率出發(fā)，針對(duì)不同類型的物品，設(shè)計(jì)的裝箱策略有所不同。

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

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

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

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

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

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

圖3 場(chǎng)景一分揀策略流程圖

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

圖4 場(chǎng)景二分揀策略流程圖

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

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

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

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

表1 場(chǎng)景一分揀效率對(duì)照表

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

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

表2 場(chǎng)景二分揀效率對(duì)照表

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

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

5 結(jié)語(yǔ)

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