自動(dòng)化立體倉庫出入庫路徑優(yōu)化研究

李媛媛，鄭 孟 （蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070）

自動(dòng)化立體倉庫系統(tǒng)，是由高層立體貨架、堆垛機(jī)、輸送系統(tǒng)、信息識(shí)別系統(tǒng)、計(jì)算機(jī)控制系統(tǒng)、通信系統(tǒng)、監(jiān)控系統(tǒng)、管理系統(tǒng)等組成的自動(dòng)化系統(tǒng)，可持續(xù)地檢查過期或查找?guī)齑娴漠a(chǎn)品，防止不良庫存，提高管理水平。

倉庫的出入庫效率直接影響到整個(gè)物流系統(tǒng)的效率，因此出入庫路徑的優(yōu)化就成為提高整個(gè)物流系統(tǒng)效率的關(guān)鍵問題，出入庫通過堆垛機(jī)的揀選作業(yè)來完成，解決堆垛機(jī)行駛路徑優(yōu)化問題是提高自動(dòng)化倉庫運(yùn)行效益的有效手段。本文根據(jù)自動(dòng)化立體倉庫的作業(yè)特點(diǎn)建造了數(shù)學(xué)模型，使用近似動(dòng)態(tài)規(guī)劃進(jìn)行了求解,并通過仿真程序證實(shí)了算法的有效性。

朱文真[1]、鄭歡[2]、劉巍巍[3]等人都曾在自己的文章中針對(duì)倉庫出入庫路徑優(yōu)化問題建立了相關(guān)模型并采用相應(yīng)算法進(jìn)行求解，求解算法多為遺傳算法、禁忌算法、蟻群算法等現(xiàn)代啟發(fā)式算法，在收斂性、最優(yōu)解及求解速度上各有千秋。本文針對(duì)此問題使用了近似動(dòng)態(tài)規(guī)劃算法（Approximate Dynamic Programming，ADP） 來進(jìn)行求解。ADP由美國普林斯頓大學(xué)的數(shù)學(xué)家Powell[4]教授提出，相較于動(dòng)態(tài)規(guī)劃方法，ADP利用近似結(jié)構(gòu)逼近DP方法中精確計(jì)算值函數(shù)的過程，可徹底解決動(dòng)態(tài)規(guī)劃的“維數(shù)災(zāi)”問題。

1 問題分析

倉庫調(diào)度優(yōu)化問題的核心是揀選作業(yè)的優(yōu)化調(diào)度問題，揀選作業(yè)是由堆垛機(jī)來完成的。因此，從本質(zhì)上來講，倉庫調(diào)度實(shí)際上就是堆垛機(jī)調(diào)度。堆垛機(jī)是立體倉庫中的一種貨物輸送車輛，能夠沿著規(guī)定的路線行駛，將貨物送到指定的地方。存儲(chǔ)貨物時(shí)，由巷道堆垛機(jī)將暫時(shí)存在入庫臺(tái)的貨物搬運(yùn)到目的位置；取出貨物時(shí)，需要堆垛機(jī)將貨物從存儲(chǔ)貨架搬運(yùn)到巷道口，暫時(shí)存放在出庫臺(tái)等待后續(xù)操作。在實(shí)際生產(chǎn)中，倉庫的主要作業(yè)就是存取作業(yè)，任務(wù)非常繁重，通過多臺(tái)堆垛機(jī)并行、高速工作以滿足揀選任務(wù)要求。由于作業(yè)任務(wù)量大，工作過程復(fù)雜，如果對(duì)倉庫系統(tǒng)調(diào)度不合理，就會(huì)出現(xiàn)貨物擁擠堵塞現(xiàn)象，影響了貨物周轉(zhuǎn)率，降低了立體倉庫整體工作效率。因此當(dāng)倉庫中有成批貨物進(jìn)行出入庫作業(yè)時(shí)，對(duì)倉庫系統(tǒng)的調(diào)度就顯得特別重要。

