基于智能計算方法的AGV制造車間調(diào)度問題研究現(xiàn)狀*

馬 駿，王亞東，蔡國旗，夏琴香，程秀全

（1. 珠海格力精密模具有限公司， 廣東珠海 519070； 2. 華南理工大學機械與汽車工程學院， 廣州 510641；3. 廣州民航職業(yè)技術(shù)學院， 廣州 510403）

0 引言

AGV 是由計算機控制并配備不同導航系統(tǒng)以實現(xiàn)物料水平移動的無人駕駛的車輛[1]。AGV 非常適合物料從/到多個目的地的長距離水平移動。它們也適用于重復/可預測的材料運輸和/或危險任務[2]。AGV 的運行控制可以集成到計算機控制系統(tǒng)中，也可以自身集成導航與控制為一體來進行工作，多AGV組成的系統(tǒng)一般都由遠端計算機進行中央控制。AGV到目前為止已經(jīng)廣泛應用于制造、物流等領(lǐng)域。在柔性制造系統(tǒng)（Flexible Manufacturing System，F(xiàn)MS）中，AGV 能同機床共同協(xié)作，在不同機床間傳遞物料，一般運輸盛放物料/貨物的托盤；自升式AGV可以應用在自動化集裝箱碼頭等轉(zhuǎn)運系統(tǒng)上，而無需其他設(shè)備將負載轉(zhuǎn)移到車輛上[3]。在倉儲中，AGV 不僅能夠?qū)⑽锪蠌膫}儲位置運送到所有工作中心，也能夠在各工作站點間來回傳送。

高效的調(diào)度對于AGV應用至關(guān)重要，不僅僅能夠減少能耗，而且能夠減少系統(tǒng)中機器的待機時間，提高整個系統(tǒng)的工作效率。術(shù)語 “調(diào)度” 是指將AGV分配給任務的過程，考慮到完成操作成本和所需時間[4]?？紤]到調(diào)度問題的目標、局限性和考慮因素的多樣性，不斷改進的AGV調(diào)度以獲得在真實環(huán)境的效果仍然是當前研究熱點。大型AGV系統(tǒng)需要建立新的分析和仿真模型，以克服計算量大、NP 完全性、擁塞、系統(tǒng)死鎖和延遲以及有限的規(guī)劃時間[5]，AGV調(diào)度準則大概有6 個：（1）完工時間；（2）總完工時間；（3）平均流動時間；（4）平均等待時間；（5）延遲時間；（6）拖期。到目前為止，大多數(shù)AGV調(diào)度的文獻很少考慮特別的約束場景，如運輸作業(yè)過程中單個AGV負載大小約束、制造車間與其他設(shè)備相配合調(diào)度形式以及待機過程時?？康淖顑?yōu)位置，這些約束在大型AGV系統(tǒng)的實際應用中變得越來越重要。

智能計算（Intellectual Computing，IC）是人們面對生物進化后逐步適應現(xiàn)實世界的規(guī)律進行模仿設(shè)計的算法。解決AGV 調(diào)度問題需要合適的數(shù)學優(yōu)化算法，智能計算方法為解決AGV 調(diào)度問題提供了眾多優(yōu)秀的算法，主要包含遺傳算法、粒子群算法、蟻群算法、人工神經(jīng)網(wǎng)絡等。本文主要通過群智能計算、遺傳算法、人工神經(jīng)網(wǎng)絡等主流算法開展對AGV 調(diào)度研究，主要涉及車間柔性制造系統(tǒng)研究進展及前景的探討。

1 群智能計算

