AGV作業調度模型及改進的DE算法研究

楊鋒英，劉會超

YANG Fengying1,LIU Huichao2

1.黃淮學院 信息工程學院，河南 駐馬店 463000

2.黃淮學院 網絡信息管理中心，河南 駐馬店 463000

1.School of Information Engineering,Huanghuai University,Zhumadian,Henan 463000,China

2.Center of Network Information Management,Huanghuai University,Zhumadian,Henan 463000,China

1 引言

隨著信息化的深入，許多企業建立了自動化立體倉庫系統（Automated Storage and Retrieval System，AS/RS），用于對生產物料和產品進行集中化的管理和配送。和傳統倉庫相比，AS/RS實現了貨物存儲的立體化、自動化和智能化。而自動化搬運系統在其中扮演了重要角色。常用的自動化搬運設備有堆垛機、傳送帶（輪）和自動導航小車（Automatic Guided Vehicle，AGV）等。不同規模的倉庫會根據功能需求采用不同的搬運設備組合。隨著柔性制造需求的不斷增長，AS/RS與企業生產環節逐漸相互融合，出現了集成生產的AS/RS系統。在集成生產環境中，AGV是連接倉庫和生產車間的重要紐帶，成為AS/RS中不可缺少的重要組成部分。

AS/RS系統的運行效率與出入庫作業的優化調度效果密切相關。作業調度的任務是對用戶提交的多個作業進行重新排列并分配到合適的自動化搬運設備執行，使作業的整體運行時間最少。作業調度是一種邏輯層次的全局調度，具體調度過程要依據底層自動化搬運設備的運行狀態信息。在由多種設備構成的搬運系統中，一項作業的執行時間是各個設備運送時間的累加，作業調度具有管理和協調各種搬運設備的作用。若搬運系統只有一種搬運設備，則作業調度等同于直接對搬運設備的調度。在集成生產的AS/RS環境中，AGV運行最為耗時，對整個自動化搬運系統的效率具有決定性影響。因此，可將集成生產環境中的作業調度問題簡化為AGV的作業調度問題。

在關于AS/RS的各種優化研究中，關于巷道分揀系統的存取優化[1]和AGV小車在自由空間移動時的路徑規劃優化[2-5]的研究比較多，也比較成熟。關于作業調度的研究則比較少。甘劍鋒等[6]用排隊論理論對AGV調度系統進行建模，得到了一個M/G/1模型，并用該模型對AGV調度效率進行了分析。金芳等[7]用排隊論理論對AGV調度系統建立了一個M/M/1模型，并對調度效率進行了分析。雷定猷等[8]從柔性制造的一般環境出發對AGV調度系統建立了一個多AGV多請求的一般優化模型，并提出了一種求解的遺傳算法。文獻[9-10]簡化了AGV調度的相關約束，建立了一個簡化的優化模型，并分別提出用遺傳算法和PSO算法來進行求解。但總體來說，目前對AGV作業調度問題的研究還很不成熟。

差分演化算法（DE）是模擬大自然的演化過程而提出的一種基于種群的隨機搜索算法[11-12]。自提出以來，其優異的優化性能已經得到了普遍的認可，并應用在很多優化領域[13]。本文首先對AGV作業調度問題進行了分析，建立了問題的優化模型，并分析了模型的特點。AGV作業調度問題可以抽象為一種帶約束的多重TSP問題，也是一種NP完全問題，當前并不存在可在多項式時間內確定求解的算法。為此，本文針對優化模型提出了改進的差分演化算法，引入了新的兩段編碼方法和基于生存時間的個體重置機制。模擬實驗結果驗證了改進算法的有效性。

2 AGV作業調度問題

2.1 問題描述

在集成生產的AS/RS環境中，用戶在生產車間通過管理系統發出貨物的出入庫請求，而AGV的任務就是接收管理系統的調度在倉庫和工作間之間運送貨物。因此，AGV是聯系倉庫和工作間的重要紐帶。當用戶提交的作業較少時，AGV只需要依次執行各個作業即可，不涉及調度問題。但當用戶提交的作業遠大于現有AGV數量時，AGV按不同的順序執行作業對系統的運行效率有很大影響，因此需要合適的優化調度算法來決定如何向AGV分配作業以及讓AGV按什么順序執行這些作業[10]，這就是AGV的作業調度問題。

