制造車間自動導引車調(diào)度新進展

曹立佳，劉 洋

1.四川輕化工大學 計算機科學與工程學院，四川 宜賓644000

2.人工智能四川省重點實驗室，四川 自貢643000

3.四川輕化工大學 自動化與信息工程學院，四川 宜賓644000

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

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

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

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

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

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

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

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

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

AGV調(diào)度優(yōu)化的另一個關鍵問題是優(yōu)化算法的選擇和改進，以適應特定的優(yōu)化需求和優(yōu)化模型。現(xiàn)階段最常用的優(yōu)化算法是智能優(yōu)化算法，尤其是遺傳算法大量被用來求解調(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)化技術相結(jié)合的方法。

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

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

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

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

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

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

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

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

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

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

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

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

最近三年除了占主導地位的遺傳算法，AGV調(diào)度中使用的其他智能優(yōu)化方法還包括：鯨魚算法、花授粉算法（Flower Pollinaton Algorithm，F(xiàn)PA）、蝙蝠算法（Bat Algorithm，BA）、差分進化算法、模擬退火算法（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）等，相應的關鍵字索引見表2。

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

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

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

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

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

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

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

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

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

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

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

基于規(guī)則的方法能夠保證實際生產(chǎn)環(huán)境中的AGV正常運行，但是其結(jié)果幾乎不能達到最優(yōu)調(diào)度要求。同時輔以軟件仿真，能夠直觀看到AGV運行動態(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ī)則和基于軟時間窗的Window規(guī)則，采用Plant Simulation仿真軟件對以上規(guī)則進行實驗比較，結(jié)果表明基于軟時間窗的AGV調(diào)度規(guī)則表現(xiàn)較好。Zhao等[44]針對車間多AGV調(diào)度問題，應用優(yōu)先級規(guī)則進行調(diào)度，同時還使用A*算法進行路徑規(guī)劃。Fontes等[45]建立機器調(diào)度和AGV調(diào)度的新MILP模型，并用商業(yè)軟件Gurobi進行求解。

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

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

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

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

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

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

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

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

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

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

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

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