制造車間自動(dòng)導(dǎo)引車調(diào)度新進(jìn)展

曹立佳，劉 洋

1.四川輕化工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，四川 宜賓644000

2.人工智能四川省重點(diǎn)實(shí)驗(yàn)室，四川 自貢643000

3.四川輕化工大學(xué) 自動(dòng)化與信息工程學(xué)院，四川 宜賓644000

自動(dòng)導(dǎo)引車（Automated Guided Vehicle，AGV）作為一種全自動(dòng)或半自動(dòng)的運(yùn)載工具，服務(wù)于制造行業(yè)。其優(yōu)點(diǎn)是載重能力強(qiáng)、運(yùn)載起止地準(zhǔn)確、運(yùn)載時(shí)間可準(zhǔn)確控制、無(wú)人化、節(jié)能、高效、綠色、工作環(huán)境適應(yīng)性強(qiáng)等。自動(dòng)導(dǎo)引車的應(yīng)用幫助制造類企業(yè)節(jié)約了人力成本，實(shí)現(xiàn)了車間自動(dòng)化中物料和工件運(yùn)輸這一關(guān)鍵步驟。自動(dòng)導(dǎo)引車能夠與各物料站點(diǎn)和機(jī)器工位之間形成協(xié)調(diào)配合的工作方式，讓每一臺(tái)機(jī)器都能盡最大可能發(fā)揮其工作效率，從而提高工作車間的整體生產(chǎn)效率。20世紀(jì)50年代，美國(guó)Basrrett Electric公司發(fā)明了第一臺(tái)用于倉(cāng)儲(chǔ)貨物運(yùn)輸?shù)淖詣?dòng)導(dǎo)引車以后，自動(dòng)導(dǎo)引車隨即開始服務(wù)于制造業(yè)[1]，乃至于當(dāng)今的服務(wù)業(yè)、公共安全等領(lǐng)域。

AGV服務(wù)于制造企業(yè)，離不開其良好的調(diào)度系統(tǒng)，文獻(xiàn)[2]主要對(duì)2018年及以后國(guó)內(nèi)外AGV調(diào)度領(lǐng)域的文獻(xiàn)進(jìn)行了綜述。本文主要針對(duì)文獻(xiàn)[2]以后的最近三年制造車間AGV調(diào)度領(lǐng)域的文獻(xiàn)進(jìn)行了分析，對(duì)研究的問題、研究的方法進(jìn)行了歸納總結(jié)，指出了現(xiàn)階段存在的不足，對(duì)將來(lái)的研究方向提出了一些建議。

1 AGV調(diào)度問題描述

制造企業(yè)中AGV系統(tǒng)包括AGV小車、充電樁[3-4]、運(yùn)行路徑[5-8]、緩沖區(qū)[9]、作業(yè)工位以及其他協(xié)同配合的機(jī)器[10-11]等。AGV調(diào)度優(yōu)化的目的是保證完成相應(yīng)的生產(chǎn)搬運(yùn)任務(wù)，同時(shí)保證某項(xiàng)或某些性能指標(biāo)達(dá)到最優(yōu)。

AGV調(diào)度的數(shù)學(xué)模型一般可表述如下：

公式中ai、bi、ci為常數(shù)，l、m、n為非負(fù)整數(shù)。公式（1）中f(x)為待優(yōu)化的目標(biāo)函數(shù)；公式（2）、（3）為不等式約束；公式（4）為等式約束。約束條件一般包括AGV與任務(wù)之間的分配關(guān)系，AGV與其他設(shè)備（如機(jī)器）的匹配關(guān)系，AGV和/或其他設(shè)備的處理過程持續(xù)不能中斷，AGV和/或其他設(shè)備的作業(yè)順序、開始/完成時(shí)間、故障和修復(fù)時(shí)間[12]，物料裝卸順序，AGV提前或延遲到達(dá)工位，AGV可承載的容量，解空間搜索區(qū)域，AGV運(yùn)行方向，AGV電池余量等。

AGV調(diào)度優(yōu)化的目標(biāo)函數(shù)f(x)可以是單獨(dú)一個(gè)優(yōu)化目標(biāo)，也可以是多個(gè)優(yōu)化目標(biāo)。當(dāng)今制造車間的規(guī)模較大，且倡導(dǎo)節(jié)能減排的綠色生產(chǎn)政策，加之現(xiàn)如今計(jì)算機(jī)的算力進(jìn)一步提升，AGV調(diào)度的目標(biāo)函數(shù)是以兩個(gè)或者更多優(yōu)化目標(biāo)為主。近三年的文獻(xiàn)中大多數(shù)文獻(xiàn)的研究工作均是以雙目標(biāo)和多目標(biāo)優(yōu)化模型展開研究的。