AGV系統是一個涉及多個環節的復雜系統，作業調度優化的效果也會受到多方面因素的影響。為更好地探討問題的本質和求解策略，有必要對問題進行必要的簡化和說明。

（1）AGV作業調度貫穿于倉庫運行的整個過程，因此，實際的AGV作業調度問題屬于典型的動態調度問題，這類問題往往難以求解。為降低求解難度，可假設整個調度過程由一系列的調度周期組成，在每個調度周期內待調度的作業數量是穩定的。這就可將復雜的動態調度問題轉化成一系列離散的靜態AGV作業調度問題。

（2）在度量一個作業的執行代價時，需要計算AGV在執行作業時所經過路徑的距離。在某些應用環境中，AGV的運行路徑無法事先預知，需要專門的路徑規劃功能動態確定，這已超出了本文的討論范圍。故此處假定所有AGV的運行路徑都是已知且穩定的。

（3）某些倉庫環境中，AGV執行完一項作業后，必須回到駐點才能執行下一項作業。此種情形下，作業優化調度的效果有限。故本文假定AGV執行完一項作業后直接執行隊列中的其他作業，只有在作業隊列為空時才會回到駐點。

（4）為了問題表述的方便，假設AGV的運行速度是恒定的，其運行時間與路徑長度成正比。

2.2 作業執行過程

AGV執行一項作業需要經歷兩個階段。假設有一臺AGV初始停靠在駐點處。當接收到執行作業命令時，AGV要先從駐點出發到達作業的起始點。這是作業執行的第一階段，此時AGV處于空載狀態，并不實際運送貨物，是作業的準備階段，花費的時間稱為作業準備時間(tp)。接下來，AGV將作業起點處的貨物裝載，并運送到作業指定的目的地，完成作業。這是作業執行的第二階段，屬于作業的執行階段，花費的時間稱為作業執行時間(te)。此時，如果還有其他待執行的作業，AGV直接移動到下一項作業的起點，然后將貨物送達作業指定的目的地。如此反復，直至所有作業執行完畢，AGV返回到駐點等待。

作業執行階段是作業執行的重要組成部分，但其時間是直接可預測的。一旦作業的起點和終點確定，不論作業的調度次序如何變化，作業從其起點到終點需要的運行時間相對穩定，與兩點間的執行路徑距離成正比。當倉庫和生產車間的布局結構確定后，布局內點到點的路徑會隨著系統的持續優化而趨于穩定，因此，可將不同的路徑抽象為一個帶權圖（權為兩點間的距離）存儲在系統內。由于AGV的運行速度是已知的，則AGV在兩點之間的運行時間te可由公式（1）求出。

其中，dmn為兩點m和n之間的距離，v是AGV運行速度。作業執行的準備時間與AGV的當前位置密切相關。除了AGV在駐點的情況，AGV的當前位置是前一項作業的終點，會隨著作業執行順序的變化而不同。因此，AGV需要執行哪些作業以及按什么順序執行這些作業都將影響到作業的執行效率。這也正是AGV作業調度主要任務。AGV作業調度是集成生成環境下倉庫管理系統的重要功能之一。采用合理的作業調度策略來優化AGV的執行作業過程，對提高自動化倉庫的運行效率起到至關重要的作用。

2.3 調度優化模型

設有m個AGV和n個待執行的作業。用Ai(i=1，2，…，m)表示第 i個AGV，Ji(i=1，2，…，n)表示第 i個作業。AGV執行作業Ji需要的總時間ti為：

其中tpi是AGV從前一作業的終點移動到當前作業起點所花費的時間，是執行作業Ji的準備時間；tei是AGV從當前作業起點運送到作業終點所花費的時間，屬于作業的執行時間。

