孫陽君，趙 寧

(北京科技大學 機械工程學院，北京100083)

隨著電商業(yè)務的持續(xù)繁榮和人工成本持續(xù)走高，在倉儲環(huán)節(jié)以“機器換人”為目標的智能物流裝備成為越來越多物流企業(yè)的選擇。2008年，Kiva systems公司[1]首次將上百輛互相協(xié)作的自尋址車(autonomous vehicle，AV)同時用于倉儲作業(yè)中。2011年，Enright等[2]將其命名為多機器人存取系統(tǒng)(robotic mobile fulfillment system，RMFS)。圖1為RMFS系統(tǒng)俯視圖。AV依靠掃描地面的二維碼定位。定義每個二維碼標識的區(qū)域為路塊(圖2黑色方框)，2個路塊之間的連線為線段(圖2黑色粗線)，AV在路塊上據(jù)指令向任意方向行駛。

圖1 RMFS系統(tǒng)俯視圖Figure 1 Top view of RMFS

圖2路塊與線段Figure 2 Squares and routes

隨著RMFS系統(tǒng)在亞馬遜、京東、阿里巴巴等企業(yè)中的成功應用，相關(guān)科研成果不斷涌現(xiàn)。從規(guī)劃角度，通過對RMFS系統(tǒng)的規(guī)劃設(shè)計和對現(xiàn)有系統(tǒng)的優(yōu)化改進，提升系統(tǒng)性能，增加作業(yè)效率。Yuan等[3]采用開放排隊網(wǎng)模型總結(jié)了AV的數(shù)量、運行速度對系統(tǒng)性能影響規(guī)律。Lamballais等[4]采用排隊網(wǎng)模型總結(jié)了貨架布局長寬比對作業(yè)效率的影響規(guī)律。Boysen等[5]采用排隊網(wǎng)模型對訂單排序進行了優(yōu)化。Zou等[6]提出了一種AV與揀選站的匹配規(guī)則并設(shè)計了近優(yōu)解的鄰域搜索算法。同時鄒碧攀[7]也研究了系統(tǒng)寬長比對作業(yè)效率的影響。Zou等[8]通過排隊網(wǎng)模型得出換電池模式和充電模式對系統(tǒng)效率的影響。由上述研究可見，排隊網(wǎng)模型是針對RMFS廣泛采用的方法。該方法雖取得很好的成果，但忽略了AV群沖突的影響。AV群體間的沖突容易造成連環(huán)沖突和擁堵，甚至造成死鎖現(xiàn)象，排隊網(wǎng)模型難以準確表達出AV群的沖突，常常忽略AV的擁堵和死鎖。

最近，有學者開始從調(diào)度角度研究AV的沖突。Roy等[9]通過一個通道內(nèi)有AV時不許其他AV經(jīng)過的協(xié)議，杜絕了AV碰撞和擁堵的可能。李榮華[10]提出了時域協(xié)作的A*路徑規(guī)劃算法，在規(guī)劃階段避免路徑交錯以杜絕沖突。張丹露等[11]利用改進的A*算法預約表和動態(tài)加權(quán)地圖實現(xiàn)動態(tài)協(xié)同路徑規(guī)劃，解決智能倉庫內(nèi)多輛AV的沖突和碰撞問題。Merschformann等[12-13]針對AV沖突問題建立了減少沖突和死鎖的路徑規(guī)劃方法，該方法可大量減少沖突，但仍不能杜絕沖突。圍繞該方法，Merschformann等[14]進一步建立了針對RMFS的仿真系統(tǒng)。

