考慮倒箱的Auto Store倉儲揀選系統(tǒng)提箱作業(yè)優(yōu)化

師浩森,陳航慧,王 皓,王曉軍,楊春霞

(太原科技大學 交通與物流學院,太原 030024)

Auto Store是一種貨到人的拆零揀選系統(tǒng),該系統(tǒng)將密集倉儲系統(tǒng)與AGV進行整合,致力于實現(xiàn)高密度存儲與高效率揀選的完美融合,如圖1所示。雖然Auto Store的優(yōu)越性顯而易見,但該系統(tǒng)在進行提箱作業(yè)時,會涉及料箱的倒箱作業(yè),進而導(dǎo)致倉庫作業(yè)效率的降低。

圖1 頂層移動示意圖Fig.1 Schematic diagram of top floor movement

目前,國內(nèi)對于Auto Store的研究還處于起步階段,關(guān)于Auto Store的學術(shù)研究成果較少。簡素萍等[1]提出了將存儲貨架從中間分為上下兩部分的建議,達到提高Auto Store的存取作業(yè)效率的目的;王金龍等[2]使用隨機存儲策略,推導(dǎo)出了服務(wù)強度與料箱填充率之間的關(guān)系表達式。王曉軍等[3]提出了基于改進A*算法的路徑規(guī)劃和基于貪心算法的區(qū)域避碰決策,該方法能有效縮短整體作業(yè)完成時間。M.B.M.deKoster等[4]發(fā)現(xiàn)專用存儲策略效率更高,但儲位成本也隨之增高,易出現(xiàn)儲位浪費的情況。綜合Auto Store的國內(nèi)外的研究現(xiàn)狀來看,目前已發(fā)表的論文中都未考慮Auto Store中提箱作業(yè)的優(yōu)化問題,因此對該問題的研究存在很大空間,但同時也意味著沒有文獻可供參考。因Auto Store的提箱作業(yè)問題與集裝箱的提箱作業(yè)比較類似,因此在建模方面,本文將主要參考集裝箱的倒箱作業(yè)及箱位指派相關(guān)的文獻。

在集裝箱倒箱作業(yè)方面,劉志雄等[5]建立了一個多貝位下以堆場貝位和船舶貝位翻箱次數(shù)之和最小的優(yōu)化模型。郭文文等[6]建立了一個單貝位下以最短場橋總作業(yè)時間的數(shù)學模型。在集裝箱箱位指派方面,鄭紅星等[7]建立了一個箱區(qū)間作業(yè)量均衡的多目標整數(shù)規(guī)劃模型。高鵬等[8]建立了一個兩層嵌套的組合優(yōu)化模型,分別針對提箱訂單和倒箱作業(yè)成本最小的移動路徑實現(xiàn)倒箱優(yōu)化。綜合集裝箱倒箱[9-11]和箱位指派[12]的研究現(xiàn)狀,可以看出其主流方向是通過減少倒箱次數(shù)來降低倒箱作業(yè)的影響,對于Auto Store的倒箱作業(yè)來說,不能通過減少倒箱次數(shù)來優(yōu)化倒箱作業(yè),但可以通過優(yōu)化倒箱作業(yè)流程來減少倒箱作業(yè)時間。

本文主要研究在考慮倒箱路徑的情況下Auto Store的揀選提箱作業(yè)的作業(yè)效率,提出一種專門適用于Auto Store的倒箱策略,達到通過優(yōu)化倒箱作業(yè)流程來減少揀選提箱作業(yè)的作業(yè)時間的目的,最后通過與理論倒箱策略下界的比較分析來驗證該策略的有效性。

1 問題描述

在提箱作業(yè)中,需要被取出的貨物所在的料箱稱為待提箱。由于Auto Store中料箱的堆存狀態(tài)和揀選車的作業(yè)能力限制,為取出待提箱,常常需要將其上方的料箱移走,這類料箱稱為待倒箱,待倒箱移動的目標位置稱為待倒箱的落箱位,而移動待倒箱的作業(yè)流程稱為倒箱作業(yè)。以下依次對Auto Store系統(tǒng),倒箱作業(yè)規(guī)則以及提箱作業(yè)過程進行描述。

1.1 Auto Store系統(tǒng)

Auto Store系統(tǒng)在布局上由若干個存儲柱構(gòu)成,每個存儲柱由若干個貨格組成,每個料箱所在的位置均由X,Y,Z三維坐標構(gòu)成,料箱本身具有編號編碼,貨物的位置由貨物所在料箱的編號和其所在位置的三維坐標對應(yīng)確認,且一個料箱只存放一類貨物,因此Auto Store系統(tǒng)的堆放狀態(tài)時常處于變化中,需要對其堆存狀態(tài)進行實時監(jiān)測。