在大多數情況下，AGV總是連續地執行多個作業。設將作業隊列中的個作業分配給 Ai，則 Ai執行si個作業需要的總時間Ti為：

當有多個AGV時，每個AGV并行執行所有的作業。m個AGV并行執行完所有作業的總執行時間為：

此外，每項作業還可能存在完成時間的約束。設作業Ji的請求時間為tqi，限定的最遲完成時間為tci。在每個AGV執行隊列中，作業Ji的執行完成時間tri為：

則作業Ji的約束條件滿足程度ei可定義為：

則所有n個作業的總體約束條件滿足情況E為：

作業調度的最終目標就是找出最優的作業執行序列和分配方案，使得所有作業總的執行時間最小且滿足所有約束條件。即

2.4 模型分析

當環境中只有一個AGV時，AGV作業調度問題只需合理安排作業的執行順序，不涉及作業的分配問題，此時，該問題等價于一個帶時間約束的TSP問題。在實際的生產過程中，AGV數量一般有多臺。此時，AGV作業調度問題可近似為帶時間約束的多重TSP問題。由于TSP或多重TSP問題已被證明是NP完全問題[11]，顯然AGV作業調度問題也是一個NP完全問題，當前還找不到可以在多項式時間內求解該問題的確定性算法。

在不考慮約束的情況下，AGV作業調度問題的求解空間非常巨大。將n個作業分配給m個AGV有mn種組合。設每個AGV被分配si(i=1，2，…，m)個作業，則每個AGV執行所有作業的順序有si!種不同選擇。設s=max(si)，則AGV作業調度問題的搜索空間為：s.mn。可見，隨著作業和AGV數量的增加，問題求解空間呈指數增長。

3 改進的差分進化算法（IDE）

3.1 差分進化算法簡述

差分進化算法是由Storn和Price于1995年提出的一種基于種群的隨機搜索算法[11-12]，其主要原理是模擬自然界“優勝劣汰、適者生存”的進化法則。DE算法具有迭代過程簡單，控制參數少，尋優能力強等特點，自算法提出以來，就得到了廣泛的關注和快速的發展。研究者已針對不同的問題提出了多種DE變體。當前，除了傳統的函數優化領域外[14-15]，DE在組合優化、約束優化以及眾多實際工程領域都得到了成功應用[13]。

和遺傳算法類似，DE的基本操作也包括：變異、交叉及選擇三種操作。在計算迭代中，算法隨機選擇兩個不同的個體向量相減產生差分向量，然后將差分向量賦予權值后與另一隨機選出的個體向量相加，從而生成變異向量。變異向量與目標個體向量進行混合交叉，得到測試個體向量；然后測試個體與原目標個體進行一對一競爭，擇優生成新一代的種群。

變異操作是DE算法的核心操作，這也是其與遺傳算法的主要區別。在DE算法中，變異操作將父代種群中多個個體進行線性組合生成變異向量，其中最基本的變異成分是父代個體的差分向量。以廣泛使用的DE/rand/1變體為例，變異向量vi定義如下：

其中，{xr1，xr2，xr3} 是在父代種群中隨機選擇的三個個體，且 r1≠r2≠r3≠i，NP為種群規模，且滿足 NP≥4，F為縮放因子。

交叉操作的目的是產生測試向量，并通過變異向量和目標向量各維分量的隨機重組以提高種群個體的多樣性。常用的交叉操作有二項交叉和指數交叉。通過指數交叉產生測試向量如式（10）所示。

其中 n，L∈[0，D-1]，D為問題維度，n為隨機選擇的正整數，L的生成由交叉因子Cr∈[0,1]控制，通過循環累加獲得表示求模函數，D為模數。

DE算法的選擇操作采用精英保留模式，當且僅當測試向量ui的個體適應值比目標向量xi的適應值更好時，ui才會被種群接受。否則xi仍將保留在下一代的種群中。在最小化問題中，選擇操作如式（11）所示。

其中，t為當前演化代數。通過父代和子代的競爭和優勝劣汰，子代種群總是優于或等于父代種群，從而使種群始終向最優解的方向進化。

3.2 算法改進策略