群 智 能（Swarm Intelligence， SI）， 也 稱 仿 生 網(wǎng) 絡（Bio-inspired networking，BIN），是由一組自由個體（individ?ual/agent）遵循簡單行為規(guī)則、通過個體間的局部通信以及個體與環(huán)境間的交互作用而涌現(xiàn)出來的集體智能行為的自組織特性，是對現(xiàn)實世界中的群居性生物或人工群體所呈現(xiàn)出的有序群行為（Swarm behavior）的抽象[6]，群智能計算是指利用群集優(yōu)勢在沒有集中控制、不提供全局模型的前提下，可由大量簡單個體組成的群體分布式協(xié)作尋找復雜問題最優(yōu)解。

群智能計算方法屬于啟發(fā)式計算方法，其涉及模型通常具有生物激勵的特性，主要包括蟻群算法、粒子群優(yōu)化、人工免疫系統(tǒng)、智能水滴算法、分組搜索優(yōu)化、魚群搜索算法、細菌趨藥算法、螢群算法、蜜蜂交配優(yōu)化、跳蛙算法、入侵性雜草優(yōu)化、蝙蝠算法[7-13]等。

1.1 粒子群優(yōu)化

粒子群優(yōu)化（Particle Swarm Optimization，PSO）最初是用來研究模擬鳥群尋找食物的集體行為，其基本原理是種群中每個成員作為獨立粒子在每次迭代中以一定的速度和加速度向更好的位置移動，圖1 所示為每代任意粒子迭代過程[17]，最終求得最佳位置得到問題的解。粒子群優(yōu)化算法運算高效、結(jié)構(gòu)簡單，是近些年來研究FMS 調(diào)度問題，特別是具體到車間AGV系統(tǒng)調(diào)度研究熱點。

圖1 粒子迭代框架

FMS 中的調(diào)度問題能很好地用PSO 方法解決，比如在對于車間與AGV 同步調(diào)度研究上，Murata 等[18]采用二元粒子群優(yōu)化算法(Binary Particle Swarm Optimization，BPSO)用最大完工時間最小化的函數(shù)對多臺機床與AGV調(diào)度進行了優(yōu)化。通過與時間窗（Time Windows Approach，TWA）方法[19]、遺傳算法（Genetic Algorithm coding by Ulusoy）[20]、遺傳算法（Ge?netic Algorithm coding by Abdelmaguid）[21]進行對比，BPSO 在應對機床與AGV同步調(diào)度中總體性能表現(xiàn)更好。Zhang等[22]針對多品種、小批量生產(chǎn)訂單驅(qū)動的AGV服務制造系統(tǒng)的優(yōu)化問題進行了研究，以機床與AGV 的利用率為綜合評價函數(shù)，建立了一種集成機床與AGV的調(diào)度模型，并提出了一種改進的粒子群算法（Improved Particle Swarm Optimization，IPSO），算法具有主粒子與嵌套粒子的特點。通過實驗與PSO 和遺傳算法（Genetic Algorithm，GA）相比，嵌套粒子群算法收斂和求解效率方面具有更大優(yōu)勢，能夠為AGV服務制造系統(tǒng)的柔性調(diào)整提供有益借鑒。

PSO 與其他算法相結(jié)合較為容易，學界已經(jīng)有基于PSO的混合算法來研究AGV 調(diào)度問題。Mousavi 等[23]將PSO 與GA相結(jié)合研究了在FMS 的多目標AGV 調(diào)度問題，特別考慮了AGV電池損耗的影響，通過最小化AGV的最大完工時間和數(shù)量建立了多目標數(shù)學模型，通過對單一算法（PSO/GA）與所提算法進行試驗，3種算法都具有對問題解決的適用性，混合GA-PSO算法在平均AGVs運算效率具有更高的效率。在考慮FMS的工作中心處理最小行程和等待時間上，Chawla等[24]提出了多負載AGV 和任務的同步調(diào)度思想，將PSO 與因模算法（MA）相結(jié)合，提出了一種改進文化基因粒子群算法（Modi?fied Memetic Particle Swarm Optimization，MMPSO），試驗結(jié)果表明，與PSO算法相比，MMPSO在多負載AGV的實施動態(tài)調(diào)度具有更好的效果，能夠有效生成多負載AGV調(diào)度問題的最優(yōu)初始解。

