自動化立體倉庫調(diào)度模型分析及優(yōu)化

蔡安江，史啟程

（西安建筑科技大學 機電工程學院，陜西 西安 710055）

1 引言

自動化立體倉庫是當代物流技術(shù)，倉儲技術(shù)、自動化和計算機技術(shù)高度集成的產(chǎn)物[1]，衡量其存取效率的標準是單位時間內(nèi)貨物的存取量，為保證整個倉庫的性能指標最優(yōu)，需要對堆垛機路徑進行調(diào)度，降低存/取貨物所需時間，使其能夠高效協(xié)調(diào)運轉(zhuǎn)[2]。

堆垛機調(diào)度問題是在倉庫模型和出/入庫位點確定的前提下，合理安排任務執(zhí)行順序，以求得所需時間最短的方案。國內(nèi)外學者對立體倉庫路徑優(yōu)化調(diào)度問題進行了大量的研究，文獻[3]用遺傳算法對倉庫調(diào)度問題進行研究，該算法很容易陷入“早熟”，對求解的精度有一定影響；文獻[4]將模擬退火算法和遺傳算法相結(jié)合，將每次迭代的結(jié)果當作父代種群，兩種算法交替進行，實際每次迭代種群進化兩次，算法結(jié)合方式過于生硬；在上述研究中，均未對同軌雙車情況下堆垛機的調(diào)度路徑模型進行研究，而雙車存儲效率遠高于單車。細菌覓食優(yōu)化算法（Bacterial ForagingOptimization BFO）是文獻[5]于2002年提出的，引起不同領(lǐng)域廣泛關(guān)注和應用，然而目前將BFO算法應用于自動化立體倉庫調(diào)度的并不多，該算法針對種群的單一性擴大搜索范圍，因此文章通過BFO算法對趨化步長加以改進，使其能夠?qū)?yōu)，在搜索過程中具有自適應調(diào)節(jié)，從而提高收斂速度和倉儲效率。

2 問題描述

在生產(chǎn)物流中，傳統(tǒng)倉庫模型貨架縱深過長，導致單臺堆垛機運行時間較長，出/入庫臺或其緩沖區(qū)經(jīng)常處于閑置狀態(tài)[6]。為縮短出/入庫臺到貨架深處庫位點的距離，提高庫位緩沖區(qū)的利用率，提出一種兩端式同軌雙車的倉庫模型。

同軌雙車模式下兩端式倉庫布局結(jié)構(gòu)圖，如圖1所示。通過在立體倉庫兩端各設(shè)置一個出/入庫臺，并在同一巷道上增加一臺堆垛機，將貨架深處庫位點轉(zhuǎn)移至倉庫中心位置，縮短堆垛機行進路線，大幅提高存取效率。

針對同軌雙車倉庫布局模型，當一批存/取任務輸入后，同一軌道上兩臺堆垛機同時工作，完成這批任務所需時間為兩臺堆垛機完成各自任務后，用時最長的堆垛機的運行時間：

式中：TL，TR—貨架左右兩端堆垛機完成各自任務的運行時間。

將一條入庫任務和一條出庫任務組合而成的復合任務，稱為DC任務；單獨執(zhí)行一條入庫任務或一條出庫任務，稱為SC任務[7]。組合成DC任務，可以減少堆垛機從出/入庫臺到庫位點的往返次數(shù)，因而效率更高。在實際應用中，入庫任務數(shù)和出庫任務數(shù)往往不等，基于此，同軌雙車模式下，其中任意一臺堆垛機運行的時間為

其中，m=min（Npike，Nput），n=max（Npike，Nput）。

式中：TDCi—堆垛機執(zhí)行第i條DC任務花費的時間；TSCi—堆垛機執(zhí)行第i條SC任務花費的時間；Npike—出庫任務數(shù)量；Nput—入庫任務數(shù)量。

3 出入庫調(diào)度模型

在同軌雙車運行模式下，兩堆垛機在同一巷道上同時工作，它們各自的水平位移和垂直位移互不干涉。故其中一臺堆垛機完成一次存/取任務所花費的時間為水平、垂直作業(yè)所需時間的最大值。設(shè)一個貨架的長度為l、高度為h，堆垛機水平位移速度為Vx、垂直位移速度為Vy。則其中一臺堆垛機以位置［xa，ya］為起點，以位置［xb，yb］為終點，所需時間為：

3.1 任務分配方式