雖然DE算法及其變體在求解各類優化問題時表現出了優異的性能，但并不存在可以求解所有優化問題的統一算法。針對不同的問題，DE算法要在編碼方式、變異策略、控制參數等方面需要作出必要的調整和改進。由于AGV作業調度問題的優化結果既要確定作業集的分組方式，并把每個分組恰當地分配給特定的AGV，又要確定每個分組內作業的執行順序。這是傳統的個體編碼方式所無法解決的，需要設計新的個體編碼方式。而編碼方式的改變必將導致算法在種群初始化、交叉變異策略及適應值評估方式等方面的變化。

3.2.1 兩段編碼方式

傳統的單序列個體編碼方法無法同時解決AGV作業調度問題中面臨的作業集分組優化和作業執行順序優化兩個問題。為此，本文設計了一種新的兩段編碼方法。如圖1所示。

圖1 兩段編碼方式示意圖

每個個體的編碼由兩段構成。第一段為作業段，由所有作業 Ji(i=1，2，…，n)的編號排列構成，包含了所有作業的分組分配和執行順序信息。分組分配信息要結合后面的分配段來確定。分配段由m-1個位置指針Pi(i=2，3，…，m)組成，指針 Pi的值表示第 i個AGV需要執行的作業子序列在作業段的開始位置，同時也表示第i-1個AGV執行的作業子序列的結束位置。第1個AGV執行子序列的開始位置默認為0，結束位置為指針P2的值。若系統中只有1個AGV設備，則編碼中的分配段省略。

采用兩段編碼方式后，每個個體的元素由n+m-1位整數構成。若將n個作業依次用0，1，…，n-1表示，則個體中每個元素的取值范圍均為：[0，n-1]，且段內元素互不重復。采用相同的取值空間便于后續演化操作的實現。兩段編碼方式可以看作是傳統單序列編碼的擴展，既有效解決了AGV作業調度問題中的優化信息表示問題，又簡潔易于實現。

3.2.2 種群初始化

采用兩段編碼方式后，個體由具有不同意義的兩部分構成，因此，初始化操作也要針對每個部分單獨進行。按均勻分布隨機初始化個體是最常用的種群初始化方式。因此，對于個體作業段部分的初始化仍采用傳統的隨機初始化方式，同時要保證作業序列中不存在重復作業。

由2.3節的優化模型可知，若要取得較好的優化調度結果，所有AGV應該相對均衡地承擔所有作業，防止出現AGV空載或負荷過重的情況。為此，分配段部分的初始化要采用區間均衡隨機初始化方法。假如系統中有m臺AGV，則需要構建由m-1個元素組成的分配段（首元素默認為0）。首先將n個作業構成的分配空間均分為m段，則分割點集為：。然后，分配段中每個元素的值就可依次以分割點為均值，并按高斯分布 N(π，σ)生成，其中。采用區間均衡隨機初始化方式既保證了分割點是一個遞增序列，又實現了初始分配的均衡性。

3.2.3 變異交叉操作

變異交叉操作是DE算法的核心操作算子，是保證算法搜索性能的重要手段。由于AGV作業調度問題是一種組合優化問題，在搜索過程中保持優良的搜索模式是非常必要的。由于DE/rand/1/exp變異模式已在眾多文獻中得到應用，顯示了優良的搜索性能和收斂速度。因此，本文對于個體作業段部分也采用DE/rand/1/exp變異模式。具體實現方式見式（9）、（10）。

為了保持分配段的相對穩定，分配段采用遺傳算法中常用的算術交叉方式。如式（12）所示。

其中，α為交叉因子，r1，r2，r3為隨機選擇的3個父個體的位置。

算法在變異交叉操作時會產生一些無效個體向量，如存在重復元素等。當出現無效個體向量時，直接將之丟棄，并根據前述方法重新生成新的個體向量，直至個體合法。

3.2.4 適應值評估及選擇