由上述研究可見，由于路網(wǎng)結(jié)構(gòu)復雜，AV數(shù)量多，AV沖突具有強動態(tài)性和交錯性?，F(xiàn)有方法多從路徑規(guī)劃上盡量減少沖突范圍，但卻不能從全局的角度出發(fā)徹底優(yōu)化沖突，只能定性減少沖突而不能定量消除沖突，也不能精確預判任務完成時間。因此，本文提出一種可徹底消除AV群沖突的調(diào)度方法，能精確預測任務完成時間并具有節(jié)能、延壽的優(yōu)勢。該方法借鑒作業(yè)車間調(diào)度的思想，基于無等待作業(yè)車間調(diào)度的方法(no wait job-shop scheduling method, NWJSM)實現(xiàn)對AV群的無沖突調(diào)度。NWJSP是在作業(yè)車間調(diào)度的基礎(chǔ)上，增加同一工件的前一道工序和下一道工序之間不允許等待這一約束。本文并非首次將該方法應用于車輛的沖突協(xié)調(diào)。例如，昆士蘭大學的劉仕強等[15-16]將火車的沖突調(diào)度抽象為無等待柔性作業(yè)車間調(diào)度問題，以解決路塊動態(tài)沖突問題。

1問題描述

使用r個AV在路塊數(shù)為s的倉庫中完成q個任務，倉庫中有v個貨架和l個揀貨點。每個任務都需要一臺AV完成。AV需要從停放路塊移動到貨架所在路塊，再將貨架從當前路塊運送到揀貨點路塊，揀貨后將貨架運回存放路塊，行駛過程不發(fā)生任何沖突。目標是尋找總?cè)蝿胀瓿蓵r間T最小的調(diào)度解。

無沖突調(diào)度是在AV啟動前預判沖突，等待一段時間后再出發(fā)，以避免出現(xiàn)被動停車。圖3為傳統(tǒng)的沖突后調(diào)度和無沖突調(diào)度的情況。如表1所示，在沖突后調(diào)度中，AV3為避讓AV4造成AV1、AV2和AV5的啟停，需要等待4次，增加4次停車。在無沖突調(diào)度中，預判到后續(xù)的調(diào)度情況，AV4和AV5主動等待，不產(chǎn)生任何沖突，總共等待2次，新增停車次數(shù)為0。

AV調(diào)度問題和NWJSP有很多共性，可利用NWJSP的思路描述圖3的示例。將AV當作工件，路塊當作機器；路徑當作加工順序；路徑進入的路塊當作加工工序；路塊上的運行時間當作加工時間；AV離開一個路塊就立刻進入下一路塊，即無等待。圖4中每個小方格表示AV從當前路塊到下一路塊所需要的時間，不同顏色的小方格代表不同的AV。圖中可以直接看出沖突后調(diào)度的完成時間為10，無沖突調(diào)度的完成時間只有9。利用NWJSP描述AV調(diào)度問題能時刻掌握AV的運行情況，準確描述AV的調(diào)度現(xiàn)狀，精準預測任務的完成時間。無沖突調(diào)度不但減少了等待次數(shù)和停車次數(shù)，還減少了完成時間，加快完成任務的效率。

圖3沖突后調(diào)度和無沖突調(diào)度示例Figure 3 Example of interference scheduling and interference-free scheduling

表1沖突后調(diào)度和無沖突調(diào)度對比表Table 1 Comparison between interference scheduling and interference-free scheduling

AV調(diào)度問題和NWJSP還有一定差別。NWJSP中工件的加工順序和加工時間已知，機器間無約束。在AV調(diào)度問題中，需要先進行任務分配和路徑規(guī)劃才能明確AV在路塊上的運行順序并計算運行時間，而且AV在路塊上可以等待，運行時間是可變的，路塊間有約束關(guān)系。為AV分配任務可以采用就近原則，AV選擇距離最近的任務執(zhí)行，直到所有任務都完成分配。利用A*算法進行路徑規(guī)劃，生成最短路徑作為AV的運行路徑。A*算法的主要思想是在當前路塊的可達路塊中選擇與終點曼哈頓距離最小的路塊作為下一路塊。如果當前路塊無可達路塊，則當前路塊成為不可達路塊，算法從上一路塊的其他可達路塊中尋找新的可達點，直到可達路塊中包含終點，算法運行結(jié)束。多次運行A*算法，從中選擇一條最短路徑作為AV完成當前任務的路徑。根據(jù)AV的運行路徑可獲得AV在每個路塊上的運行時間，因主動等待而變動的運行時間通過NWJSM方法計算。