一批生產(chǎn)任務(wù)中，通常包含若干個(gè)入庫任務(wù)和出庫任務(wù)，堆垛機(jī)出入庫作業(yè)有單一作業(yè)（單一入庫作業(yè)、單一出庫作業(yè)）和復(fù)合作業(yè)兩種。多數(shù)研究表明，復(fù)合作業(yè)相比起單一作業(yè)更有效率[5]，即通過將一個(gè)入庫任務(wù)和出庫任務(wù)配對(duì)執(zhí)行來提高整體的運(yùn)行效率。如圖1所示，假設(shè)O點(diǎn)為堆垛機(jī)運(yùn)行起始點(diǎn)，此時(shí)A要進(jìn)行入庫作業(yè)，B進(jìn)行出庫作業(yè)，若只進(jìn)行單一作業(yè)，則堆垛機(jī)行駛的時(shí)間t單=2tOA+2tOB，而完成相同的任務(wù)，進(jìn)行復(fù)合作業(yè)的時(shí)間為t復(fù)=tOA+tAB+tOB。可以看出，復(fù)合作業(yè)比單一作業(yè)運(yùn)行時(shí)間更少，效率更高。

圖1 單一作業(yè)與復(fù)合作業(yè)

通過對(duì)復(fù)合作業(yè)中堆垛機(jī)運(yùn)行情況的觀察，每次任務(wù)所消耗的時(shí)間主要由以下3部分組成[3]：（1）負(fù)載運(yùn)行時(shí)間，即堆垛機(jī)承載托盤行進(jìn)所花費(fèi)的時(shí)間（如tOA和tOB）；

（2）空載運(yùn)行時(shí)間，堆垛機(jī)在沒有承重的情況下行進(jìn)所花費(fèi)的時(shí)間（如tAB）；

（3）取/放貨時(shí)間，堆垛機(jī)在貨架和貨臺(tái)取放托盤時(shí)所花費(fèi)的時(shí)間。

在以上3部分中，堆垛機(jī)負(fù)載運(yùn)行的時(shí)間和取/放貨時(shí)間都是固定的，所以此路徑優(yōu)化問題是通過對(duì)堆垛機(jī)的任務(wù)隊(duì)列進(jìn)行合理排序，減少堆垛機(jī)的空載運(yùn)行時(shí)間來降低完成所有任務(wù)的總時(shí)間。

堆垛機(jī)每一次的復(fù)合作業(yè)可以簡化理解為非對(duì)稱TSP問題，TSP屬于一種典型的組合優(yōu)化問題，描述為在給定了n個(gè)點(diǎn)，要求從任一個(gè)位置出發(fā)，經(jīng)歷所有的點(diǎn)，最后回到出發(fā)的位置，且所經(jīng)歷的路徑最短。定義兩點(diǎn)i和j之間的距離為dij，非對(duì)稱TSP問題即使dij≠dji，優(yōu)化目標(biāo)為路徑S=dij+djk+…+dmn。一批生產(chǎn)任務(wù)中的取送作業(yè)是由多次復(fù)合作業(yè)和單一作業(yè)組成，每一次復(fù)合作業(yè)都可看成一個(gè)小的非對(duì)稱TSP問題，通過對(duì)復(fù)合作業(yè)的組合排列達(dá)到倉庫路徑優(yōu)化的目的。模型以優(yōu)化最小化時(shí)間為主，優(yōu)化的是堆垛機(jī)的空載時(shí)間。

目前市場上最常見的是貨叉式單立柱堆垛機(jī)，適用于存取托盤型貨物，堆垛機(jī)在巷道中的一次穿梭只能完成一個(gè)貨物的存或取[6]。為了方便后續(xù)計(jì)算，結(jié)合堆垛機(jī)及倉庫的實(shí)際情況作如下假設(shè)：

