郭春暉 （蘭州交通大學 機電技術(shù)研究所，甘肅 蘭州730070）

GUO Chun-hui (Institute of Electrical and Mechanical Technology, Lanzhou Jiaotong University, Lanzhou 730070, China)

0 引 言

圖1 為大型貨運站集裝貨物立體庫的平面布置示意圖，它由以下四大部分組成：（1） ULD 輥道式立體貨架，是ULD 貨物的存放單元。 （2） 升降式轉(zhuǎn)運車（ETV），在貨位之間的地面軌道上行走，實現(xiàn)貨架上貨物的存入或取出。（3） 集裝貨物分解組合系統(tǒng)與直通轉(zhuǎn)運系統(tǒng)設備，用于集裝貨物的分解、組合等任務。（4） 管理控制中心，負責整個貨運站的信息數(shù)據(jù)處理、監(jiān)控終端、相關(guān)電氣控制設備的運行[1]。

ETV 在地面軌道上穿梭，完成集裝貨物的出、入庫任務。操作員或管理中心將取、送貨的信息發(fā)送給ETV 的控制計算機，由計算機控制ETV 的運動。在任務量高峰時，如果ETV 執(zhí)行存、取貨任務過程中接收到新的任務指令，控制計算機會把新的命令加入到任務隊列等待執(zhí)行。但在實際的貨運站內(nèi)，尤其在任務密集的時間段，ETV 調(diào)度算法的優(yōu)劣往往成為物流系統(tǒng)中的制約環(huán)節(jié)，所以針對ETV 的調(diào)度進行優(yōu)化顯得尤為關(guān)鍵。

1 ETV 運行的數(shù)學模型建立

選擇ETV 的運動模型時，本文使用柔性S 型加減速度算法[2]。提出一種七段S 型加減速度算法，但該算法缺點是計算量大。五段S 型加減速算法與七段相比，省略勻加速和勻減速階段，在保持速度平滑性的同時，大大降低了計算復雜度[3]。圖2為五段S 型算法中速度V，加速度a，加速圓角參數(shù)j隨時間的變化規(guī)律。T1為加加速和減加速時間；T2為勻速時間；T3為加減速和減減速時間。

根據(jù)加加速度、加速度、速度及位移間的動力學規(guī)律有:

進而可以得到：

每個貨位長度為X，高度為Y。ETV 每完成一次調(diào)度操作要運行M列N層，則水平方向運行距離Sx=X*M，垂向運動距離為Sy=Y*N。

ETV 理參數(shù)如表1 所列：

表1 ETV 運行參數(shù)

集裝立體貨架采用縱向存儲式，單個貨位長為3.75m，共45 列；層高為3.75m，共5 層，貨位數(shù)45*5*2=450。ETV 在水平運行時間和垂向運行時間分別為Tx,Ty：

那么ETV 在兩個貨位點之間運行的時間開銷為：

通常，貨運站貨物處理區(qū)的任一批次的出入庫都包含n個集裝貨物任務的操作，每個任務花費的時間主要由3 部分組成：（1） 兩個貨位點間負重行走時間Tτa；（2） 兩個貨位點間空載行走時間Tτb；（3） 每完成一次取/放貨時間Tc，這部分的時間恒定。

由以上分析可知，完成1 個集裝貨物任務的操作的時間為：

2 遺傳算法計算與求解

遺傳算法以自然選擇和遺傳理論為基礎，通過對生物在遺傳和進化過程中選擇、交叉、變異機理的模仿，來完成對問題最優(yōu)解的自適應搜索的一種算法[4]。選擇、交叉、變異運算是遺傳算法的主要步驟，改進的遺傳算法將針對這三個算子實現(xiàn)算法性能的提升。

2.1 選擇編碼策略

在研究調(diào)度優(yōu)化問題時通常采用實數(shù)編碼。因此在用改進的遺傳算法對貨運站調(diào)度進行優(yōu)化時，首先要建立貨位號和貨位編碼的對照表。

本文中的集裝貨物存儲區(qū)有2 行、5 層、45 列。假設貨位處于第2 行、第3 層、第3 列，則貨位號用（2-3-3） 表示，對應編碼號為28。具體編碼方式參照表2。