AGV調(diào)度的優(yōu)化目標(biāo)函數(shù)包括總完工時(shí)間、運(yùn)輸總成本、工件加工成本、周期時(shí)間、AGV數(shù)量、AGV空載運(yùn)行時(shí)間、AGV電能消耗、AGV等待時(shí)間、AGV提前到達(dá)代價(jià)、AGV延遲到達(dá)代價(jià)、負(fù)載平衡等，多目標(biāo)優(yōu)化可表示為：

公式（5）中x為優(yōu)化模型中考慮的變量；L為目標(biāo)函數(shù)的個(gè)數(shù)；ωj為第j個(gè)目標(biāo)函數(shù)的權(quán)重因子，并且滿足用來(lái)調(diào)整第j個(gè)目標(biāo)函數(shù)fj(x)的取值范圍。

AGV調(diào)度優(yōu)化的另一個(gè)關(guān)鍵問題是優(yōu)化算法的選擇和改進(jìn)，以適應(yīng)特定的優(yōu)化需求和優(yōu)化模型?，F(xiàn)階段最常用的優(yōu)化算法是智能優(yōu)化算法，尤其是遺傳算法大量被用來(lái)求解調(diào)度模型。優(yōu)化的結(jié)果可由表格呈現(xiàn)，也可以用甘特圖（Gantt chart）繪制出更直觀的優(yōu)化結(jié)果。

2 AGV調(diào)度智能優(yōu)化算法

AGV調(diào)度的優(yōu)化方法主要有：傳統(tǒng)分析方法、建模與軟件仿真法、智能優(yōu)化算法、混合優(yōu)化方法等[2]。近三年，主要的研究方法是基于智能優(yōu)化方法中的遺傳算法為基本算法框架，并在其框架之上與其他智能優(yōu)化方法的部分算子或者其他優(yōu)化技術(shù)相結(jié)合的方法。

2.1 基于遺傳算法框架的算法

遺傳算法是模擬生物進(jìn)化的一種智能優(yōu)化方法，通過迭代進(jìn)化找出可行域中的最優(yōu)解或近優(yōu)解。遺傳算法相比于其他智能優(yōu)化方法最大的優(yōu)勢(shì)在于能夠跳出局部最優(yōu)，實(shí)現(xiàn)廣域搜索。為了實(shí)現(xiàn)更快的搜索速度，通常將其他智能優(yōu)化方法的部分算子與遺傳算法相結(jié)合，如文獻(xiàn)中有：灰狼優(yōu)化算法（Grey Wolf Optimization，GWO）、鯨魚優(yōu)化算法（Whale Optimization Algorithm，WOA）、差分進(jìn)化算法（Differential algorithm，DE）、粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）、蟻群算法（Ant Colony Optimization，ACO）、迭代貪婪算法（Iterated Greedy Algorithm，IGA）；此外，也將其他優(yōu)化技術(shù)與遺傳算法相結(jié)合，如：局部搜索、精英保留策略、排隊(duì)論、模糊、自適應(yīng)交叉率和變異率、拍賣（Auction）等。相應(yīng)的關(guān)鍵字索引見表1。

表1 基于遺傳算法的方法中關(guān)鍵字索引Table 1 Keywords index in methods based on genetic algorithm

遺傳算法在初始化階段通過整數(shù)編碼將待優(yōu)化工序編碼成為遺傳算法中所使用的染色體。染色體在遺傳算法迭代優(yōu)化過程中可能出現(xiàn)不合理的情況，在每一次遺傳操作后設(shè)置染色體合理性檢查機(jī)制，對(duì)不合理的染色體進(jìn)行重新生成或者進(jìn)行修補(bǔ)。另外，在算法剛開始迭代的階段，必須保證種群中染色體的多樣性[7]，或者采用足夠大的種群進(jìn)行實(shí)驗(yàn)，以使算法能夠盡可能大地搜索整個(gè)解空間，提高優(yōu)化質(zhì)量。

Wang等[13]根據(jù)AGV的電能消耗和完工時(shí)間建立調(diào)度模型，提出的改進(jìn)遺傳算法中增加了任務(wù)序列與AGV電池電量匹配，還增加了AGV充電判斷。Chen等[14]研究空間受限場(chǎng)景下的AGV調(diào)度問題，采用遺傳算法進(jìn)行求解，算法中使用漢明距離評(píng)價(jià)種群多樣性、使用災(zāi)難算子增加種群多樣性，并且通過靈敏度分析，篩選出遺傳算法的最佳參數(shù)值。Zhang等[15]提出了一種混合負(fù)荷AGV調(diào)度模型，分析了混合負(fù)荷AGV的優(yōu)缺點(diǎn)，該模型根據(jù)不同物料的規(guī)格配置不同類型的AGV，采用遺傳算法求解汽車裝配站的最小總物流成本。Rahman等[16]建立物料運(yùn)輸?shù)幕旌险麛?shù)線性規(guī)劃（Mixed integer Linear Programming，MILP）模型，提出遺傳算法和迭代貪婪算法進(jìn)行求解，以保證物料的順暢流通。Lu等[17]采用遺傳算法和基于時(shí)空?qǐng)D的蟻群算法相結(jié)合來(lái)優(yōu)化混合模型裝配線的效率。李崢峰等[18]用改進(jìn)的遺傳算法求解多AGV作業(yè)車間調(diào)度問題，并分析了運(yùn)輸時(shí)間、AGV數(shù)量和電量之間的相互影響關(guān)系。

