改進(jìn)多種群遺傳算法的AutoStore系統(tǒng)多AGV調(diào)度優(yōu)化

王曉軍，王 博，晉民杰，楊春霞，白新利

(1.太原科技大學(xué) 交通與物流學(xué)院，山西 太原 030024；2.山西海德拉太礦國(guó)際采礦刀具設(shè)備有限公司，山西 太原 030024)

AutoStore系統(tǒng)是一種新興緊致密集型倉(cāng)儲(chǔ)系統(tǒng)[1]。如圖1所示，該系統(tǒng)主體結(jié)構(gòu)為鋁制框架，每一列為一個(gè)貨格。規(guī)格統(tǒng)一的料箱是基本存儲(chǔ)單元，依次堆存在貨格中。AGV小車四側(cè)都有輪子，能通過(guò)貨架頂層軌道實(shí)現(xiàn)前后左右4個(gè)方向的移動(dòng)，同時(shí)小車底部有一個(gè)提升裝置，能伸入貨格內(nèi)抓取或放入料箱。該系統(tǒng)屬于“貨到人”工作模式[2]，在執(zhí)行出入庫(kù)作業(yè)時(shí)，AGV小車將裝有目標(biāo)貨物的料箱或空箱搬運(yùn)至工作臺(tái)，由工作人員揀選或放入貨物后，再將料箱運(yùn)回。因此，AGV調(diào)度是該系統(tǒng)的核心環(huán)節(jié)，對(duì)其進(jìn)行優(yōu)化研究，可提高作業(yè)效率，減少作業(yè)成本。

圖1 AutoStore系統(tǒng)示意圖Figure 1 Sketch map of AutoStore system

該新型倉(cāng)儲(chǔ)系統(tǒng)沒(méi)有巷道，存儲(chǔ)密度大，且拓展性強(qiáng)，近幾年在歐洲出現(xiàn)后便迅速流行起來(lái)。但目前在國(guó)內(nèi)還鮮有見(jiàn)到[1,3]，通過(guò)文獻(xiàn)檢索，也尚未找到針對(duì)AGV調(diào)度的學(xué)術(shù)研究。此處先根據(jù)出、入庫(kù)作業(yè)模式對(duì)傳統(tǒng)密集型倉(cāng)儲(chǔ)系統(tǒng)相關(guān)研究進(jìn)行分析。

1) 出、入庫(kù)單獨(dú)作業(yè)模式。設(shè)置集中補(bǔ)貨時(shí)間，期間只安排入庫(kù)作業(yè)；其余時(shí)間根據(jù)訂單進(jìn)行出庫(kù)作業(yè)[4]。該模式較為簡(jiǎn)單，根據(jù)訂單任務(wù)按順序進(jìn)行即可，但AGV空載較多，會(huì)導(dǎo)致資源浪費(fèi)。

2) 出、入庫(kù)聯(lián)合作業(yè)模式。楊瑋等[5]在考慮AGV加減速運(yùn)動(dòng)的前提下，通過(guò)分析驗(yàn)證聯(lián)合作業(yè)能降低AGV空載率。闞世奇等[6]為實(shí)現(xiàn)多層穿梭車系統(tǒng)的聯(lián)合作業(yè)，提出一種存取訂單序列匹配方法，以提高系統(tǒng)作業(yè)能力。劉高強(qiáng)等[7]針對(duì)生產(chǎn)車間多AGV任務(wù)分配問(wèn)題，以作業(yè)時(shí)間最小為優(yōu)化目標(biāo)。李騰等[8]通過(guò)分析“貨到人”揀選系統(tǒng)作業(yè)流程，提出在分批下發(fā)訂單任務(wù)情況下的一種隨機(jī)調(diào)度策略。崔敬偉[9]重點(diǎn)關(guān)注AGV動(dòng)態(tài)分配問(wèn)題，保證調(diào)度方案的可操作性。楊智飛等[10]考慮AGV調(diào)度的多目標(biāo)性，優(yōu)化目標(biāo)包含作業(yè)完成時(shí)間、AGV配備數(shù)量及懲罰成本等三方面。Tavakoli等[11]研究工業(yè)系統(tǒng)中的AGV調(diào)度與分配問(wèn)題，建立數(shù)學(xué)模型，并提出一種啟發(fā)式算法進(jìn)行求解。Miyamoto等[12]考慮有限沖突條件下的AGV任務(wù)分配問(wèn)題，將其描述成一個(gè)整數(shù)規(guī)劃，并提出局部/隨機(jī)搜索方法。Liu等[13]建立自動(dòng)倉(cāng)儲(chǔ)系統(tǒng)的AGV調(diào)度多目標(biāo)模型，采用多種群自適應(yīng)遺傳算法進(jìn)行求解，并證明其有效性。Fazlollahtabar等[14]考慮提前和延遲的懲罰，以保證得到無(wú)沖突任務(wù)分配方案。

