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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1 單獨入庫作業(yè)

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

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

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

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

1.2 單獨出庫作業(yè)

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

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

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

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

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

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

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

2.1 基本假設(shè)

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

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

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

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

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

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

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

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

1) 單獨出庫作業(yè)。

式(1)表示最小化出庫作業(yè)時間，包括AGV從工作臺到出庫點的空載移動時間加上AGV從出庫點至工作臺的負(fù)載移動時間。

2) 單獨入庫作業(yè)。

式(2)表示最小化入庫作業(yè)時間，包括AGV從工作臺到入庫點的負(fù)載移動時間加上AGV從入庫點到工作臺的空載移動時間。

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

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

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

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

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

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

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

3.1 編碼方法

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

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

3.2 初始解生成及評價

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

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

圖4 基因組對比Figure 4 Genome comparison

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算例分析及驗證

4.1 算例初始條件

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

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

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

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

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

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

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

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

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

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

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

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

表3 AGV分配方案(30個任務(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é)果，迭代過程 (每一代的最短時間) 如圖8所示。

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

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