裘柯鈞， 鮑中凱， 陳 璐

(上海交通大學(xué) 機械與動力工程學(xué)院，上海 200240)

自動引導(dǎo)車(Automatic Guided Vehicle, AGV)是一種服務(wù)物流配送的智能化設(shè)備，憑借其高效、經(jīng)濟、靈活以及自動化水平高等優(yōu)勢，在某民用客機總裝車間的物料配送中發(fā)揮著重要作用.該總裝車間采用脈動式移動裝配線生產(chǎn)模式，線邊庫采用立體倉庫存儲各裝配大綱(Assembly Order, AO)的物料料包，車間內(nèi)共有3個工位，分別完成功能系統(tǒng)的安裝、功能系統(tǒng)的總裝測試以及最終功能試驗3大類作業(yè).各工位邊設(shè)置了工位暫存區(qū)，在AO工序開始前，車間內(nèi)AGV將其料包提前從線邊庫配送至工位暫存區(qū)，供工人取用.

總裝車間內(nèi)AGV的調(diào)度優(yōu)化是提高總裝生產(chǎn)物流配送效率，滿足生產(chǎn)計劃正常有序進行的關(guān)鍵.對AGV的調(diào)度優(yōu)化是指在生產(chǎn)計劃的約束下，為多輛AGV分配配送任務(wù)，并規(guī)劃每輛AGV的配送路徑，同時避免AGV間碰撞、死鎖等沖突現(xiàn)象發(fā)生.目標(biāo)是在滿足生產(chǎn)計劃的前提下，最小化AGV的使用成本.AGV的調(diào)度優(yōu)化問題得到了很多國內(nèi)外學(xué)者的關(guān)注，目前已有研究大都集中在任務(wù)分配和路徑規(guī)劃兩個方面.

針對AGV的任務(wù)分配問題，Hu等[1]針對自動化集裝箱碼頭中的聯(lián)合車輛調(diào)度和存儲分配問題建立了混合整數(shù)線性規(guī)劃模型, 并設(shè)計了一種基于貪婪搜索的三階段分解方法進行求解.Zou等[2]以矩形制造車間為背景，建立AGV任務(wù)分配問題的混合整數(shù)規(guī)劃模型，并設(shè)計了一種離散人工蜂群算法實現(xiàn)求解.夏揚坤等[3]將AGV的配送問題定義為一個帶軟時間窗需求的車輛路徑優(yōu)化模型，并設(shè)計了具有自適應(yīng)性的禁忌搜索算法(Tabu Search Algorithm, TSA)進行求解.Zou等[4]針對AGV在多品種小批量生產(chǎn)制造車間取貨送貨的調(diào)度過程，構(gòu)建了多目標(biāo)混合整數(shù)線性規(guī)劃模型，并提出一種多目標(biāo)進化算法進行求解.

針對考慮實時路徑及避撞的AGV路徑規(guī)劃問題，常用算法包括Dijkstra算法[5-6]、A*算法[7-8]、遺傳算法[9-10]、人工勢場法[11-12]等.Xing等[13]提出了一種改進TSA解決多個AGV同時工作時可能發(fā)生的沖突，以提高自動化倉庫中AGV的揀貨效率.曾慶成等[14]針對自動化集裝箱碼頭物流系統(tǒng)提出一種動態(tài)路徑規(guī)劃策略，建立AGV路徑規(guī)劃模型，并設(shè)計了基于動態(tài)路徑規(guī)劃策略的多種群蟻群算法進行求解.劉輝等[15]將多智能體強化學(xué)習(xí)應(yīng)用于AGV的路徑規(guī)劃問題，并提出了一種基于最大化累計回報頻率的獨立強化學(xué)習(xí)的方法.Murakami[16]針對AGV在柔性制造系統(tǒng)中的無沖突路徑規(guī)劃問題，分別考慮AGV和物料流動，建立了時空網(wǎng)絡(luò)模型，并將其轉(zhuǎn)化為混合整數(shù)規(guī)劃問題進行求解.