上述研究盡管目的和思路各有不同，但從約束條件上大多具有如下特點(diǎn)：1) 出入庫(kù)作業(yè)在同一平臺(tái)進(jìn)行，任務(wù)分配時(shí)通常將其視為一個(gè)點(diǎn)；2) 作業(yè)模式單一，為出入庫(kù)單獨(dú)作業(yè)模式或聯(lián)合作業(yè)模式，一般情況下，聯(lián)合作業(yè)時(shí)間要小于單獨(dú)出入庫(kù)作業(yè)時(shí)間之和。

AutoStore系統(tǒng)中，出入庫(kù)作業(yè)臺(tái)設(shè)置在貨架最外圍，且數(shù)量不唯一，此時(shí)情況要復(fù)雜得多。AGV可以在多個(gè)作業(yè)臺(tái)工作，即起始點(diǎn)和終點(diǎn)不確定。以圖2為例進(jìn)行說(shuō)明。圖2為一個(gè)規(guī)模為10行10列倉(cāng)儲(chǔ)貨架頂層，4個(gè)出入庫(kù)作業(yè)臺(tái)A1～A4分別布置在貨架角落。

圖2 出入庫(kù)作業(yè)示意圖Figure 2 Schematic diagram of warehousing operationm

設(shè)現(xiàn)有2個(gè)任務(wù)，一是需要將料箱存入貨格S1，二是需要從貨格R1提取料箱。采用單獨(dú)作業(yè)方案時(shí)，需安排2臺(tái)AGV，路徑分別為：A1—S1—A1、A3—R1—A3，總路徑長(zhǎng)度為16格。若采用聯(lián)合作業(yè)時(shí)，可只安排1臺(tái)AGV：從A1搬運(yùn)料箱至S1完成入庫(kù)，空駛至R1，從R1搬運(yùn)料箱至A3完成出庫(kù)，總路徑長(zhǎng)度為18格。

從上述分析可知，AutoStore系統(tǒng)存在多個(gè)出入庫(kù)作業(yè)臺(tái)，聯(lián)合作業(yè)時(shí)間并不一定小于單獨(dú)作業(yè)時(shí)間。為提高作業(yè)效率，會(huì)出現(xiàn)單獨(dú)出庫(kù)作業(yè)、單獨(dú)入庫(kù)作業(yè)及聯(lián)合出入庫(kù)作業(yè)3種模式并存的現(xiàn)象，這使得傳統(tǒng)研究方法無(wú)法適應(yīng)該系統(tǒng)。

為此，本文將在作業(yè)流程分析基礎(chǔ)上，綜合考慮3種作業(yè)模式，建立總作業(yè)時(shí)間最小模型，并通過(guò)改進(jìn)多種群遺傳算法進(jìn)行求解，最后利用算例進(jìn)行分析和驗(yàn)證。本文研究將給AutoStore系統(tǒng)AGV任務(wù)分配及調(diào)度提供思路。

1 出入庫(kù)作業(yè)流程分析

1.1 單獨(dú)入庫(kù)作業(yè)