演化出新個體之后需要對其適應值進行評估。首先將個體中分配段的值按從小到大進行排序，然后依據分配段的值將作業段中的作業序列劃分為m個子序列，每個子序列的大小為 si(i=1，2，…，m)。將每個子序列依次分配給AGV進行執行，并按照公式（3）計算出每個子序列的執行時間Ti，然后按公式（4）求出所有子序列的最大執行時間 f即為該個體的適應值。同時，可按照式（5）～（7）求出個體的約束滿足值E。

在AGV作業調度中，作業的時間約束并不是十分嚴格。為便于迭代及選擇操作，定義如下擇優標準：

其中Ii和Ij表示兩個個體，f和E表示個體的適應值和約束值。按照式（13），當測試向量優于目標向量時替代目標向量，否則目標向量繼續保留在種群中。

3.2.5 基于生存時間的種群多樣性增強機制

DE算法采用精英保留策略，父代和子代直接進行競爭、優勝劣汰，種群的選擇壓力比較大，算法容易早熟收斂或陷入局部最優。為了提高種群的多樣性和算法的搜索能力，本文引入了一種新的基于生存時間的種群多樣性增強機制，該機制類似于人工蜂群算法（ABC）[16]中偵察蜂的機制，但并不限制每代淘汰個體的數量。在ABC算法中，偵察蜂可以增強算法搜索能力已得到廣泛認可。

種群中每個個體都增加一個生存時間（life）屬性，并在初始化時置為0。當個體經過一代演化后若適應值沒有被更新，則life值增加1。若個體已被新個體取代，則life值重置為0。算法設置了一個新的最大生存時間（MaxLife）參數。每經過一代演化，系統檢查每個個體的life值。當個體的life值大于MaxLife時，則表示個體經過了MaxLife代仍沒有更新，個體已經喪失了搜索能力。若該個體不是種群中最優個體則將其從種群中刪除，并按3.2.2節中方法重新初始化一個新的個體加入種群。該機制可以淘汰種群中的局部最優點，隨機生成的新個體可以增強種群的多樣性，提高算法的搜索能力，防止算法陷入局部最優。

4 仿真實驗及分析

為驗證改進算法的有效性，本文設計了一組模擬實驗。實驗以一個實際應用的場地布局為參照，共設置了22個站臺。為了對算法進行全面的評估，實驗設計不同的AGV數量和AGV負荷的情況。結合實際應用情況，將AGV數量 m分別設為1、2、4、8四種情況，將AGV的平均負載情況ld分別設為5、10、20三種情況。每次實驗根據m和ld，隨機生成m×ld個待執行作業，然后分別用先來先服務（FIFO）算法和改進的差分演化算法（IDE）及其簡化版本（不含種群多樣性增強機制）（SIDE）依次對生成的作業進行調度。為了更清晰地考察算法的尋優能力，各組實驗沒有考慮作業的時間約束問題。

差分演化算法的參數設置如下：

種群大小（NP）為 50，最大評估次數（MaxFEs）為100000，縮放因子（F）為0.5，交叉因子（Cr）為0.8，最大生存時間（MaxLife）為5。

優化調度結果如表1～表3所示。標記為FIFO、SIDE和IDE的行表示分別采用FIFO算法、SIDE算法和IDE算法調度后AGV執行完所有作業所用的時間（s）；S/F行表示SIDE算法相對于FIFO算法優化提高效率的比率；I/F行表示IDE算法相對與FIFO算法提高效率的百分比。

表1 負荷ld=5時的優化調度結果

表2 負荷ld=10時的優化調度結果

表3 負荷ld=20時的優化調度結果

從表3可以看出，在三種算法中FIFO算法的調度時間總是最差，SIDE算法居中，而IDE算法總能取得最好的調度結果。這說明本文提出的算法改進策略是有效的。另一方面SIDE和IDE的性能差異并沒有確定的規律可循，當ld=10時，IDE性能優化提高率是SIDE算法的5倍，當ld=5時這一比率約為2。此外，在負載較大時，IDE可以普遍提高效率20%左右，而SIDE算法在各種情況下的效率提高均不超過10%。這些差異是由基于生存時間的種群多樣性增強機制造成，說明該機制確實可有效增強算法的搜索能力，提高算法的尋優效率。當模擬作業數量(m×ld)小于20時，模擬數據的波動較大，這主要是由于場地的AGV站點多于作業數量時，隨機生成的作業無法對各站點進行均勻覆蓋所致。

