姜 山，季業(yè)飛

JIANG Shan1, JI Ye-fei2

（1. 交通運輸部公路科學(xué)研究院 公路交通發(fā)展研究中心，北京 100088；2. 中國中元國際工程公司 工程事業(yè)二部，北京 100089）

GASA混合優(yōu)化算法在自動化立體倉庫堆垛機作業(yè)調(diào)度問題中的應(yīng)用

Application of GASA hybrid optimization algorithm in the stacker’s dispatch problem in as/rs

姜 山1，季業(yè)飛2

JIANG Shan1, JI Ye-fei2

（1. 交通運輸部公路科學(xué)研究院 公路交通發(fā)展研究中心，北京 100088；2. 中國中元國際工程公司 工程事業(yè)二部，北京 100089）

堆垛機出入庫調(diào)度優(yōu)化問題是提高自動化立體倉庫工作效率的關(guān)鍵技術(shù)之一。本文通過對出入庫調(diào)度問題中影響堆垛機作業(yè)時間因素的分析，把堆垛機調(diào)度的優(yōu)化路線問題轉(zhuǎn)化為TSP問題，然后采用遺傳—模擬退火混合優(yōu)化算法來解決。數(shù)值試驗表明混合優(yōu)化算法吸收了單一算法的各自優(yōu)點，克服了本身的缺點，顯示出較強的全局優(yōu)化能力，為立體倉庫任務(wù)調(diào)度問題提供了新的求解思路。

遺傳算法；模擬退火算法；堆垛機；自動化立體倉庫

0 引言

自動化立體倉庫是物流系統(tǒng)的重要組成部分，又稱自動存儲自動檢索系統(tǒng)（Automatedstorage/Retrieval system，As/Rs），是一種新型的倉儲技術(shù)。它是以高層貨架為主體，以成套搬運設(shè)備為基礎(chǔ)，以計算機控制技術(shù)為手段的高效率物流、大容量存儲的機電一體化高科技集成系統(tǒng)。它的出現(xiàn)大大拓展了倉庫功能，使之從“靜態(tài)倉庫”變成了“動態(tài)倉庫”，由單純的保管型向綜合的流通型方向發(fā)展，通過有效銜接生產(chǎn)與庫存，加快了物資周轉(zhuǎn)，大大降低了生產(chǎn)成本。

近30年來自動化立體倉庫的硬件設(shè)備的技術(shù)、自動控制以及通訊技術(shù)己十分完善，工作效率有了大幅提高，但現(xiàn)代機械制造對倉庫的工作效率的要求也在不斷提高。如何在不增加設(shè)備投資的情況下，通過優(yōu)化倉庫的管理和調(diào)度，減少作業(yè)時間，就成為提高自動化立體倉庫工作效率的關(guān)鍵研究技術(shù)，其中堆垛機出入庫調(diào)度優(yōu)化問題是一個重要的研究課題。本文通過對立體倉庫出入庫調(diào)度問題中影響堆垛機作業(yè)時間因素的分析，把堆垛機調(diào)度的優(yōu)化路線問題轉(zhuǎn)化為常見的TSP問題，然后采用遺傳—模擬退火混合優(yōu)化算法（GASA）來求解，取得了較好的效果。

1 堆垛機作業(yè)調(diào)度優(yōu)化問題

自動化立體倉庫貨物的存取有兩種基本方式：一種是單一作業(yè)方式，另一種是復(fù)合作業(yè)方式。在單一作業(yè)方式下，堆垛機作業(yè)時間是一個定值，與作業(yè)任務(wù)的執(zhí)行順序無關(guān)。在復(fù)合作業(yè)時，堆垛機接到一批出入庫指令，即堆垛機從原點出發(fā)執(zhí)行第一條指令，運行到指定貨格取出托盤并將托盤運送到原點，由操作人員按單據(jù)具體內(nèi)容取出或放人物料，接著堆垛機再將托盤放回原庫位處，從而完成一個庫位作業(yè)。之后，堆垛機并不回到原點而是直接執(zhí)行下一個指令，即尋找下一個庫位號，如此反復(fù)直到完成所有的指令為止。堆垛機復(fù)合作業(yè)方式如圖1所示：

