李 騰，馮 珊

(哈爾濱商業(yè)大學(xué) 管理學(xué)院，黑龍江 哈爾濱150028)

電商的迅速發(fā)展為物流帶來了新的挑戰(zhàn)，傳統(tǒng)的“人到貨”揀選系統(tǒng)中，揀貨員的揀貨時間占其工作時間的60%～70%，這種揀選方式效率較低，已經(jīng)不能滿足消費者對配送時間的需求[1]。隨著美國亞馬遜Kiva系統(tǒng)的廣泛應(yīng)用[2]，在揀選系統(tǒng)中采用AGV配合人來完成揀選作業(yè)受到了越來越多的關(guān)注。這種“貨到人”的揀選方式可以大幅度提高揀選效率，具有更好的靈活性[3-5]。對于該揀選系統(tǒng)，如何進行AGV調(diào)度是影響揀選系統(tǒng)效率的主要因素。

近年來，許多學(xué)者從不同角度對AGV調(diào)度問題進行了研究。傅正堂等[6]研究了AGV調(diào)度問題，從AGV初始剩余電量不同的角度，考慮AGV空載與重載耗電量的差異，建立AGV調(diào)度模型，解決初始電量不同的AGV調(diào)度問題，減少AGV使用數(shù)量，并提高了作業(yè)效率。梁承姬等[7]考慮中轉(zhuǎn)平臺與容量約束，以任務(wù)完成時間最短為優(yōu)化目標，建立具有時間窗約束的AGV調(diào)度模型，利用遺傳算法求解模型，解決AGV的調(diào)度問題，減少了作業(yè)時間。韓曉龍等[8]設(shè)計3種不同的AGV調(diào)度策略，通過仿真分析，得出AGV調(diào)度與數(shù)量配置是提高效率的關(guān)鍵因素，最后對AGV調(diào)度策略與數(shù)量配置提出了建議。Fazlollahtabar等[9]對AGV調(diào)度進行研究，考慮AGV提前到達會造成等待時間的浪費，以最小化提前到達與遲到的懲罰為目標函數(shù)，實現(xiàn)了AGV的調(diào)度。Singh等[10]針對AGV調(diào)度問題，提出一種新的調(diào)度方案，將車間加工區(qū)域進行劃分并為每個區(qū)域分配一臺AGV，提升了系統(tǒng)運行的效率。沈博聞等[11]針對AGV調(diào)度問題展開研究，考慮系統(tǒng)的擁塞程度，通過對AGV完成任務(wù)的總代價進行優(yōu)化，實現(xiàn)了AGV的智能調(diào)度并降低了系統(tǒng)的運行成本。袁瑞萍等[12]針對AGV調(diào)度問題，提出多個揀選臺同步揀選與異步揀選2種揀選方式，以所有任務(wù)的完成時間最短為優(yōu)化目標，建立2種揀選方式下的AGV調(diào)度模型，利用改進遺傳算法對兩調(diào)度模型進行求解，通過實例仿真得出同步揀選具有更高的效率，同時解決了AGV的調(diào)度問題。

目前，多數(shù)學(xué)者針對不同領(lǐng)域的AGV調(diào)度問題進行研究，上述文獻中任務(wù)的下發(fā)方式為一次下發(fā)。而在實際工作過程中，任務(wù)通常是以分批的形式下發(fā)，并且多數(shù)文獻只考慮了AGV的運行時間，沒有考慮到AGV的排隊等待時間。大多數(shù)系統(tǒng)在進行AGV調(diào)度時，通常會調(diào)度空閑的AGV來完成當(dāng)前的任務(wù)以減少任務(wù)的完成時間，但這也會導(dǎo)致AGV的等待時間增加，使任務(wù)的完成時間增加。因此，本文針對“貨到人”揀選系統(tǒng)，提出分批下發(fā)任務(wù)情況的一種隨機調(diào)度策略，同時考慮AGV在揀選臺的排隊等待時間，以所有任務(wù)的完成時間最短為優(yōu)化目標，進行AGV隨機調(diào)度。

1問題描述