為改善初始種群的質(zhì)量的影響，李廣博等[19]針對(duì)柔性制造車間的AGV調(diào)度，在遺傳算法中設(shè)計(jì)了一種包含啟發(fā)式與隨機(jī)結(jié)合的初始解。Qu等[20]針對(duì)汽車裝配系統(tǒng)中的AGV調(diào)度問題，提出了一種改進(jìn)的遺傳算法，根據(jù)物資需求點(diǎn)的時(shí)空距離對(duì)物資需求點(diǎn)進(jìn)行聚類，生成初始種群。Rahman等[16]提出兩種啟發(fā)式算法來(lái)生產(chǎn)元啟發(fā)式算法的初始解。

遺傳算法中固定的變異率和交叉率致使算法求解時(shí)間長(zhǎng)，學(xué)者們通過引入自適應(yīng)交叉率和變異率來(lái)動(dòng)態(tài)調(diào)整整個(gè)求解過程中的交叉率和變異率，以縮短求解時(shí)間，并提高解的質(zhì)量。Mousavi等[3]和岳笑含等[4]討論了柔性制造系統(tǒng)中的多目標(biāo)AGV調(diào)度，分別提出一種模糊混合遺傳算法粒子群優(yōu)化（GA-PSO）算法，在考慮AGV電池充電的情況下，求解最小完工時(shí)間和最少AGV數(shù)量。其中遺傳算法部分采用模糊邏輯調(diào)節(jié)交叉率和變異率。Umar等[8]提出了一種基于混合遺傳算法的FMS環(huán)境下作業(yè)與AGV集成調(diào)度、分配與無(wú)沖突路徑規(guī)劃算法，算法中采用模糊邏輯控制技術(shù)自適應(yīng)地控制交叉率和變異率。李廣博等在文獻(xiàn)[19]中采用線性調(diào)節(jié)的方法動(dòng)態(tài)調(diào)整變異率。Liu等[21]建立倉(cāng)庫(kù)自動(dòng)分揀系統(tǒng)AGV多目標(biāo)調(diào)度模型，將兩種自適應(yīng)遺傳算法和一種多自適應(yīng)遺傳算法相結(jié)合進(jìn)行求解。

在AGV調(diào)度優(yōu)化模型中單目標(biāo)函數(shù)往往可以用一條染色體編碼鏈進(jìn)行表示，但是針對(duì)多目標(biāo)函數(shù)的組合優(yōu)化模型，使用單條染色體表示將增加交叉和變異算子設(shè)計(jì)的復(fù)雜性。因此，賀長(zhǎng)征等[5]使用遺傳算法求解柔性作業(yè)車間的AGV調(diào)度問題時(shí)，在算法中設(shè)計(jì)了三鏈?zhǔn)骄幋a結(jié)構(gòu)及AGV編碼鏈的交叉、變異算子，同時(shí)在遺傳算法的解碼操作中將Dijkstra算法與時(shí)間窗原理相結(jié)合，規(guī)劃出一條無(wú)碰撞無(wú)沖突的最短路徑。Xiao等[6]建立了柔性作業(yè)車間中的單向路徑網(wǎng)絡(luò)AGV調(diào)度模型，分別用二進(jìn)制染色體和整數(shù)編碼染色體表示單向路徑網(wǎng)絡(luò)和任務(wù)序列。

遺傳操作中突變算子使算法能夠跳出局部最優(yōu)，實(shí)現(xiàn)廣度搜索。其局部搜索能力的提升除調(diào)節(jié)交叉率，還可以引入其他優(yōu)化技術(shù)。正如遺傳算法中的隨機(jī)選擇操作會(huì)破壞種群中的優(yōu)良個(gè)體，為了避免這種逆優(yōu)化現(xiàn)象，往往將精英保留策略加入到遺傳算法中。王體春等[22]針對(duì)倉(cāng)儲(chǔ)生產(chǎn)環(huán)境中多AGV調(diào)度問題，建立了倉(cāng)儲(chǔ)多AGV調(diào)度的M/M/s/Ps排隊(duì)模型，用排隊(duì)論分析目標(biāo)函數(shù)，采用融合精英保留策略的遺傳算法進(jìn)行求解。Xiao等[6]將小生境技術(shù)、領(lǐng)域搜索、精英保留策略等融入雙種群協(xié)同進(jìn)化遺傳算法對(duì)單向路徑網(wǎng)絡(luò)AGV調(diào)度模型進(jìn)行求解。Lee等[23]建立了基于組合拍賣（Combinatorial Auction，CA）的多AGV競(jìng)勝標(biāo)確定問題（Winner Determination Problem，WDP）模型，提出了一種基于知識(shí)算子的遺傳算法，來(lái)解決多AGV系統(tǒng)中的調(diào)度與路徑規(guī)劃整合的難題。Rahman等[16]提出一種兩步局部搜索方法。詹逸鵬[24]采用基于文化算法框架的改進(jìn)NSGA-III（Non-dominated Sorting Genetic Algorithm）算法，對(duì)多AGV調(diào)度的多目標(biāo)優(yōu)化模型進(jìn)行求解。