統(tǒng)籌分配原則的目標是在一組出/入庫任務分配完成后，兩堆垛機完成各自任務的運行時間最短；兩堆垛機運行時間差的絕對值最小。數(shù)學模型表達如下：

3.2 DC作業(yè)方式

同軌雙車模式下的DC作業(yè)方式為：一批出/入庫任務分配給兩臺堆垛機后，兩堆垛機同時工作，各自從出/入庫臺運載貨物運行到入庫任務指定庫位點，卸載貨物后直接運行到出庫任務指定庫位點裝載貨物，再將貨物運至出/入庫臺。同軌雙車情況下，DC作業(yè)方式下堆垛機路徑示例，如圖2所示。

圖2 DC作業(yè)方式下堆垛機路徑示例圖Fig.2 DC Operating Mode Stacker Road Sample Diagram

圖中：IO—出/入庫臺；P1，P3—兩堆垛機的入庫貨位；P2，P4—兩堆

垛機的出庫貨位。

式中：TDC—兩臺堆垛機完成DC任務的運行時間中較大值。

3.3 SC作業(yè)方式

在實際的應用過程中，入庫任務數(shù)量和出庫任務數(shù)量并不相同，兩堆垛機在執(zhí)行完組合而成的數(shù)條DC任務后，剩下的入庫或出庫任務即為SC任務。同軌雙車情況下，SC作業(yè)方式下堆垛機路徑示例，如圖3所示。

圖3 SC作業(yè)方式下堆垛機路徑示例圖Fig.3 SC Operating Mode Stacker Road Sample Diagram

圖中：IO—出/入庫臺；P1—分配給堆垛機的入庫貨位；P2—分配給堆垛機的出庫貨位。

只討論其中一臺堆垛機，運行路徑為IO→P1→IO，無論是入庫任務還是出庫任務，運行時間為：

3.4 建立同軌雙車模式下調(diào)度模型

在實際執(zhí)行出/入庫任務中，一批任務在分配給兩臺堆垛機后，每臺堆垛機獲得的出庫任務、入庫任務的數(shù)量可能不一致。因此假設(shè)兩堆垛機分別獲得nL、nR個入庫任務與mL、mR個出庫任務，取：

根據(jù)在同軌雙車情況下對DC任務、SC任務的分析，兩堆垛機分別有QL2、QR2個DC任務和QL1-QL2、QR1-QR2個SC任務。

基于此，貨架兩端堆垛機完成各自任務的運行時間為：

因此，完成一批出/入庫任務時，堆垛機最優(yōu)路徑模型為：

4 進出庫調(diào)度優(yōu)化

利用BFO算法對堆垛機進行路徑優(yōu)化分析，通過四種基元反應操縱，求得同軌雙車的最優(yōu)或近似最優(yōu)任務序列。

4.1 編碼設(shè)計

為了方便問題的求解，采用基于任務編號排序的間接編碼法[8]將每臺堆垛機的出庫任務和入庫任務分別寫成兩段編碼。

4.2 算法步驟

同軌雙車運行模式下，采用統(tǒng)籌分配原則不能保證一次分配的結(jié)果為最優(yōu)，通過在BFO算法中增加調(diào)整分配結(jié)果的操作，可逐步尋得最優(yōu)解[9]。細菌覓食優(yōu)化算法具體步驟如下：

步驟1設(shè)定初始參數(shù)，包括出/入庫任務庫位點坐標，初始分子個數(shù)，最大反應次數(shù)Max-BFO；

步驟2根據(jù)統(tǒng)籌分配原則將任務分配給兩臺堆垛機，產(chǎn)生初代分子；

步驟3：初始化細菌種群個體位置，定義初始化參數(shù)Niter、Nc、Ns、Nre、Ned；

步驟4：種群進化代數(shù)：n=n+1；

步驟 3：遷移代數(shù)：l=l+1；

步驟 4：繁殖行為：k=k+1；

步驟 5：趨化行為：j=j+1；

步驟6：不可行解可能攜帶若干可行解無法獲取的有用信息，如距離全局最優(yōu)解較近，能夠快速獲取搜索全局最優(yōu)解，采用提出的部分不可行解保留策略以提高算法收斂速度；

步驟7：若j≤Nc，則返回步驟5繼續(xù)趨化操作；

步驟8：種群繁殖，達到臨界趨化次數(shù)時細菌將完成一個生命周期，并根據(jù)健康評價標準進行優(yōu)勝劣汰，將給定的序號為1到N的N個細菌個體，定義第i個細菌健康程度為：

