物流中心多AGV無碰撞路徑規(guī)劃

楊 潔，田 釗，劉國寧

（1.鄭州大學(xué)機(jī)械與動(dòng)力工程學(xué)院，河南 鄭州 450001；2.鄭州大學(xué)軟件學(xué)院，河南 鄭州 450002）

1 引言

近年來隨著企業(yè)對(duì)倉儲(chǔ)物流中心自動(dòng)化水平的需求的不斷提高，AGV已經(jīng)成為了決定物流中心工作效率的主要運(yùn)輸工具，主要負(fù)責(zé)物流中心、車間等區(qū)域的包裹或物料運(yùn)輸。因此，AGV的運(yùn)輸效率和協(xié)調(diào)能力也就成為了決定倉儲(chǔ)物流自動(dòng)化水平高低的主要因素之一。

目前，AGV 的路徑優(yōu)化已經(jīng)成為國內(nèi)外于倉儲(chǔ)物流中的主要研究問題之一，為了規(guī)劃出無死鎖無沖突的路徑，學(xué)者們采用了不同的算法對(duì)AGV進(jìn)行路徑規(guī)劃［1］。文獻(xiàn)［2］將A*算法和D*Lite算法相結(jié)合完成了對(duì)路徑規(guī)劃問題的解決。 文獻(xiàn)［3］采用混合啟發(fā)式算法對(duì)帶有時(shí)間窗的車輛進(jìn)行路徑規(guī)劃，使得行駛的路徑最短。文獻(xiàn)［4］使用改進(jìn)的A*算法生成候選路徑，提出了兩種啟發(fā)式時(shí)間窗搜索算法以搜索每條候選路徑上的空閑時(shí)間窗組合進(jìn)而完成了對(duì)物流中心AGV路徑進(jìn)行規(guī)劃。文獻(xiàn)［5］通過增加AGV共享路徑的懲罰值來改進(jìn)A*算法并完成了對(duì)智能倉儲(chǔ)中AGV的無碰撞路徑規(guī)劃。文獻(xiàn)［6］將傳統(tǒng)的人工蜂群算法和粒子群算法思想相結(jié)合提出了混合蟻群粒子群的方法，通過此方法完成了對(duì)智能倉庫中AGV搬運(yùn)貨物的路徑優(yōu)化。文獻(xiàn)［7］采用改進(jìn)的Dijkstra算法和時(shí)間窗相結(jié)合的方法對(duì)碰撞進(jìn)行分類，并基于碰撞類型實(shí)現(xiàn)了自動(dòng)化倉庫系統(tǒng)中多AGV的路徑規(guī)劃。文獻(xiàn)［8］通過對(duì)A*算法進(jìn)行改進(jìn)減少了AGV的運(yùn)輸路徑長(zhǎng)度，實(shí)現(xiàn)了對(duì)AGV路徑的規(guī)劃并提高了AGV的運(yùn)行效率。

目前針對(duì)采用遺傳算法求解多AGV路徑的研究相對(duì)較少。本研究專注于對(duì)多路徑、多節(jié)點(diǎn)的復(fù)雜場(chǎng)景中的多AGV作業(yè)路徑進(jìn)行優(yōu)化，提出了基于遺傳算法和時(shí)間推理相結(jié)合的多AGV路徑規(guī)劃的兩種模型，然后設(shè)計(jì)實(shí)驗(yàn)并將兩種模型的實(shí)驗(yàn)結(jié)果進(jìn)行了分析和對(duì)比。本研究對(duì)復(fù)雜條件下多AGV路徑規(guī)劃問題的解決具有參考意義。

2 問題描述

2.1 場(chǎng)景描述

這里以典型倉儲(chǔ)物流中心分揀庫區(qū)為應(yīng)用背景進(jìn)行研究。整體按照功能布局，分為貨架區(qū)，運(yùn)輸區(qū)以及工作臺(tái)區(qū)。貨架區(qū)和工作區(qū)之間為AGV運(yùn)輸區(qū)。如圖1所示，貨架1區(qū)和貨架2區(qū)分別由2行5列共10個(gè)貨架組成，中間區(qū)域?yàn)锳GV運(yùn)輸區(qū)，右側(cè)工作臺(tái)區(qū)由3個(gè)工作臺(tái)組成。分揀庫區(qū)的作業(yè)過程為AGV將目標(biāo)貨架運(yùn)送到相應(yīng)的工作臺(tái)，隨后員工完成揀選、掃碼以及裝箱等業(yè)務(wù)。AGV越多，越有利于提高效率，但也大大增加AGV之間的碰撞概率。為了避免碰撞現(xiàn)象的產(chǎn)生，此研究從多AGV路徑規(guī)劃方面著手進(jìn)行研究；為了給AGV規(guī)劃路徑和計(jì)算路徑的長(zhǎng)度以及完成任務(wù)花費(fèi)的時(shí)間，此研究采用拓?fù)浣７▽?duì)物流分揀場(chǎng)景進(jìn)行數(shù)學(xué)建模并采用鄰接矩陣的方法對(duì)有向圖G(V，E)進(jìn)行表示。