1) 入庫(kù)任務(wù)產(chǎn)生階段。工作人員收到訂單后，確定訂單貨物類別與數(shù)量。如已存有同類別貨物，檢查對(duì)應(yīng)料箱是否有空余位置。如果有，直接確定入庫(kù)料箱，如果存儲(chǔ)空間不足則調(diào)用其余空箱，并確認(rèn)存放位置。如果沒(méi)有同類別貨物，也調(diào)用空箱，確定存放位置。

2) AGV搬運(yùn)目標(biāo)料箱至入庫(kù)工作臺(tái)階段。對(duì)當(dāng)前任務(wù)，首先檢索空閑狀態(tài)AGV，并進(jìn)行任務(wù)分配，如沒(méi)有空閑AGV則等到有空閑AGV為止。對(duì)接到任務(wù)的AGV，首先移動(dòng)至目標(biāo)料箱頂部，若目標(biāo)料箱上面還有其他料箱，需進(jìn)行倒箱操作，即把目標(biāo)箱上部的阻礙箱搬運(yùn)至其他貨格；當(dāng)目標(biāo)箱位于頂層時(shí)，將目標(biāo)箱搬運(yùn)至入庫(kù)口放下。

3) 工作臺(tái)操作階段。工作人員在入庫(kù)口接收目標(biāo)料箱，將訂單貨物存入，并在系統(tǒng)確定目標(biāo)箱存儲(chǔ)位置。

4) AGV運(yùn)回目標(biāo)料箱階段。再次檢索空閑AGV并調(diào)用，將料箱運(yùn)回原來(lái)貨格。任務(wù)完成后，釋放AGV。

1.2 單獨(dú)出庫(kù)作業(yè)

1) 出庫(kù)任務(wù)產(chǎn)生階段。與入庫(kù)任務(wù)類似，工作人員將訂單貨物種類和數(shù)量與系統(tǒng)庫(kù)存相比對(duì)，選擇要提取的料箱，并確定為目標(biāo)料箱。

2) AGV將目標(biāo)料箱搬運(yùn)至出庫(kù)口。AGV調(diào)用與入庫(kù)流程類似。

3) 工作臺(tái)出庫(kù)。工作人員從料箱中揀選所需貨物，并確定目標(biāo)存儲(chǔ)位置。

4) AGV搬運(yùn)目標(biāo)料箱至目標(biāo)存儲(chǔ)位置，并更新系統(tǒng)相關(guān)狀態(tài)。

1.3 聯(lián)合出入庫(kù)作業(yè)

聯(lián)合作業(yè)則是根據(jù)訂單順序?qū)⒊鰩?kù)和入庫(kù)組合起來(lái)，可減少AGV空載時(shí)間。首先根據(jù)訂單要求，將出庫(kù)與入庫(kù)匹配，對(duì)某一AGV而言，先執(zhí)行入庫(kù)訂單，不用返回工作臺(tái)，直接執(zhí)行出庫(kù)訂單。其余步驟與出入庫(kù)流程類似。

2 AGV調(diào)度任務(wù)分配優(yōu)化模型

2.1 基本假設(shè)

1) AGV數(shù)量滿足要求，不會(huì)出現(xiàn)無(wú)空余AGV可調(diào)用的情況；

2) AGV勻速行駛，考慮空載和負(fù)載速度差異，暫不考慮沖突；

3) AGV一次只能搬運(yùn)一個(gè)料箱；

4) 訂單任務(wù)無(wú)優(yōu)先級(jí)，即不提前指定AGV執(zhí)行任務(wù)的順序。

2.2 考慮多作業(yè)模式的優(yōu)化模型

設(shè)w 為工作臺(tái)數(shù)目； n1、 n2分別為入庫(kù)、出庫(kù)任務(wù)數(shù)；v1、 v2分別為AGV空載和負(fù)載的行駛速度；對(duì)任務(wù)i， Bi為 需進(jìn)行出入庫(kù)任務(wù)的貨位， Pi為出入庫(kù)任務(wù)對(duì)應(yīng)工作臺(tái)位置， dPkBi為從目標(biāo)工作臺(tái)到目標(biāo)貨格的距離， dBiPk為從目標(biāo)貨格到目標(biāo)工作臺(tái)的距離，dBiBj為 i任 務(wù)貨格到 j任務(wù)貨格距離；對(duì)作業(yè)臺(tái)k ， tRk、 tSk、 tCk分別是單獨(dú)出庫(kù)、單獨(dú)入庫(kù)及聯(lián)合出入庫(kù)作業(yè)時(shí)間。

