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

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

0 引言

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

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

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

1 圖表轉(zhuǎn)化

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

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

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

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

2 遺傳算法

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

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

2.2 改進的遺傳算法

2.2.1 初始種群

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

2.2.2 更新種群

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

圖1 更新種群流程圖

3 實驗

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

圖2 倉儲部署圖

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

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

圖3 抽象及權(quán)值簡化圖

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

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

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

圖5 更新種群后的權(quán)值簡化圖

圖6 染色體的最終位置圖

4 結(jié)語

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

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

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

[3] 申艷光,張玲玉 ,劉永紅.基于混合遺傳算法的物流路徑優(yōu)化方法研究[J/OL].計算機技術(shù)與發(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] 李延梅. 一種改進的遺傳算法及應(yīng)用[D].廣州：華南理工大學(xué),2012.

[7] 梁芳. 遺傳算法的改進及其應(yīng)用[D].武漢：武漢理工大學(xué),2008.