張彥如，陳 灝，石 珂

(合肥工業(yè)大學(xué)機(jī)械工程學(xué)院，安徽 230009)

0 引言

自動化物料處理是集成制造的關(guān)鍵，目前，由自動引導(dǎo)車輛(AGV)組成的自動引導(dǎo)車輛系統(tǒng)(AGV系統(tǒng))是最先進(jìn)的，自動導(dǎo)引車(AGV)是一種無人駕駛的物料處理設(shè)備，使用可充電電池和感應(yīng)電機(jī)，遵循引導(dǎo)路徑，并由計(jì)算機(jī)控制。隨著生產(chǎn)車間對AGV需求的增加，AGV系統(tǒng)中AGV的數(shù)量和車間物料運(yùn)輸?shù)娜蝿?wù)也相應(yīng)增加，因此，如何合理調(diào)度AGV任務(wù)，設(shè)計(jì)優(yōu)化的任務(wù)調(diào)度方案，使物料分配時(shí)間最小化，已成為一個(gè)重要的問題。

任務(wù)調(diào)度的目的是將每個(gè)任務(wù)分配給合適的AGV，以提高自動化系統(tǒng)的效率，必須考慮AGV的性能，避免碰撞。AGV調(diào)度問題基本上分為路由問題和調(diào)度問題，本文主要研究調(diào)度問題。目前，研究者們已經(jīng)做了大量的研究和應(yīng)用。FAZLOLLAHTABAR等[1]對AGV的調(diào)度和路徑規(guī)劃問題進(jìn)行了詳細(xì)的綜述，并對相關(guān)方法進(jìn)行了比較。NISHI等[2]提出了一種雙層分解算法，較好地解決了多AGV系統(tǒng)的同時(shí)調(diào)度和無沖突路徑規(guī)劃問題。RASHIDI等[3]建立了一個(gè)最小費(fèi)用流模型，提出了一種新的算法NSA2，它擴(kuò)展了標(biāo)準(zhǔn)網(wǎng)絡(luò)單純形算法(NSA)，可用于求解多項(xiàng)式時(shí)間復(fù)雜度的大型問題。另外，常見的路徑規(guī)劃算法包括Dijkstra算法[4]、A*算法[5-6]、人工勢場算法[7]、模糊路徑規(guī)劃算法[8-9]等。SUN等[4]對Dijkstra算法進(jìn)行了改進(jìn)，增加了AGV的轉(zhuǎn)彎次數(shù)和轉(zhuǎn)彎角度作為評價(jià)指標(biāo)，并結(jié)合時(shí)間窗法建立了多AGV調(diào)度系統(tǒng)。WANG、SHEN等[5-6]分別對A*算法進(jìn)行了改進(jìn)，并對AGV路徑規(guī)劃問題進(jìn)行了詳細(xì)研究。對于多AGV調(diào)度系統(tǒng)，靜態(tài)算法往往效率低下，或者無法解決AGV的碰撞問題，因此SMOLIC等[7]提出了一種時(shí)間窗方法，可以有效地解決AGV的碰撞問題。綜上所述，大多數(shù)學(xué)者從任務(wù)與AGV同步調(diào)度和AGV無沖突路徑規(guī)劃兩個(gè)方面對調(diào)度系統(tǒng)進(jìn)行優(yōu)化，使調(diào)度系統(tǒng)的效率得到一定程度的提高。在幾乎所有AGV調(diào)度研究中，都有一個(gè)共同的假設(shè)，即AGV以恒定的速度運(yùn)行，但由于實(shí)際環(huán)境中AGV的速度是可變的，需要在調(diào)度系統(tǒng)中考慮AGV的速度。