1.2 蟻群算法

蟻群算法（Ant Colony Optimization，ACO）是Dorigo 于1995年通過模擬自然界中螞蟻覓食行為的集體尋徑行為而提出的一種基于種群的仿生進化算法。與粒子群算法一樣，自20世紀90年代誕生以來，兩者在智能算法領(lǐng)域引起了研究者們巨大興趣。相比較于其他算法，ACO 最顯著的特點是采用了正反饋的機制，單個個體只能夠感知局部信息，不能直接利用全局信息。

ACO 每一次迭代中，都會考慮一些人工螞蟻，其中的單個個體都通過在假定的路徑圖從一個點走到另一個點來構(gòu)建一個解決方案，并且限制不訪問其在行走中已經(jīng)訪問過的任何頂點。在解構(gòu)造的每一步，螞蟻都會根據(jù)信息素偏向的隨機機制選擇要訪問的下一個頂點：在頂點i中，下一個頂點是在先前未訪問的頂點中隨機選擇的，如圖2所示[25]。

圖2 城市中的螞蟻通過一個隨機機制選擇下一個要訪問的城市

在過去10年間，有學者對ACO能否為制造業(yè)中AGV小車提供更多智能理念進行了探索[26]，研究針對ACO在AGV系統(tǒng)設(shè)計與控制中應用是否具有可行性，但研究未見在具體到調(diào)度方面。對于車間AGV調(diào)度問題學界利用該算法也進行了探索。針對AGV的無沖突路由問題（CFRP）和最基本的車間作業(yè)調(diào)度問題（JSSP），Saidi-Mehrabad 等[27]研究了AGV 的車間作業(yè)調(diào)度問題（Job-Shop Scheduling Problem，JSSP）和無沖突路由問題（Conficlt-Free Routing Problem，CFRP）的集成模型，提出了一種混合整數(shù)線性規(guī)劃模型，并采用兩階段蟻群算法進行求解。該項工作意義在于通過建立混合整數(shù)數(shù)學模型來同時考慮JSSP 和CFRP 的問題，最后通過采用ACA 進行求解。結(jié)果表明，與Exact算法相比，在時間上ACA能夠更有效率地得出結(jié)果。

有學者對ACO 結(jié)合其他算法進行對調(diào)度問題進行了研究，Deng 等[28]提出了一種基于多種群策略、協(xié)同進化機制、信息素更新策略和信息素擴散機制的改進蟻群算法（Im?proved Ant Colony Optimization，ICMPACO），平衡了收斂速度和解的多樣性，提高了求解大規(guī)模優(yōu)化問題的優(yōu)化性能，能夠很好解決經(jīng)典的旅行商問題和門分配問題，在未來勢必將會為AGV調(diào)度研究中能夠利用ACO提供理論參考。

1.3 人工蜂群算法

人工蜂群算法（Artificial Bee Colony，ABC）是模仿蜂群提出的一種優(yōu)化方法，其主要特點是不需要了解問題的特殊信息，只需要對問題進行優(yōu)劣的比較，通過各個個體間的協(xié)作來尋找最優(yōu)解的算法。迄今為止，利用ABC 對現(xiàn)實世界的研究最為廣泛[29]。

由承辦部門將合同相關(guān)的簽約依據(jù)、相對人資質(zhì)、合同文本等資料分類上傳至合同管理信息系統(tǒng)并送審。合同承辦部門應對所提交資料的真實性、合同草本中標的金額的準確性、一致性等負責。