2.2 定義適應度函數(shù)

將目標函數(shù)進行變換可得到適應度函數(shù)，依據(jù)目標函數(shù)要遍歷所有等待任務的貨位點而費時最短原則，目標函數(shù)可定義為：

由于在貨運站內(nèi)，等待任務列隊是即時變化的，故每加入一個新的調(diào)度任務后需執(zhí)行一次新的優(yōu)化，會使個別任務等待時間太長。因此，考慮任務等待時間的因素，目標函數(shù)變?yōu)椋?/p>

表2 編碼號與貨位號對照表

式中：ti表示任務等待的時間；β 表示根據(jù)工作模式使用的參數(shù)。

2.3 遺傳算法的三個算子的改進

2.3.1 基于序的選擇算子設計

適應度值是進行選擇過程的依據(jù)。為了加快算法的收斂速度，本文采取的方法是快速選中種群中的優(yōu)秀個體，并使優(yōu)秀個體馬上參與到下一代交叉運算。通過增大優(yōu)劣個體間的適應度值，可將優(yōu)秀個體快速選出。為了增大個體之間適應度值的區(qū)分度，通過基于序的評價函數(shù)來實現(xiàn)。首先對種群中的個體按花費總時間的長短排序，并據(jù)此確定個體在隊列中的序號，對總時間越少的個體賦予小的序號數(shù)。如耗費最少時間的個體被賦予序號數(shù)1，則耗費最長時間的個體序號數(shù)為n，然后用下面的基于序的指數(shù)評價函數(shù)計算適應度：

式中，base為取值范圍在0 到1 間的基數(shù)，μ 是個體通過排序后得到的序號數(shù)，由于評價函數(shù)經(jīng)指數(shù)計算后得到數(shù)據(jù)值較小，乘以10 000 的目的是放大數(shù)據(jù)從而使其不會在計算中被舍去。例如，個體A序號數(shù)是5，個體B序號數(shù)是7，個體C序號數(shù)是2，選擇基數(shù)為0.5，個體A、B、C的適應度分別為：

顯然，通過該評價函數(shù)計算后C的適應度是A的8 倍，是B的32 倍，個體C的優(yōu)越性變得更加突出，它被選作父代的可能性就大為提升。確保適應度最高的基因快速傳到下代，加速算法收斂速度。

2.3.2 基于普萊姆算法的交叉算子設計

在用遺傳算法求解貨運站的調(diào)度優(yōu)化問題時，貨運站內(nèi)每個貨位點的位置編碼采用實數(shù)編碼，經(jīng)常用到的交叉算子有：部分匹配交叉算子，順序交叉算子，循環(huán)交叉算子等，上述交叉算子只是單純產(chǎn)生新個體，在設計時沒有充分結(jié)合問題本身的特性進行考慮，最終算法尋優(yōu)效果在整體性能方面不理想。在貨運站內(nèi)，規(guī)定ETV 的起始點貨位為1，最后執(zhí)行完任務后要回到起始貨位點，則把每個出入庫任務貨位點連起來是完全圖。把ETV 從上一貨位點到下一貨位點運行所需的時間稱為權(quán)，則要使ETV 依次抵達n個貨位點，至少需要n-1 條邊來表示，n個貨位點和n-1 條邊可生成一棵樹，把n-1 條邊的權(quán)值求和后存在一顆和最小的樹，稱這樣的樹為最小代價樹。設U表示n個貨位點的集合，E表示n-1 條邊的集合，那么普萊姆算法就是一種求最小代價樹的算法。

用普萊姆算法生成最小代價樹的例子如圖3 所示。

最小代價樹生成方法如下：

（1） 任意選一頂點A，令U=｛A｝，尋找A的相鄰邊使其權(quán)值最小，產(chǎn)生一條邊（A,B），則將B添入U內(nèi)，（A,B）添入E內(nèi)，得到U=｛A,B｝,E=｛（A,B）｝；

（2） 在E外再尋找A、B的鄰邊使權(quán)值最小，得到邊（A,C），再將C添入U內(nèi)，并把（A,C）添入E內(nèi)，此時U=｛A,B,C｝，E=｛（A,B）,（A,C）｝；

