民用客機(jī)總裝車(chē)間自動(dòng)引導(dǎo)車(chē)任務(wù)分配及路徑規(guī)劃

裘柯鈞， 鮑中凱， 陳 璐

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

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

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

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

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

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

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

1 總裝車(chē)間地圖建模

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

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

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

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

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

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

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

2.1 行程規(guī)劃

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

式中：C表示排列組合符號(hào).

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

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

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

模型參數(shù)及變量定義如下：I為AO料包集合；K為AGV車(chē)輛集合；R為每輛AGV實(shí)際配送的行程集合.第i(i∈I)個(gè)料包從線(xiàn)邊庫(kù)出發(fā)至目標(biāo)工位暫存區(qū)的配送時(shí)長(zhǎng)為T(mén)i，最晚送達(dá)時(shí)間為L(zhǎng)i；第j(j∈J)種行程種類(lèi)的AGV運(yùn)行估計(jì)時(shí)長(zhǎng)為Cj.AGV的單位投入成本和單位時(shí)間的運(yùn)行成本分別定義為CV和CT.

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

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

(1)

(16)

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

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

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

3.1 時(shí)間窗算法

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

hd=ld/vd+td

(17)

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

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

Ms=[BIststartkYrank]

(18)

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

Tw, sd=[qtin, dtout, d]

(19)

式中：q為節(jié)點(diǎn)nd在節(jié)點(diǎn)集合Ns中的順序編號(hào)；tin, d為車(chē)輛k進(jìn)入節(jié)點(diǎn)nd的時(shí)間；tout, d為車(chē)輛k離開(kāi)節(jié)點(diǎn)nd的時(shí)間.對(duì)于節(jié)點(diǎn)nd的時(shí)間窗，滿(mǎn)足下式：

tout, d=tin, d+hd

(20)

若節(jié)點(diǎn)nd為起始節(jié)點(diǎn)，則進(jìn)入起始節(jié)點(diǎn)的時(shí)間等于工作開(kāi)始時(shí)間；若節(jié)點(diǎn)nd不是起始節(jié)點(diǎn)，則進(jìn)入節(jié)點(diǎn)的時(shí)間等于AGV離開(kāi)路徑中第q-1個(gè)節(jié)點(diǎn)的時(shí)間，即

(21)

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

對(duì)于一個(gè)節(jié)點(diǎn)上的多個(gè)時(shí)間窗可用向量的形式表示為

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

(22)

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

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

l=1, 2, …,P}

(23)

CK確定后，節(jié)點(diǎn)nd上的時(shí)間窗的進(jìn)入時(shí)間如下：

(24)

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

tin, d=(tout, d)P

(25)

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

(26)

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

3.1.3時(shí)間窗算法步驟 時(shí)間窗算法具體的步驟如下.

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

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

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

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

步驟5實(shí)際送達(dá)時(shí)間計(jì)算.根據(jù)式(25)計(jì)算各個(gè)AO料包的實(shí)際送達(dá)時(shí)間.

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

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

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

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

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

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

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

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

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

步驟2搜索得到集合I′中第1個(gè)料包所在的行程編號(hào)sp.

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

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

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

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

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

4 實(shí)例驗(yàn)證

4.1 算例描述

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

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

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

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

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

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

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

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

4.2 求解結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

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