現(xiàn)有同時考慮AGV的任務(wù)分配與路徑規(guī)劃的研究中，基本都是通過簡化其中一個問題的求解來實現(xiàn)的.如，楊雅潔等[17]基于網(wǎng)格路徑布局地圖建立了混合整數(shù)規(guī)劃模型對任務(wù)分配進行求解，通過在模型中加入AGV在路口避碰約束以實現(xiàn)無沖突路徑規(guī)劃.泰應(yīng)鵬等[18]則針對任務(wù)分配建立了混合整數(shù)規(guī)劃模型，并通過對經(jīng)過路徑的時間窗的排布和更新解決碰撞沖突問題.Kelen等[19]通過TSA算法實現(xiàn)任務(wù)分配的優(yōu)化，接著基于Dijkstra算法的最短路徑和時間窗方法實現(xiàn)AGV的路徑規(guī)劃.Hao等[20]針對無人地下停車場中AGV系統(tǒng)的任務(wù)分配和路徑規(guī)劃問題，提出了一種基于混合遺傳算法的AGV調(diào)度方法和一種基于時空圖搜索算法的路徑優(yōu)化方法.Riazi等[21]提出了一種基于改進Benders分解的方法，將AGV調(diào)度問題分解為任務(wù)分配和碰撞避免約束可行性檢查兩個階段，但不適用于AGV數(shù)量較多的場景.

此外，現(xiàn)有文獻都是假設(shè)AGV僅執(zhí)行單次配送，鮮有文獻考慮AGV在配送過程中執(zhí)行多次往返配送(即配送站點及工位暫存區(qū)之間的往返配送)的問題，這是由于在AGV調(diào)度優(yōu)化過程中考慮多次往返配送時，建模和求解過程變得非常復(fù)雜.為了解決民用客機總裝車間物流配送過程中AGV的調(diào)度優(yōu)化問題，本文提出任務(wù)分配與路徑規(guī)劃兩階段求解方法，同時針對AGV在車間內(nèi)的多次往返配送現(xiàn)象，基于車間柵格化地圖，設(shè)計了基于“行程”的AGV任務(wù)分配模型，進而采用時間窗算法對AGV實際配送中經(jīng)過的柵格節(jié)點進行時間窗排布，并設(shè)計開發(fā)高效的啟發(fā)式調(diào)整策略實現(xiàn)物料配送時間沖突消解.

1 總裝車間地圖建模

總裝車間地圖采用柵格表示法，通過離散化的柵格來近似連續(xù)的地圖空間，進而達到簡化描繪的目標(biāo)[22].在基于柵格的地圖表示中，地圖被劃分為大小相等的柵格，每個柵格對應(yīng)真實環(huán)境中的一個區(qū)域.在總裝車間中，AGV的行駛道路已經(jīng)提前規(guī)劃好并柵格化，格點大小與AGV的尺寸一致，每個格點中心有一個二維碼實現(xiàn)定位，如圖1所示.

圖1 總裝車間柵格化地圖Fig.1 Grid map of final assembly workshop

車間內(nèi)包含兩條AGV行駛道路，且均為單向行駛.根據(jù)行駛方向?qū)Ω鞴?jié)點進行順序編號，節(jié)點集合N={n1,n2, …,nm}，其中nk1,nk2,nk3分別表示3個工位邊的物料暫存區(qū).AGV通過內(nèi)側(cè)道路行駛至目標(biāo)工位暫存區(qū)配送AO料包，配送任務(wù)完成后通過外側(cè)道路返回到AGV充電樁附近的?？奎c.

基于柵格化地圖模型，提出AGV任務(wù)分配與路徑規(guī)劃兩階段求解方法，流程圖如圖2所示.

圖2 兩階段求解方法流程圖Fig.2 Flow chart of two-stage method

2 基于行程的AGV任務(wù)分配模型