“貨到人”揀選系統(tǒng)的布局如圖1所示，貨架之間的區(qū)域為AGV的行走通道，揀選區(qū)域由多個揀選臺組成，每個揀選臺有1名揀選人員完成揀選作業(yè)，多個揀選臺可以同時作業(yè)，系統(tǒng)中的AGV可以在不同的揀選臺等待揀選。系統(tǒng)接收客戶訂單后，倉庫管理系統(tǒng)將某一時間段內(nèi)的訂單按照其任務(wù)是否在同一貨架上的規(guī)則進行分批處理，然后將處理后的任務(wù)發(fā)送至調(diào)度系統(tǒng)，調(diào)度系統(tǒng)進行AGV的調(diào)度并將任務(wù)進行分配。此時，AGV將從初始位置到達被分配任務(wù)所在的貨架位置識別貨架，將其搬運至指定的揀選臺等待揀選。揀選人員確定貨物信息后，在該貨架的指定貨位將所需貨物揀出并進行掃描。掃描完成后，揀選人員將貨物放至指定的貨筐中，同時AGV將此貨架搬運至原來的位置，并在該位置等待任務(wù)的再次分配。在AGV完成任務(wù)的過程中，如果電量低于安全電量，AGV將在完成當(dāng)前任務(wù)后，到達充電區(qū)進行充電，直到充滿才可以對其分配任務(wù)。

圖1“貨到人”揀選系統(tǒng)布局Figure 1 Layout of the "rack to picker"picking system

本文所提隨機調(diào)度策略是指將任務(wù)進行分配之前，不確定AGV的狀態(tài)，任務(wù)可以分配給所有的AGV來完成。如果在任務(wù)分配的同時，AGV處于忙碌狀態(tài)，則需要等待該AGV完成上一個任務(wù)后才能完成該任務(wù)。這種調(diào)度策略下部分目標貨架可能需要等待，會造成時間的浪費，但相比于目前使用較多的調(diào)度空閑AGV策略可能會得到全局近似最優(yōu)解。調(diào)度空閑AGV策略是指確定系統(tǒng)中AGV的狀態(tài)，任務(wù)每次只分配給空閑的AGV來完成。這種調(diào)度策略雖然解決了目標貨架的等待時間的浪費，但不能從全局的角度進行AGV的任務(wù)分配。本文通過優(yōu)化AGV完成所有任務(wù)所用時間來提高揀選效率。

2模型構(gòu)建

2.1研究假設(shè)

針對“貨到人”揀選系統(tǒng)調(diào)度策略，本文做出如下假設(shè)。

1)初始時刻，系統(tǒng)中的所有AGV處于空閑狀態(tài)；

2)完成任務(wù)的過程中，系統(tǒng)中所有AGV的電量始終大于安全電量；

3)AGV將貨架搬回后，在該貨架位置等待下一次任務(wù)的分配；

4)AGV在完成任務(wù)的過程中，始終勻速行駛，并且所有AGV的行駛速度相同；

5)AGV在行走過程中，不存在避障等狀況；

6)貨物是隨機存儲在貨架上的；

7)每個揀選臺對應(yīng)的揀選人員每次完成揀貨工作的時間相同，分貨時間相同。

2.2參數(shù)設(shè)計

1)m為AGV的總數(shù)量，n為任務(wù)的總數(shù)量，q為 揀選臺的總數(shù)量；

2)i為第i臺AGV，i∈[1,m]，j為第j個任 務(wù)，為第k個揀選臺

3)(xAi,yAi)表示第i臺AGV的位置坐標，表示第j個任務(wù)的位置坐標， (xPk,yPk)表示第k個揀選臺的位置坐標；

4)d1io j表 示第i臺AGV從初始位置到第j個任務(wù)所行駛的最小距離，d2i jk表示第i臺AGV從第j個任務(wù)到第k個揀選臺所行駛的最小距離，d3ik j表示第i臺AGV從第k個揀選臺回到第j個任務(wù)所行駛的最小距離。本文所有最小距離計算均采用曼哈頓距離，即

5)v表示AGV的行駛速度；

6)t1表 示揀選人員的揀貨時間，t2表示揀選人員的分貨時間；