圖1 拓?fù)浣７?gòu)建的地圖Fig.1 Topological Model of the Logistics Center

在有向圖G(V，E)中，V代表圖中的頂點(diǎn)集合，E代表連接相鄰兩頂點(diǎn)的邊的集合，每條邊用兩個(gè)頂點(diǎn)的有序元素對(duì)(Vi，Vj)進(jìn)行表示［9］，并且每條邊都有對(duì)應(yīng)的權(quán)重W(Vi，Vj)。這里用一個(gè)|V|×|V|階的鄰接矩陣A來存儲(chǔ)各邊的權(quán)重并把每條邊的長(zhǎng)度d(Vi，Vj)作為此邊權(quán)重W(Vi，Vj)。若節(jié)點(diǎn)Vi和Vj之間有邊線存在，則這條邊的邊的實(shí)際長(zhǎng)度d(Vi，Vj)為這條邊的權(quán)重W(Vi，Vj)，否則，此邊的權(quán)重為∞，當(dāng)用矩陣A進(jìn)行存儲(chǔ)此邊時(shí)先用一個(gè)正數(shù)除以0得到一個(gè)正無窮大，再通過Double的POSITIVE_INFINITY進(jìn)行表示，最后進(jìn)行存儲(chǔ)。本研究采用頂點(diǎn)的有序集合來代表路徑［10］，頂點(diǎn)的排列順序代表路徑經(jīng)過各個(gè)頂點(diǎn)的順序，依次找出相鄰兩個(gè)頂點(diǎn)間的邊進(jìn)行連接就可以表示出這條路徑。

基于應(yīng)用場(chǎng)景，這里提出以下規(guī)定：

（1）每輛AGV在任意一條邊均為雙向行駛，每個(gè)頂點(diǎn)僅允許一輛AGV占用。

（2）每輛AGV 運(yùn)行過程中速度保持不變且所有AGV 速度相同。

（3）每輛AGV在頂點(diǎn)處90度拐彎時(shí)需要0.5s。

（4）圖中單一路徑長(zhǎng)度均為3m，每輛AGV 的車身長(zhǎng)度約為1.2m，頂點(diǎn)為圓形且直徑與車長(zhǎng)相同。

（5）所有貨架的規(guī)格均相同且貨架長(zhǎng)度與AGV長(zhǎng)度相同。

（6）物料運(yùn)輸終點(diǎn)的工作臺(tái)節(jié)點(diǎn)不作為AGV通過節(jié)點(diǎn)。

（7）此場(chǎng)景未考慮避障問題。

2.2 沖突類型描述

運(yùn)輸過程中AGV之間可能出現(xiàn)的沖突類型有：

2.2.1 節(jié)點(diǎn)沖突

類型一：如圖2（a）所示，AGV1由西向東行駛，AGV2由南向北行駛，兩輛AGV同時(shí)到達(dá)頂點(diǎn)就會(huì)發(fā)生沖突，這類沖突為節(jié)點(diǎn)沖突的第一種類型。

類型二：如圖2（b）所示，AGV1由西向東行駛，AGV2先由南向北行駛到達(dá)頂點(diǎn)處拐彎由西向東行駛，兩輛AGV同時(shí)到達(dá)頂點(diǎn)就會(huì)發(fā)生沖突，這類沖突為節(jié)點(diǎn)沖突的第二種類型。

類型三：如圖2（c）所示，AGV1先由西向東行駛?cè)缓笤陧旤c(diǎn)處拐彎由南向北行駛，AGV2先由南向北行駛到達(dá)頂點(diǎn)處拐彎由西向東行駛，兩輛AGV同時(shí)到達(dá)頂點(diǎn)就會(huì)發(fā)生沖突，這類沖突為節(jié)點(diǎn)沖突的第三種類型。