設(shè)整個Auto Store系統(tǒng)的堆存狀態(tài)集合為S,S中任意一個貨格si的位置坐標由一個三元組表示,記為si=(Xsi,Ysi,Zsi),因此Auto Store系統(tǒng)的堆存狀態(tài)S可以表示為:

(1)

式中:Xmax,Ymax,Zmax是該Auto Store系統(tǒng)中行、列、層的最大值。作業(yè)期間Auto Store系統(tǒng)的堆存狀態(tài)S是實時監(jiān)測的,即是已知的。

1.2 倒箱作業(yè)規(guī)則

在提箱作業(yè)中倒箱時,需要遵循以下幾個規(guī)則。

規(guī)則1:落箱位需在可存儲范圍內(nèi)選擇。

因存在貨格已滿或工作臺設(shè)置等其他因素導(dǎo)致不能進行倒箱作業(yè)的情況,所以需設(shè)定可存儲范圍來限制落箱位的選擇。vijk表示待提箱gi上第j個待倒箱的第k個落箱位的落箱位置,記vijk=(Xvijk,Yvijk,Zvijk).定義所有待倒箱的落箱位對應(yīng)的平面坐標集合為W,記W={wi}.則:

(Xvijk,Yvijk)∈W

(2)

規(guī)則2:待倒箱的落箱位必須為空,且當落箱位不在第一層時,其下方相鄰箱位不為空。

則當落箱位在第一層時,

θ((Xvijk,Yvijk,Zvijk))=0,Zvijk=1

(3)

當落箱位不在第一層時,

θ((Xvijk,Yvijk,Zvijk))=0,

θ((Xvijk,Yvijk,Zvijk-1))=1,Zvijk≥2

(4)

規(guī)則3:最大堆存高度限制。

倒箱作業(yè)過程中,待倒箱的落箱位所在的存儲柱堆積高度需小于最大可堆存高度。

Zvijk≤Zmax

(5)

1.3 提箱作業(yè)過程

在提箱作業(yè)過程中,需首先確定待提箱集合G,其次對于某個待提箱確定其待倒箱集合U,對于某個待倒箱確定其落箱位集合V,所有待倒箱的落箱位對應(yīng)的平面坐標集合,最后依次確定所有待倒箱的最短倒箱作業(yè)時間,進而確定最短提箱作業(yè)時間。

本文只考慮單個訂單內(nèi)的提箱作業(yè),一個訂單中包含多種商品,且提箱順序根據(jù)訂單順序確定。

設(shè)某一訂單內(nèi),存在a種商品,定義所有待提箱為集合G.

G={g1,g2,g3,…,gi,…,ga},i=1,2,…a

(6)

式中:a表示該訂單內(nèi)的商品個數(shù),gi表示提箱作業(yè)過程中待提箱的初始位置,記gi=(Xgi,Ygi,Zgi).

對于待提箱gi上,存在bi個待倒箱,定義所有待倒箱為集合U.

U={ui1,ui2,ui3,…,uij,…,uibi},j=1,2,…bi

(7)

式中:bi表示待提箱gi上的待倒箱的個數(shù),uij表示待提箱gi上第j個待倒箱在堆場中的初始位置,記uij=(Xuij,Yuij,Zuij).

對于待倒箱uij,存在cij個可放置的落箱位,定義所有落箱位為集合V.

V={vij1,vij2,…,vijk,…,vijcij},k=1,2,…cij

(8)

式中:cij表示待倒箱uij的可選擇的落箱位個數(shù),vijk表示待提箱gi上第j個待倒箱的第k個落箱位的位置,記vijk=(Xvijk,Yvijk,Zvijk).

將整個Auto Store系統(tǒng)分為四個集合,用以確定倒箱作業(yè)的作業(yè)范圍以及可作業(yè)坐標,分別是以待提箱gi為中心向外水平擴展w距離的平面坐標集合wi0,α,β為偏離待提箱坐標的行列數(shù)。

(9)

w中待提箱gi,設(shè)以下平面坐標集合:貨格已滿不能進行倒箱的集合wi1;因工作臺設(shè)置等其他因素導(dǎo)致不能倒箱的集合wi2;可選擇的落箱位的集合wi.

則所有待倒箱的可選擇落箱位對應(yīng)的平面坐標集合W為:

W={wi|wi=wi0-wi1-wi2}

(10)

2 揀選作業(yè)數(shù)學模型

2.1 模型假設(shè)

1)只考慮取貨環(huán)節(jié);

2)只考慮一個揀選車;

3)揀選車移動速度為勻速,即不考慮重量影響;

4)只考慮單個訂單內(nèi)的取貨;

5)設(shè)倉庫底層左上方的貨格為原點坐標(1,1,1);

6)倉庫堆存狀態(tài)和貨物位置已知。

2.2 模型符號與決策變量

2.2.1 符號定義

tl——揀選車水平方向移動單位距離所用時間;

td——揀選車垂直方向移動單位距離所用時間;

tc——揀選車水平方向每次轉(zhuǎn)向所用時間;

tbi——待提箱gi上存在bi個待倒箱時的提箱作業(yè)時間;

o=(Xo,Yo)——揀選車o所在初始位置;

e=(Xe,Ye)——Auto Store系統(tǒng)的出口所在位置;

(pijk,qijk)——將待倒箱uij搬運到其可選擇的落箱位vijk所行走的水平和垂直距離;

Dij——將待倒箱uij搬運到其可選擇的落箱位vijk所行走的水平與垂直距離的集合;

tuij——將待倒箱uij搬運到其可選擇的落箱位vijk的倒箱作業(yè)時間。

2.2.2 決策變量

2.3 模型建立

根據(jù)待提箱位于Auto Store系統(tǒng)的位置,可分為兩種情況,分別是待倒箱個數(shù)為0和待倒箱個數(shù)為j(j=1,2…,bi),計算提箱作業(yè)的時間。

當待提箱gi存在0個待倒箱時,提箱作業(yè)時間為:

t0=(|Xgi-Xo|+|Ygi-Yo|)·tl+

2(Zmax-Zgi+1)·td+

|Xgi-Xe|+|Ygi-Ye|)·tl+2Zmax

(11)

當待提箱gi上存在bi個待倒箱時,提箱作業(yè)時間為:

tbi=(|Xgi-Xo|+|Ygi-Yo|)·tl+

2(Zmax-Zgi+1)·td+(|Xgi-Xe|+|Ygi-Ye|)·

tl+2Zmax

(12)

綜上所述,本文建立以單訂單內(nèi)最短提箱作業(yè)時間為目標的數(shù)學模型:

(13)

待倒箱落箱位選擇的范圍約束為:

(14)

W={wi|wi=wi0-wi1-wi2}

(15)

(Xvijk,Yvijk)∈W

(16)

待倒箱的落箱位選擇的時間約束

Dij=

(17)

(18)

待倒箱落箱位不能懸空放置的約束為:

(ⅰ)當落箱位在第一層時:

θ((Xvijk,Yvijk,Zvijk))=0

(19)

Zvijk=1

(20)

(ⅱ)當落箱位不在第一層時:

θ((Xvijk,Yvijk,Zvijk))=0

(21)

((Xvijk,Yvijk,Zvijk-1))=1

(22)

Zvijk≥2

(23)

每個存儲柱的存儲高度要小于最高可堆存高度的約束為:

Zvijk≤Zmax

(24)

每個箱位至多被1個存儲箱占用的約束為:

θ(si)≤1,si∈S

(25)

決策變量均為0-1變量,即

θ(si)∈{0,1}

(26)

η(o)∈{0,1}

(27)

λ(bi)∈{0,1}

(28)

3 啟發(fā)式算法設(shè)計

3.1 算法原理

本數(shù)學模型可以看做是一個外層模型與一個內(nèi)層模型嵌套的雙層模型,在求解過程中,將內(nèi)層模型的運行結(jié)果作為外層模型的已知條件進行運算。內(nèi)層模型用來求解每個待倒箱uij的最優(yōu)落箱位vijk的三維坐標;外層模型將內(nèi)層模型的計算結(jié)果作為已知條件,求出訂單內(nèi)每個商品的最短提箱作業(yè)時間,最后求出單個訂單內(nèi)所有商品的最短總提箱作業(yè)時間[13]。

3.2 算法步驟

4 算例分析與比較

4.1 算例求解

基于上述算法,以10個商品的單訂單為例,Auto Store系統(tǒng)的倉庫模型的形狀為方形,大小為20*20*8,使用隨機數(shù)作為Auto Store系統(tǒng)的倉庫的存儲情況,根據(jù)王金龍所得到的Auto Store系統(tǒng)的料箱填充率和服務(wù)強度之間的關(guān)系,通過Excel生成4至8的隨機數(shù),其料箱填充率約為74%,其中w=3;o=(1,1);tl=1;td=1;tc=2.