圖2顯示了當AGV數量為1，負載為20時的演化收斂曲線。可以看出，兩種算法都有較快的收斂速度。雖然IDE算法在演化早期收斂速度較慢，但其搜索過程可以持續發現更優解，使搜索得到較好的最終解。SIDE算法的早期收斂速度比較快，但其發現新解的能力較差，容易陷入局部最優。

圖2 演化過程收斂曲線（m=1，ld=20）

5 結束語

AGV作業調度問題是集成生產環境中的一類典型的調度優化問題，其對AS/RS系統的執行效率具有重要影響。由于問題本身的復雜性，相關的研究還比較少。經過對問題進行必要的簡化，去除了問題的動態特性，并抽象出了AGV作業調度的靜態優化模型。可以看出AGV作業調度問題實質是帶約束的多重TSP問題，是一個NP完全問題。并且具有巨大的求解空間，當前還無法找到具有多項式時間的確定算法能對其求解。本文針對AGV作業調度的特點，提出了一種改進的差分演化算法，設計了新的兩段編碼方式，并對DE算法中的交叉、變異、評估及選擇操作進行了改造，以適合問題的求解。同時，還提出了新的基于生存時間的種群多樣性增強機制，用以提高算法的搜索能力，防止算法陷入局部最優。仿真實驗表明IDE算法可以有效求解AGV作業調度問題，且具有較快的收斂速度。

[1]姜山，季業飛.GASA混合優化算法在自動化立體倉庫堆垛機作業調度問題中的應用[J].制造業自動化，2010，32（10）：63-64.

[2]劉國棟，曲道奎，張雷多.AGV調度系統中的兩階段動態路徑規劃[J].機器人，2005，27（3）：210-214.

[3]李莉，張立明，詹躍東.求解AGV路徑優化問題的遺傳算法參數優化[J].昆明理工大學學報：理工版，2006，31（4）：26-31.

[4]夏謙，雷勇，葉小勇.遺傳算法在AGV全局路徑優化中的應用[J].四川大學學報：自然科學版，2008，45（5）：1129-1136.

[5]任小龍，溫浩宇，李華.無向Petri網的多AGV最優路徑方法研究[J].西安電子科技大學學報：自然科學版，2008，35（3）：517-521.

[6]甘劍鋒，周曉光.基于排隊論的自動化立體倉庫AGV調度效率分析[J].計算機測量與控制，2004，12（7）：657-659.

[7]金芳，方凱，王京林.基于排隊論的AGV調度研究[J].儀器儀表學報，2004（4）：844-846.

[8]雷定猷，張蘭.AGV系統的調度優化模型[J].科學技術與工程，2008，8（1）：66-69.

[9]柳賽男，柯映林.自動化倉庫系統AGV小車優化調度方法[J].組合機床與自動化加工技術，2008（6）：23-25.

[10]邊培瑩，李德信，包寶軍，等.粒子群算法在生產物流調度中的應用研究[J].計算機工程與應用，2010，46（17）：220-223.

[11]Storn R，Price K.Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces，tech.rep.TR-95-012[R].Berkeley，CA，1995.

[12]Storn R，Price K.Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization，1997，11：341-359.

[13]Das S，Suganthan P N.Differential evolution：a survey of the state-of-the-art[J].IEEE Trans on Evol Comput，2011，15（1）：4-31.

[14]Qin A K，Huang V L，Suganthan P N.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Trans on Evol Comput，2009，13（2）：398-417.

[15]Wang H，Wu Z J，Rahnamayan S.Enhanced oppositionbased differential evolution for solving high-dimensional continuous optimization problems[J].Springer J Soft Comput，2011，15：2127-2140.

[16]Karaboga D.An idea based on honey bee swarm for numerical optimization，technical report-TR06[R].Computer Engineering Department，Engineering Faculty，Erciyes University，2005.