圖4 沖突后調(diào)度和無沖突調(diào)度示例甘特圖Figure 4 Gannt chart of the example of interference scheduling and interference-free scheduling

與NWJSP主要優(yōu)化工件的加工順序類似，本文主要優(yōu)化AV執(zhí)行任務的順序。通過已知的AV運行路徑和運行時間，按照解決NWJSP的思路進行求解，最終確定每個路塊上經(jīng)過的AV順序，明確AV在每個路塊上的運行時間，規(guī)劃AV主動等待的路塊和等待時間，得到完整的調(diào)度方案。

2數(shù)學模型

2.1假設(shè)條件

1)所有AV、貨架、揀選站在0時刻準備就緒，所有任務在0時刻到達；

2)任務間互相獨立，沒有優(yōu)先級；

3)一輛AV只接取一個任務；

4)同一時刻，路塊上最多只有一輛AV；

5)同一時刻，AV只能位于一個路塊上；

6)路塊間的通行是雙向的；

7)AV不能通過人員所在路塊，攜帶貨架時也不能通過貨架和揀選架所在路塊；

8)忽略AV沒電和損壞的情況；

9)貨架揀選完后返回原儲位。

2.2符號定義

符號定義見表2。

2.3調(diào)度優(yōu)化模型

針對AV調(diào)度問題，建立了以最小總?cè)蝿胀瓿蓵r間為目標的調(diào)度優(yōu)化模型。

表2符號定義表Table 2 Notations

其中，式(2)表示同任務的兩相鄰節(jié)點具有緊前緊后關(guān)系。式(3)表示同一路塊b上，只有上輛AV離開，下輛AV才能進入。式(4)計算運行時間Eabcd，運行時間由通過時間、啟停時間、升降時間、轉(zhuǎn)向時間、揀貨時間和等待時間組成(見圖5)，bec為任務c的貨架路塊代號，b fc為任務c的揀貨點路塊代號。只有在初始路塊、貨架所在路塊和轉(zhuǎn)彎路塊，AV才能等待，才會有等待時間。式(5)解決AV的相向沖突問題。圖6為2輛AVa和AVg在相鄰節(jié)點上的運行情況，圖下數(shù)字表示這種情況下Kbacdgi(j+1)和Khac(d+1)gij的值?？梢钥闯觯挥衶(-1,1),(1,-1)}這2種情況會發(fā)生相向沖突。為避免AV相向沖突，約束Kbacdgi(j+1)Khac(d+1)gij≠-1。式(6)計算任務c的完成時間。式(7)約束變量Kbacdgij的取值范圍。

圖5 AV在不同路塊上的運行時間Figure 5 Occupation time of AV in different squares

圖6相鄰節(jié)點AV運行情況Figure 6 The possible operations of two AVs on adjacent squares

3解決方法

3.1基于SA算法的任務順序優(yōu)化方法

模擬退火算法(simulated annealing，SA)的適用范圍廣、受初始值約束小，在處理調(diào)度問題時有很好的表現(xiàn)。因此，采用SA算法優(yōu)化任務順序，利用基于NWJSM的方案評估方法評估SA算法生成的個體。算法流程如圖7所示。

Step 1算法初始化。首先，產(chǎn)生多個個體。采用基于任務的編碼方式編碼，編碼的順序表示任務的執(zhí)行順序，長度為任務數(shù)量q。例如，[5 3 1 4 2]可作為5個任務時某個個體的編碼。其次，根據(jù)個體的編碼確定任務順序，依次利用基于NWJSM的方案評估方法進行評估。最后，采用式(8)和式(9)計算初溫W0和終溫WZ。

其中，Tmax為群體內(nèi)目標最大值；Tmin為群體內(nèi)目標最小值；pc為初始接受概率；pf為終止接受概率。

Step 2溫度達到終止溫度，算法運行結(jié)束，輸出最優(yōu)調(diào)度方案。否則，轉(zhuǎn)至Step 3。

Step 3內(nèi)循環(huán)達到一定次數(shù)，轉(zhuǎn)至Step 6，否則，轉(zhuǎn)至Step 4。

圖7算法流程圖Figure 7 Flow chart for SA