首先通過行程規(guī)劃列舉出車間內(nèi)AGV所有可能的行程種類，在此基礎(chǔ)上以最小化AGV的配送總成本為目標(biāo)，建立基于行程的AGV任務(wù)分配混合整數(shù)規(guī)劃模型.通過對AGV的行程規(guī)劃，提前確定不同任務(wù)組合下的可能行程信息，能夠簡化物料送達時間約束的定義，進而降低決策變量維度，提高模型的求解效率.

2.1 行程規(guī)劃

行程是指AGV從線邊庫出發(fā)，行駛至所有目標(biāo)暫存區(qū)完成AO料包的配送，并最終回到AGV充電樁附近停靠點的整個回路.首先根據(jù)配送料包數(shù)量、行駛道路的特點、目標(biāo)暫存區(qū)組合等對AGV行程進行分類，并估算每個行程的總行駛時長.假設(shè)工位暫存區(qū)數(shù)量為W，AGV的裝載容量為Q，用J表示AGV所有可能的行程種類集合，則行程種類總數(shù)為

式中：C表示排列組合符號.

一個行程種類信息可以用一個長度為W的向量α來表示，向量中第i個值表示送往暫存區(qū)i的AO料包數(shù)量，向量同時確定了AGV的所有目標(biāo)暫存區(qū)，例如αj=[0Q… 0 0]表示該行程需要將Q個AO料包送往暫存區(qū)2.為了建立AGV配送的AO料包組合與行程的對應(yīng)關(guān)系，首先為W個暫存區(qū)進行編號取值D=[D1D2…DW]，第j種行程種類的編號取值通過以下公式計算得到：

為了區(qū)分行程種類，需要設(shè)計D=[D1D2…DW]的取值，使得計算出的各個行程種類的編號取值各不相同，在任務(wù)分配模型時可以通過行程配送料包組合的不同，計算出編號取值Nj，得到該組合下的行程種類，實現(xiàn)料包組合與行程種類的一一對應(yīng).

2.2 AGV任務(wù)分配模型

模型參數(shù)及變量定義如下：I為AO料包集合；K為AGV車輛集合；R為每輛AGV實際配送的行程集合.第i(i∈I)個料包從線邊庫出發(fā)至目標(biāo)工位暫存區(qū)的配送時長為Ti，最晚送達時間為Li；第j(j∈J)種行程種類的AGV運行估計時長為Cj.AGV的單位投入成本和單位時間的運行成本分別定義為CV和CT.

模型決策變量包括：xikr(i∈I,k∈K,r∈R)為0-1變量，表示第i個料包是否由第k個AGV的第r次行程完成，是為1、否為0；wjkr(j∈J,k∈K,r∈R)為0-1變量，表示第k輛AGV的第r次行程是否為第j種行程種類，是為1、否為0；ckr(k∈K,r∈R)為連續(xù)型變量，表示第k輛AGV的第r次行程的運行時長；zkr(k∈K,r∈R)為連續(xù)型變量，表示第k輛AGV的前r次行程的總運行時長；yk(k∈K)為0-1變量，表示第k輛AGV是否被啟用，是為1、否為0；ti(i∈I)為連續(xù)型變量，表示第i個料包的實際送達時間.

建立AGV多行程任務(wù)分配模型如下：

(1)

(16)

目標(biāo)函數(shù)式(1)為最小化AGV投入和運行成本總和；式(2)保證每個AO料包有且僅由一輛AGV的一趟行程進行配送；式(3)保證AGV至少配送1個AO料包時就認為被啟用；式(4)為AGV的裝載容量約束；式(5)～(6)為AGV每趟行程中配送料包組合與行程種類的對應(yīng)關(guān)系式；式(7)為計算AGV每趟行程的估計路徑運行時長；式(8)～(9)為計算每個料包的實際送達時間；式(10)為每個料包的最晚送達時間約束；式(11)保證AGV的啟用順序為從k-1到k；式(12)保證配送行程的順序從r-1到r；式(13)～(16)為決策變量的可行域.