7)r表示每個揀選臺一次呼叫任務(wù)的數(shù)量，每次呼叫的時間點為上一批任務(wù)中最早到達該揀選臺的時間點，其中r∈[1,n]；

8)l表示任務(wù)到達揀選臺的順序，序號l∈[1,n]；

9)tcj表 示第j個任務(wù)被呼叫的時間點；

10)tlk j表 示第l個 到達第k個揀選臺的第j個任務(wù)到達該揀選臺的時間點；

11)tp(l-1)k j表 示第l-1個 到達第k個揀選臺的第j個任務(wù)被揀選完成的時間點；

12)tbi j表示由第i臺AGV完成的第j個任務(wù)被揀選完成后，該AGV回到該任務(wù)位置的時間點；

13)tqilk j為由第i臺AGV完成的第l個 到達第k個揀選臺的第j個任務(wù)在該揀選臺的等待時間tqilk j=

14)T i為 第i臺AGV完成被分配任務(wù)所花費的總時間；

[38]王裕巽估算，嘉靖一朝四十五年，白銀采納總額共計1928100兩。王裕巽：《明代白銀國內(nèi)開采與國外流入數(shù)額試考》，《中國錢幣》，1998年第3期。

15)T為所有任務(wù)的完成時間；

16)決策變量Xi j表示第i臺AGV是否完成第j個任務(wù)，且

2.3隨機調(diào)度策略模型

在揀選系統(tǒng)中，一批任務(wù)的完成時間為所有AGV完成各自被分配的任務(wù)所花費的最長時間。本文以耗時最長的AGV的完成任務(wù)時間最短為目標函數(shù)，最小化訂單的完成時間，以任務(wù)分配為決策變量，考慮AGV在揀選臺的排隊等待時間，建立隨機調(diào)度策略模型。

上述模型中，Xi j為決策變量；式(1)為最小化所有AGV中完成各自任務(wù)的最長時間；式(2)將其分為AGV完成任務(wù)所行走的時間與AGV在揀選臺的排隊等待時間，其中，AGV的行走距離分為3個部分，d1io j為該AGV上次完成的任務(wù)所在位置；式(3)為由第i臺AGV完成的第l個 到達第k個揀選臺的第j個任務(wù)在揀選臺的排隊等待時間，與該AGV所在排隊隊列中的前一臺AGV被揀選完成的時間點和該AGV到揀選臺的時間點有關(guān)；式(4)為任務(wù)被揀選完成的時間，由AGV到達揀選臺的時間點、AGV的等待時間、揀選人員的揀貨時間以及分貨時間決定；式(5)為AGV將貨架搬運至原來位置的時間點；式(7)表示系統(tǒng)中的每個任務(wù)只能由一臺AGV完成。

3模型求解

遺傳算法在求解組合優(yōu)化問題時，具有操作簡單、并行性、計算效率高、通用性以及穩(wěn)定性等特點[13-14]。由于AGV調(diào)度問題與任務(wù)分配問題屬于組合優(yōu)化問題，并且采用遺傳算法中實數(shù)編碼的方式可以將AGV的調(diào)度結(jié)果、任務(wù)分配結(jié)果以及揀選序列直觀地體現(xiàn)出來，因此，本文采用遺傳算法對上述模型進行求解。

1)生成初始種群。首先確定初始種群的數(shù)量與每次呼叫任務(wù)的數(shù)量。然后，將訂單中所有任務(wù)進行分組，每組任務(wù)中不能調(diào)度相同的AGV。最后，采用實數(shù)進行編碼生成染色體，如圖2所示。染色體的長度為單個訂單中任務(wù)的總數(shù)；每個基因位代表一個任務(wù)；基因位上對應(yīng)的值表示該序號的AGV完成該位置的任務(wù)。這種編碼方式可以縮短染色體的長度，直接觀察出每臺AGV完成的任務(wù)以及同一臺AGV完成任務(wù)的先后順序。

圖2染色體編碼方式Figure 2 Chromosome coding

2)計算適應(yīng)度值。每條染色體的適應(yīng)度值為所有AGV完成各自全部任務(wù)耗費時間中的最大值的倒數(shù)。適應(yīng)度函數(shù)為