遺傳算法和其他智能優(yōu)化方法組合的混合優(yōu)化方法將各算法的優(yōu)點(diǎn)組合在一起，可以獲得優(yōu)于其中任意一種優(yōu)化算法的優(yōu)化效果。熊曄等[9]建立了緩沖區(qū)有限的AGV調(diào)度模型，并提出一種混合灰狼遺傳算法（HGWOGA）進(jìn)行求解。該算法在遺傳算法的選擇操作步驟加入了灰狼社會(huì)等級(jí)制度和狼群狩獵機(jī)制，相比精英保留策略，提升了全局搜索能力。差分進(jìn)化算法有較快的收斂速度，楊智飛等[25]提出一種引入差分進(jìn)化的自適應(yīng)多目標(biāo)遺傳差分進(jìn)化算法（Adaptive Multi-Objective Genetic Algorithm with Differential Evolution，AMOGA-DE）求解制造車間多AGV調(diào)度問題。李西興等[11]在鯨魚優(yōu)化算法中引入遺傳算法的交叉、變異操作來(lái)提升全局搜索能力，并使用鄰域結(jié)構(gòu)和精英保留策略來(lái)提升局部搜索能力，提出了一種混合遺傳鯨魚算法來(lái)求解AGV和作業(yè)車間集成調(diào)度模型。Goli等[26]將AGV考慮進(jìn)單元制造系統(tǒng)（Cellular Manufacturing System，CMS）模型中，建立了一個(gè)模糊MILP模型，并提出混合遺傳算法和鯨魚優(yōu)化算法進(jìn)行求解。在調(diào)度優(yōu)化階段引入路徑規(guī)劃算法，得到的優(yōu)化結(jié)果可以保證路徑可行性，有較高的工程實(shí)際價(jià)值。Lyu等[7]將基于時(shí)間窗的Dijkstra算法嵌入到遺傳算法中，同時(shí)解決AGV的調(diào)度和路徑規(guī)劃問題。但是文中每一次算法迭代都需要進(jìn)行路徑規(guī)劃，無(wú)疑大大增加了時(shí)間復(fù)雜度。Xu等[27]針對(duì)柔性制造系統(tǒng)（Flexible Manufacturing Systems，F(xiàn)MS）中AGV的多目標(biāo)多維優(yōu)化調(diào)度問題，提出了分段編碼遺傳算法（SE-GA）、分段編碼離散粒子群優(yōu)化算法（SEDPSO）和分段編碼遺傳算法與離散粒子群混合優(yōu)化算法（H-SE-GA-DPSO），實(shí)驗(yàn)結(jié)果表明H-SE-GA-DPSO算法優(yōu)于其他算法。利用物聯(lián)網(wǎng)技術(shù)實(shí)時(shí)獲得的請(qǐng)求信息，Xu等[28]提出了一種動(dòng)態(tài)調(diào)度方法，從分配給AGV的任務(wù)序列和AGV分配兩個(gè)維度對(duì)智能制造車間的物流調(diào)度過程進(jìn)行考慮，結(jié)合雙層混合遺傳算法和蟻群優(yōu)化算法（DLH-GA-ACO）進(jìn)行求解。采用遺傳算法求解AGV調(diào)度的還有Yao等[29]。

許多學(xué)者已經(jīng)研究了AGV數(shù)量對(duì)優(yōu)化目標(biāo)的影響，通過減少AGV的數(shù)量可以節(jié)約很多建設(shè)成本，并且可以降低AGV路徑?jīng)_突概率。不過，在建立AGV調(diào)度模型時(shí)，常常忽略了眾多因素，如裝卸時(shí)間、生產(chǎn)環(huán)境中的緩沖區(qū)容量、AGV突發(fā)故障以及AGV差異性等。在實(shí)際生產(chǎn)環(huán)境中存在AGV運(yùn)行速度變化，發(fā)生突發(fā)故障，生產(chǎn)計(jì)劃變更，AGV的充電時(shí)間和續(xù)航時(shí)間各不相同等因素需在建模時(shí)予以考慮。其次，絕大多數(shù)調(diào)度優(yōu)化均是靜態(tài)調(diào)度。另外，相比單載量AGV已經(jīng)開展的工作，多載量AGV調(diào)度的研究還有許多方面未考慮到，比如電能消耗、提前到達(dá)和延遲到達(dá)代價(jià)、物料分配平滑性等。