（1）根據(jù)作業(yè)任務(wù)指派需要訪問的出入庫后，堆垛機(jī)揀選出入庫的時(shí)間不會(huì)隨著存取路徑順序的不同而不同，其訪問出入庫的時(shí)間是固定的。

（2）由于存取貨物時(shí)，貨叉伸縮時(shí)間為恒定，假設(shè)忽略該時(shí)間。

（3）堆垛機(jī)在水平方向和垂直方向上均以恒定速度獨(dú)立運(yùn)行，忽略其啟動(dòng)及制動(dòng)時(shí)間。

假設(shè)有m個(gè)入庫任務(wù)，n個(gè)出庫任務(wù)，且m≠n，則有min（ m,n）個(gè)復(fù)合作業(yè)需要執(zhí)行。設(shè)出入庫位于a列b層，貨架的長度和高度分別為l和h，堆垛機(jī)起始點(diǎn)坐標(biāo)為 （0,0 ），入庫任務(wù)出入庫為 （xa,xb），出庫任務(wù)出入庫為 （ya,yb），執(zhí)行一次復(fù)合作業(yè)需要的時(shí)間為：

其中：p為第p次復(fù)合作業(yè)，vx為堆垛機(jī)水平運(yùn)行的平均速度，vy為堆垛機(jī)垂直運(yùn)行的平均速度。

其中：q為第q次單一作業(yè)。

則有倉庫路徑優(yōu)化目標(biāo)函數(shù)為：

2 ADP簡介

Bellman于1957年提出了最優(yōu)性原理：無論過去的狀態(tài)和決策如何，相對(duì)于當(dāng)前的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。Bellman把這一過程描述為如下遞歸等式[4,7]：

式中：Vt（St）表示當(dāng)前狀態(tài)St的值函數(shù)；Vt+1（St+1）|St表示下一個(gè)狀態(tài)St+1的條件值函數(shù)，反映了決策xt對(duì)狀態(tài)St+1及后續(xù)狀態(tài)Sk值函數(shù)的影響；γ為折扣因子，體現(xiàn)后續(xù)狀態(tài)對(duì)當(dāng)前價(jià)值影響的折扣。

上式中含有期望值的計(jì)算，而現(xiàn)在大多問題的狀態(tài)空間和決策空間是高維的，因此求出精確最優(yōu)解會(huì)變得非常困難，這也是經(jīng)典動(dòng)態(tài)規(guī)劃的缺陷之處。經(jīng)典動(dòng)態(tài)規(guī)劃在求解問題時(shí)，需要枚舉每一次遷移中的當(dāng)前狀態(tài)、所采取的動(dòng)作、外部的隨機(jī)信息和下一狀態(tài)，以獲得最優(yōu)決策。這種方式能夠獲得精確的最優(yōu)解，但是容易產(chǎn)生“維數(shù)災(zāi)難”，在大規(guī)模問題應(yīng)用中受到了限制。在問題規(guī)模比較大的時(shí)候，使用貝爾曼方程遞推各狀態(tài)的精確值函數(shù)是不能現(xiàn)實(shí)的，由此產(chǎn)生了近似動(dòng)態(tài)規(guī)劃法，使用近似值函數(shù)來替代精確值函數(shù)同時(shí)減少期望的求解。

近似動(dòng)態(tài)規(guī)劃法的思想就是在求解問題時(shí)使用近似方法對(duì)狀態(tài)的值函數(shù)進(jìn)行近似，以值迭代或策略迭代的方式，不斷更新狀態(tài)值函數(shù)的近似估計(jì)，在迭代終止時(shí)獲得問題的近似解，從而避開求精確最優(yōu)解。每次迭代各時(shí)段只有少量狀態(tài)而非所有可行狀態(tài)參與近似值函數(shù)的計(jì)算，計(jì)算量不再隨計(jì)算規(guī)模的增加指數(shù)增長，從而克服“維數(shù)災(zāi)”問題。和DP相反的是，它采取從前往后遞推的方式，以避免維數(shù)的急劇增長。