3)選擇。選擇一定數(shù)量的適應(yīng)度值較高的優(yōu)良個體作為父代。

4)交叉。按照交叉概率，采用不定點交叉的方式進行交叉操作，過程如圖3所示。將染色體按照每次呼叫任務(wù)的數(shù)量進行分段，在任務(wù)的組數(shù)范圍內(nèi)隨機生成2個值為交叉位置，表示一條染色體的某段基因與另一條染色體的某段基因進行交叉。

5)變異。按照變異對染色體進行變異操作。在任務(wù)總數(shù)范圍內(nèi)，隨機產(chǎn)生一個整數(shù)表示發(fā)生變異的基因位，該基因位的值不能與同一段基因位的值相同，表示同一組任務(wù)內(nèi)不可調(diào)度相同序號的AGV。

6)終止。設(shè)置最大迭代次數(shù)，當(dāng)達到最大迭代次數(shù)時，終止迭代，輸出最優(yōu)結(jié)果。

圖3交叉過程Figure 3 Chromosome crossing process

4實例仿真與分析

為驗證隨機調(diào)度策略的有效性，利用遺傳算法設(shè)計仿真實驗。其初始種群個數(shù)設(shè)置為400，交叉概率為0.6，變異概率為0.08。假設(shè)仿真實驗在60 m×60 m的倉庫中進行，將倉庫左下角的第1個揀選臺坐標位置設(shè)為(0,0)。針對一個揀選臺的5批訂單展開研究，設(shè)置該揀選臺每批訂單中的任務(wù)數(shù)量為60，其中，第1批訂單中任務(wù)的位置如表1所示，系統(tǒng)中有10臺AGV并且電量始終充足，其隨機初始位置如表2所示，該揀選臺的揀選人員每次完成揀貨工作的時間為8 s，分貨時間為6 s。首先將一批訂單中的所有任務(wù)進行分組，每次呼叫3個任務(wù)，呼叫時間為上一組任務(wù)中最早到達揀選臺的時間點，該訂單的完成時間為所有AGV中完成各自任務(wù)耗時最長的時間。對每批訂單進行10次仿真實驗，取10組數(shù)據(jù)中的最小值作為AGV完成該訂單中所有任務(wù)的總時間。

對隨機調(diào)度策略進行仿真。圖4為AGV完成所有任務(wù)總時間的迭代圖，表3為所有任務(wù)的分配結(jié)果。

在實際的倉庫運行過程中，通常會調(diào)用空閑的AGV來完成當(dāng)前的任務(wù)以減少任務(wù)的完成時間。但在這種情況下，每次可調(diào)度的AGV數(shù)量減少，且沒有考慮到AGV在揀選臺的等待時間，反而會導(dǎo)致任務(wù)的完成時間變長，因此為了驗證隨機調(diào)度策略的效果，對調(diào)度空閑AGV策略進行對比仿真。調(diào)度空閑AGV策略的數(shù)學(xué)模型中增加了約束參數(shù)Yi，表示每次呼叫的任務(wù)只能由空閑的AGV來完成，只有Yi與Xi j的值同時為1時，第i臺AGV才完成第j個任務(wù)。AGV是否為空閑取決于當(dāng)前任務(wù)的呼叫時間點與該AGV完成上一個任務(wù)的時間點之間的差值，如式(9)所示。

表1第1批訂單的任務(wù)位置Table 1 Position of the tasks of the first order

表2 AGV位置Table 2 Position of AGVs

針對以上任務(wù)，采用調(diào)度空閑AGV策略進行仿真。圖5為AGV完成所有任務(wù)總時間的迭代圖，任務(wù)分配結(jié)果如表4所示。

從圖4和圖5可以看出，隨著迭代次數(shù)的增加，AGV完成所有任務(wù)的總時間不斷減少，最終找到最優(yōu)解。表3、表4中任務(wù)分配結(jié)果的第1個數(shù)字代表AGV的序號，后面則是該AGV依次完成的任務(wù)序號。從表中可以看出，不同的調(diào)度策略得到的任務(wù)分配結(jié)果不同，所有任務(wù)的完成時間不同。通過數(shù)值比較，本文所提出的隨機調(diào)度策略的AGV完成所有任務(wù)總時間優(yōu)于調(diào)度空閑AGV策略。為進一步驗證隨機調(diào)度策略具有更優(yōu)的效率，分別采用2種調(diào)度策略對5批訂單進行仿真。圖6為針對5批訂單采用2種調(diào)度策略下的AGV完成所有任務(wù)總時間的對比圖。從圖6可以看出，隨機調(diào)度策略較調(diào)度空閑AGV策略揀選效率更高。