表1為單訂單內(nèi)商品在Auto Store系統(tǒng)的倉庫模型的所在三維坐標,其所在行列層均為隨機生成,根據(jù)其現(xiàn)存料箱數(shù),可得到每個商品的需倒箱次數(shù),通過算法設(shè)計,排除了二次倒箱的影響。

表1 單訂單內(nèi)商品在Auto Store系統(tǒng)中的坐標Tab.1 Coordinates of goods in single order in auto store system

表2為每個商品的倒箱作業(yè)時間以及直提作業(yè)時間,可以看出該訂單內(nèi)的10個商品的總倒箱作業(yè)時間為286,總直提作業(yè)時間為566,即完成該訂單的總時間為852.

表2 啟發(fā)算法下的倒箱及直提時間Tab.2 Time of dumping and lifting based on heuristic algorithm

4.2 下界分析

為了驗證所提出的模型有效性,計算理論上的下界是必不可少的,通過分析,可知不同的倒箱作業(yè)規(guī)則會則對倒箱作業(yè)時間影響較大。因此,為縮短倒箱作業(yè)時間,必須優(yōu)化倒箱作業(yè)流程,提高倒箱作業(yè)的效率。因此,本文計算了通過就近原則進行倒箱作業(yè)的倒箱作業(yè)時間,以此為下界,驗證算例的有效性,結(jié)果如表3所示。

表3 理論下界的倒箱及直提時間Tab.3 The time of dumping and lifting in theory lower bound

具體的下界約束及求解過程如下所示:

(1)確定訂單商品的位置。首先按照訂單順序,確定訂單商品的有關(guān)信息。

(2)進行倒箱作業(yè)。倒箱規(guī)則如下:待倒箱的落箱位選擇范圍為w=3,落箱位優(yōu)先選擇所存料箱最少的存儲柱內(nèi),以保持整個倉庫的存儲均衡;同時為了減少不必要的倒箱作業(yè)時間,本文只考慮與X,Y方向平行的存儲柱,避免因轉(zhuǎn)彎導(dǎo)致倒箱時間增加的情況。

(3)進行出庫作業(yè)。

(4)計算提箱作業(yè)時間。將倒箱作業(yè)時間與直提作業(yè)時間求和便得到提箱作業(yè)時間。

4.3 算法比較

利用Excel軟件進行計算,為驗證算法的有效性,本文通過隨機生成的Auto Store系統(tǒng)的倉庫模型以及訂單信息,采用啟發(fā)式算法求解,將優(yōu)化模型與理論下界進行比較分析,結(jié)果如表4所示。

表4 啟發(fā)式算法和下界比較Tab.4 Heuristic algorithm and lower bound comparison

可以看出,啟發(fā)式算法下的倒箱作業(yè)時間比理論下界有所降低,單訂單內(nèi)的總優(yōu)化效果約為27.4%,平均每個商品的優(yōu)化效果達到了約30.6%,這主要是由于倒箱作業(yè)規(guī)則的不同導(dǎo)致不同倒箱量的產(chǎn)生,表明倒箱作業(yè)規(guī)則對取箱作業(yè)效率影響較大。因此,需要通過對倒箱作業(yè)規(guī)則的優(yōu)化以達到提高取箱作業(yè)效率的目的。

5 結(jié)論

Auto Store倉儲系統(tǒng)的提箱作業(yè)優(yōu)化的重要目標之一是提高其提箱作業(yè)效率。本文在已知Auto Store倉儲系統(tǒng)的料箱存儲狀態(tài)及訂單商品的前提下,研究Auto Store倉儲系統(tǒng)的提箱作業(yè)優(yōu)化問題,以作業(yè)時間來衡量作業(yè)效率的高低,建立了以最短提箱作業(yè)時間為目標的數(shù)學模型,設(shè)計啟發(fā)式算法對模型進行求解,分析了Auto Store倉儲系統(tǒng)的倒箱作業(yè)下界,并通過算例實驗對該問題進行討論。算例結(jié)果表示,Auto Store倉儲系統(tǒng)在該啟發(fā)式算法下的倒箱作業(yè)時間與理論下界相比,減少了約27.4%,較好的驗證了算法和模型的有效性,為Auto Store倉儲系統(tǒng)的倒箱作業(yè)優(yōu)化提供了理論依據(jù)。