決策變量 xik∈{0, 1}，當(dāng)作業(yè)臺(tái)k執(zhí)行任務(wù)i時(shí)為1，否則為0；決策變量 yijk∈{0, 1}，從作業(yè)臺(tái)k出發(fā)的AGV執(zhí)行完任務(wù)i后轉(zhuǎn)向作業(yè)臺(tái)取值為1，否則為0。決策變量 zijk∈{0, 1}，當(dāng)作業(yè)臺(tái)k的任務(wù)i不是任務(wù)j的前置任務(wù)取值為1，否則為0。

模型建設(shè)分兩步：首先分別建立單獨(dú)出庫(kù)、單獨(dú)入庫(kù)作業(yè)和聯(lián)合出入庫(kù)作業(yè)的模型；其次將三者相加，形成總作業(yè)時(shí)間模型。

1) 單獨(dú)出庫(kù)作業(yè)。

式(1)表示最小化出庫(kù)作業(yè)時(shí)間，包括AGV從工作臺(tái)到出庫(kù)點(diǎn)的空載移動(dòng)時(shí)間加上AGV從出庫(kù)點(diǎn)至工作臺(tái)的負(fù)載移動(dòng)時(shí)間。

2) 單獨(dú)入庫(kù)作業(yè)。

式(2)表示最小化入庫(kù)作業(yè)時(shí)間，包括AGV從工作臺(tái)到入庫(kù)點(diǎn)的負(fù)載移動(dòng)時(shí)間加上AGV從入庫(kù)點(diǎn)到工作臺(tái)的空載移動(dòng)時(shí)間。

3) 聯(lián)合出入庫(kù)作業(yè)。

式(3)表示最小化聯(lián)合作業(yè)時(shí)間，包括3部分：AGV從工作臺(tái)到入庫(kù)點(diǎn)的負(fù)載移動(dòng)時(shí)間、AGV從任務(wù)i位置移動(dòng)到任務(wù)j的空載移動(dòng)時(shí)間、AGV從任務(wù)j移動(dòng)至工作臺(tái)負(fù)載移動(dòng)時(shí)間。

4) 系統(tǒng)總作業(yè)時(shí)間。

由式(1)、(2)、(3)得多種作業(yè)模式并存下的總作業(yè)時(shí)間數(shù)學(xué)模型，優(yōu)化目標(biāo)為總作業(yè)時(shí)間最短。

約束條件中，式(5)表示每個(gè)任務(wù)只能由一輛AGV執(zhí)行；式(6)表示聯(lián)合出入庫(kù)任務(wù)AGV行走距離小于單獨(dú)進(jìn)行出入庫(kù)作業(yè)AGV行走距離之和；式(7)、(8)表示單個(gè)AGV單次最多執(zhí)行一個(gè)任務(wù)。

3 改進(jìn)多種群遺傳算法

與傳統(tǒng)遺傳算法(GA)相比，多種群遺傳算法(multiple population GA, Multi-pop GA)[15]通過(guò)種群迭代提高解的多樣性，搜索能力提高。本文在標(biāo)準(zhǔn)算法基礎(chǔ)上，考慮了初始解判斷規(guī)則和自適應(yīng)遺傳策略，以提高收斂速度。

3.1 編碼方法

本算法采用實(shí)數(shù)編碼形式，每個(gè)染色體中，基因數(shù)目表示任務(wù)總數(shù)，基因位置表示任務(wù)，基因數(shù)值為執(zhí)行該任務(wù)的AGV編號(hào)。如圖3所示，共10個(gè)任務(wù)，其中，任務(wù)1、4、8由1號(hào)AGV執(zhí)行。