表3隨機調(diào)度策略的任務(wù)分配結(jié)果Table 3 Task assignment results of random scheduling strategy

表4調(diào)度空閑AGV策略的任務(wù)分配結(jié)果Table 4 Task assignment results of scheduling idle AGV

圖4隨機調(diào)度策略下AGV完成所有任務(wù)的總時間迭代圖Figure 4 Total time to complete all tasks using a random scheduling strategy

圖5調(diào)度空閑AGV策略下完成所有任務(wù)的總時間迭代圖Figure 5 Total time to schedule idle AGV to complete all tasks

圖6 2種調(diào)度策略下AGV完成5批訂單的時間Figure 6 Time for AGV to complete five orders under the two scheduling strategies

在仿真中發(fā)現(xiàn)，調(diào)度空閑AGV策略下，AGV可選集合中AGV的數(shù)量較少，為進一步驗證以上所得出隨機調(diào)度策略較優(yōu)的結(jié)果是否受AGV數(shù)量的影響，將AGV的數(shù)量分別取12、14、16及18，對不同數(shù)量AGV分別進行10次仿真實驗，每組最小值作為該數(shù)量AGV完成所有任務(wù)的總時間，如圖7所示，對不同AGV數(shù)量情況下的2種調(diào)度策略分別進行仿真。

從圖7可以看出采用隨機調(diào)度策略時所有任務(wù)的總完成時間始終低于調(diào)度空閑AGV情況，說明隨機調(diào)度策略優(yōu)于調(diào)度空閑AGV策略。隨著AGV數(shù)量的增加，采用隨機調(diào)度策略，能在一定程度上提高效率，但當(dāng)AGV數(shù)量高于一定值時，效率提升并不明顯。對于調(diào)度空閑AGV策略，最初曲線呈下降趨勢，但當(dāng)AGV數(shù)量為16時，反而降低了效率，由此可以得到較優(yōu)的AGV數(shù)量配置。為進一步分析曲線上升原因，考慮到所有任務(wù)的完成時間由AGV的行走時間與AGV在揀選臺的等待時間組成，因此，對仿真結(jié)果中AGV的等待時間做進一步分析，如圖8所示。

圖7 不同AGV數(shù)量情況下采用2種調(diào)度策略的所有任務(wù)完成時間Figure 7 All task completion time with two scheduling strategies for different AGV numbers

圖8為當(dāng)AGV數(shù)量為16時，分別對2種調(diào)度策略的10次仿真實驗結(jié)果降序排序?？梢钥闯觯捎秒S機調(diào)度策略時，AGV等待時間所占比例明顯少于調(diào)度空閑AGV策略時AGV等待時間所占比例，并且2種調(diào)度策略的AGV等待時間占總完成時間的比例較大，進一步對等待時間進行分析。圖9為分別采用2種調(diào)度策略時16臺AGV的總等待時間。

由圖9可以看出采用調(diào)度空閑AGV策略時，大多數(shù)AGV的總等待時間多于采用隨機調(diào)度策略時AGV的總等待時間。但此圖還無法說明16臺AGV時調(diào)度空閑AGV策略總完成時間上升，隨機調(diào)度策略時間下降減緩的現(xiàn)象。因此將AGV的數(shù)量分別取12、14及16，對AGV的總等待時間進行分析，結(jié)果如圖10所示。

圖9 2種調(diào)度策略下AGV總等待時間Figure 9 Total waiting time of each AGV under two scheduling strategies

圖10不同數(shù)量AGV情況下2種調(diào)度策略AGV總等待時間Figure 10 Total waiting time of AGV of two scheduling strategies with different numbers of AGV