（3） 在E外搜索A、B、C的鄰邊使其權(quán)值最小，得到邊（B,D），將D添入U內(nèi)，同時（B,D）加到E中，此時U=｛A,B,C,D｝，E=｛（A,B）,（A,C）,（B,D）｝，到此U中包括了所有的頂點。求得E的最小權(quán)值和為6。

根據(jù)普萊姆算法生成最小代價樹的思想，設計一種基于普萊姆算法的交叉算子步驟如下：

（1） 在種群中選取兩個個體Pa、Pb 作為父代，隨機產(chǎn)生一個貨位點，并把這個貨位點作為子代個體Ca首先到達的貨位點；

（2） 搜索ri在Pa、Pb 優(yōu)化順序中右邊的貨位點rj1、rj2，比較con（ri,rj1）和con（ri,rj2）耗時的大小，如果con（ri,rj1）＞con（ri,rj2），則按照ri到rj2的順序更快，進入（4）；

（3） 若con（ri,rj1）＜con（ri,rj2），則按照ri到rj1的順序更快，就把rj1加入到ETV 下一訪問順序的貨位點，同時刪去Pa、Pb中ri的值，重新將ri賦值rj1，再進入（2） 開始下一步搜索，直到Pa、Pb 中剩下唯一的貨位點；

（4） 將rj2看成ETV 下一訪問的貨位點，同時刪去Pa、Pb 中ri的值，重新將ri賦值rj2，繼續(xù)轉(zhuǎn)入（2） 開始搜索，直到Pa、Pb 中只剩下最后一個貨位點；

（5） 通過Pa、Pb 向右尋優(yōu)搜索雜交產(chǎn)生子代個體Ca。同樣對Pa、Pb 向左尋優(yōu)搜索雜交產(chǎn)生子代個體Cb。

2.3.3 基于隨機時間長度的變異算子設計

設計一種基于隨機時間長度的變異算子，可增大種群多樣性，同時減小破壞優(yōu)良個體基因概率，方法如下：

（1） 任意產(chǎn)生貨位點r1和r2，初始循環(huán)次數(shù)p=1；

（2） 計算調(diào)度隊列中上述兩個貨位點間的貨位點數(shù)q；

（4） 在r1和r2之間選取兩個貨位點ri、rj，替換ri、rj的次序，p=p+1；

（5） 若k＜m，則返回（4），否則跳出。

該交叉方法由初始的貨物點r1,r2之間的貨物點數(shù)量q確定需要隨機交換的次數(shù)s。若q越大，進行的替換次數(shù)就越多，否則就越少。根據(jù)時間耗費長短控制變異的次數(shù)，可以在保存了優(yōu)良個體的同時增加了種群多樣性。長短控制變異的次數(shù)，可以在保存了優(yōu)良個體的同時增加了種群多樣性。數(shù)量q確定需要隨機交換的次數(shù)s。若q越大，進行的替換次數(shù)就越多，否則就越少。根據(jù)時間耗費長短控制變異的次數(shù)，可以在保存了優(yōu)良個體的同時增加了種群多樣性。

3 仿真驗證

為了測試改進的遺傳算法的性能，對圖1 所示的集裝貨物存儲區(qū)進行仿真試驗。實際中出入庫作業(yè)主要集中于空側(cè)區(qū)域，因此只討論空側(cè)區(qū)域的I/O 口?？諅?cè)區(qū)域入口總共7 個，位置編號為41，101，181，201，311，341，441；出口共計6 個，編號為71，151，261，291，391，421。

有30 個入庫任務R1～R30，貨位編碼為：53、79、235、154、337、335、435、287、399、69、88、6、197、133、142、77、330、379、434、400、277、199、84、9、108、321、342、222、263、21。

30 個出庫任務C1～C30，貨位編號為：8、55、183、79、83、160、255、365、302、421、5、17、13、72、11、121、180、200、340、263、38、175、438、411、393、10、45、383、415、400。