3 基于時間窗算法的AGV路徑規(guī)劃

得到各AGV的任務(wù)分配結(jié)果和AGV每趟行程的具體信息后，通過時間窗算法來實現(xiàn)AGV在實際行駛過程中的無沖突路徑規(guī)劃.時間窗算法[23]是建立在AGV外界環(huán)境無干擾假設(shè)下的一種預(yù)測式避障算法，即通過建立AGV的路徑信息矩陣，預(yù)先安排AGV占用柵格地圖中節(jié)點的順序，避免行駛過程中的沖突和碰撞.

3.1 時間窗算法

3.1.1行程信息的定義 總裝車間柵格化地圖中的每個柵格都可以用節(jié)點來表示，各節(jié)點的權(quán)重值定義為AGV通過該節(jié)點的運行時間與在該節(jié)點上的卸貨時間之和：

hd=ld/vd+td

(17)

式中：ld為節(jié)點nd對應(yīng)柵格的實際物理長度；vd為AGV在節(jié)點nd對應(yīng)柵格上行駛的平均速度；td為在節(jié)點nd對應(yīng)柵格上的卸貨時間，該時間僅在卸貨節(jié)點存在.

以每輛AGV的每趟行程為單位，依次對每趟行程進行時間窗的排布.為了后續(xù)時間窗規(guī)劃，對任務(wù)分配結(jié)果中所有AGV的所有行程進行重新編號，獲得行程集合S，并通過一個列表Ms來表示每個行程的具體信息，轉(zhuǎn)化為時間窗規(guī)劃工作，作為時間窗算法的輸入：

Ms=[BIststartkYrank]

(18)

3.1.2柵格節(jié)點時間窗定義Ms對應(yīng)的行程s按照順序經(jīng)過的所有節(jié)點集合定義為Ns?{n1,n2, …,nm}，Ms在節(jié)點nd∈Ns上的時間窗函數(shù)定義如下：

Tw, sd=[qtin, dtout, d]

(19)

式中：q為節(jié)點nd在節(jié)點集合Ns中的順序編號；tin, d為車輛k進入節(jié)點nd的時間；tout, d為車輛k離開節(jié)點nd的時間.對于節(jié)點nd的時間窗，滿足下式：

tout, d=tin, d+hd

(20)

若節(jié)點nd為起始節(jié)點，則進入起始節(jié)點的時間等于工作開始時間；若節(jié)點nd不是起始節(jié)點，則進入節(jié)點的時間等于AGV離開路徑中第q-1個節(jié)點的時間，即

(21)

式中：dq為AO料包q的目標(biāo)暫存區(qū)對應(yīng)的節(jié)點編號.

對于一個節(jié)點上的多個時間窗可用向量的形式表示為

Tw, d=[Tw, 1dTw, 2d…Tw, Pd]

(22)

式中：P為當(dāng)前所有行程規(guī)劃出的路徑中經(jīng)過節(jié)點nd的總行程數(shù).

若一條邊上存在多個工作的時間窗，新加入工作時間窗中的進入時間必須滿足：①進入該條邊的時間必須大于AGV從上一條邊的離開時間；②該條邊的空閑時間窗的長度足夠使車輛k在該時間內(nèi)行駛離開該條邊.假設(shè)在完成工作Ms之前，已經(jīng)有s-1個工作安排，且該s-1個工作中有P個工作規(guī)劃的行程是經(jīng)過節(jié)點nd的，為找出一個足夠長的空余時間窗來安排新的工作，空余時間窗系數(shù)由下式確定：

l=1, 2, …,P}

(23)

CK確定后，節(jié)點nd上的時間窗的進入時間如下：

(24)

若節(jié)點nd上的前P個時間窗排列緊密，無法在之前的空余時間窗排布出一個新的時間窗，則新的時間窗需要排在第P個時間窗之后，進入時間的對應(yīng)函數(shù)為

tin, d=(tout, d)P