類型四：如圖2（d）所示，AGV1先由西向東行駛?cè)缓笤陧旤c(diǎn)處拐彎由南向北行駛，AGV2由南向北行駛，兩輛AGV同時(shí)到達(dá)頂點(diǎn)就會(huì)發(fā)生沖突，這類沖突為節(jié)點(diǎn)沖突的第四種類型。

圖2 節(jié)點(diǎn)沖突Fig.2 Node Conflict

2.2.2 線路沖突

AGV1 由西向東行駛，AGV2 由東向西行駛，兩輛AGV 相向行駛就會(huì)發(fā)生沖突，這種沖突為線路沖突，如圖3所示。

圖3 線路沖突Fig.3 Line Conflict

2.3 路徑規(guī)劃模型一

2.3.1 模型一符號(hào)說明

以圖1為例進(jìn)行研究，研究中要計(jì)算每輛AGV 行駛的路徑長(zhǎng)度、到達(dá)路徑中每個(gè)頂點(diǎn)的時(shí)間，以及從每個(gè)頂點(diǎn)出發(fā)的時(shí)間。下述以kn為例給出相應(yīng)的計(jì)算方法，其中，kn表示序號(hào)為n的AGV。

（1）kn從起點(diǎn)Ps到終點(diǎn)Gs路徑Jn=(Vs1，Vs2，Vs3，…，Vsm)的總長(zhǎng)度［8］Ln：

（2）kn在行駛過程中到達(dá)第L個(gè)頂點(diǎn)附近的時(shí)間TnL：

（3）kn開始進(jìn)入第L個(gè)頂點(diǎn)的時(shí)間：

（4）kn在行駛過程中從第L個(gè)頂點(diǎn)出發(fā)的時(shí)間TnLf：

式中：Tn(L-1)f—kn在第(L- 1 )個(gè)頂點(diǎn)處出發(fā)的時(shí)間；v—kn的速度；l—圓形節(jié)點(diǎn)的直徑；tnL—kn在第L個(gè)頂點(diǎn)附近等待的時(shí)間；ts—kn的出發(fā)時(shí)間，即給kn發(fā)放任務(wù)的時(shí)間；tc—在第L個(gè)頂點(diǎn)的轉(zhuǎn)彎時(shí)間。

假設(shè)K{k1，k2，…，kn} 為所有AGV 的集合，R{r1，r2，r3…，rt}為所有任務(wù)的集合，P{p1，p2，p3，…，pt} 為所有任務(wù)起點(diǎn)的集合，G{g1，g2，g3，…，gt} 為所有任務(wù)終點(diǎn)的集合，這里則用r s={s，ts，ps，gs，kn} 表示用kn去完成出發(fā)時(shí)間為ts，起點(diǎn)為ps終點(diǎn)為gs的任務(wù)，其中，s∈{1 ，2，3，…，t}ps∈Pgs∈Gkn∈K，kn從起點(diǎn)ps到終點(diǎn)gs的行駛路徑表示為Jn=(Vs1，Vs2，Vs3，…，Vsm)；到達(dá)路徑中各個(gè)頂點(diǎn)附近的時(shí)間為Mn =(Tn1，Tn2，Tn3，…，Tnm)；開始進(jìn)入各個(gè)頂點(diǎn)的時(shí)間為從各個(gè)節(jié)點(diǎn)出發(fā)的時(shí)間Mnf=(Tn1f，Tn2f，Tn3f，…，Tnmf)；kn與ki在行駛過程中經(jīng)過相同點(diǎn)的序列為Dni=(VP1，VP2，VP3，…，VPe)。

2.3.2 第一類模型建立

本模型中含t個(gè)任務(wù)，n輛AGV，且t≤n，所有AGV的出發(fā)點(diǎn)均為它們攜帶的任務(wù)的起點(diǎn)。

（1）車輛的優(yōu)先級(jí)規(guī)則

在取貨區(qū)AGV無優(yōu)先級(jí)排序；在運(yùn)輸區(qū)AGV的優(yōu)先級(jí)由kn的序號(hào)決定，序號(hào)n越小優(yōu)先級(jí)越高。當(dāng)優(yōu)先級(jí)高的AGV和優(yōu)先級(jí)低的AGV預(yù)計(jì)同一時(shí)刻到達(dá)某一頂點(diǎn)，優(yōu)先級(jí)高的AGV可以直接通行，優(yōu)先級(jí)低的AGV必須在此頂點(diǎn)附近進(jìn)行等待。

（2）沖突判斷方法

①節(jié)點(diǎn)沖突判斷方法