2.2 其他智能優(yōu)化方法

最近三年除了占主導(dǎo)地位的遺傳算法，AGV調(diào)度中使用的其他智能優(yōu)化方法還包括：鯨魚算法、花授粉算法（Flower Pollinaton Algorithm，F(xiàn)PA）、蝙蝠算法（Bat Algorithm，BA）、差分進(jìn)化算法、模擬退火算法（Simulated Annealing Algorithm，SAA）、入侵雜草優(yōu)化算法（Invasive Weed Algorithm，IWA）、布谷鳥搜索算法（Cuckoo Search Algorithm，CSA）、和聲搜索算法（Harmony Search Algorithm，HSA）、人工蜂群算法（Artificial Bee Colony Algorithm，ABC）、蟻群算法、禁忌搜索算法（Tabu Search，TS）等，相應(yīng)的關(guān)鍵字索引見表2。

表2 其他智能優(yōu)化方法中關(guān)鍵字索引Table 2 Keywords index in other intelligent optimization methods

AGV調(diào)度是整數(shù)規(guī)劃問題，需要對(duì)智能優(yōu)化算法進(jìn)行改進(jìn)來(lái)適應(yīng)待求解的模型。Barak等[30]將柔性制造系統(tǒng)中的AGV和機(jī)器都視為資源，建立了考慮AGV燃料消耗的多目標(biāo)生產(chǎn)調(diào)度模型，提出了一種改進(jìn)多目標(biāo)粒子群優(yōu)化算法（MMOPSO）來(lái)求解。Zou等[31]提出了一種新的迭代貪婪算法。

模擬座頭鯨捕食獵物的方式，2016年提出了鯨魚優(yōu)化算法，該算法提高了優(yōu)化求解速度，但是其易陷入局部最優(yōu)值。徐云琴等[32]針對(duì)FMS中的AGV調(diào)度問題，建立了考慮學(xué)習(xí)效應(yīng)和惡化效應(yīng)的最短完工時(shí)間的調(diào)度模型，并提出一種具有混沌搜索策略的鯨魚算法來(lái)防止陷入局部最優(yōu)解。鄒裕吉等[33]提出一種離散鯨魚優(yōu)化算法，采用三段式編碼，設(shè)計(jì)一種結(jié)合混沌映射和對(duì)立學(xué)習(xí)的擴(kuò)展GLR種群初始化方法和三種鄰域結(jié)構(gòu)，同時(shí)采用基于時(shí)間窗的Dijkstra算法進(jìn)行無(wú)沖突路徑規(guī)劃。同樣，為了避免蝙蝠算法早熟和陷入局部最優(yōu)，魏永來(lái)等[34]建立了包含物料配送AGV的路徑、時(shí)間和成本的多目標(biāo)優(yōu)化模型，提出一種混合禁忌蝙蝠算法來(lái)求解模型。該算法中采用ROV規(guī)則的編碼，并且融合了禁忌表、藐視準(zhǔn)則和幾種局部搜索策略。伍樂等[35]建立一種機(jī)器和AGV雙資源約束調(diào)度模型，提出一種改進(jìn)離散差分進(jìn)化算法進(jìn)行求解，在算法中引入了模擬退火算法和變鄰域結(jié)構(gòu)來(lái)提升解的質(zhì)量。劉二輝等[36]對(duì)機(jī)器和AGV集成調(diào)度問題，提出一種基于改進(jìn)花授粉算法進(jìn)行求解。為保證算法跳出局部最優(yōu)和種群多樣性，該算法中包含了基于染色體相似度矩陣的初始解、交叉算子和基于主成分分析法的變異算子。

入侵雜草優(yōu)化算法模擬自然界中雜草的擴(kuò)散、繁殖和競(jìng)爭(zhēng)性生存的過程，迭代過程中根據(jù)個(gè)體適應(yīng)度值確定產(chǎn)生種子數(shù)量，并且使用正態(tài)隨機(jī)數(shù)和非線性調(diào)節(jié)因子進(jìn)行局部搜索。同樣，布谷鳥搜索算法模擬自然界中布谷鳥將鳥蛋下在寄生鳥巢中，由寄生鳥進(jìn)行孵化并撫養(yǎng)，只有優(yōu)質(zhì)的鳥巢才能進(jìn)入下一次迭代。Nabovati等[12，37]建立了機(jī)器和AGV的同時(shí)調(diào)度問題的雙目標(biāo)MILP模型，在模型中考慮了機(jī)器的故障時(shí)間和修復(fù)時(shí)間，提出了一種新的約束條件的染色體結(jié)構(gòu)，并先后提出模糊多目標(biāo)入侵雜草優(yōu)化（Fuzzy Multi-objective Invasive Weeds Optimization，F(xiàn)MOIWO）算法和模糊多目標(biāo)布谷鳥搜索（Fuzzy Multi-Objective Cuckoo Search，F(xiàn)MOCS）算法兩種元啟發(fā)式算法來(lái)求解該模型。其實(shí)驗(yàn)結(jié)果表明，改進(jìn)的FMOIWO搜索算法在求解大、中、小規(guī)模問題時(shí)具有較好的性能。