Step 4產(chǎn)生并評估新個體，為了充分探索解空間，新個體的生成方式從交換、插入、反轉(zhuǎn)、位移中隨機選擇一種。

Step 5確定是否接受新個體，然后轉(zhuǎn)至Step 3。如果新個體方案優(yōu)于舊個體方案，接受；反之，依概率接收，即接受概率大于0-1之間的隨機數(shù)rand時，接受新個體。接受概率pe與第o代的當前溫度Wo、新舊個體目標值之差 Δ和接受系數(shù)js有關(guān)(式10)。在溫度高時接受概率大，能大概率接受壞解，溫度低時基本不接受壞解。

Step 6采用式(11)[17]更新溫度(其中，α為溫度更新系數(shù))，返回Step 2。

3.2基于NWJSM的方案評估方法

利用基于NWJSM的方案評估方法生成和評估AV調(diào)度方案。在AV的調(diào)度順序已知的情況下，依次對每臺AV進行調(diào)度，方法流程如圖8所示。

調(diào)度規(guī)則為AV在上次停止的路塊主動進行等待，利用無沖突調(diào)度方法，規(guī)避沖突。

圖8基于NWJSM的方案評估方法流程圖Figure 8 Flow chart for evaluation approach based on NWJSM

圖9的案例詳細說明基于NWJSM的方案評估方法。AV3在路塊[2,3,4,5]上依次運行，運行時間為[2,3,1,1]。首先生成初步調(diào)度方案(圖9(a)虛線框)。圖9(b)中實線框代表其他AV已確定的調(diào)度方案，檢測出AV3在路塊5和AV7有沖突后，保留其他AV的調(diào)度方案，AV3在上次等待的路塊3處等待。調(diào)整后的調(diào)度方案見圖9(c)，AV3和其他AV之間已無路塊沖突。檢測相向沖突(圖9(d))，AV3與AV7發(fā)生相向沖突。保留其他AV的調(diào)度方案，AV3在上次等待的路塊3處等待。再次檢測沖突，無任何沖突則生成AV3最終的調(diào)度方案(圖9(e)實線框)。

4數(shù)值實驗

實驗在Intel Core i7-5557、3.10 GHz CPU、4.00 G RAM、64位Windows 10操作系統(tǒng)和Matlab 2016a編程環(huán)境下編譯運行。

問題初始布局見圖10，共有10輛AV、3揀選點和40貨架。第11行為AV初始點，方塊中的數(shù)字代表AV代號；第9行為人員和揀選架；第8行為揀選點，路塊代號分別為[42，46，50]；第2、3、5、6行的方格為貨架，其中的數(shù)字為貨架代號。AV任務情況如表3所示。運行參數(shù)為O=0.5，P=2.5，Q=0.5，R=3，S=8。算法參數(shù)為pc=0.99，pf=10-15，內(nèi)循環(huán)次數(shù)為50，α=0.99，js=0.01。

根據(jù)初始布局，隨機生成10組任務并分配AV(表3)，利用A*算法生成路徑(圖11)。

表4對比了本文提出的方法和傳統(tǒng)沖突后調(diào)度方法在10次重復實驗中的調(diào)度結(jié)果。完成時間為AV完成所有任務所需的時間，即目標值。最少啟停指AV完成任務的路徑中規(guī)劃的啟停次數(shù)。沖突后調(diào)度中部分AV因沖突而被動等待，所以啟停次數(shù)高于最少啟停。由表4可知，本文提出的AV群無沖突調(diào)度方法在多次實驗中都能獲得和傳統(tǒng)方法一樣的最優(yōu)解。完成時間最小的調(diào)度方案甘特圖如圖12所示。

圖9 調(diào)度方案甘特圖Figure 9 Gannt chart of scheduling solution

圖10初始布局圖Figure 10 Basic layout of the case

表3任務表Table 3 Tasks