如果第i和b個(gè)AGV，即ki與kb，都經(jīng)過頂點(diǎn)VPm且i＜b，頂點(diǎn)VPm為ki的路徑中第r個(gè)頂點(diǎn)，為kb的路徑中第w個(gè)頂點(diǎn)。

當(dāng)滿足式（6）或式（8）時(shí)會(huì)發(fā)生類型一的節(jié)點(diǎn)沖突；當(dāng)滿足式（7）或式（8）時(shí)會(huì)發(fā)生類型二的節(jié)點(diǎn)沖突；當(dāng)滿足式（7）或式（9）時(shí)會(huì)發(fā)生類型三的節(jié)點(diǎn)沖突；當(dāng)滿足式（6）或式（9）時(shí)會(huì)發(fā)生類型一的節(jié)點(diǎn)沖突。

當(dāng)節(jié)點(diǎn)沖突為類型一或者類型二時(shí)，kb需等待k i的車尾完全駛離頂點(diǎn)后才可以通行，則在第w個(gè)頂點(diǎn)附近等待的時(shí)間t如式（10）所示。

當(dāng)節(jié)點(diǎn)沖突為類型三或者類型四時(shí)，kb需等到k i準(zhǔn)備從節(jié)點(diǎn)出發(fā)然后和k i同時(shí)開始運(yùn)行，則在第w個(gè)頂點(diǎn)附近等待的時(shí)間t，如式（11）所示。

②線路沖突判斷方法

由下述分發(fā)任務(wù)的方法可知，k i領(lǐng)取的任務(wù)為任務(wù)i，kb領(lǐng)取的任務(wù)為任務(wù)b，且i＜b。k i路徑中第r個(gè)頂點(diǎn)為Vir，第(r+ 1 )個(gè)頂點(diǎn)為Vi(r+1)；kb路徑中第w個(gè)頂點(diǎn)為Vbw，第(w+ 1 )個(gè)頂點(diǎn)為Vb(w+1)，則：

若式（12）、式（13）和式（14）同時(shí)滿足則k i與kb會(huì)發(fā)生相向沖突。

（3）派車方法

首先從K{k1，k2，…，kn} 中按照車輛優(yōu)先級(jí)由高到低選取m輛AGV 并按照任務(wù)順序?yàn)樗麄兏髯园l(fā)放一個(gè)任務(wù)r s={s，ts，ps，gs，ks} ，然后采用路徑規(guī)劃方法為所有AGV規(guī)劃路徑，最后為所有AGV發(fā)送指令，讓所有AGV同時(shí)開始執(zhí)行任務(wù)。

（4）路徑規(guī)劃方法

第一步：當(dāng)kn接收到發(fā)放任務(wù)r n={n，tn，pn，gn，kn} 后運(yùn)用遺傳算法為其生成一條盡可能最優(yōu)路徑Jn=(Vn1，Vn2，Vn3，…，Vnm)，然后計(jì)算出kn在行駛過程中到達(dá)路徑中各個(gè)頂點(diǎn)附近的時(shí)間Mn=(Tn1，Tn2，Tn3，…，Tnm)、開始進(jìn)入各個(gè)頂點(diǎn)的時(shí)間以及從各頂點(diǎn)出發(fā)的時(shí)間Mnf=(Tn1f，Tn2f，Tn3f，…，Tnmf)。

第二步：按照優(yōu)先級(jí)高低順序依次找出所有比kn優(yōu)先級(jí)高AGV并存儲(chǔ)與集合K1。

第三步：第一類模型路徑規(guī)劃流程，如圖4所示。

圖4 第一類模型路徑規(guī)劃流程圖Fig.4 AGV Routing Method for Model I

第四步：重復(fù)上述步驟二、三、四、五為所有AGV生成路徑并計(jì)算這些AGV達(dá)到各個(gè)頂點(diǎn)的時(shí)間和開始進(jìn)入各個(gè)頂點(diǎn)的時(shí)間以及從各個(gè)頂點(diǎn)出發(fā)的時(shí)間。

第五步：總體判斷各個(gè)AGV是否仍然存在沖突，如果存在，解決沖突，直至沒有任何沖突。

2.4 路徑規(guī)劃模型二

2.4.1 模型二符號(hào)說明

以圖1為例，研究中要計(jì)算每輛AGV行駛的路徑長(zhǎng)度、到達(dá)路徑中每個(gè)頂點(diǎn)的時(shí)間，以及從每個(gè)頂點(diǎn)出發(fā)的時(shí)間。下述以kn為例給出相應(yīng)的計(jì)算方法，其中，kn表示序號(hào)為n的AGV。時(shí)間計(jì)算方法如下所示：