和聲搜索算法的迭代過程中，和聲總是朝著越來(lái)越好的方向發(fā)展，為提升其全局搜索能力，需加入保持多樣性的結(jié)構(gòu)。Li等[38-39]建立了制造系統(tǒng)中AGV調(diào)度的雙目標(biāo)函數(shù)數(shù)學(xué)模型，提出了一種改進(jìn)和聲搜索算法進(jìn)行求解，算法包括有效的和聲離散編碼方案、基于對(duì)立面學(xué)習(xí)策略的和聲庫(kù)初始化方法、動(dòng)態(tài)記憶庫(kù)取值概率以及局部搜索策略。

人工蜂群算法模擬自然界中蜜蜂尋找最佳蜜源，通過生成良好的初始解，并融入適當(dāng)?shù)木植克阉鞣椒ǎ梢蕴岣咚惴ǖ娜趾途植克阉髂芰?。Zou等[40-41]針對(duì)制造車間中AGV調(diào)度問題，提出了一種包括基于啟發(fā)式的初始化方法、幾個(gè)鄰域操作算子和一種新的跟隨蜂進(jìn)化策略的離散人工蜂群算法，用于求解物料搬運(yùn)過程中的AGV運(yùn)行序列。

為滿足特定的模型求解，也將智能優(yōu)化算法和其他優(yōu)化方法結(jié)合起來(lái)。Rahman等[10]研究以作業(yè)周期時(shí)間和總延誤最小為目標(biāo)的機(jī)器人裝配線平衡和AGV調(diào)度問題，提出一種基于啟發(fā)式和粒子群優(yōu)化算法的分步優(yōu)化算法。Zou等[42]建立了帶提貨和交貨的AGV調(diào)度的多目標(biāo)優(yōu)化模型，并設(shè)計(jì)了一種引入了重啟策略和雙點(diǎn)交叉的高效多目標(biāo)進(jìn)化算法。

智能優(yōu)化算法被用在AGV調(diào)度模型的求解中，但算法大多處于理論研究階段，并未在生產(chǎn)環(huán)境中得到應(yīng)用。與實(shí)際生產(chǎn)環(huán)境相比，調(diào)度模型還有許多影響因素需要考慮，如AGV沖突問題。多目標(biāo)優(yōu)化的研究要比單目標(biāo)復(fù)雜得多，但是現(xiàn)階段往往需要考慮多個(gè)優(yōu)化目標(biāo)。另外，智能優(yōu)化算法都是單向迭代求解，沒有信息反饋機(jī)制，在迭代過程中可能破壞最優(yōu)解結(jié)構(gòu)。

3 其他AGV調(diào)度優(yōu)化方法

相比智能優(yōu)化方法，采用其他的優(yōu)化方法的文獻(xiàn)數(shù)量要少得多，使用的方法有基于規(guī)則的調(diào)度優(yōu)化方法和建模與軟件仿真方法，較老的方法有拉格朗日松弛法（Lagrangian Relaxation，LR）和蒙特卡羅樹搜索法（Monte Carlo Tree Search，MCTS）。另外，人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network，ANN）、暴力枚舉算法（Brute Force Enumeration Algorithm）、分布估計(jì)算法（Estimation of Distribution Algorithm，EDA）和基于網(wǎng)絡(luò)概念的算法則很少被應(yīng)用于AGV調(diào)度優(yōu)化上。相應(yīng)的關(guān)鍵字索引見表3。

表3 其他優(yōu)化方法中關(guān)鍵字索引Table 3 Keywords index in other optimization methods

基于規(guī)則的方法能夠保證實(shí)際生產(chǎn)環(huán)境中的AGV正常運(yùn)行，但是其結(jié)果幾乎不能達(dá)到最優(yōu)調(diào)度要求。同時(shí)輔以軟件仿真，能夠直觀看到AGV運(yùn)行動(dòng)態(tài)情況，有利于調(diào)整規(guī)則和規(guī)則中的參數(shù)。陳敏等[43]提出了7種多AGV調(diào)度規(guī)則，分別是FCFS規(guī)則、Random規(guī)則、SPT規(guī)則、ESD規(guī)則、Nearest規(guī)則、Farther規(guī)則和基于軟時(shí)間窗的Window規(guī)則，采用Plant Simulation仿真軟件對(duì)以上規(guī)則進(jìn)行實(shí)驗(yàn)比較，結(jié)果表明基于軟時(shí)間窗的AGV調(diào)度規(guī)則表現(xiàn)較好。Zhao等[44]針對(duì)車間多AGV調(diào)度問題，應(yīng)用優(yōu)先級(jí)規(guī)則進(jìn)行調(diào)度，同時(shí)還使用A*算法進(jìn)行路徑規(guī)劃。Fontes等[45]建立機(jī)器調(diào)度和AGV調(diào)度的新MILP模型，并用商業(yè)軟件Gurobi進(jìn)行求解。