將標準遺傳算法和改進遺傳算法分別應用于機場貨運站的ETV 調(diào)度優(yōu)化中，用MATLAB7.11 進行仿真實驗。初始種群個體為30 個，代溝為0.9，雜交率為0.7，變異率為0.02，使用標準遺傳算法和改進遺傳算法分別進行500 次迭代。

為了更好地顯示改進遺傳算法的優(yōu)越性，分別比較其與標準遺傳算法的單次優(yōu)化效果和進行多次優(yōu)化后性能的提升，對比結(jié)果如圖4 和圖5 所示。

對試驗數(shù)據(jù)對比分析得出：用標準的遺傳算法進行優(yōu)化在迭代400 代左右后可得到最優(yōu)解5 600s，而改進的遺傳算法在迭代300 次后就得到最優(yōu)解5 200s，優(yōu)化提升7.14%，計算時間大約縮短20%。在前100 次的迭代中，改進遺傳算法的收斂速度明顯快于標準遺傳算法。同時，由圖5 可看出，將改進的遺傳算法與標準的遺傳算法選用相同參數(shù)分別優(yōu)化20 次，改進遺傳算法每次優(yōu)化的結(jié)果都維持在5 200 秒左右，變化很平穩(wěn)，而用標準遺傳算優(yōu)化會出現(xiàn)較突出的波動，最嚴重時可達到2%。

4 結(jié) 論

本文使用柔性S 型運動曲線模型，保證了ETV 運動的平穩(wěn)性，大大減少了運動過程中貨物的沖擊；運用組合優(yōu)化的思想對標準遺傳算法選擇、交叉、變異三個算子進行改進并應用于ETV 的調(diào)度作業(yè)，相比標準的遺傳算法具有更好的可收斂性，避免了標準遺傳算法陷入局部最優(yōu)解的缺陷，同時提高了優(yōu)化效率，節(jié)約了計算時間。仿真結(jié)果證明，該算法對于提高ETV 的調(diào)度效率是有效的，提高貨運站的服務質(zhì)量，降低運行成本都有積極意義。在今后的研究中，可考慮當多臺ETV 同時運行于一條軌道上的情況，從而使貨運站的吞吐量效率更高。

[1] 邱建東. 大型機場貨運站核心物流裝備調(diào)度優(yōu)化問題研究[D]. 蘭州：蘭州交通大學，2014.

[2] 張汝成，王廣生，聶玉同. 電梯系統(tǒng)的高精度S 型速度曲線的生成和實現(xiàn)[J]. 起重運輸機械，2009(4):6-10.

[3] 劉筱，吳文江，鄭飂默. 柔性S 型加減速控制算法研究[J]. 組合機床與自動化加工技術(shù)，2013(3):66-69.

[4] 陳建安，郭大偉，徐乃平,等. 遺傳算法理論研究綜述[J]. 西安電子科技大學學報，1998(6):363-367.

[5] 李曉輝，鄔義杰，冷洪濱. S 曲線加減速控制新方法的研究[J]. 組合機床與自動化加工技術(shù)，2007(10):50-53.

[6] 張超勇，饒運清，李培根,等. 求解作業(yè)車間調(diào)度問題的一種改進遺傳算法[J]. 計算機集成制造系統(tǒng)，2004(8):966-971.

[7] 羅勇，陳治亞. 基于改進遺傳算法的物流配送路徑優(yōu)化[J]. 系統(tǒng)工程，2012(8):118-123.

[8] 劉巍巍，趙紅，王迎春. 遺傳算法在自動化倉庫路徑調(diào)度問題中的應用[J]. 沈陽工業(yè)大學學報，2008(6):338-341.

[9] 王廳長，邱建東，商慶健,等. 病毒協(xié)同進化遺傳算法在自動化立體倉庫貨位優(yōu)化中應用的研究[J]. 計算機科學，2014(11):35-38.

[10] 李建鋒，彭艦. 云計算環(huán)境下基于改進遺傳算法的任務調(diào)度算法[J]. 計算機應用，2013(11):184-187.

[11] 趙亮，宋宇博，蔣兆遠. BP 神經(jīng)網(wǎng)絡在機場貨運站生產(chǎn)調(diào)度中的應用[J]. 起重運輸機械，2009(11):39-42.