（1）kn從起點(diǎn)Ps到終點(diǎn)Gs路徑的總長(zhǎng)度計(jì)算公式，如式（1）所示。kn在行駛過程中到達(dá)第L個(gè)頂點(diǎn)附近的時(shí)間計(jì)算公式，如式（2）所示。

（2）kn進(jìn)入第L個(gè)頂點(diǎn)的時(shí)間：

（3）kn在行駛過程中到達(dá)第L個(gè)頂點(diǎn)的時(shí)間：

（4）kn在行駛過程中從第L個(gè)頂點(diǎn)出發(fā)的時(shí)間：

此處符號(hào)與模型一中的符號(hào)除tnL意義不同外均相同，式（18）中：tnL為kn在第L個(gè)頂點(diǎn)上等待的時(shí)間。

此模型中的假設(shè)與模型一中的假設(shè)基本相同，不同之處在于此模型中假設(shè)添加了

2.4.2 第二類模型建立

本模型中含t個(gè)任務(wù)，n輛AGV，t≤n，所有AGV的出發(fā)點(diǎn)均為它們攜帶的任務(wù)的起點(diǎn)。

（1）車輛的優(yōu)先級(jí)規(guī)則：

在取貨區(qū)AGV無優(yōu)先級(jí)排序；在運(yùn)輸區(qū)AGV的優(yōu)先級(jí)由kn的序號(hào)決定，序號(hào)n越小優(yōu)先級(jí)越高。當(dāng)優(yōu)先級(jí)高的AGV和優(yōu)先級(jí)低的AGV預(yù)計(jì)同時(shí)到達(dá)某一頂點(diǎn)，優(yōu)先級(jí)高的AGV可以直接通行，優(yōu)先級(jí)低的AGV必須在前一點(diǎn)進(jìn)行等待直到優(yōu)先級(jí)高的AGV準(zhǔn)備從沖突節(jié)點(diǎn)出發(fā)時(shí)也從前一頂點(diǎn)準(zhǔn)備出發(fā)。

（2）沖突判斷方法

①節(jié)點(diǎn)沖突判斷方法

此處節(jié)點(diǎn)沖突的判斷方法與模型一中的節(jié)點(diǎn)沖突判斷方法相同。只是此模型中無論發(fā)生什么類型的節(jié)點(diǎn)沖突，kb的等待時(shí)間t的計(jì)算方法均相同，為：

②線路沖突判斷方法

線路沖突判斷方法與模型一中線路沖突判斷方法相同。

（3）派車方法：

派車方法與模型一的派車方法相同。

（4）路徑規(guī)劃方法：

除去步驟一和步驟三外，其他步驟與模型一中對(duì)應(yīng)步驟相同。

第一步：當(dāng)kn接收到的發(fā)放的任務(wù)r n={n，tn，pn，gn，kn} 后這里運(yùn)用遺傳的算法為其生成一條盡可能最優(yōu)的路徑Jn=(Vn1，Vn2，Vn3，…，Vnm)，然后計(jì)算出kn在行駛過程中開始進(jìn)入各個(gè)頂點(diǎn)的時(shí)間到達(dá)各個(gè)頂點(diǎn)的時(shí)間以及從各頂點(diǎn)出發(fā)的時(shí)間

第三步：第二類模型路徑規(guī)劃流程。此路徑規(guī)劃流程與第一類模型中路徑規(guī)劃流程不同之處在于對(duì)節(jié)點(diǎn)沖突的解決方法不同。第二類模型中的路徑規(guī)劃流程中如果存在節(jié)點(diǎn)沖突，kn在發(fā)生節(jié)點(diǎn)沖突頂點(diǎn)的前一頂點(diǎn)處等待t秒，與此同時(shí)，將Marr和Min發(fā)生節(jié)點(diǎn)沖突的頂點(diǎn)及其后所有頂點(diǎn)對(duì)應(yīng)的時(shí)間均增Mnf加t秒，將中kb進(jìn)行等待時(shí)所在頂點(diǎn)及其后所有頂點(diǎn)對(duì)應(yīng)的時(shí)間也依次增加t秒。

3 基于遺傳算法的路徑求解

3.1 編碼