有新的網(wǎng)絡(luò)理論被用來(lái)優(yōu)化AGV調(diào)度問題。Gyulai等[46]從物流網(wǎng)絡(luò)模型出發(fā)，利用網(wǎng)絡(luò)科學(xué)的概念和方法來(lái)發(fā)現(xiàn)AGV車隊(duì)管理問題中的隱藏結(jié)構(gòu)，將這種基于模塊化的結(jié)構(gòu)用于平衡車輛的預(yù)期負(fù)載和動(dòng)態(tài)調(diào)度。

人工神經(jīng)網(wǎng)絡(luò)、蒙特卡羅樹搜索、分布估計(jì)算法等算法被少數(shù)學(xué)者改進(jìn)和適配后用來(lái)求解AGV調(diào)度問題，在一些模型上也取得了與智能優(yōu)化方法相近的優(yōu)化效果。Fazlollahtabar等[47]建立了一種能滿足AGV無(wú)沖突路徑的調(diào)度模型，并提出了一種面向路徑網(wǎng)絡(luò)的啟發(fā)式搜索算法和求解方法。李紅[48]采用動(dòng)態(tài)蒙特卡羅樹搜索和變鄰域局部搜索對(duì)AGV運(yùn)輸任務(wù)順序進(jìn)行優(yōu)化。戴敏等[49]建立了機(jī)器和AGV集成調(diào)度下的多目標(biāo)能耗模型，并提出了一種改進(jìn)分布估計(jì)算法進(jìn)行求解，在算法中設(shè)計(jì)了良好的初始化、局部搜索機(jī)制和模擬退火擇優(yōu)。Fazlollahtabar[50]對(duì)AGV加工和等待時(shí)間與制造車間的路徑進(jìn)行了建模，提出了一種拉格朗日松弛法，并用次梯度法對(duì)搜索過程中的迭代次數(shù)進(jìn)行更新，實(shí)驗(yàn)結(jié)果表明針對(duì)大規(guī)模問題該方法的求解速度較快。采用改進(jìn)的A*算法進(jìn)行路徑規(guī)劃，并采用博弈論的方法消除行駛過程中產(chǎn)生的沖突。Zeng等[51]提出了一種基于拍賣的啟發(fā)式方法來(lái)解決機(jī)器和AGV的分配問題，并設(shè)計(jì)了一種改進(jìn)的析取圖模型，以優(yōu)化基于拍賣的方法得到的可行解。Heger等[52]基于隨機(jī)到達(dá)時(shí)間的離散事件仿真研究，訓(xùn)練人工神經(jīng)網(wǎng)絡(luò)，學(xué)習(xí)排序、調(diào)度、路徑規(guī)劃等不同規(guī)則組合之間的交互效應(yīng)?；谟?xùn)練好的網(wǎng)絡(luò)，對(duì)物料搬運(yùn)的AGV作業(yè)時(shí)間進(jìn)行優(yōu)化。Gutjahr等[53]優(yōu)化FMS中AGV數(shù)量和完工時(shí)間，利用暴力枚舉算法求解。Gao等[54]研究共軌雙AGV的協(xié)同調(diào)度問題，建立雙AGV調(diào)度模型，提出一種基于時(shí)間窗的訂單動(dòng)態(tài)調(diào)度方法。Chawla等[55]將自然啟發(fā)算法和優(yōu)先級(jí)混合調(diào)度規(guī)則應(yīng)用于自動(dòng)導(dǎo)引車輛（AGV）的同時(shí)調(diào)度和分配上。孫陽(yáng)君等[56]提出了一種基于數(shù)字孿生的多AGV系統(tǒng)集中式調(diào)度方法，保證虛擬系統(tǒng)與物理系統(tǒng)一致性，并對(duì)物理系統(tǒng)中的變化及時(shí)響應(yīng)調(diào)整。還有其他AGV調(diào)度的組合優(yōu)化問題的求解方法，見文獻(xiàn)[57]。

大規(guī)模調(diào)度問題和動(dòng)態(tài)調(diào)度問題研究的不足，與智能優(yōu)化算法相同。其中商業(yè)軟件仿真法的求解速度受到軟件自身的求解器極強(qiáng)的約束；人工神經(jīng)網(wǎng)絡(luò)的模型搭建、模型的超參數(shù)調(diào)整、現(xiàn)實(shí)生產(chǎn)現(xiàn)場(chǎng)數(shù)據(jù)集等都需要進(jìn)一步完善。