ADP算法尋找最優(yōu)策略路徑的算法通常有兩種：值迭代和策略迭代。

（1）值迭代算法通過反復(fù)迭代值函數(shù)來尋找最優(yōu)值函數(shù)，即最大回報(bào)值，它是關(guān)于狀態(tài)和控制動(dòng)作的概率的函數(shù)，然后使用最優(yōu)值函數(shù)逆向計(jì)算出一個(gè)最優(yōu)策略。

（2）策略迭代算法是反復(fù)迭代策略以改進(jìn)策略，在每輪迭代中，找出當(dāng)前策略的值函數(shù)，而非最優(yōu)值函數(shù)，然后利用該值函數(shù)計(jì)算出新的改進(jìn)的策略。

本文采用值迭代算法來解決自動(dòng)化立體倉庫出入庫路徑優(yōu)化問題。

3 問題求解

3.1 求解思路

應(yīng)用ADP求解倉庫問題的總體思路可表述為：（1）應(yīng)用DP的概念和符號(hào)描述倉庫路徑優(yōu)化問題，建立決策模型。（2）構(gòu)造近似值函數(shù)并得到其線性表達(dá)式，求解由階段狀態(tài)和近似值函數(shù)構(gòu)成的優(yōu)化決策模型。（3）由最終的優(yōu)化決策序列獲取堆垛機(jī)行駛路徑方案。

首先對(duì)此問題模型中涉及的時(shí)間進(jìn)行說明，文中時(shí)間區(qū)間為“階段”，時(shí)間點(diǎn)為“時(shí)刻”，在t時(shí)刻的系統(tǒng)狀態(tài)為St，并在此時(shí)做出決策xt。在階段t的時(shí)間段內(nèi)，事件發(fā)生順序如下：

（1）服務(wù)完當(dāng)前的出入庫，系統(tǒng)處于狀態(tài)St。

（2） 根據(jù)當(dāng)前狀態(tài)做出決策xt。

（3）到達(dá)下一個(gè)出入庫進(jìn)行服務(wù)，計(jì)算成本Ct。

（4）服務(wù)完當(dāng)前的出入庫任務(wù)后，進(jìn)入下一個(gè)狀態(tài)St+1。

3.2 模型建立

結(jié)合ADP建立問題的優(yōu)化模型，時(shí)間、狀態(tài)、策略、狀態(tài)轉(zhuǎn)移函數(shù)，回報(bào)值函數(shù)和近似值函數(shù)等。

（1）狀態(tài)變量描述系統(tǒng)在當(dāng)前環(huán)境所處的狀態(tài)，表示決策者做出決策之前的狀態(tài)向量，狀態(tài)變量St：

其中：t=0,1,…,n。

it：階段t時(shí)當(dāng)前服務(wù)的出入庫。

jt：出入庫t的狀態(tài)，如果出入庫i訪問過了，則jt=1；如果沒有被訪問過，jt=0。

（2） 決策變量xt

it+1：階段t+1要服務(wù)的出入庫任務(wù)。

rt：在服務(wù)下一個(gè)出入庫前，是否要返回堆垛機(jī)起始點(diǎn)，如果返回則rt=1，否則rt=0。

（3） 成本函數(shù)

每階段的成本用堆垛機(jī)行駛消耗的能量表示，可以由現(xiàn)階段的狀態(tài)和決策來決定，表示為：

（4） 狀態(tài)轉(zhuǎn)移函數(shù)

狀態(tài)轉(zhuǎn)移函數(shù)表示為：

（5） 目標(biāo)函數(shù)

目標(biāo)函數(shù)是最小化所有階段的費(fèi)用之和:

將決策的目標(biāo)函數(shù)式（9）轉(zhuǎn)化為Bellman方程式，應(yīng)用值函數(shù)近似策略求解：

3.3 近似值函數(shù)

出入庫路徑優(yōu)化問題采用值迭代和平滑策略來獲取近似值函數(shù)，具體算法步驟如下：