圖3 編碼設(shè)計(jì)Figure 3 Coding design

3.2 初始解生成及評(píng)價(jià)

為保證種群多樣性，多種群遺傳算法對(duì)不同群體采用不同算子，但如果初始解不能較好地分布在解空間，依然會(huì)使得不同種群趨向同一局部解。為解決此問(wèn)題，本改進(jìn)算法在初始解生成階段加入判斷過(guò)程。

已有初始解判斷研究大多基于海明距離，但此方法多用于0-1編碼規(guī)則，對(duì)實(shí)數(shù)編碼適用性較差。圖4編碼中，兩組基因的海明距離均為5，但放在執(zhí)行環(huán)境中，基因組1中的順序差異明顯要小于基因組2的差異。

圖4 基因組對(duì)比Figure 4 Genome comparison

為更好地描述初始解的距離，給出一種適用于實(shí)數(shù)編碼的評(píng)價(jià)因子，該因子將基因位值縮放至十進(jìn)制，即每個(gè)基因位的值為0～9。設(shè)每個(gè)初始解的基因位有m個(gè)，則最小值為 0,···,0 ， 最大為9,···,9。每次生成初始解，對(duì)實(shí)數(shù)差異大小進(jìn)行判斷，當(dāng)差異大于10m×(1.25N)-1時(shí)，保留初始解，否則認(rèn)定初始解差異性小，需重新生成。

3.3 自適應(yīng)遺傳算子設(shè)計(jì)

為有效控制種群進(jìn)化方向，設(shè)計(jì)自適應(yīng)遺傳算子，主要考慮兩個(gè)方面因素。

1) 所處進(jìn)化階段不同，對(duì)遺傳操作的需求不同，在進(jìn)化初期，可適當(dāng)降低交叉和變異幾率，以提高種群內(nèi)部適應(yīng)度值高的個(gè)體比例；在進(jìn)化后期，種群內(nèi)部個(gè)體差異性已較小，為避免陷入局部解，可提高交叉和變異的幾率。

2) 為加快搜索，希望能盡量保持適應(yīng)度高的個(gè)體即減少操作幾率，能改變適應(yīng)度低的個(gè)體即增加操作幾率。

基于以上思路，給出了自適應(yīng)遺傳算子的計(jì)算式，交叉幾率pci見(jiàn)式(9)，變異幾率pmi見(jiàn)式(10)，其中，fi、favg、fmax分別為適應(yīng)度第i代值、平均值及最大值。

式(9)中，c1、c2分別為交叉基礎(chǔ)概率的范圍，c3為隨機(jī)值，且1＞c3＞c2＞c1＞0。由計(jì)算式可知，當(dāng)適應(yīng)度值大于平均值時(shí)，可在規(guī)定的上下限內(nèi)取值，且適應(yīng)度值越高，交叉概率越??；當(dāng)適應(yīng)度值小于平均值時(shí)，交叉概率可高于基礎(chǔ)概率的上限。

與式(9)類似，式(10)中c4、c5為變異基礎(chǔ)概率范圍，c6隨機(jī)生成，且1 ＞c6＞c5＞c4＞0。

交叉操作中，對(duì)有m個(gè)基因位的個(gè)體，首先在(0, 1)區(qū)間產(chǎn)生兩個(gè)隨機(jī)數(shù)L1、L2，其次計(jì)算mL1、mL2并取整，得到交叉段起終點(diǎn)位置，最后對(duì)父代進(jìn)行交叉得到子代，見(jiàn)圖5。

圖5 交叉操作分析Figure 5 Example of cross operation

變異操作中，在1 ～m中隨機(jī)產(chǎn)生一個(gè)數(shù)，確定變異基因位，并將基因數(shù)值變異成其他隨機(jī)編碼。

多種群遺傳算法中，既包含種群內(nèi)部的進(jìn)化，也包括種群間的交流，以保證協(xié)同進(jìn)化，其中，個(gè)體遷移是銜接兩者的關(guān)鍵。為避免頻繁遷移，設(shè)定種群間最優(yōu)個(gè)體每10代遷移1次。