雖然ABC 研究領(lǐng)域眾多，但是在調(diào)度問題上目前研究較少，至于車間中AGV調(diào)度問題，近年來才逐漸引起研究者們興趣。Baradaran 等[30]提出了一個二元人工蜂群算法（Binary Artificial Bee Colony，BABC）去研究了伴有多個硬性優(yōu)先時間窗口和一個異構(gòu)車輛的路徑問題。Zou等[31]針對線型制造車間的物料搬運中AGV 調(diào)度問題，以最小化單元等待時間和AGV 總行駛距離兩者的標準差最小化為目標，提出了一個有效的離散人工蜂群算法（Discrete Artificial Bee Colony，DABC），包含了基于啟發(fā)式的初始化、六鄰域結(jié)構(gòu)和新的旁觀者蜂群進化策略。

1.4 其他群智能算法

除了以上較為熱門的群智能算法外，還有一些優(yōu)秀的群智能算法已經(jīng)被用來研究制造系統(tǒng)中AGV 調(diào)度問題，如：Gnanavelbabu 等[32]利用人工免疫算法（Artificial Immune Sys?tem，AIS）研究了FMS 中生產(chǎn)任務、AGV、自動存儲與檢索系統(tǒng)的多目標調(diào)度。隨著群智能算法研究不斷發(fā)展以及計算能力的日益提高，勢必將對車間AGV復雜調(diào)度問題提供更好研究支持。Nabovati等[33]研究一種新的機床與AGV同時調(diào)度模型，提出了兩種元啟發(fā)式算法：模糊多目標入侵雜草優(yōu)化算法（Fuzzy Multi-Objective Invasive Weed Optimization， FMI?WO）、模糊多目標布谷鳥搜索算法（Fuzzy Multi-Objective Cuckoo Search Algorithm）。計算結(jié)果表明，F(xiàn)MIWO 在求解問題方面具有最好的性能。

目前還有一些已發(fā)掘的群智能算法尚未應用研究到AGV調(diào)度問題中，伴隨著智能制造未來實施推進，某些群智能算法適合于解決特定場合的AGV調(diào)度問題將會被研究發(fā)掘。特別當應對AGV群規(guī)模比較大的調(diào)度問題時，群智能算法將會發(fā)揮其獨特地能夠解決大型優(yōu)化問題的特性。

2 遺傳算法

遺傳算法(Genetic Algorithm，GA)是由John H于1975年用來被理解為一個基于基因和自然進化機制的優(yōu)化復雜方程過程，基本算法模型如圖3所示。2001年，Ponnambalam等[34]指出GA 是最流行的進化算法類型。遺傳算法所取得的良好效果，使許多研究者開始將其應用于求解AGV調(diào)度問題，包括FMS 環(huán)境中涉及到有關(guān)AGV 配置[19-20,34-42]，以及倉儲[43]、自動化集裝箱碼頭[44-45]等領(lǐng)域。

圖3 遺傳算法模型

21世紀初，Ulusoy[35]應用遺傳算法研究了在FMS中機床與AGV 同步調(diào)度的問題，分析了算法對應包含有6 個加工中心和2 個AGV 的3 種不同F(xiàn)MS 布局配置下算法的性能，性能研究結(jié)果驗證算法的優(yōu)越性，也驗證了該算法非常適合解決此類問題。Sankar[36]對新到生產(chǎn)任務、機床和AGV 的同步調(diào)度進行了探索，利用1 臺AGV 和4 臺機床組成的FMS 進行了遺傳算法優(yōu)化及計算機仿真的思想，通過與其他算法（Kangaro算法）進行對比驗證了算法的有效性和優(yōu)越性。Taghavifard等[37]利用調(diào)度規(guī)則和遺傳算法以最小化制造周期來研究機床與AGV 的同步調(diào)度問題，將實驗結(jié)果與其他文獻的最優(yōu)值進行比較，并強調(diào)了該方法在效率與求解質(zhì)量方面的有力性能。

