遺傳算法在固定貨架堆垛機(jī)揀選路徑優(yōu)化中的應(yīng)用

倪 虹，李發(fā)強(qiáng)

（1.蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070；2.中鐵六局集團(tuán)天津鐵路建設(shè)有限公司，天津 300140）

遺傳算法在固定貨架堆垛機(jī)揀選路徑優(yōu)化中的應(yīng)用

倪 虹1，李發(fā)強(qiáng)2

（1.蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070；2.中鐵六局集團(tuán)天津鐵路建設(shè)有限公司，天津 300140）

固定貨架的揀選路徑優(yōu)化問題是一個(gè)典型的TSP問題。以堆垛機(jī)揀選路徑作為研究目標(biāo)，通過計(jì)算貨位點(diǎn)所在的坐標(biāo)位置產(chǎn)生揀選點(diǎn)。運(yùn)用基于順序的遺傳基因編碼方式編制程序，對揀選路徑進(jìn)行優(yōu)化。仿真實(shí)驗(yàn)和實(shí)際應(yīng)用表明該算法能較快找到最優(yōu)解，并有效提高系統(tǒng)運(yùn)行效率。

遺傳算法；自動(dòng)化立體倉庫；揀選路徑優(yōu)化

0 引 言

立體倉庫有三部分組成貨架區(qū)、輸送系統(tǒng)、分揀系統(tǒng)。如圖1貨架區(qū)有多排立體貨架組成，貨架的貨格內(nèi)有貨箱。兩組貨架中間設(shè)置巷道供叉車和巷道堆垛機(jī)行走。所要揀選的貨位點(diǎn)以（x,y ）表示，其中x為列，y為層，貨格的寬度為L，高度為H。操作人員在正式執(zhí)行揀選操作之前，將表單上的所有任務(wù)通過控制面板輸入到叉車的控制系統(tǒng)中，每當(dāng)一個(gè)揀選路徑完成，就按下面板上指定的按鈕，堆垛機(jī)自動(dòng)運(yùn)行到下一個(gè)揀選位置，直到所有任務(wù)完成。

1 揀選路徑優(yōu)化問題的模型

固定貨架及堆垛機(jī)運(yùn)行參數(shù)設(shè)定如下：

設(shè)定1 以揀選方式進(jìn)行揀選作業(yè)時(shí)，操作者對任何貨物的存取速度都是恒定的，不因揀選順序的改變而改變。

設(shè)定2 堆垛機(jī)存取貨物時(shí)在水平方向和垂直方向都是恒高速運(yùn)行的，水平速度Vx，垂直速度Vy；堆垛機(jī)運(yùn)行時(shí)在水平方向和垂直方向可以同時(shí)運(yùn)動(dòng)。

設(shè)定3將貨位點(diǎn)（0,0 ）作為巷道入口。貨架單個(gè)貨格寬度為L，高度為H。

根據(jù)上述模型參數(shù)，堆垛機(jī)由貨位n運(yùn)行到貨位m所需時(shí)間為：

其中， （xn,yn）， （xm, ym）分別為貨位點(diǎn)n,m的坐標(biāo)。

因此，揀選完一個(gè)貨單所有條目所需總時(shí)間T為：

揀選路徑的優(yōu)化目標(biāo)是：合理選取揀選路徑，求得最優(yōu)揀選序列使總揀選時(shí)間T最小，這一組合優(yōu)化問題稱為固定貨架揀選作業(yè)的優(yōu)化問題。此類問題可歸結(jié)為組合優(yōu)化問題中的旅行商問題 （TSP），屬于NP-C問題。

2 算法分析

2.1 遺傳算法 （Genetic Algorithm）優(yōu)化原理

遺傳算法 （Genetic Algorithm）是一種基于生物自然選擇和基因遺傳學(xué)原理的優(yōu)化搜索算法。它將 “優(yōu)勝劣汰，適者生存”的生物進(jìn)化原理引入待優(yōu)化參數(shù)中，對問題可行解的編碼進(jìn)行操作，可以用不同的編碼方法來表示不同問題的可行解，遺傳算法就是通過對生物基因的選擇、交叉和變異這三種方式的模擬來實(shí)現(xiàn)其優(yōu)化過程。

2.2 選 擇

評價(jià)函數(shù)是自然界中適者生存的基本依據(jù)。利用評價(jià)函數(shù)選擇染色體的一般原則是適合于生存環(huán)境的優(yōu)良染色體以較大概率被選擇而得以進(jìn)入種群，反之劣質(zhì)的染色體被選入種群的概率較小。

一般可采用基于序的評價(jià)函數(shù)，首先將群體排序，之后依據(jù)以下方式進(jìn)行選擇。

評價(jià)函數(shù)可以作為群體中染色體被選入種群的概率，利用評價(jià)函數(shù)可以確定染色體進(jìn)入種群的累積概率為：

評價(jià)函數(shù)值的全體稱為 “輪盤賭”，評價(jià)函數(shù)越大，在 “輪盤”中所占比例也越大，即該染色體進(jìn)入種群的概率較大。每個(gè)染色體進(jìn)入種群的方法與完備事件的仿真方法完全一致。

2.3 交 叉