因此，基于AGV的可變速度和不同的載重電能消耗的不同，本文提出了第3個(gè)優(yōu)化目標(biāo)，AGV的耗電量。系統(tǒng)消耗的電力越少，碳排放就越少，這不僅降低了運(yùn)行成本，也保證了作業(yè)車間的綠色調(diào)度，調(diào)度最終的決策需要在3個(gè)目標(biāo)之間進(jìn)行權(quán)衡，最小化最大完工時(shí)間意味著需要更多的AGV，且AGV必須是快速運(yùn)行的，而AGV的速度越高，單位時(shí)間消耗的電量越多，而如果要使AGV的數(shù)量最小化，則最大完工時(shí)間會增加，AGV必須以盡可能高的速度來完成所有的任務(wù)，這將導(dǎo)致更多的電量消耗。因此，如何平衡這3個(gè)目標(biāo)是本文研究的重點(diǎn)。

1 多AGV任務(wù)調(diào)度問題描述與數(shù)學(xué)模型

在我們的作業(yè)車間調(diào)度問題中，任務(wù)被表示為通過裝卸站(L/U)進(jìn)入和離開的作業(yè)序列[12]。本文主要研究AGV在各個(gè)工作站之間運(yùn)輸物料的任務(wù)調(diào)度，AGV可被看成是待分配的資源。本文基于3個(gè)目標(biāo)建立了AGV任務(wù)調(diào)度的數(shù)學(xué)模型：①最小化最大完工時(shí)間；②最小化AGV的使用數(shù)量；③最小化所有AGV的耗電量。

1.1 假設(shè)條件

(1)忽略貨物的體積，只考慮貨物的重量，不考慮AGV自身重量，單個(gè)貨物的重量不超過AGV的最大承載能力；

(2)AGV消耗的功率與AGV負(fù)載的重量成正比；

(3)AGV停放在充電區(qū)，直到分配調(diào)度命令，AGV在執(zhí)行任務(wù)過程當(dāng)中不會出現(xiàn)電量不足的情況；

(4)AGV的運(yùn)行速度可以根據(jù)所分配的任務(wù)重量變化，每個(gè)任務(wù)對應(yīng)一個(gè)獨(dú)立的AGV速度，在運(yùn)輸過程中保持勻速；

(5) AGV執(zhí)行時(shí)默認(rèn)采用最短路徑。最短路徑距離是由AGV的起點(diǎn)和終點(diǎn)所決定，且不存在路徑問題，碰撞、死鎖或沖突等；

(6)AGV每次任務(wù)的裝卸時(shí)間認(rèn)為固定，包含在運(yùn)輸時(shí)間內(nèi)，AGV可停留在裝卸位置；

(7)每臺AGV一次只能處理一個(gè)任務(wù)，每臺AGV在同一時(shí)間只能執(zhí)行一個(gè)任務(wù)，且單個(gè)任務(wù)中每個(gè)工作站只需要一臺AGV；

(8)所述任務(wù)集為靜態(tài)任務(wù)集，即在AGV處理任務(wù)的過程中沒有任務(wù)新增和終止。

1.2 問題描述與模型

AGV進(jìn)行物料運(yùn)輸主要包括2個(gè)階段：第1個(gè)階段是從當(dāng)前位置前往物料所在的存儲區(qū)，此時(shí)AGV處于空載階段；第2個(gè)階段是AGV在工作站之間運(yùn)送物料，運(yùn)到對應(yīng)的工作站，此時(shí)是負(fù)載階段。每完成一次運(yùn)輸，AGV會檢查當(dāng)前電量是否低于電量閾值，電量閾值設(shè)定為由當(dāng)前工作站返回充電區(qū)所需最小電量，當(dāng)電量充足時(shí)，AGV直接前往下一任務(wù)所在工作站；當(dāng)電量不足時(shí)，AGV需要前往充電區(qū)充電，充電完成后再次執(zhí)行任務(wù)。如此反復(fù)，直至所有運(yùn)輸任務(wù)執(zhí)行完畢，最后返回充電區(qū)，為更加清晰的描述模型，相關(guān)參數(shù)義總結(jié)如表1所示。

本文所建數(shù)學(xué)模型如下：

(1)

(2)

(3)

(4)

(5)

(6)

STi≥STj,?i∈I

(7)

(8)

(9)

(10)

(11)

(12)