近幾年來，遺傳算法應用不斷發(fā)展，大多以改進形式研究應用在眾多行業(yè)，尤其在制造領(lǐng)域[38-41]。Ren 等[39]根據(jù)協(xié)同制造系統(tǒng)特點，提出了一種改進的遺傳算法來求解協(xié)同制造系統(tǒng)的生產(chǎn)效率問題，改進算法不僅優(yōu)化了基因序列，而且優(yōu)化了作業(yè)操作序列和AGV運動序列。仿真結(jié)果表明了該改進算法有效性，與標準遺傳算法相比更加有效率。針對以往研究采用固定數(shù)量AGV或不考慮路由和運輸時間的問題，Lyu等[40]通過考慮AGV 的最優(yōu)數(shù)量、最短運輸時間、路徑規(guī)劃問題、無沖突路由問題，提出了一種結(jié)合基于時間窗和Dijkstra算法的遺傳算法。通過兩組實驗表明，算法在求解調(diào)度問題上與基準方法同樣有效，同時也適用于FMS 中集成調(diào)度問題。Chen 等[41]研究了基于空間約束AGV 的預制浴室單元（PBU）制造系統(tǒng)的調(diào)度問題。為了防止死鎖情況，必須控制PBU 的生產(chǎn)啟動時間，提出的遺傳算法能夠確定每個工作站操作，并為每個PBU 選擇一個啟動時間。通過實際的工業(yè)項目數(shù)據(jù)的實驗驗證了該算法的有效性。Liu等[42]將兩種自適應遺傳算法（Adaptive Genetic Algorithm, AGA）和一種多目標遺傳算法（Multi-adaptive Genetic Algorithm，MAGA）相結(jié)合，建立了AGV的多目標數(shù)學模型，并將其應用于AGV任務調(diào)度中，還考慮了AGV的充電任務和速度變化，最小化了AGV最大完工時間、使用數(shù)量、電量損耗。實驗證明MAGA 在3 種算法表現(xiàn)最好，優(yōu)化前后目標值變化30%，驗證了模型和MAGA算法的有效性。

已有學者基于GA 結(jié)合其他智能算法也開展了FMS 的AGV調(diào)度研究[18,46]。Umar[46]提出一種基于遺傳算法的FMS環(huán)境下作業(yè)和AGV的集成調(diào)度且無沖突路由選擇的算法。該算法在考慮優(yōu)化最大完工時間、AGV 的旅行商問題和由于沖突而導致作業(yè)延誤和延遲的因素的同時，生成一個完整的調(diào)度和詳細的路由路徑。采用模糊專家系統(tǒng)對遺傳算子進行控制，提高了前兩代群體的群體性能。該算法特點是考慮了AGV調(diào)度、作業(yè)調(diào)度、路由選擇各因素，保證了各集成要素可行性和有效性，通過計算實驗驗證了算法的有效性。

遺傳算法目前仍是最重要的優(yōu)化方法之一，在工業(yè)界的建模設(shè)計、優(yōu)化、控制等等方面發(fā)揮著巨大的作用，隨著AGV 智能化程度和車間等應用場景復雜度提高，將來應用遺傳算法進行AGV調(diào)度研究將會繼續(xù)發(fā)展下去。

3 人工神經(jīng)網(wǎng)絡

人工神經(jīng)網(wǎng)絡（Artificial Nueral Network，ANN）又簡稱為神經(jīng)網(wǎng)絡，是一種模仿生物神經(jīng)網(wǎng)絡（動物的中樞神經(jīng)系統(tǒng)，特別是大腦）的結(jié)構(gòu)和功能的數(shù)學模型或計算模型，用于對函數(shù)進行估計或近似，它是一種重要的智能計算方法，也是當今受到火熱研究的機器學習的基礎(chǔ)。從簡單的單層神經(jīng)網(wǎng)絡（圖4）發(fā)展到現(xiàn)在已經(jīng)產(chǎn)生兩層、多層類型網(wǎng)絡，如BP、 Pre-training、 Drop?out 等，并廣泛地延伸到各個學科領(lǐng)域，其中也包含了對于AGV 調(diào)度應用研究[47]。