（1） 初始化

②設(shè)置n=1，N=50，n為取樣路徑標(biāo)記，N為總的取樣次數(shù)。

（5） n+1，如果n≤N，跳轉(zhuǎn)至步驟（2）。

接下來計(jì)算近似價(jià)值函數(shù)的線性表達(dá)式，在出入庫路徑優(yōu)化問題中，定義近似值函數(shù)是關(guān)于距離lt的線性函數(shù)。在狀態(tài)S下，構(gòu)造近似價(jià)值函數(shù)的線性表達(dá)式：

式中：θ1,θ2為待定參數(shù)，根據(jù)上述ADP求解問題的算法步驟（6） 達(dá)到穩(wěn)態(tài)的一組有效值，采用線性回歸的方法求解得到待定參數(shù)，從而得到近似價(jià)值函數(shù)的線性表達(dá)式。

得到近似價(jià)值函數(shù)后，對(duì)倉庫出入庫路徑優(yōu)化問題進(jìn)行具體的指導(dǎo)應(yīng)用，求解決策函數(shù)式（10）。

4 算例仿真

現(xiàn)通過一個(gè)具體實(shí)例來驗(yàn)證算法的有效性，假設(shè)有一個(gè)10列9層的立體化倉庫，有一批出入庫任務(wù)，其中有10個(gè)入庫任務(wù)，8個(gè)出庫任務(wù)，任務(wù)如表1所示。

表1 隨機(jī)任務(wù)序列

設(shè)定模型中相應(yīng)的參考數(shù)值，取l=1.5m，h=2m，vx=vy=3m/s。使用matlab進(jìn)行線性擬合及編程，同時(shí)為了證明ADP具有更好地求解出入庫路徑優(yōu)化問題的能力，對(duì)此問題分別采用ADP及DP方法進(jìn)行優(yōu)化。

取第50次迭代的最后一組系統(tǒng)狀態(tài)近似值進(jìn)行擬合求解，求得近似價(jià)值函數(shù)的線性表達(dá)式，如表2所示。

表2 第50次取樣的系統(tǒng)近似值

得到近似值函數(shù)表達(dá)式如下：

利用得到的近似值函數(shù)來指導(dǎo)求解決策函數(shù)，得到近似最優(yōu)解90.6s，具體路徑如圖2所示，可以很明顯看出在進(jìn)行優(yōu)化后堆垛機(jī)行駛路徑清晰明確，減少了不必要的損耗。

同樣，利用DP求解同一問題得到最優(yōu)解88.2s，但求解時(shí)間幾乎是ADP的3倍之多，比較來看，ADP算法有效地克服了動(dòng)態(tài)規(guī)劃計(jì)算量大、計(jì)算時(shí)間長的弱點(diǎn)，提高了自動(dòng)化立體倉庫出入庫的效率，具有明顯的優(yōu)越性。

5 總 結(jié)

本文針對(duì)自動(dòng)化立體倉庫出入庫路徑優(yōu)化問題進(jìn)行了詳細(xì)研究，結(jié)合DP方法建立了考慮堆垛機(jī)運(yùn)行時(shí)間最短的數(shù)學(xué)模型。在此模型的基礎(chǔ)上，使用近似動(dòng)態(tài)規(guī)劃法求解該模型。與動(dòng)態(tài)規(guī)劃的對(duì)比試驗(yàn)結(jié)果表明，ADP相較于DP，減少了模型求解的計(jì)算量，縮短了計(jì)算時(shí)間，在一定程度上得到了近似最優(yōu)解，很好地解決了自動(dòng)化立體倉庫出入庫路徑優(yōu)化問題。不足之處在于近似值函數(shù)線性擬合存在的誤差較大，以后可考慮使用可能多的離散值，或者用非線性的表達(dá)方式來得出近似值函數(shù)。

圖2 優(yōu)化后堆垛機(jī)行駛路徑圖