采用二進(jìn)制編碼和排列編碼相結(jié)合的方法進(jìn)行編碼，編碼后每條染色體代表一條路徑。對(duì)于一個(gè)給定的圖形，染色體的總長(zhǎng)度為圖上頂點(diǎn)的總數(shù)目的2倍，假設(shè)圖中頂點(diǎn)的總數(shù)目為n，染色體總長(zhǎng)度即為2n。染色體上的第1位到第n位上的基因用二進(jìn)制編碼且第1位和第n位的基因值均為1，其他基因位上的基因值為0或?yàn)?由計(jì)算機(jī)隨機(jī)產(chǎn)生一個(gè)0到1之間的一個(gè)小數(shù)然后進(jìn)行四舍五入后決定；染色體上第(n+ 1 )位到第( 2n)位上的基因值為圖上各頂點(diǎn)的序號(hào)。第(n+ 1 )位放置需要求解的路徑的起始頂點(diǎn)的序號(hào)，第( 2n)位上放置結(jié)束頂點(diǎn)的序號(hào)，然后將除去頂點(diǎn)和終點(diǎn)的其他頂點(diǎn)隨機(jī)排列組合并依次放置在染色體上第(n+ 2 )位到第( 2n- 1 )位上，其中染色體上第(n+ 1 )位到第( 2n)位的頂點(diǎn)序號(hào)不可重復(fù)。一條長(zhǎng)度為10，出發(fā)點(diǎn)為頂點(diǎn)3，結(jié)束點(diǎn)為頂點(diǎn)5的染色體編碼示意圖，如圖5所示。

圖5 染色體編碼示意圖Fig.5 Coding Method for AGV Routing Path

3.2 解碼

當(dāng)產(chǎn)生一條染色體后，依次找出這條染色體上第1位到第n位的基因序列中基因值為1的基因所處的基因位的序號(hào)I，并將染色體上第(I+n)位上的基因值按順序取出放置于集合D，D中基因值為路徑中經(jīng)過的頂點(diǎn)［9］，D中的排列順序則為這個(gè)AGV在行駛過程中經(jīng)過頂點(diǎn)的先后順序。一條長(zhǎng)度為10，出發(fā)點(diǎn)為頂點(diǎn)3，然后經(jīng)過頂點(diǎn)4到達(dá)結(jié)束點(diǎn)頂點(diǎn)5的染色體解碼示意圖，如圖6所示。

圖6 染色體解碼示意圖Fig.6 Decoding Method for AGV Routing Path

3.3 適應(yīng)度函數(shù)

對(duì)于給定的圖形，先用鄰接矩陣表示出各個(gè)頂點(diǎn)之間的連接關(guān)系及每條邊的權(quán)重。因?yàn)檫@里要求解最短路徑且根據(jù)下文可知這里應(yīng)用的是輪盤賭進(jìn)行選擇，所以綜合考慮，用（1∕路徑總長(zhǎng)度）作為適應(yīng)度，適應(yīng)度函數(shù)為：

3.4 選擇

采用的選擇方法為輪盤賭選擇法，運(yùn)用這種選擇方法完成對(duì)父代P1的選擇，直接選取前代種群中適應(yīng)度值最好的個(gè)體作為母代P2。

3.5 交叉

采用單點(diǎn)交叉的方法進(jìn)行交叉。首先產(chǎn)生一個(gè)（0～1）之間的隨機(jī)數(shù)與交叉概率進(jìn)行比較，當(dāng)交叉概率大于隨機(jī)數(shù)且滿足個(gè)體不是精英時(shí)進(jìn)行交叉。交叉步驟：首先在染色體的第1位到第n位基因組中隨機(jī)選擇一個(gè)位置。然后將父代染色體此位置之前的基因（包括此位置的基因）和母類染色體的此位置之后的基因進(jìn)行組合產(chǎn)生子代染色體。當(dāng)交叉后的染色體的適應(yīng)度大于P2適應(yīng)度，保留交叉后的個(gè)體在種群中，否則保留原染色體。兩條長(zhǎng)度為10的染色體交叉示意圖，如圖7所示。

圖7 染色體交叉示意圖Fig.7 Chromosome Crossing Diagram

3.6 變異

隨機(jī)產(chǎn)生一個(gè)0到1之間的數(shù)，當(dāng)隨機(jī)數(shù)大于變異概率且滿足個(gè)體不是精英時(shí)進(jìn)行變異。變異步驟：（1）在染色體的第2位到第(n- 1 )位采用位翻轉(zhuǎn)變異方法進(jìn)行變異，根據(jù)染色體位的初始值，將它的第2位到第(n- 1 )位中的某幾位從1反轉(zhuǎn)為0或從0翻轉(zhuǎn)為1；（2）在染色體的第( 2 +n)位到第( 2n- 1 )位置中隨機(jī)選擇兩個(gè)不同的位置s位和d位并將這兩個(gè)位置的基因交換，與此同時(shí)，將染色體的第(s-n)位和第(d-n)位兩個(gè)位置上的基因也交換；重復(fù)數(shù)次步驟2。當(dāng)變異后的染色體的適應(yīng)度大于變異種群中適應(yīng)度最好的個(gè)體的適應(yīng)度，保留變異后的個(gè)體在種群中，否則保留原個(gè)體。長(zhǎng)度為10的染色體的變異示意圖，如圖8所示。

