遺傳算法在固定貨架堆垛機揀選路徑優化中的應用

倪 虹，李發強

（1.蘭州交通大學 交通運輸學院，甘肅 蘭州 730070；2.中鐵六局集團天津鐵路建設有限公司，天津 300140）

遺傳算法在固定貨架堆垛機揀選路徑優化中的應用

倪 虹1，李發強2

（1.蘭州交通大學 交通運輸學院，甘肅 蘭州 730070；2.中鐵六局集團天津鐵路建設有限公司，天津 300140）

固定貨架的揀選路徑優化問題是一個典型的TSP問題。以堆垛機揀選路徑作為研究目標，通過計算貨位點所在的坐標位置產生揀選點。運用基于順序的遺傳基因編碼方式編制程序，對揀選路徑進行優化。仿真實驗和實際應用表明該算法能較快找到最優解，并有效提高系統運行效率。

遺傳算法；自動化立體倉庫；揀選路徑優化

0 引 言

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

1 揀選路徑優化問題的模型

固定貨架及堆垛機運行參數設定如下：

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

設定2 堆垛機存取貨物時在水平方向和垂直方向都是恒高速運行的，水平速度Vx，垂直速度Vy；堆垛機運行時在水平方向和垂直方向可以同時運動。

設定3將貨位點（0,0 ）作為巷道入口。貨架單個貨格寬度為L，高度為H。

根據上述模型參數，堆垛機由貨位n運行到貨位m所需時間為：

其中， （xn,yn）， （xm, ym）分別為貨位點n,m的坐標。

因此，揀選完一個貨單所有條目所需總時間T為：

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

2 算法分析

2.1 遺傳算法 （Genetic Algorithm）優化原理

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

2.2 選 擇

評價函數是自然界中適者生存的基本依據。利用評價函數選擇染色體的一般原則是適合于生存環境的優良染色體以較大概率被選擇而得以進入種群，反之劣質的染色體被選入種群的概率較小。

一般可采用基于序的評價函數，首先將群體排序，之后依據以下方式進行選擇。

評價函數可以作為群體中染色體被選入種群的概率，利用評價函數可以確定染色體進入種群的累積概率為：

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

2.3 交 叉

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

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

2.4 變 異

變異是指由父代群體產生的子代群體中的一些個體，其染色體的某些基因信息以較小的概率發生改變，突變為新的染色體，產生了具有某些非遺傳特征的個體。

變異是提高全局最優搜索能力的有效步驟，也是保持群體差異，防止過早出現收斂現象的重要手段。通常指定一個實數α（ 0＜α＜1），并且使α的值接近0，產生一個（0,1 ）隨機數ε，如果ε＜α則子代群體中該染色體發生變異。

產生一個1：n（n為訪問節點總數）的自然隨機數n1，再產生另一個1：n的隨機自然數n2，如果n1=n2，重新生成，直至n1≠n2，交換編碼中第n1與第n2位置的編碼信息，變異規則如圖3所示。

3 算 例

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

表1

通過仿真計算，找到最優路徑：

最優值為：514.67

4 結 論

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

[1]商允偉，劉長有，田國會.神經網絡在自動化立體倉庫的一類作業優化中的應用[C]//1996中國控制與決策學術年會論文集，沈陽：東北大學出版社，1996：517-521.

[2]田國會，張攀，尹建芹,等.基于混合遺傳算法的固定貨架揀選優化問題研究[J].山東大學機械工程學報，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]常發亮，劉增曉，辛征,等.自動化立體倉庫揀選作業路徑優化問題研究[J].系統工程理論與實踐，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-），女，江蘇儀征人，蘭州交通大學交通運輸學院碩士研究生，研究方向：交通運輸規劃與管理；李發強（1981-），男，甘肅白銀人，中鐵六局集團天津鐵路建設有限公司，經濟師。