基于智能計算方法的AGV制造車間調度問題研究現狀*

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

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

0 引言

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

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

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

1 群智能計算

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

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

1.1 粒子群優化

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

圖1 粒子迭代框架

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

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

1.2 蟻群算法

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

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

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

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

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

1.3 人工蜂群算法

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

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

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

1.4 其他群智能算法

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

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

2 遺傳算法

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

圖3 遺傳算法模型

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

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

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

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

3 人工神經網絡

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

圖4 單層神經網絡

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

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

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

4 結束語

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

（1）群智能計算作為新興的計算方法，已經越來越受到關注，并且與其他算法如遺傳算法等聯系緊密，未來利用該方法與進化方法結合將會是研究AGV調度問題的重要方向。

（2）遺傳算法在智能優化計算領域仍然占據重要位置，在AGV調度領域以及其他眾多領域仍然具有重要研究與應用價值。

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