圖1 堆垛機復(fù)合作業(yè)示意圖

此種方式下，圖1所示三個作業(yè)任務(wù)時的作業(yè)時間為：

不難推導(dǎo)出堆垛機執(zhí)行完n條作業(yè)任務(wù)時，總的作業(yè)時間是：

其中Tn為堆垛機完成所有的作業(yè)任務(wù)所花費的總時間，T0,j為從原點P0（出入庫臺處）到Pi（指定庫位處）所用的時間，Ti,0為堆垛機從點Pi（指定庫位處）到原點P0處所用的時間， Ti-1,i為從點Pi-1（前一庫位）到Pi（當(dāng)前庫位）所用時間。最后一項 為堆垛機完成所有出入庫任務(wù)后從最后一個庫位Pn處回到原點P0（出入庫臺處）待命所用的時間。

不難發(fā)現(xiàn)，當(dāng)一批出入庫任務(wù)指定后，不管任務(wù)執(zhí)行的先后順序如何，第一部分的值總是確定的，它對堆垛機的運行時間是沒有影響的。而第二部分為一個從原點出發(fā)途經(jīng)各指定庫位的回路，當(dāng)堆垛機采用不同的行走順序，路徑長度是不同的，執(zhí)行的時間也不相同。對于這部分堆垛機所走的路徑就是一個從原點出發(fā)途經(jīng)各指定庫位再回到原點的回路，這是一個典型的旅行商(TSP)問題。

2 GASA混合優(yōu)化算法求解堆垛機作業(yè)調(diào)度優(yōu)化問題

旅行商（TSP）問題是典型的非多項式時間可解難題(NP-hard Problem)。目前遺傳算法(Genetic Algorithm，GA)和模擬退火算法( Simulated Annealing Algorithm， SA)等智能優(yōu)化算法被廣泛用于求解TSP問題。但是對于NP難問題，單一機制的優(yōu)化算法很難實現(xiàn)全局優(yōu)化，且效率也不高。遺傳算法有較強的全局搜索能力，但算法的一些參數(shù)如果選取不當(dāng)，易陷入局部最優(yōu)解難以自拔。模擬退火算法有較強的局部搜索能力，但其參數(shù)一樣很難確定，且返回一個高質(zhì)近似解的時間花費較多，當(dāng)問題規(guī)模增大時，難于承受的運行時間將使算法喪失可行性。多種優(yōu)化機制的相互結(jié)合，是提高全局優(yōu)化能力的有效途徑之一。本文提出利用遺傳—模擬退火混合優(yōu)化算法求解堆垛機作業(yè)調(diào)度優(yōu)化問題。

遺傳—模擬退火混合優(yōu)化算法可以歸納如下：GA利用SA得到的解作為初始種群，通過復(fù)制、交叉、變異等遺傳操作使種群得以進化；SA對GA得到的進化種群進行進一步優(yōu)化，溫度較高時表現(xiàn)出較強的概率突變性，體現(xiàn)為對種群的“粗搜索”，溫度較低時演化為局部搜索，體現(xiàn)為對種群的“細搜索”?；旌蟽?yōu)化算法求解堆垛機作業(yè)調(diào)度問題步驟如下：

1）對作業(yè)序列決策變量隨機編碼產(chǎn)生初始種群X(1)，確定初溫和合理的適應(yīng)度函數(shù)。

2）計算種群中每一個體xi(k)，k=1,2,……N的適應(yīng)度。如果連續(xù)幾代個體平均適應(yīng)度的差異小于某一個極小的閾值，則選當(dāng)前最佳的個體為最優(yōu)染色體，進行解碼得到最優(yōu)解。否則轉(zhuǎn)3）。

3）根據(jù)適應(yīng)度分布復(fù)制種群X(k)。

4）根據(jù)交叉概率Pc，執(zhí)行交叉操作。

5）根據(jù)變異概率Pm，執(zhí)行變異操作，從而得到新種群X(k+1)。