圖8 染色體變異示意圖Fig.8 Schematic Diagram of Chromosome Variation

4 案例分析

4.1 實(shí)驗(yàn)環(huán)境

在Myeslipe平臺(tái)上采用Java語言進(jìn)行編程完成實(shí)驗(yàn)仿真并得出實(shí)驗(yàn)結(jié)果；在MATLAB平臺(tái)上實(shí)現(xiàn)對(duì)實(shí)驗(yàn)結(jié)果中的路徑展示。

4.2 實(shí)驗(yàn)前提

實(shí)驗(yàn)前提：（1）每輛AGV的速度均為36m∕min；（2）這里采用了4輛AGV進(jìn)行實(shí)驗(yàn)驗(yàn)證；（3）為所有AGV發(fā)送指令的時(shí)間設(shè)置為第0s。（4）這里默認(rèn)在兩種模型求解的路徑均為最短且路徑相同的情況下，完成任務(wù)花費(fèi)總時(shí)間越短模型越優(yōu)。

4.3 實(shí)驗(yàn)設(shè)置

（1）首先隨機(jī)為4輛AGV分別生成4個(gè)任務(wù)請(qǐng)求：

任務(wù)1：r1={1 ，0，p4，30，k1} ；

任務(wù)2：r2={2 ，0，p11，50，k2} ；

任務(wù)3：r3={3 ，0，p19，10，k3} ；

任務(wù)4：r4={4 ，0，p1，30，k4} ；

（2）運(yùn)用遺傳算法為4輛AGV生成路徑，其中遺傳算法中交叉概率Pc= 0.99，變異概率Pm= 0.0005，精英數(shù)elitismCount= 2，種群數(shù)N= 1000，終止代數(shù)generations= 300。

（3）實(shí)驗(yàn)方法：分別采用模型一和模型二為所有AGV規(guī)劃路徑并分析實(shí)驗(yàn)結(jié)果。

4.4 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果，如表1～表3、圖9～圖11所示。

圖9 第一組多AGV路徑規(guī)劃圖Fig.9 The First Set of multi-AGV Path Planning Diagram

圖11 第三組多AGV路徑規(guī)劃圖Fig.11 The Third Set of Multi-AGV Path Planning Diagram

表1 多AGV路徑中轉(zhuǎn)彎頂點(diǎn)及轉(zhuǎn)彎花費(fèi)時(shí)間匯總Tab.1 Simulation Results for Time on AGV Turning at Turning Points along the Path

表3 采用模型二的多AGV路徑規(guī)劃結(jié)果Tab.3 Multi-AGV Path Planning Results Using Model 2

表1統(tǒng)計(jì)了多AGV在行駛過程中進(jìn)行轉(zhuǎn)彎的頂點(diǎn)及轉(zhuǎn)彎花費(fèi)的時(shí)間。

表2 統(tǒng)計(jì)了采用模型一完成任務(wù)時(shí)所有AGV 的行駛路徑、AGV 在行駛中到達(dá)各個(gè)節(jié)點(diǎn)附近的時(shí)間、進(jìn)入各個(gè)節(jié)點(diǎn)的時(shí)間和從各個(gè)節(jié)點(diǎn)出發(fā)的時(shí)間以及完成所有任務(wù)所花費(fèi)的總時(shí)間

表2 采用模型一的多AGV路徑規(guī)劃結(jié)果Tab.2 Multi-AGV Path Planning Results for Model One

表3 統(tǒng)計(jì)了采用模型二完成任務(wù)時(shí)所有AGV 的行駛路徑、AGV在行駛過程中到達(dá)每個(gè)頂點(diǎn)的時(shí)間和從各頂點(diǎn)出發(fā)的時(shí)間以及完成所有任務(wù)所花費(fèi)的總時(shí)間。