為了更好地測試無等待調(diào)度模式求解RMFS問題的性能，針對20個AV、20個任務、5個揀選點和200個貨架的更大規(guī)模問題進行求解，初始布局圖和任務表見附錄。表5對比了本文方法和傳統(tǒng)沖突后調(diào)度方法在10次重復實驗中的調(diào)度結(jié)果?？梢钥闯觯鄬τ谛∫?guī)模問題，大規(guī)模問題不但能夠降低啟停次數(shù)，還能減少完成時間，加快完成任務的速度，提高系統(tǒng)效率。

為了驗證SA算法優(yōu)化任務完成順序的能力，對比了遺傳算法和SA算法在解決小規(guī)模問題時的調(diào)度結(jié)果。遺傳算法的選擇方式采用輪盤賭選擇；交叉方式采用線性次序交叉；變異方式等同于SA算法的產(chǎn)生新個體方式。參數(shù)為種群個數(shù)100，交叉概率0.9，變異概率0.1，代數(shù)800。表6對比了本文算法和使用遺傳算法優(yōu)化任務完成順序之后的10次實驗結(jié)果。從表中可以看出，遺傳算法找到了和SA算法同樣最優(yōu)解146，但是相比于SA算法每次都能找到最優(yōu)解，采用遺傳算法僅有30%的實驗找到了最優(yōu)解。這證明了相比于遺傳算法，SA算法更為有效穩(wěn)定。此外，如果只隨機生成一個任務順序[8 9 2 1 7 6 3 5 10 4]進行調(diào)度，最小完成時間為173.5。經(jīng)算法優(yōu)化后，最小完成時間為146。相比隨機給定任務順序，經(jīng)SA算法優(yōu)化后的調(diào)度方案節(jié)約了15%的完成時間，證明了SA算法的尋優(yōu)能力。

圖11 AV路徑圖Figure 11 Paths for AV

5結(jié)論

針對RMFS中的AV調(diào)度問題，提出了一種AV群無沖突調(diào)度方法，從全局角度出發(fā)徹底優(yōu)化和消解AV群沖突問題，同時精準預判任務完成時間。首先，分析RMFS系統(tǒng)中AV群無沖突調(diào)度問題，借助NWJSP的思想建立問題的數(shù)學模型。采用SA算法進行任務順序的優(yōu)化，提出基于NWJSM的方案評估方法生成和評估調(diào)度方案。實驗結(jié)果證實，相比初始調(diào)度方案，經(jīng)SA算法優(yōu)化后的調(diào)度方案能大幅度節(jié)約完成時間，算法有效性和穩(wěn)定性都優(yōu)于遺傳算法實驗結(jié)果?；贜WJSM的方案評估方法能精確評價調(diào)度方案，確定AV在每一時刻的動向，完全消除AV群沖突。此外，還對比了無沖突調(diào)度方法和傳統(tǒng)沖突后調(diào)度方法的調(diào)度效果。相比沖突后調(diào)度方法，本文方法能在不降低工作效率的前提下，大幅減少啟停次數(shù)，減少AV能耗從而延長AV壽命。本文目前的研究還局限在小規(guī)模AV群，AV路線也只采用最短路徑，未來將進一步結(jié)合路徑規(guī)劃研究大規(guī)模AV群無沖突調(diào)度方法。

表4本文方法和傳統(tǒng)方法調(diào)度結(jié)果對比Table 4 Comparison between interference scheduling and interference-free scheduling (small scale)

圖12本文方法最優(yōu)調(diào)度方案甘特圖Figure 12 Gannt chart of the best solution for interference-free scheduling

表5本文方法和傳統(tǒng)方法調(diào)度結(jié)果對比(20任務)Table 5 Comparison between interference scheduling and interference-free scheduling (20 tasks)

表6 SA和遺傳算法調(diào)度結(jié)果對比(小規(guī)模問題)Table 6 Comparison between SA and GA (small scale)

(責任編輯:張廣珍)

附錄 大規(guī)模問題參數(shù)

大規(guī)模問題初始布局如圖13所示，揀選點增加到5個，揀選點所在路塊代號為[75，79，83，87，91]。隨機生成20組任務，表7為任務表。

圖13大規(guī)模問題初始布局圖Figure 13 Basic layout of 20 tasks

表7任務表(20任務)Table 7 Tasks(20 tasks)