6）對X(k+1)中每一個體進行Metropolis抽樣。

7）由SA狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新個體。

8）以概率接受新個體。

9）若抽樣穩(wěn)定，退溫，轉(zhuǎn)2）。否則，轉(zhuǎn)7）。

關(guān)于上述算法的說明：

1）在1）中，堆垛機執(zhí)行復(fù)合作業(yè)要實現(xiàn)時間越少越好，即實際優(yōu)化目標(biāo)函數(shù)為因此確定混合優(yōu)化算法的適應(yīng)度函數(shù)為為一數(shù)值較大的實數(shù)。

2）在7）中，SA狀態(tài)產(chǎn)生函數(shù)可設(shè)計為互換操作(SWAP)，即隨機交換染色體中兩不同基因的位置，也可設(shè)計為逆序操作(INV)，即將染色體中兩不同隨機位置間的基因串逆序。

3 數(shù)值模擬

假設(shè)某自動化立體倉庫巷道堆垛機從上位管理機接受單據(jù)，任務(wù)序數(shù)為1～7，貨位地址（XK，Yk）（k=l，2，…，7），其中1、4、5、7為入庫任務(wù)，2、3、6為出庫任務(wù)。堆垛機從出入庫臺O點(0，0)出發(fā)進行復(fù)合作業(yè)，最后要返回到出入庫臺0點。各個貨位之間的運行時間如表1 所示。

表1 各個貨位之間的運行時間 單位：秒

分別采取遺傳算法、模擬退火算法和GASA混合優(yōu)化算法求解，三種優(yōu)化算法都得到相同的復(fù)合作業(yè)順序結(jié)果，7個貨位點之間進行復(fù)合作業(yè)的順序為(1，2，5，4，6，7，3)，即堆垛機按照(0→1→2→0→5→0→4→6→0→7→3→0)完成復(fù)合作業(yè)，對應(yīng)的堆垛機運行時間為264.5秒。但從表2中可以看出SA優(yōu)化時間性能較差，GA略有改善，GASA混合優(yōu)化算法在時間性能上優(yōu)于它們。

表2 混合算法和相關(guān)算法性能統(tǒng)計比較

4 結(jié)束語

本文運用遺傳—模擬退火混合優(yōu)化算法求解自動化立體倉庫堆垛機的作業(yè)調(diào)度優(yōu)化問題。數(shù)值模擬實驗表明，混合優(yōu)化算法吸收了單一算法的各自優(yōu)點，克服了它們本身的缺點，大大提高了搜索效率。遺傳算法與模擬退火算法的結(jié)合顯示出卓越的優(yōu)勢，遺傳算法跟其它優(yōu)化算法的結(jié)合在求解自動化立體倉庫堆垛機調(diào)度問題方面也可能發(fā)揮更大的威力，對此問題我們將另文討論。

[1] 周明,孫樹棟.遺傳算法原理及應(yīng)用(M).北京:國防工業(yè)出版社,1999.

[2] 康立山,謝云,尤矢勇,等.非數(shù)值并行算法(第一冊):模擬退火算法[M].北京:科學(xué)出版社, 1997.

[3] 王凌.智能優(yōu)化算法及其應(yīng)用(M).北京:清華大學(xué)出版社,2001.

[4] 劉偉銘,姜山.基于GASA混合優(yōu)化策略的雙層規(guī)劃模型求解算法研究[J].土木工程學(xué)報,2003,36(7):27-32.

[5] 朱耀明.自動化立體倉庫優(yōu)化調(diào)度研究[D].濟南:山東大學(xué),2006.

[6] 劉惠.自動化立體倉庫效率優(yōu)化研究[D].沈陽:遼寧工程技術(shù)大學(xué),2007.

TH166

B

1009-0134(2010)10(上)-0063-03

10.3969/j.issn.1009-0134.2010.10(上).19

2010-04-06

姜山（1977 -），男，山東諸城人，經(jīng)濟師，碩士，研究方向為交通運輸工程與交通運輸經(jīng)濟。