圖4 單層神經(jīng)網(wǎng)絡

Li等[47]針對AGV系統(tǒng)中死鎖問題提出了一種基于ANN的AGV 調(diào)度算法，該方法充分利用了傳統(tǒng)調(diào)度算法和深度學習（Deep Learning，DL）的優(yōu)點，前者防止了死鎖和沖突，后者提高了效率。Hegera[48]以簡單性和小計算時間用于排序操作、路由作業(yè)和調(diào)度AGV為優(yōu)先規(guī)則，訓練人工神經(jīng)網(wǎng)絡，學習排序、調(diào)度、路由等不同規(guī)則組合對系統(tǒng)性能的影響。在訓練網(wǎng)絡的基礎(chǔ)上，對規(guī)則的組合進行了優(yōu)化，降低了系統(tǒng)性能變化時作業(yè)的平均延誤。

隨著人工智能在近幾年爆發(fā)，以DL為代表的神經(jīng)網(wǎng)絡技術(shù)對智能算法被研究在AGV 中，其中Xue 等[49]采用了強化學習方法研究了多AGV 流水作業(yè)調(diào)度問題，通過定義狀態(tài)特征、行為空間和報酬函數(shù)，將調(diào)度問題歸結(jié)為馬爾科夫問題，提出了一種強化學習的調(diào)度方法。仿真結(jié)果表明，該方法在動態(tài)環(huán)境下學習了以往的最優(yōu)或近似最優(yōu)解，比多智能體調(diào)度方法具有更好的性能。Hu 等[50]針對車間環(huán)境的高動態(tài)性、復雜性和不確定性的問題，以最小化車間的完工時間和延遲率為問題的目標，提出了一種基于混合規(guī)則的自適應深度強化學習AGVs 實施調(diào)度方法。根據(jù)訓練過程和對比實驗，該方法能夠有效地基于柔性車間的場景來選擇合適的調(diào)度規(guī)則和AGV。

隨著大數(shù)據(jù)、5G、云計算技術(shù)興起，基于ANN的智能算法思想正不斷演化到研究于高技術(shù)產(chǎn)業(yè)中，對于AGV調(diào)度問題研究也正在不斷被探索與應用中，本文認為雖然目前人工神經(jīng)網(wǎng)絡在AGV調(diào)度中應用較少，但是隨著人工智能技術(shù)發(fā)展，未來利用人工神經(jīng)網(wǎng)絡為基礎(chǔ)的智能學習算法的AGV調(diào)度研究勢必將會成為新的AGV領(lǐng)域研究熱點。

4 結(jié)束語

本文結(jié)合智能計算方法對AGV調(diào)度問題的研究近況進行了綜述，通過對群智能計算、遺傳算法、人工神經(jīng)網(wǎng)絡等主流智能算法引入介紹，分析了算法間的特性，闡述了在制造車間開展AGV調(diào)度問題的研究主要思路。通過對這些工作回顧與總結(jié)梳理，為相關(guān)學者提供關(guān)于AGV智能調(diào)度研究的參考。

（1）群智能計算作為新興的計算方法，已經(jīng)越來越受到關(guān)注，并且與其他算法如遺傳算法等聯(lián)系緊密，未來利用該方法與進化方法結(jié)合將會是研究AGV調(diào)度問題的重要方向。

（2）遺傳算法在智能優(yōu)化計算領(lǐng)域仍然占據(jù)重要位置，在AGV調(diào)度領(lǐng)域以及其他眾多領(lǐng)域仍然具有重要研究與應用價值。

（3）人工智能研究最近幾年呈爆發(fā)趨勢，人工神經(jīng)網(wǎng)絡是基于學習的方法，對于此類帶有經(jīng)驗的智能方法來研究AGV車間調(diào)度問題，未來將是此類研究的重要趨勢。