由圖9和表2以及圖9表1和表3中的第一組實(shí)驗(yàn)結(jié)果可以清晰地看出采用兩種模型進(jìn)行求解時(shí)4輛AGV之間均沒有發(fā)生沖突，因此使用兩種模型的實(shí)驗(yàn)結(jié)果相同，花費(fèi)總時(shí)間均為252.5s。由圖10和表2中第二組實(shí)驗(yàn)結(jié)果可以看出采用模型一時(shí)k3和k2為了避免在頂點(diǎn)28發(fā)生沖突，k3在頂點(diǎn)28附近等待了3.5s直至k2的車尾駛離頂點(diǎn)才開始進(jìn)入頂點(diǎn)，避免了和k2的碰撞，花費(fèi)總時(shí)間為255.5s；由圖10和表1、表3中的第二組實(shí)驗(yàn)結(jié)果可以看出采用模型二時(shí)k3為了避免和k2在頂點(diǎn)28發(fā)生碰撞，在頂點(diǎn)28的前一頂點(diǎn)33等待了4.5s直至k2開始從頂點(diǎn)28出發(fā)才開始從頂點(diǎn)33出發(fā)，順利地避免了沖突，花費(fèi)總時(shí)間為256.5s。通過比較可以知曉采用模型一完成任務(wù)比采用模型二完成任務(wù)花費(fèi)時(shí)間少1s。

圖10 第二組實(shí)驗(yàn)多AGV路徑規(guī)劃圖Fig.10 The Second Set of Multi-AGV Path Planning Diagram

將圖11和表2中的第三組實(shí)驗(yàn)結(jié)果可以看出采用模型一時(shí)k2在頂點(diǎn)26附近等待了3s直到k1開始從頂點(diǎn)26出發(fā)才開始駛進(jìn)頂點(diǎn)；k3在頂點(diǎn)27附近等待了4.5s直至k1的車尾駛出頂點(diǎn)才開始駛進(jìn)頂點(diǎn)；同理，k4在頂點(diǎn)17附近等待了3s直至k3的車尾駛出頂點(diǎn)才開始駛進(jìn)頂點(diǎn)。采用模型一完成任務(wù)花費(fèi)總時(shí)間為263.5s；將圖11、表1 和表3 中的第三組實(shí)驗(yàn)結(jié)果可以看出采用模型二時(shí)k2在頂點(diǎn)26的前一頂點(diǎn)25等待了6s直到k1開始從頂點(diǎn)26 出發(fā)時(shí)才開始從頂點(diǎn)25 出發(fā)；k3在頂點(diǎn)32 等待了5.5s 直到k1開始從頂點(diǎn)27出發(fā)時(shí)才開始從頂點(diǎn)32出發(fā)；k4為了避免和k3在節(jié)點(diǎn)17 發(fā)生沖突，在頂點(diǎn)16 等了5s 直到k3開始從頂點(diǎn)17出發(fā)才開始從頂點(diǎn)16 出發(fā)。采用模型二花費(fèi)總時(shí)間為269.5s。通過比較可以知曉采用模型一完成任務(wù)比采用模型二完成任務(wù)花費(fèi)時(shí)間少3s。由實(shí)驗(yàn)結(jié)果可知采用模型一和模型二均可以有效避免AGV之間碰撞使所有AGV可以順利地完成任務(wù)，在沒有沖突時(shí)，采用模型一和模型二花費(fèi)時(shí)間相同。但存在沖突且規(guī)劃路徑相同時(shí)，使用模型一比使用模型二可能花費(fèi)時(shí)間更短，因此綜合考慮采用模型一規(guī)劃路徑更合理。

5 總結(jié)

這里針對(duì)物流中心多AGV的路徑規(guī)劃問題，采用拓?fù)浣７▽?duì)倉儲(chǔ)物流中心分揀庫區(qū)進(jìn)行建模，并針對(duì)提出的兩種路徑規(guī)劃模型，利用基因遺傳算法，對(duì)多AGV的運(yùn)行路徑，所需時(shí)間，等待時(shí)間，沖突節(jié)點(diǎn)和等待節(jié)點(diǎn)等進(jìn)行了實(shí)驗(yàn)仿真。研究結(jié)果表明，對(duì)兩種模型而言，利用這里提出的編碼方法和算法，均可實(shí)現(xiàn)多AGV的無碰撞路徑規(guī)劃，但在規(guī)劃路徑相同且存在沖突的情況下采用模型一完成任務(wù)花費(fèi)時(shí)間更短。另外，這里研究方法也適用于物流中心多批次多AGV的派車、路徑規(guī)劃和路徑優(yōu)化，對(duì)提升倉儲(chǔ)物流分揀區(qū)的效率具有意義。