3.4 適應(yīng)度值與終止條件

式(4)目標(biāo)為總作業(yè)時(shí)間最短，因此適應(yīng)度函數(shù)f設(shè)為目標(biāo)函數(shù)的倒數(shù)。將迭代次數(shù)作為終止條件，可以設(shè)置為1 000次。

4 算例分析及驗(yàn)證

4.1 算例初始條件

AutoStore為三維立體貨架，考慮到AGV只在頂層移動(dòng)，在某個(gè)貨格或工作臺(tái)頂部進(jìn)行料箱的提取或存入工作時(shí)，和路徑安排無(wú)關(guān)，因此，以貨架頂層網(wǎng)格為路徑地圖。地圖橫縱分別有70個(gè)貨格，每一個(gè)貨格可用坐標(biāo)節(jié)點(diǎn)來(lái)表示。設(shè)工作臺(tái)數(shù)量為4個(gè)，分別布置在貨架4個(gè)角，編號(hào)和坐標(biāo)分別為A1(0, 0)、A2(0, 70)、A3(70, 0)、A4(70, 70)。AGV數(shù)量為5臺(tái)，空載速度為1 m/s，負(fù)載速度為0.8 m/s。隨機(jī)生成50個(gè)任務(wù)，其中出庫(kù)27個(gè)，入庫(kù)23個(gè)，對(duì)應(yīng)出入庫(kù)點(diǎn)的坐標(biāo)見(jiàn)表1。

表1 出入庫(kù)任務(wù)列表Table 1 Inventory task list

依次求解前20、前30和50個(gè)任務(wù)的AGV分配方案。算法設(shè)計(jì)時(shí)，取多種群算法的種群數(shù)為5，最大迭代次數(shù)為1 000。同時(shí)，為驗(yàn)證本文所提出算法(adaptive multi-pop GA)的有效性，分別與傳統(tǒng)遺傳算法(GA)、多種群遺傳算法(multi-pop GA)進(jìn)行對(duì)比。

4.2 任務(wù)規(guī)模為20的AGV分配方案

GA算法在第379次迭代得到最優(yōu)解，Multi-pop GA算法在第360次得到最優(yōu)解，本文所提Adaptive Multi-pop GA算法在第340次迭代達(dá)到最優(yōu)，迭代過(guò)程見(jiàn)圖6。

圖6 Adaptive Multi-pop GA迭代過(guò)程(任務(wù)規(guī)模20)Figure 6 Calculation process of adaptive Multi-pop GA(20 tasks)

求解所得AGV調(diào)度方案見(jiàn)表2。對(duì)1號(hào)AGV，其行駛路徑為從工作臺(tái)A1出發(fā)，執(zhí)行入庫(kù)任務(wù)5，接著執(zhí)行出庫(kù)任務(wù)16，后回到A1，再依次執(zhí)行入庫(kù)任務(wù)14和出庫(kù)任務(wù)6，最后回到工作臺(tái)1。其余4臺(tái)AGV調(diào)度方案詳見(jiàn)表2。可以看出，1號(hào)、4號(hào)和5號(hào)AGV采用的是聯(lián)合作業(yè)模式，2號(hào)AGV為聯(lián)合作業(yè)模式與單獨(dú)入庫(kù)相結(jié)合，3號(hào)AGV為單獨(dú)出庫(kù)作業(yè)模式，3種作業(yè)模式并存，驗(yàn)證了本文所述模型的合理性。

表2 AGV分配方案(20個(gè)任務(wù)規(guī)模)Table 2 AGV scheme for 20 tasks

4.3 任務(wù)規(guī)模為30的AGV分配方案

經(jīng)過(guò)驗(yàn)算，GA算法在第510次迭代得到最優(yōu)解，Multi-pop GA算法在第460次迭代得到最優(yōu)結(jié)果，而本文Adaptive Multi-pop GA算法在第450次迭代就得到最優(yōu)結(jié)果，迭代曲線 (每一代的最短時(shí)間)見(jiàn)圖7。