式中，式(1)～式(3)為模型的目標(biāo)函數(shù)，分別代表最大完工時(shí)間最小、使用的AGV數(shù)量最小和AGV總耗電量最小；其中最大完工時(shí)間由AGV到達(dá)任務(wù)點(diǎn)所需時(shí)間、AGV完成任務(wù)所需時(shí)間(包括裝卸時(shí)間)和執(zhí)行充電任務(wù)所需時(shí)間3部分組成；式(4)～式(6)分別代表AGV是否參與任務(wù)、任務(wù)i是否由AGVa來執(zhí)行以及AGV執(zhí)行完任務(wù)i后是否執(zhí)行任務(wù)j，兩個(gè)變量均為0～1變量；式(7)為時(shí)間約束，表示下一任務(wù)開始時(shí)間晚于上一任務(wù)完成時(shí)間；式(8)計(jì)算的是AGV返回充電區(qū)域所需電量；式(9)表示AGV運(yùn)行速度與其負(fù)載和電量的關(guān)系；式(10)為執(zhí)行充電任務(wù)所需時(shí)間，當(dāng)AGV的電量不足以完成任務(wù)時(shí)，AGV需要執(zhí)行充電任務(wù)；式(11)決定了一個(gè)任務(wù)只能由一臺AGV執(zhí)行一次；式(12)是等式約束，分別表示AGV到達(dá)任務(wù)點(diǎn)所需的時(shí)間、完成任務(wù)所需的時(shí)間以及AGV的充電時(shí)間，由于AGV在處理自身任務(wù)時(shí)，會選擇最短路徑，且最短路徑距離是由AGV的起始點(diǎn)和結(jié)束點(diǎn)唯一確定的，這3個(gè)變量都由AGV的速度決定。

2 改進(jìn)算法設(shè)計(jì)

遺傳算法通過對問題進(jìn)行編碼解碼，適應(yīng)于各類問題且易于操作，且對種群的遺傳操作是并行的，因此算法具體較強(qiáng)的全局搜索能力，被廣泛的應(yīng)用到作業(yè)車間調(diào)度問題上，但是現(xiàn)有遺傳算法存在初始解質(zhì)量低和進(jìn)化后期收斂速度慢兩個(gè)方面的問題，針對此，本文提出了一種改進(jìn)的自適應(yīng)遺傳算法，通過對初始種群和交叉變異概率自適應(yīng)策略的優(yōu)化，提高初始種群的質(zhì)量和算法的收斂速度。

2.1 染色體表達(dá)與編碼

遺傳算法有很多種編碼規(guī)則，包括二進(jìn)制編碼、浮點(diǎn)數(shù)編碼以及實(shí)數(shù)編碼等。針對本文所研究內(nèi)容，采用了一種雙層實(shí)數(shù)編碼方法，每一條染色體代表一種任務(wù)分配計(jì)劃，由不同的AGV配送任務(wù)組成，染色體的前半部分表示AGV編號i，后半部分染色體片段表示AGV執(zhí)行任務(wù)時(shí)的速度。每臺AGV在同一時(shí)間只能執(zhí)行一個(gè)任務(wù)，因此，染色體上的基因編碼可以表示AGV的序號，基因序列為任務(wù)集，需要找到可以完成該任務(wù)的最優(yōu)分配方案，用以平衡3個(gè)優(yōu)化目標(biāo)。染色體如圖1所示，圖中代表任務(wù)1由2號AGV完成，AGV的速度為1.0 m/s。

圖1 染色體編碼

2.2 種群初始化

對于算法進(jìn)化來說，初始種群的選擇非常重要，傳統(tǒng)遺傳算法和現(xiàn)有的改進(jìn)遺傳算法在初始種群選擇時(shí)大多采用隨機(jī)生成的方法，以保證選擇的隨機(jī)性和初始種群個(gè)體的多樣性，但初始種群的質(zhì)量將直接影響到世代的進(jìn)化，隨機(jī)生成的種群可能會導(dǎo)致初始解的質(zhì)量低下，從而增加迭代次數(shù)。為了保證初始種群的多樣性并提高初始種群的質(zhì)量，本文引入了種群熵，初始種群的創(chuàng)建步驟如下：