(25)

時間窗規(guī)劃完成后，得到的AO料包q的實際送達時間由下式給出：

(26)

式中：sq為AO料包q對應(yīng)的時間窗規(guī)劃工作Msq的編號.

3.1.3時間窗算法步驟 時間窗算法具體的步驟如下.

步驟1時間窗規(guī)劃工作的定義.將AGV任務(wù)分配模型求解得到的所有AGV行程通過式(18)轉(zhuǎn)化為時間窗規(guī)劃工作.

步驟2時間窗的初始化.根據(jù)工作對應(yīng)的行程種類，找出行程經(jīng)過的節(jié)點集合Nd?{n1,n2, …,nm}，根據(jù)式(19)～(21)為每個節(jié)點排布出理想的時間窗分布.

步驟3時間窗的更新.在排布出理想情況下的節(jié)點時間窗后，再來檢查不同行程之間是否包含相同的節(jié)點.若無相同節(jié)點，則結(jié)束時間窗規(guī)劃；若存在相同節(jié)點，根據(jù)式(22)得到該節(jié)點的時間窗向量.

步驟4時間窗的插入.根據(jù)式(23)計算出空余時間窗系數(shù)CK，通過式(24)確定進入時間，并更新該工作在相同節(jié)點之后的所有節(jié)點的時間窗.

步驟5實際送達時間計算.根據(jù)式(25)計算各個AO料包的實際送達時間.

3.2 基于啟發(fā)式策略的沖突消解

時間窗算法在進行無沖突路徑規(guī)劃時，AO料包的實際送達時間會因沖突產(chǎn)生的等待而延遲，從而發(fā)生違反最晚送達時間的現(xiàn)象，對此設(shè)計了3種遞進的調(diào)整策略以實現(xiàn)沖突的消解.

(1) 料包交換策略：對違背約束的料包，搜索具有相同目標(biāo)暫存區(qū)的料包，通過交換兩個料包的配送車輛編號及配送行程，實現(xiàn)料包實際送達時間的互換，若交換后兩個料包的最晚送達時間約束都能滿足，則進行互換.料包交換策略的具體步驟如下.

步驟1檢查時間窗算法路徑規(guī)劃結(jié)果，得到違背約束的料包集合I′，以及集合中料包數(shù)量KV，并令p=1.

步驟2得到集合I′中第p個料包的目標(biāo)暫存區(qū)，在所有料包集合I中搜索與之目標(biāo)暫存區(qū)相同的料包集合Ip.

步驟3遍歷料包集合Ip，判斷是否存在料包q滿足：料包q的實際送達時間小于料包p的最晚送達時間，且料包p的實際送達時間小于料包q的最晚送達時間.若存在，則轉(zhuǎn)至步驟4，否則，結(jié)束料包交換策略，并轉(zhuǎn)至優(yōu)先級提前策略.

步驟4交換料包p和q的配送車次和行程輪次，并將第p個料包從集合I′中移除，判斷集合I′是否為空集，若I′為空集，結(jié)束料包交換策略，調(diào)整完成；若I′非空，則令p=p+1，并轉(zhuǎn)至步驟2.

(2) 優(yōu)先級提前策略：若料包交換策略失效，則對違背約束的料包，找出料包所在行程，并將行程對應(yīng)的時間窗規(guī)劃工作優(yōu)先級提前，重新進行時間窗規(guī)劃，同時采用料包交換策略進行輔助調(diào)整.優(yōu)先級提前策略的具體步驟如下.

步驟1檢查時間窗算法路徑規(guī)劃結(jié)果，得到違背約束的料包集合I′以及集合中料包數(shù)量KV，若I′為空集，結(jié)束優(yōu)先級提前策略，調(diào)整完成；若I′非空，則轉(zhuǎn)步驟2.

步驟2搜索得到集合I′中第1個料包所在的行程編號sp.

