改進(jìn)遺傳算法在ETV 調(diào)度優(yōu)化中的應(yīng)用研究

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

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

0 引 言

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

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

1 ETV 運(yùn)行的數(shù)學(xué)模型建立

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

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

進(jìn)而可以得到：

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

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

表1 ETV 運(yùn)行參數(shù)

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

那么ETV 在兩個(gè)貨位點(diǎn)之間運(yùn)行的時(shí)間開(kāi)銷為：

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

由以上分析可知，完成1 個(gè)集裝貨物任務(wù)的操作的時(shí)間為：

2 遺傳算法計(jì)算與求解

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

2.1 選擇編碼策略

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

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

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

將目標(biāo)函數(shù)進(jìn)行變換可得到適應(yīng)度函數(shù)，依據(jù)目標(biāo)函數(shù)要遍歷所有等待任務(wù)的貨位點(diǎn)而費(fèi)時(shí)最短原則，目標(biāo)函數(shù)可定義為：

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

表2 編碼號(hào)與貨位號(hào)對(duì)照表

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

2.3 遺傳算法的三個(gè)算子的改進(jìn)

2.3.1 基于序的選擇算子設(shè)計(jì)

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

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

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

2.3.2 基于普萊姆算法的交叉算子設(shè)計(jì)

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

用普萊姆算法生成最小代價(jià)樹(shù)的例子如圖3 所示。

最小代價(jià)樹(shù)生成方法如下：

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

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

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

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

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

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

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

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

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

2.3.3 基于隨機(jī)時(shí)間長(zhǎng)度的變異算子設(shè)計(jì)

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

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

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

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

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

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

3 仿真驗(yàn)證

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

有30 個(gè)入庫(kù)任務(wù)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 個(gè)出庫(kù)任務(wù)C1～C30，貨位編號(hào)為：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。

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

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

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

4 結(jié) 論

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

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

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

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

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

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

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

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

[8] 劉巍巍，趙紅，王迎春. 遺傳算法在自動(dòng)化倉(cāng)庫(kù)路徑調(diào)度問(wèn)題中的應(yīng)用[J]. 沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2008(6):338-341.

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

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

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