圖10為當(dāng)AGV數(shù)量不同時，2種調(diào)度策略下AGV的等待時間，將每種情況的仿真結(jié)果降序排序。當(dāng)AGV數(shù)量相同時，實線的大部分點低于虛線點，表示采用隨機調(diào)度策略時，AGV的總等待時間低于采用調(diào)度空閑AGV策略時AGV的總等待時間，間接說明了采用隨機調(diào)度策略時所有任務(wù)的完成時間少于調(diào)度空閑AGV時所有任務(wù)的完成時間的原因。隨著AGV數(shù)量的增加，2種調(diào)度策略的AGV總等待時間增加，但采用調(diào)度空閑AGV 策略時，AGV總等待時間的增量大于采用隨機調(diào)度策略時AGV總等待時間的增量。

圖11為AGV數(shù)量增加時，10次實驗的2種調(diào)度策略下AGV的平均等待時間與平均行走時間。隨著AGV數(shù)量的增加，2種調(diào)度策略的AGV總等待時間增加，但采用隨機調(diào)度策略時AGV等待時間的增量小于采用調(diào)度空閑AGV策略時的增量，AGV數(shù)量為16時，采用調(diào)度空閑AGV策略的AGV總等待時間的增量大于AGV總行走時間的減少量，因此此時AGV完成所有任務(wù)的總時間會增加。這就解釋了圖7中采用調(diào)度空閑AGV策略時，AGV數(shù)量增加反而會導(dǎo)致所有任務(wù)的總完成時間增加的結(jié)果。

圖11 AGV數(shù)量增加情況下2種調(diào)度策略的AGV等待時間與行走時間Figure 11 Waiting time and traveling time of AGV of the two scheduling strategies when the number of AGV increases

綜上分析，隨著AGV數(shù)量的增加，可以調(diào)度的AGV數(shù)量增加，AGV將貨架搬運至揀選臺所花費的時間減少，意味著每次呼叫的時間提前，這導(dǎo)致了排隊等待的AGV數(shù)量增加和所有AGV等待時間的增加。由于采用調(diào)度空閑AGV策略時，隨著AGV數(shù)量的增加，所增加的AGV的等待時間大于AGV搬運任務(wù)所花費時間的減少量，因此完成所有任務(wù)的總時間增加，而采用隨機調(diào)度策略時，隨著AGV數(shù)量的增加，所增加的AGV等待時間小于AGV搬運任務(wù)所花費時間的減少量，因此完成所有任務(wù)的總時間減少。當(dāng)AGV數(shù)量一定時，隨機調(diào)度策略與調(diào)度空閑AGV策略相比，每次可以調(diào)度的AGV數(shù)量較多，進而可以得到全局最優(yōu)解。通過以上仿真結(jié)果進行分析，隨機調(diào)度策略比調(diào)度空閑AGV策略效率更高。當(dāng)采用隨機調(diào)度策略時，隨著AGV數(shù)量的增加，系統(tǒng)效率的提升并不明顯，所以，考慮AGV的投入成本較高，配置14臺AGV完成以上任務(wù)比較合理。

5結(jié)論

在“貨到人”揀選系統(tǒng)中，為了提高系統(tǒng)的揀選效率，本文從AGV調(diào)度策略角度進行優(yōu)化，提出了一種隨機調(diào)度策略。以耗時最長的AGV的完成任務(wù)時間最短為目標函數(shù)，考慮AGV在揀選臺的排隊等待時間，建立隨機調(diào)度策略的數(shù)學(xué)規(guī)劃模型，通過遺傳算法進行求解。仿真實驗結(jié)果表明，本文所提出的隨機調(diào)度策略減少了AGV在揀選臺的排隊等待時間，提高了揀選效率。通過不同數(shù)量AGV揀選效率對比實驗仿真發(fā)現(xiàn)，AGV數(shù)量的增加對最終效率提升的貢獻有限。該結(jié)果對揀選系統(tǒng)中AGV的數(shù)量配置具有一定的指導(dǎo)作用。本文所提隨機調(diào)度策略在得到全局近似最優(yōu)解的同時解決了AGV調(diào)度與揀選系列問題，為揀選系統(tǒng)的設(shè)計與應(yīng)用提供了參考。