步驟3若sp=1，結(jié)束優(yōu)先級提前策略，轉(zhuǎn)至預(yù)留時長放寬策略；若sp≠1，則將行程sp的優(yōu)先級與行程sp-1的優(yōu)先級互換，重新通過時間窗算法排布行程集合P中的所有行程.

(3) 預(yù)留時長放寬策略：成倍放寬任務(wù)分配階段行程的估計行駛時長，給AGV的沖突預(yù)留更多時間，重新求解任務(wù)分配模型，并運行時間窗算法進行路徑規(guī)劃，同時采用料包交換策略和優(yōu)先級提前策略進行輔助調(diào)整.預(yù)留時長放寬策略的具體步驟如下.

步驟1設(shè)置放寬倍數(shù)v=1.1.

步驟2放寬任務(wù)分配階段各個行程種類的估計行駛時長，令Cj=vCj，并重新調(diào)用兩階段求解方法進行任務(wù)分配和路徑規(guī)劃.

步驟3重新檢查時間窗算法路徑規(guī)劃結(jié)果，得到違背約束的料包集合I′以及集合中料包數(shù)量KV，若I′為空集，結(jié)束預(yù)留時長放寬策略，調(diào)整完成；若I′非空，通過料包交換策略和優(yōu)先級提前策略進行調(diào)整，得到最終違背約束的料包集合I″，若I″為空集，結(jié)束預(yù)留時長放寬策略，調(diào)整完成，否則，令v=1.1v，轉(zhuǎn)步驟2.

4 實例驗證

4.1 算例描述

為驗證本文方法的有效性，在Python 3.6.2中進行數(shù)值實驗分析，并使用GUROBI 9.1求解器進行模型的求解.電腦配置為Intel Core TM i7-8550U CPU 1.80 GHz 以及16.0 GB內(nèi)存的Windows操作系統(tǒng).

某民用客機制造企業(yè)總裝車間現(xiàn)場布局如圖1所示.車間內(nèi)共有3個工位暫存區(qū)，每輛AGV的配送料包數(shù)量上限為2個，計算得到所有行程種類，如表1所示.

表1 行程信息Tab.1 Information of trips

根據(jù)物料需求計劃，民用飛機一個架次的總裝需要總計812個AO料包，部分料包的信息如表2所示，包括AO料包的編號、需求時間和需要送達的目標(biāo)工位.

表2 部分AO料包的物料需求計劃Tab.2 Material requirement information for some AO

車間采取日配送的計劃，即AGV提前1 d將下一工作日需要的所有AO料包從線邊庫配送至工位暫存區(qū)，每日所需配送AO料包數(shù)量如表3所示.

表3 每日所需配送料包數(shù)量Tab.3 Number of packages required to be daily delivered

考慮到目前該型號民用客機的產(chǎn)量將逐年快速遞增，每日所需配送的AO料包數(shù)量也會相應(yīng)增加，因此本文設(shè)計了規(guī)模不等的算例，所包含的AO料包數(shù)量分別為50、100、150.各AO料包的最晚送達時間依據(jù)生產(chǎn)計劃中各AO的開工時間生成.

4.2 求解結(jié)果分析

各規(guī)模算例的求解時長及使用的調(diào)整策略如表4所示.

表4 料包數(shù)為50、100、150的各算例求解時長和調(diào)整策略Tab.4 Solution time and adjustment strategy of examples with 50, 100, and 150 packages

由表中的數(shù)據(jù)分析可得：

(1) 料包數(shù)為50、100、150的算例平均求解時長分別為15.86、41.12、162.29 s，在最大規(guī)模即料包數(shù)為150時，平均求解時長達到162.29 s，在有限時間內(nèi)得到了最優(yōu)解，驗證了模型的正確性.

