馮晨鐘，宋世創(chuàng)，李慕航

(山西農(nóng)業(yè)大學，山西 太谷 030800)

0 引言

近幾年，電子商務在我國高速發(fā)展，快遞行業(yè)發(fā)展迅猛，部分派件點經(jīng)常出現(xiàn)排隊現(xiàn)象，派件時間效率等都受到限制。本論文深入研究智能派件，倉儲系統(tǒng)中通常有多輛小車并發(fā)執(zhí)行任務，遺傳算法、蟻群等算法可以解決單個小車到達目的地的最短路徑問題，如果兩車即將發(fā)生碰撞，通常采用優(yōu)先級的方式依靠停車進行錯車，這樣做雖然路程最短，但忽略了停車時間的長短，在智能派件中時間參數(shù)是我們考慮的第一要素。

梁肖[1]將遺傳算法的路徑優(yōu)化應用到小麥收割機的收割過程；何慶[2]提出一種改進自適應的Metropolis準則,使模擬退火算法部分的染色體跳變更具有自適應性,利于算法尋優(yōu)解決遺傳算法一出現(xiàn)局部最優(yōu)的問題；申艷光[3]提出了通過聚類分析中K-means算法與改進遺傳算法相結合的混合遺傳算法，實現(xiàn)優(yōu)化配送路線；周建國[4]將遺傳算法應用到農(nóng)產(chǎn)品配送的路徑優(yōu)化上，提高其配送效率。

遺傳算法在優(yōu)化路徑方面達到很好的效果，論文結合實際把遺傳算法應用到倉儲機器人的路徑優(yōu)化問題，解決多個機器人在同一倉庫工作的沖突問題。

1 圖表轉(zhuǎn)化

采用柵格法對倉庫實際與計算能識別的矩陣建立對應關系。柵格法實質(zhì)上是將AGV的工作環(huán)境進行單元分割，將其用大小相等的方塊表示出來，這樣柵格大小的選取是影響規(guī)劃算法性能的一個很重要的因素。通常邊長應該略大于小車的長度，方便小車在格柵中行走。本文考慮小車所在的環(huán)境因素，對小車環(huán)境進行抽象描述：以邊長為a*a的正方形格為單位，將小車所在環(huán)境進行分解，建立起形狀相似、面積相同的柵格圖。

格柵與路徑權值：設置速度和格柵的邊長(考慮小車的長度)得到每個柵格的權值，論文把該值設為2S，即小車通過一個格柵的權值為2。

在柵格圖中定義左上角第一個柵格坐標(0,0)，橫向為x軸，縱向為y軸建立直角坐標系。假設倉儲長為L米(對應縱坐標)，寬W米(對應橫坐標)，以邊長為a米的單元柵格為單位，則每行的方格數(shù)為h(W/a)，每列的方格數(shù)為v(L/a)。

柵格編號：id=y*(W/a)+(x+1)

2 遺傳算法

2.1 傳統(tǒng)遺傳算法

遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。遺傳算法的操作使用符合適者生存原則，在潛在的解決方案種群中逐次產(chǎn)生一個近似最優(yōu)的方案，在遺傳算法的每一代中，根據(jù)個體的問題域中的適應度值和從自然遺傳學中借鑒來的改造方法進行個體選擇，產(chǎn)生一個新的近似解。使得種群中的個體進化，更適應環(huán)境。

2.2 改進的遺傳算法

2.2.1 初始種群

傳統(tǒng)遺傳算法的初始群體固定不變，計算的行走距離只考慮路徑的路程，即長度,相當于只考慮靜態(tài)的路徑，沒有考慮多輛車同時執(zhí)行任務避障的時間。

2.2.2 更新種群

每一輛小車的行走路徑都要在已經(jīng)規(guī)劃好并且還未執(zhí)行完的路徑的基礎上進行設計規(guī)劃。首先判斷新路徑和已經(jīng)存在的路徑是否存在交叉，交叉包括路徑上的交叉和時間上的交叉，在路徑交叉的基礎上判斷是否時間交叉。如果存在時間交叉(獲取到達該段的時刻，判斷其是否在鎖定時間)，即該路段處于上鎖狀態(tài)，如果不存在時間交叉，即處于解鎖狀態(tài)。通過權值的動態(tài)變換來更新種群。更新種群流程圖如圖1所示。

圖1 更新種群流程圖

3 實驗

為了驗證算法適應性，分別進行了貨架數(shù)量為2和貨架數(shù)量為6的仿真實驗。當貨架數(shù)量為6，倉儲部署圖如圖2所示。

圖2 倉儲部署圖

抽象及權值簡化圖(本文涉及的倉儲簡化圖中的黑點表示起點和終點)如圖3所示，將倉儲實際跟遺傳算法的用種群矩陣建立聯(lián)系。

假設此車規(guī)劃路徑時，⑥-⑦與其他車已規(guī)劃好的路徑存在非同向交叉。

圖3 抽象及權值簡化圖

傳統(tǒng)遺傳算法運行的最優(yōu)、平均函數(shù)值如圖4所示，30代左右，最優(yōu)函數(shù)值趨于穩(wěn)定；從對比及最優(yōu)函數(shù)值變化趨勢可知，該算法可以很好地解決倉儲的最優(yōu)路徑規(guī)劃問題。

圖4 最優(yōu)，平均函數(shù)值變化趨勢圖

更新種群后權值簡化圖如圖5所示。圖6為染色體最終位置圖。從染色體的最終效果可以看出算法能很好地解決沖突問題，實現(xiàn)路徑最優(yōu)化。

圖5 更新種群后的權值簡化圖

圖6 染色體的最終位置圖

4 結語

本文采用遺傳算法實現(xiàn)倉儲機器人的路徑規(guī)劃，采用時間同步、上鎖與解鎖的方法解決多車執(zhí)行任務中出現(xiàn)的沖突、碰撞等問題，建立了自適應的種群更新機制。該方法對遺傳算法的種群進行了更新，實現(xiàn)根據(jù)實際情況的自適應種群。仿真和模擬實驗表明，該算法可以有效解決兩車或多車經(jīng)過同一點的沖突問題，采用傳統(tǒng)的遺傳算法實現(xiàn)處理后的種群的最優(yōu)路徑的選擇。本文改進的遺傳算法達到了仿真及模擬實驗的要求，取得了較好的效果。

[1] 梁肖,周湘貞.基于遺傳算法的小麥收割機路徑智能優(yōu)化控制研究[J].農(nóng)機化研究,2018,40(2):56-60.

[2] 何慶,吳意樂,徐同偉.改進遺傳模擬退火算法在TSP優(yōu)化中的應用[J].控制與決策,2018,33(2):219-225.

[3] 申艷光,張玲玉 ,劉永紅.基于混合遺傳算法的物流路徑優(yōu)化方法研究[J/OL].計算機技術與發(fā)展, 2018(3)[2018-04-07] http://kns.cnki.net/kns/brief/default_result.aspx.

[4] 周建國.基于改進遺傳算法的農(nóng)產(chǎn)品配送路徑優(yōu)化研究[J].中國市場,2018(1):136-138.

[5] ChenLin.An Adaptive Genetic Algorithm based on Population Diversity Stratety [A].Junfa Mao.2009 Third International Conference on Genetic and EvolutionaryComputing[C],New York:IEEE,2009:93-96.

[6] 李延梅. 一種改進的遺傳算法及應用[D].廣州：華南理工大學,2012.

[7] 梁芳. 遺傳算法的改進及其應用[D].武漢：武漢理工大學,2008.