4 總結(jié)及未來(lái)工作

制造車間AGV調(diào)度問題的研究，幫助指導(dǎo)制造車間完成生產(chǎn)任務(wù)的同時(shí)也為企業(yè)節(jié)約了不少成本和時(shí)間。另外，AGV調(diào)度問題的研究也為搬運(yùn)系統(tǒng)的建設(shè)提供了參考建議?，F(xiàn)階段AGV調(diào)度仍然存在一些問題和不足：

（1）建模方面的不足。建立的數(shù)學(xué)模型作為一種對(duì)現(xiàn)實(shí)情況的抽象，并不能完全反應(yīng)真實(shí)情況，并且需要在經(jīng)濟(jì)適用性和模型準(zhǔn)確性之間做一個(gè)平衡。

（2）大規(guī)模場(chǎng)景的優(yōu)化研究較少。絕大多是已有的研究均是基于靜態(tài)調(diào)度和小規(guī)模場(chǎng)景開展的，而隨著AGV的規(guī)模增大，求解時(shí)的計(jì)算量將呈激增態(tài)勢(shì)，不能滿足實(shí)際生產(chǎn)的要求。

在大數(shù)據(jù)，人工智能的盛行的當(dāng)下，制造車間的AGV調(diào)度問題可以有以下幾個(gè)值得開展的研究方向：

（1）多載量AGV調(diào)度。對(duì)于多種類小數(shù)量的物品輸送搬運(yùn)任務(wù)，若采用小型AGV運(yùn)輸，則場(chǎng)景中AGV數(shù)量巨大，導(dǎo)致調(diào)度困難且故障率增加；若采用大型AGV運(yùn)輸，還存在資源浪費(fèi)的問題。因此采用一臺(tái)AGV運(yùn)輸多種物品是一個(gè)值得研究的方向。與單載量AGV相比，多載量AGV[15]能夠以較少數(shù)量的AGV完成相同的任務(wù)量，并且較大程度利用了AGV的運(yùn)載能力，減少能源消耗。

（2）基于人工智能的突發(fā)狀況識(shí)別和AGV作業(yè)預(yù)測(cè)。對(duì)于大規(guī)模的AGV場(chǎng)景中，AGV擁擠的運(yùn)行區(qū)域更容易發(fā)生運(yùn)行故障和降低AGV系統(tǒng)搬運(yùn)效率，可以采用人工智能的方法對(duì)有礙于AGV運(yùn)行的突發(fā)情況進(jìn)行預(yù)測(cè)，并做出相應(yīng)的決策以保障系統(tǒng)高效運(yùn)作。尤其是針對(duì)大規(guī)模AGV場(chǎng)景，能夠避免因少數(shù)AGV發(fā)生沖突和故障進(jìn)而導(dǎo)致大量AGV發(fā)生沖突或故障損壞，造成的延誤和損失。同時(shí)，利用人工智能的方法對(duì)生產(chǎn)制造環(huán)境下的不確定時(shí)間物料運(yùn)輸進(jìn)行預(yù)測(cè)也可以起到提升企業(yè)生產(chǎn)效率的作用。

（3）動(dòng)態(tài)調(diào)度?，F(xiàn)階段的AGV調(diào)度研究是以靜態(tài)調(diào)度為主，對(duì)于動(dòng)態(tài)情況下可能出現(xiàn)的差異性未做考慮，比如出現(xiàn)突發(fā)AGV故障或環(huán)境故障、生產(chǎn)計(jì)劃變更[25]、AGV由于充電完成或故障恢復(fù)時(shí)進(jìn)入、充電或故障發(fā)生時(shí)退出等，因此動(dòng)態(tài)調(diào)度[28]可以作為一個(gè)研究方向。

（4）基于大數(shù)據(jù)的實(shí)時(shí)AGV調(diào)度與路徑規(guī)劃算法。隨著傳感器、物聯(lián)網(wǎng)等技術(shù)的發(fā)展，工業(yè)大數(shù)據(jù)已經(jīng)成為當(dāng)今的熱點(diǎn)。利用工業(yè)大數(shù)據(jù)來(lái)搭建AGV調(diào)度和路徑規(guī)劃的模型，巨大的數(shù)據(jù)量可以保證更多的實(shí)際運(yùn)行情況被考慮進(jìn)來(lái)，保障AGV的實(shí)時(shí)運(yùn)行性能，提高搬運(yùn)系統(tǒng)穩(wěn)定性。尤其是針對(duì)大規(guī)模AGV場(chǎng)景，能夠避免因建模困難、分布式計(jì)算造價(jià)高且系統(tǒng)復(fù)雜等困難。