(2) 隨著料包數(shù)量的增加，在料包數(shù)為150的10個算例中出現(xiàn)了70%的算例需要通過料包交換策略進行調(diào)整.這表明，由于料包數(shù)量的增多，更容易出現(xiàn)料包的最晚送達時間違背約束的情況，也更需要相應(yīng)調(diào)整策略.同時，由于AGV的數(shù)量較少，大部分料包的最晚送達時間約束比較寬松，只需前兩種策略即可完成調(diào)整，未出現(xiàn)需要預(yù)留時長放寬策略進行調(diào)整的算例.

4.3 調(diào)整策略分析

以算例17為例，進一步分析沖突消解策略的應(yīng)用.表5所示為該算例的最優(yōu)AGV任務(wù)分配，表中元素為對應(yīng)行程及AGV所配送的AO料包編號，配送AO料包編號按行程進行組合，并根據(jù)行程開始時間的先后進行排序.

表5 算例17的最優(yōu)任務(wù)分配方案Tab.5 Optimal task allocation solution of Example 17

通過時間窗算法得到最優(yōu)任務(wù)分配結(jié)果下各節(jié)點的時間窗如圖3所示，橫坐標(biāo)為配送時間軸T，縱坐標(biāo)為柵格地圖中各個節(jié)點的編號nd，不同顏色表示不同AGV的行程，每個色塊的顏色表示對應(yīng)的AGV，色塊的縱坐標(biāo)表示AGV經(jīng)過的節(jié)點編號，色塊的橫向長度表示該顏色對應(yīng)的AGV在該趟行程中占用該節(jié)點的時間窗長度.

圖3 算例17的各節(jié)點時間窗規(guī)劃結(jié)果Fig.3 Time window planning results of Example 17

通過兩階段算法對算例17進行求解的過程中，第27個料包、第80個料包和第94個料包發(fā)生了實際送達時間違背最晚送達時間約束的情況.在嘗試料包交換策略失敗后，對這些料包采用了優(yōu)先級提前策略進行了調(diào)整.圖4所示為AGV4的第1～7個行程，以第7個行程中的第27個料包為例，將行程7的優(yōu)先級提升至行程4之前，使第27個料包的送達時間從60.4 min縮短至50.4 min，滿足了最晚送達時間為60 min的約束，并且重新檢驗料包送達時間信息，發(fā)現(xiàn)行程4、行程5、行程6所有料包的實際送達時間均小于最晚送達時間，通過優(yōu)先級提前策略實現(xiàn)了沖突消解.實驗表明，本方法實現(xiàn)了AGV高效的任務(wù)分配以及AGV間無沖突的路徑規(guī)劃.

圖4 調(diào)整前后行程1～7在節(jié)點10～21的時間窗規(guī)劃結(jié)果Fig.4 Time window planning results of Trips 1—7 at Nodes 10—21 before and after adjustment

5 結(jié)語

本文研究了民用客機總裝車間物流配送過程中的AGV多次往返配送問題.針對多次往返以及任務(wù)分配和路徑規(guī)劃協(xié)同決策等復(fù)雜問題特征，提出了一種AGV任務(wù)分配與路徑規(guī)劃的兩階段求解方法，分解任務(wù)分配和路徑規(guī)劃兩個子問題：第1階段提出“行程”的概念，通過行程規(guī)劃對AGV行程進行分類，大大降低了建模的復(fù)雜度，在此基礎(chǔ)上建立了基于“行程”的任務(wù)分配模型；第2階段設(shè)計了以行程表為輸入的時間窗算法與3種沖突消解策略.數(shù)值實驗表明，該方法能在有限時間內(nèi)找到AGV的最優(yōu)調(diào)度方案，不僅能夠有效解決當(dāng)前產(chǎn)量下總裝車間AGV多次往返配送問題，同時也能適應(yīng)未來飛機產(chǎn)量快速提升的生產(chǎn)物流需求.

然而，本文假設(shè)AGV的裝卸貨均為固定時長，考慮AGV裝卸貨延遲隨機性的動態(tài)優(yōu)化問題有助于提高AGV調(diào)度方案的穩(wěn)定性以及AGV的運行效率，將是AGV調(diào)度后續(xù)值得深入研究的問題.