步驟1：根據(jù)可供調(diào)度的AGV數(shù)量，確定AGV的編號范圍[1,M]；

步驟2：用創(chuàng)建任意離散隨機(jī)種群的方法，對個(gè)體的每個(gè)基因位產(chǎn)生一個(gè)隨機(jī)數(shù)ri，個(gè)體基因的位數(shù)等于車間中工作站的總數(shù)；

步驟3：為了提高種群多樣性，引入種群熵，算法每隔幾代根據(jù)當(dāng)前種群內(nèi)個(gè)體的適應(yīng)值估計(jì)種群熵，更新控制參數(shù)，從而得到更優(yōu)秀的種群；

步驟4：重復(fù)上述步驟N次，產(chǎn)生一個(gè)包含N個(gè)個(gè)體的初始種群。

該方法既繼承了傳統(tǒng)遺傳算法在選擇機(jī)器時(shí)選擇的隨機(jī)性，又大大提高了初始種群的質(zhì)量。

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

對于多目標(biāo)優(yōu)化問題，由于目標(biāo)之間一般是相互沖突的，因此需要尋求多目標(biāo)之間的帕累托最優(yōu)解，帕累托效率意味著資源以最有效的方式分配。因此，可對每一個(gè)子目標(biāo)函數(shù)fi(x)賦予權(quán)重ωi，其中ωi表示相應(yīng)的fi(x)在多目標(biāo)優(yōu)化問題中的評價(jià)函數(shù)，則整體適應(yīng)度函數(shù)可表示如下：

f(x)=∑ωi·fi(x)

(13)

由于這是一個(gè)極小化問題，我們選擇目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，即：

(14)

在本研究中，設(shè)置3個(gè)目標(biāo)的權(quán)重分別為0.6、0.24和0.16。為了使3個(gè)目標(biāo)具有相似的變化范圍，調(diào)整系數(shù)分別為1、30和20，從而得到整體適應(yīng)度函數(shù)的表達(dá)式為：

(15)

2.4 交叉操作

圖2 交叉操作

交叉操作是將兩個(gè)配對的染色體部分基因交換從而形成兩個(gè)新的染色體，該操作不能過多破壞個(gè)體中表現(xiàn)優(yōu)良的編碼串，交叉操作是為了產(chǎn)生不同多樣的AGV任務(wù)分配方案，可以增大任務(wù)分配解空間的搜索范圍。交叉方法采用子路徑交叉(subtour exchange crossover)方法，假設(shè)父代1:α[p1]=a,b,c,d,e；父代2:α[p2]=c,d,e,b,a，從兩代父染色體中隨機(jī)選取基因a,b,e，位置可以不連續(xù)，但是兩染色體被選基因相同，然后將這兩個(gè)基因從中選取出來，并且在對應(yīng)的子代中使它們與原父代中的位置一樣，然后按照基因的出現(xiàn)順序，交換兩父代染色體中的位置，一次生成兩個(gè)子代，具體操作如圖2所示。

2.5 變異操作

為了增強(qiáng)遺傳算法的局部搜索能力并且能夠提高種群的多樣性，變異操作將染色體編碼串中的某些基因進(jìn)行改變，從而使遺傳算法以良好的搜索能力來完成最優(yōu)化的過程。本文采用基因段兩點(diǎn)變異法的變異模式，其具體操作過程如下：

步驟1：在父代基因序列parent1上隨機(jī)產(chǎn)生兩個(gè)變異點(diǎn)，此處隨機(jī)取兩個(gè)位置為變異點(diǎn)，如圖3所示。

圖3 兩點(diǎn)變異法

步驟2：在子代染色體變異點(diǎn)對應(yīng)的位置，將此處基因替換為其他的基因值，此處新替換的基因來源于對應(yīng)任務(wù)的可選AGV集合。

步驟3：將父代基因序列parent1中除了變異點(diǎn)位置意外的所有基因值進(jìn)行復(fù)制，遺傳到子代中，保證其基因值和順序與父代一致。

