GASA混合優化算法在自動化立體倉庫堆垛機作業調度問題中的應用

姜 山，季業飛

JIANG Shan1, JI Ye-fei2

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

GASA混合優化算法在自動化立體倉庫堆垛機作業調度問題中的應用

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

姜 山1，季業飛2

JIANG Shan1, JI Ye-fei2

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

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

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

0 引言

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

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

1 堆垛機作業調度優化問題

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

圖1 堆垛機復合作業示意圖

此種方式下，圖1所示三個作業任務時的作業時間為：

不難推導出堆垛機執行完n條作業任務時，總的作業時間是：

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

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

2 GASA混合優化算法求解堆垛機作業調度優化問題

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

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

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

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

3）根據適應度分布復制種群X(k)。

4）根據交叉概率Pc，執行交叉操作。

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

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

7）由SA狀態產生函數產生新個體。

8）以概率接受新個體。

9）若抽樣穩定，退溫，轉2）。否則，轉7）。

關于上述算法的說明：

1）在1）中，堆垛機執行復合作業要實現時間越少越好，即實際優化目標函數為因此確定混合優化算法的適應度函數為為一數值較大的實數。

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

3 數值模擬

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

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

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

表2 混合算法和相關算法性能統計比較

4 結束語

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

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

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

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

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

[5] 朱耀明.自動化立體倉庫優化調度研究[D].濟南:山東大學,2006.

[6] 劉惠.自動化立體倉庫效率優化研究[D].沈陽:遼寧工程技術大學,2007.

TH166

B

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

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

2010-04-06

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