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

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

0 引言

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

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

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

1 圖表轉(zhuǎn)化

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

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

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

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

2 遺傳算法

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

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

2.2 改進(jìn)的遺傳算法

2.2.1 初始種群

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

2.2.2 更新種群

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

圖1 更新種群流程圖

3 實(shí)驗(yàn)

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

圖2 倉儲(chǔ)部署圖

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

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

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

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

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

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

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

圖6 染色體的最終位置圖

4 結(jié)語

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

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

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

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

[4] 周建國.基于改進(jìn)遺傳算法的農(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] 李延梅. 一種改進(jìn)的遺傳算法及應(yīng)用[D].廣州：華南理工大學(xué),2012.

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