李媛媛，鄭 孟 （蘭州交通大學 交通運輸學院，甘肅 蘭州 730070）

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

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

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

1 問題分析

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

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

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

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

（2）空載運行時間，堆垛機在沒有承重的情況下行進所花費的時間（如tAB）；

（3）取/放貨時間，堆垛機在貨架和貨臺取放托盤時所花費的時間。

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

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

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

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

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

（3）堆垛機在水平方向和垂直方向上均以恒定速度獨立運行，忽略其啟動及制動時間。

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

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

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

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

2 ADP簡介

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

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

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

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

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

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

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

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

3 問題求解

3.1 求解思路

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

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

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

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

（3）到達下一個出入庫進行服務，計算成本Ct。

（4）服務完當前的出入庫任務后，進入下一個狀態(tài)St+1。

3.2 模型建立

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

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

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

it：階段t時當前服務的出入庫。

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

（2） 決策變量xt

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

rt：在服務下一個出入庫前，是否要返回堆垛機起始點，如果返回則rt=1，否則rt=0。

（3） 成本函數(shù)

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

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

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

（5） 目標函數(shù)

目標函數(shù)是最小化所有階段的費用之和:

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

3.3 近似值函數(shù)

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

（1） 初始化

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

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

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

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

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

4 算例仿真

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

表1 隨機任務序列

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

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

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

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

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

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

5 總 結(jié)

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

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