根據(jù)以上步驟進(jìn)行變異，可以得到新的子代染色體基因序列offerspring1。

2.6 改進(jìn)的自適應(yīng)策略

遺傳算法的交叉概率Pc和變異概率Pm是決定遺傳算法性能好壞的關(guān)鍵，所以通過引入自適應(yīng)策略，Pc和Pm就可以隨適應(yīng)度值自動改變，在保證種群多樣性的同時(shí)，保證算法收斂性，這也是自適應(yīng)遺傳算法相對普通遺傳算法來說的優(yōu)點(diǎn)所在，Pc和Pm可以按照式(16)、式(17)進(jìn)行調(diào)整：

(16)

(17)

式中，gmax為種群最大的適應(yīng)度值；ga為種群的平均適應(yīng)度值；g′為要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值；g為要變異個(gè)體的適應(yīng)度值；k1、k2、k3、k4為4個(gè)常數(shù)，取值范圍在0～1之間。

雖然傳統(tǒng)的自適應(yīng)遺傳策略可以很好地保留優(yōu)解，并且容易找到圍繞局部最優(yōu)解的全局最優(yōu)解，但這種方法在進(jìn)化的早期階段并不理想。在早期階段，優(yōu)解的概率值非常小，因此它們的優(yōu)秀模型無法有效分散，優(yōu)解幾乎保持不變狀態(tài)，導(dǎo)致其在進(jìn)化的后期，很難跳出原來的局部最優(yōu)解，最終會導(dǎo)致算法的搜索速度非常緩慢，甚至停滯。

本文為了克服上述問題，在自適應(yīng)交叉變異概率的基礎(chǔ)上，提出了一種改進(jìn)的自適應(yīng)策略，利用3個(gè)加權(quán)參數(shù)Pc(m)min、Pc(m)max、Pc(m)mid使其在不同適應(yīng)度之間具有約束，交叉概率可以根據(jù)種群進(jìn)化情況進(jìn)行連續(xù)自適應(yīng)調(diào)整。在進(jìn)化早期，為了避免在局部最優(yōu)時(shí)過早收斂，通過調(diào)整參數(shù)，使交叉和變異概率偏高，提高了全局搜索能力，增加了種群的個(gè)體多樣性。在進(jìn)化后期，個(gè)體適應(yīng)度值較高，如果算法仍然隨機(jī)無目的搜索，則會導(dǎo)致收斂速度慢，此時(shí)通過調(diào)整加權(quán)參數(shù)來降低交叉和變異概率，以提高收斂速度。設(shè)置自適應(yīng)交叉概率如下：

(18)

(19)

式中，Pcmin和Pcmax分別為交叉概率取值的最小值和最大值，交叉概率一般取值范圍在[0.6,0.8]；Pmmin和Pmmax分別為變異概率取值的最小值和最大值，變異概率一般取值范圍在[0.01,0.1]；Pc(m)mid為兩者取值的中位數(shù)。

2.7 迭代終止

本文采用的終止條件是連續(xù)8代種群均值沒有變化就停止迭代。通常GA迭代終止條件是連續(xù)數(shù)代目標(biāo)值或最優(yōu)解不發(fā)生改變就停止，但很多時(shí)候往往經(jīng)過幾次迭代種群中最優(yōu)個(gè)體雖然未發(fā)生變化，種群均值卻仍在變化,種群還在不斷進(jìn)化，此時(shí)迭代終止，會阻止更優(yōu)解的產(chǎn)生。只有當(dāng)種群均值數(shù)代不發(fā)生變化時(shí)，說明種群已經(jīng)停止進(jìn)化，最優(yōu)個(gè)體已不會發(fā)生改變，才能終止迭代。

3 實(shí)例

3.1 車間布局及相關(guān)數(shù)據(jù)

圖4 車間布局圖