式中表示種群中每個細菌在趨化過程中完成適應度的累加之和，并對N個細菌健康程度指標按降序進行排列，只保留健康程度較好的部分細菌。

步驟9：若k≤Nre，則返回步驟4繼續(xù)繁殖操作；

步驟10：遷移操作，為了增強細菌的全局尋優(yōu)能力，保持規(guī)則進行概率遷移，種群內(nèi)的所有細菌將會按照自身指定的概率遷移到解空間中一個隨機位置；

步驟11：若l≤Ned，則返回步驟3繼續(xù)執(zhí)行遷移操作；

步驟12：若n≤Niter，則返回步驟2繼續(xù)種群進化操作；否則輸出優(yōu)化結(jié)果。

統(tǒng)籌分配原則的BFO算法流程圖，如圖4所示。

圖4 統(tǒng)籌分配原則的BFO算法流程圖Fig.4 Flow Chart of BFO Algorithm of Overall Allocation Principle

通過上述融入統(tǒng)籌分配原則的BFO算法的操作步驟，可以對路徑優(yōu)化問題進行有效的全局搜索[10]，通過分解與合成操作，不易使算法陷入局部最小值。

5 仿真驗證

以某企業(yè)實際自動化倉庫為研究對象，驗證數(shù)學模型的適應性和BFO算法的有效性。倉庫貨架位置固定，大小一致，每排貨架共840個貨位，分為12層，70列，每排貨架兩端各一個出/入庫臺，出/入庫臺坐標分別為［0，1］，［71，1］，用于工業(yè)產(chǎn)品的出庫運輸和入庫存儲。

在某批出/入庫任務中，對應的庫位點坐標，如表1所示。提出的細菌覓食算法可以使可搜索的解空間得到擴大的同時，可以有效地引導BFO向最優(yōu)解靠近，不僅提高求解質(zhì)量，也提高收斂速度。利用所建立的堆垛機調(diào)度模型對上述出/入庫任務運用MATLAB進行仿真優(yōu)化，堆垛機運行所需時間的優(yōu)化曲線，如圖5所示。

表1 出/入庫任務坐標Tab.1 Out/In Bound Task Coordinates

圖5 堆垛機運行時間優(yōu)化曲線Fig.5 Optimization Curve of Stacker Running Time

由圖5可以看出，堆垛機的運行時間隨著算法迭代次數(shù)的增加不斷減小，于第42代求得最優(yōu)解。

出/入庫任務優(yōu)化前后，堆垛機運行時間的對比，如表2所示。由表2知，通過優(yōu)化后堆垛機的調(diào)度效率提高了29.5%。在求得堆垛機路徑調(diào)度最優(yōu)解后，根據(jù)輸出的最優(yōu)解任務序列，其堆垛機運行路徑圖，如圖6所示。

表2 優(yōu)化前后堆垛機運行時間Tab.2 Stacker Running Time Before and After Optimization

圖6堆垛機運行路徑圖Fig.6 Stacker Running Path Map

圖6 中，白色方塊為倉庫兩端出/入庫臺；黑色方塊及實線為SC任務的運行路徑；灰色方塊及虛線為DC任務的運行路徑?？梢钥闯?，兩臺堆垛機各自執(zhí)行分配所得的出/入庫任務，不存在碰撞情況。

結(jié)合表2，兩堆垛機運行時間差的絕對值為ΔT=2；Right堆垛機先完成任務后，如果執(zhí)行用時最短的編號為9的出庫任務，所需時間為tmin=34.27。滿足式（14）的分配原則，故分配結(jié)果為最優(yōu)解。

6 結(jié)束語

為提高立體倉庫的存儲效率，滿足物流系統(tǒng)性能要求，研究了在同軌雙車情況下，堆垛機的路徑優(yōu)化調(diào)度模型。取得以下成果：（1）基于BFO算法鄰域搜索能力和跳出局部極小值能力強的特點，對所建立的同軌雙車堆垛機調(diào)度模型進行優(yōu)化分析，縮短了堆垛機工作時長，通過優(yōu)化，堆垛機的調(diào)度效率提高了29.5%。（2）結(jié)合實際任務進行仿真驗證表明，所建立的調(diào)度模型對兩端為出/入庫臺的同軌雙車調(diào)度問題有很好的適應性，采用統(tǒng)籌分配原則可有效避免碰撞和產(chǎn)生無效任務序列，其分配結(jié)果是合理、高效的。BFO算法在解決此類問題上是有效可行的。