圖7 Adaptive Multi-pop GA迭代過(guò)程(任務(wù)規(guī)模30)Figure 7 Calculation process of Adaptive Multi-pop GA(30 tasks)

求解所得AGV調(diào)度方案見(jiàn)表3。與20個(gè)任務(wù)規(guī)模類似，30個(gè)任務(wù)情況下也存在3種作業(yè)模式并存的情況。不同的是，隨著任務(wù)規(guī)模增大，AGV活動(dòng)范圍更大，因此在任務(wù)結(jié)束后AGV往往會(huì)停在不同于起始工作臺(tái)的位置。

表3 AGV分配方案(30個(gè)任務(wù)規(guī)模)Table 3 AGV scheme for 30 tasks

4.4 任務(wù)規(guī)模為50的AGV分配方案

GA算法在第900次迭代得到最優(yōu)結(jié)果，Multipop GA算法在第750次迭代得到最優(yōu)結(jié)果，而本文Adaptive Multi-pop GA算法在第720次迭代就得到最優(yōu)結(jié)果，迭代過(guò)程 (每一代的最短時(shí)間) 如圖8所示。

圖8 Adaptive Multi-pop GA迭代過(guò)程(任務(wù)規(guī)模50)Figure 8 Calculation process of Adaptive Multi-pop GA (50 tasks)

求解結(jié)果如表4所示。隨著任務(wù)規(guī)模進(jìn)一步增大，對(duì)每臺(tái)AGV，起終點(diǎn)不一致的情況增多，多種作業(yè)模式共存的情況下，路徑更為復(fù)雜。

表4 50個(gè)任務(wù)規(guī)模下求解結(jié)果Table 4 Solution results under 50 tasks

4.5 不同任務(wù)規(guī)模求解對(duì)比

為驗(yàn)證算法的適用性，在相同環(huán)境下反復(fù)運(yùn)算10次，取平均值。表5為模型求解結(jié)果對(duì)比，表6為搜索效率對(duì)比。

表5 不同算法求解作業(yè)時(shí)間對(duì)比Table 5 Comparison of different algorithms for solving job time

表6 不同算法搜索效率對(duì)比Table 6 Comparison of search efficiency of different algorithms

從求解結(jié)果分析，本文所提算法較傳統(tǒng)GA和傳統(tǒng)Multi-pop GA都有不同程度的提高，且隨著任務(wù)規(guī)模的增加，搜索效果得到保證。從求解效率看，本文所提算法迭代速度更快，迭代次數(shù)更少。

5 結(jié)論

針對(duì)AutoStore倉(cāng)儲(chǔ)系統(tǒng)作業(yè)特點(diǎn)，研究了多AGV任務(wù)分配問(wèn)題，主要結(jié)論如下。

1) 考慮到該系統(tǒng)出、入庫(kù)單獨(dú)作業(yè)和聯(lián)合出入庫(kù)作業(yè)共存的情況，給出了3種作業(yè)模式總時(shí)間最小模型，能反映該系統(tǒng)作業(yè)特點(diǎn)。求解算例表明，所得AGV分配方案中，3種作業(yè)模式并存，驗(yàn)證了模型的合理性。

2) 對(duì)傳統(tǒng)多種群遺傳算法從以下兩方面進(jìn)行改進(jìn)：首先給出了適應(yīng)于實(shí)數(shù)編碼的初始解評(píng)價(jià)因子，增加初始解的均勻性；其次，給出了自適應(yīng)遺傳因子計(jì)算式，能根據(jù)進(jìn)化程度和個(gè)體適應(yīng)值情況確定不同的操作概率，以提高解的質(zhì)量。不同規(guī)模算法計(jì)算表明，與傳統(tǒng)遺傳算法和傳統(tǒng)多種群遺傳算法相比，本文算法搜索效率和搜索效果都得到不同程度提高。

需注意的是，本文問(wèn)題分析是在某一固定時(shí)間段內(nèi)進(jìn)行，在后續(xù)研究中，將進(jìn)一步加入時(shí)間窗來(lái)滿足訂單處理的時(shí)效性限制。