為驗(yàn)證模型的有效性，借鑒文獻(xiàn)[9]和文獻(xiàn)[11]，建立車間工作站模型，如圖4所示，圖中白色方塊代表AGV完成所需任務(wù)所到達(dá)的工作站，每個(gè)工作站有各自的坐標(biāo)，工作站與工作站之間的距離，可用曼哈頓距離來表示，由此可以得到AGV的移動距離，黑色代表物料儲存區(qū)，AGV在裝卸站卸下物料后，如果電量充足，可以繼續(xù)進(jìn)行下一個(gè)任務(wù)，否則需要返回充電區(qū)充電，充電區(qū)位置位于X軸上，坐標(biāo)可表示為(5,3)。在本文的仿真試驗(yàn)中，假設(shè)有50個(gè)任務(wù)需要完成，可用AGV數(shù)量為20輛，AGV速度從0.5 m/s～1.5m/s不等，AGV驅(qū)動過程中單位載重電能系數(shù)α取0.001。

3.2 實(shí)驗(yàn)結(jié)果分析

假設(shè)車間中所有工作站都需要配送物料，本文通過一種改進(jìn)的自適應(yīng)遺傳算法，在MATLAB環(huán)境下對多任務(wù)多AGV調(diào)度模型進(jìn)行了仿真，算法參數(shù)的相關(guān)設(shè)置為：種群規(guī)模為100，最大迭代次數(shù)為200，選擇率為0.5，初始交叉概率為0.8，初始變異概率為0.07。

圖5 基于傳統(tǒng)遺傳算法的任務(wù)調(diào)度甘特圖

圖6 基于改進(jìn)遺傳算法的任務(wù)調(diào)度甘特圖

表2 算法測試結(jié)果

傳統(tǒng)遺傳算法和改進(jìn)自適應(yīng)遺傳算法迭代搜索過程分別如圖7和圖8所示，傳統(tǒng)的遺傳算法約在第125代收斂，改進(jìn)的自適應(yīng)遺傳算法約在第68代收斂。

圖7 傳統(tǒng)遺傳算法迭代過程 圖8 改進(jìn)自適應(yīng)遺傳算法迭代過程

可以看出，IAGA算法在收斂速度方面表現(xiàn)良好，且具有較強(qiáng)的全局搜索能力，因?yàn)镮AGA的交叉率和變異率是基于個(gè)體的適應(yīng)度值自適應(yīng)調(diào)整的，如果個(gè)體適應(yīng)度值較大，則交叉和變異的比率將較低，因此大的基因序列更自然地進(jìn)入下一代而不被破壞。因此，IAGA的應(yīng)用有助于快速找到合適的解決方案。

4 結(jié)束語

本文以作業(yè)車間中多AGV任務(wù)調(diào)度為研究對象，首先考慮AGV運(yùn)行時(shí)在運(yùn)載不同重量物料時(shí)的速度差異，同時(shí)在功耗中引入重量系數(shù)，建立了多目標(biāo)調(diào)度模型，指導(dǎo)AGV在物料配送過程中的調(diào)度。然后，針對該模型，采用了一種改進(jìn)的自適應(yīng)遺傳算法，通過引入種群熵改進(jìn)初始種群質(zhì)量，并提出了一種改進(jìn)的自適應(yīng)策略，使得交叉率和變異率在迭代的各個(gè)時(shí)期根據(jù)適應(yīng)度值的變化進(jìn)行合理地調(diào)整。最后，在MATLAB環(huán)境中進(jìn)行了仿真試驗(yàn)，獲得了多任務(wù)調(diào)度的近似最優(yōu)調(diào)度，并對比了傳統(tǒng)遺傳算法與改進(jìn)自適應(yīng)遺傳算法的調(diào)度結(jié)果以及迭代過程差異。仔細(xì)比較前后的數(shù)據(jù)，實(shí)驗(yàn)結(jié)果表明，在合適的速度下，使用較少的AGV可以完成所有任務(wù)的調(diào)度，從而縮短了完工時(shí)間，減少了AGV的使用數(shù)量，降低了總功耗。并且每個(gè)優(yōu)化目標(biāo)的值降低了25%，著重證明了模型和IAGA的有效性。