交叉是算法中獲得優(yōu)良個(gè)體的重要手段。其方法是種群中的個(gè)體作為父代，依照一定的規(guī)則相互交換特定位置的基因信息，從而產(chǎn)生繼承父代大部分信息而又不同于父代的子代染色體。一般采用雙親雙子法，則TSP問題的交叉規(guī)則如圖2所示。

選取1位 （可以是多位）基因信息，將其信息交換，為使交叉后獲得的染色體代碼屬于解空間，每一個(gè)代碼做必要的內(nèi)部交換，以防止某些節(jié)點(diǎn)被訪問多次，某些節(jié)點(diǎn)不能訪問的情況出現(xiàn)。

2.4 變 異

變異是指由父代群體產(chǎn)生的子代群體中的一些個(gè)體，其染色體的某些基因信息以較小的概率發(fā)生改變，突變?yōu)樾碌娜旧w，產(chǎn)生了具有某些非遺傳特征的個(gè)體。

變異是提高全局最優(yōu)搜索能力的有效步驟，也是保持群體差異，防止過早出現(xiàn)收斂現(xiàn)象的重要手段。通常指定一個(gè)實(shí)數(shù)α（ 0＜α＜1），并且使α的值接近0，產(chǎn)生一個(gè)（0,1 ）隨機(jī)數(shù)ε，如果ε＜α則子代群體中該染色體發(fā)生變異。

產(chǎn)生一個(gè)1：n（n為訪問節(jié)點(diǎn)總數(shù)）的自然隨機(jī)數(shù)n1，再產(chǎn)生另一個(gè)1：n的隨機(jī)自然數(shù)n2，如果n1=n2，重新生成，直至n1≠n2，交換編碼中第n1與第n2位置的編碼信息，變異規(guī)則如圖3所示。

3 算 例

綜合以上算法分析，應(yīng)用遺傳算法求解TSP問題。在某立體倉庫中，隨機(jī)產(chǎn)生30個(gè)貨位點(diǎn)的揀選單，各貨位點(diǎn)坐標(biāo)如表1，圖4所示。堆垛機(jī)從倉庫原位出發(fā)揀選物品，最后回到原位，要求路徑最短。

表1

通過仿真計(jì)算，找到最優(yōu)路徑：

最優(yōu)值為：514.67

4 結(jié) 論

隨著自動(dòng)化立體倉庫的迅速發(fā)展，揀選作業(yè)路徑的優(yōu)化與否直接影響倉庫作業(yè)的運(yùn)行效率。遺傳算法簡單實(shí)用，又具有全局尋優(yōu)的特性，且搜索效率高，能夠有效獲取全局優(yōu)化的揀選路徑，該算法在執(zhí)行效率和優(yōu)化效果方面均能很好地滿足作業(yè)要求。

[1]商允偉，劉長有，田國會(huì).神經(jīng)網(wǎng)絡(luò)在自動(dòng)化立體倉庫的一類作業(yè)優(yōu)化中的應(yīng)用[C]//1996中國控制與決策學(xué)術(shù)年會(huì)論文集，沈陽：東北大學(xué)出版社，1996：517-521.

[2]田國會(huì)，張攀，尹建芹,等.基于混合遺傳算法的固定貨架揀選優(yōu)化問題研究[J].山東大學(xué)機(jī)械工程學(xué)報(bào)，2004(2)：141-144.

[3]Ratliff,H.Donald,Rosenthal Arnon S.Order-picking in a rectangular warehouse：A solvable case of the traveling salesman problem[J].Operations Research,1983,31(3)：507-521.

[4]常發(fā)亮，劉增曉，辛征,等.自動(dòng)化立體倉庫揀選作業(yè)路徑優(yōu)化問題研究[J].系統(tǒng)工程理論與實(shí)踐，2007(2)：139-143.

[5]Davis L．Adapting operator probabilities in genetic algorithm[C]//Proceedings of the third international conference on genetic algorithms,George Mason University,United States,1989：61-69.

Application of the Genetic Algorithm in Order-Picking Rules Optimization for a Fixed-Shelf System

NI Hong1,LI Fa-qiang2

(1.Lanzhou Jiaotong University,School of Traffic and Transportation,Lanzhou 730070,China;2.China Railway Sixth Group Tianjin Railway Construction Co.,LTD.,Tianjin 300140,China)

The order-picking rules optimization for a fixed-system is a typical TSP.Genetic algorithm is adopted to resolve the order-picking problem,through the calculation of position in the coordinate location get picking materials.The program based on genetic coding manner is utilized to optimize the order-picking rules.The simulation test and application show that it can find optimal solutions with less time and effectively improve the system efficiency.

genetic algorithm;automated warehouse;order-picking optimization

F406.5

A

1002-3100(2011)10-0072-04

2011-08-12

倪 虹（1986-），女，江蘇儀征人，蘭州交通大學(xué)交通運(yùn)輸學(xué)院碩士研究生，研究方向：交通運(yùn)輸規(guī)劃與管理；李發(fā)強(qiáng)（1981-），男，甘肅白銀人，中鐵六局集團(tuán)天津鐵路建設(shè)有限公司，經(jīng)濟(jì)師。