楊鋒英，劉會超

YANG Fengying1,LIU Huichao2

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

2.黃淮學院 網(wǎng)絡(luò)信息管理中心，河南 駐馬店 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 引言

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

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

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

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

2 AGV作業(yè)調(diào)度問題

2.1 問題描述

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

AGV系統(tǒng)是一個涉及多個環(huán)節(jié)的復(fù)雜系統(tǒng)，作業(yè)調(diào)度優(yōu)化的效果也會受到多方面因素的影響。為更好地探討問題的本質(zhì)和求解策略，有必要對問題進行必要的簡化和說明。

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

（2）在度量一個作業(yè)的執(zhí)行代價時，需要計算AGV在執(zhí)行作業(yè)時所經(jīng)過路徑的距離。在某些應(yīng)用環(huán)境中，AGV的運行路徑無法事先預(yù)知，需要專門的路徑規(guī)劃功能動態(tài)確定，這已超出了本文的討論范圍。故此處假定所有AGV的運行路徑都是已知且穩(wěn)定的。

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

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

2.2 作業(yè)執(zhí)行過程

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

作業(yè)執(zhí)行階段是作業(yè)執(zhí)行的重要組成部分，但其時間是直接可預(yù)測的。一旦作業(yè)的起點和終點確定，不論作業(yè)的調(diào)度次序如何變化，作業(yè)從其起點到終點需要的運行時間相對穩(wěn)定，與兩點間的執(zhí)行路徑距離成正比。當倉庫和生產(chǎn)車間的布局結(jié)構(gòu)確定后，布局內(nèi)點到點的路徑會隨著系統(tǒng)的持續(xù)優(yōu)化而趨于穩(wěn)定，因此，可將不同的路徑抽象為一個帶權(quán)圖（權(quán)為兩點間的距離）存儲在系統(tǒng)內(nèi)。由于AGV的運行速度是已知的，則AGV在兩點之間的運行時間te可由公式（1）求出。

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

2.3 調(diào)度優(yōu)化模型

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

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

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

當有多個AGV時，每個AGV并行執(zhí)行所有的作業(yè)。m個AGV并行執(zhí)行完所有作業(yè)的總執(zhí)行時間為：

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

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

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

作業(yè)調(diào)度的最終目標就是找出最優(yōu)的作業(yè)執(zhí)行序列和分配方案，使得所有作業(yè)總的執(zhí)行時間最小且滿足所有約束條件。即

2.4 模型分析

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

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

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

3.1 差分進化算法簡述

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

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

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

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

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

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

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

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

3.2 算法改進策略

雖然DE算法及其變體在求解各類優(yōu)化問題時表現(xiàn)出了優(yōu)異的性能，但并不存在可以求解所有優(yōu)化問題的統(tǒng)一算法。針對不同的問題，DE算法要在編碼方式、變異策略、控制參數(shù)等方面需要作出必要的調(diào)整和改進。由于AGV作業(yè)調(diào)度問題的優(yōu)化結(jié)果既要確定作業(yè)集的分組方式，并把每個分組恰當?shù)胤峙浣o特定的AGV，又要確定每個分組內(nèi)作業(yè)的執(zhí)行順序。這是傳統(tǒng)的個體編碼方式所無法解決的，需要設(shè)計新的個體編碼方式。而編碼方式的改變必將導(dǎo)致算法在種群初始化、交叉變異策略及適應(yīng)值評估方式等方面的變化。

3.2.1 兩段編碼方式

傳統(tǒng)的單序列個體編碼方法無法同時解決AGV作業(yè)調(diào)度問題中面臨的作業(yè)集分組優(yōu)化和作業(yè)執(zhí)行順序優(yōu)化兩個問題。為此，本文設(shè)計了一種新的兩段編碼方法。如圖1所示。

圖1 兩段編碼方式示意圖

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

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

3.2.2 種群初始化

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

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

3.2.3 變異交叉操作

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

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

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

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

3.2.4 適應(yīng)值評估及選擇

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

在AGV作業(yè)調(diào)度中，作業(yè)的時間約束并不是十分嚴格。為便于迭代及選擇操作，定義如下?lián)駜?yōu)標準：

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

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

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

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

4 仿真實驗及分析

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

差分演化算法的參數(shù)設(shè)置如下：

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

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

表1 負荷ld=5時的優(yōu)化調(diào)度結(jié)果

表2 負荷ld=10時的優(yōu)化調(diào)度結(jié)果

表3 負荷ld=20時的優(yōu)化調(diào)度結(jié)果

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

圖2顯示了當AGV數(shù)量為1，負載為20時的演化收斂曲線?？梢钥闯觯瑑煞N算法都有較快的收斂速度。雖然IDE算法在演化早期收斂速度較慢，但其搜索過程可以持續(xù)發(fā)現(xiàn)更優(yōu)解，使搜索得到較好的最終解。SIDE算法的早期收斂速度比較快，但其發(fā)現(xiàn)新解的能力較差，容易陷入局部最優(yōu)。

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

5 結(jié)束語

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

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

[2]劉國棟，曲道奎，張雷多.AGV調(diào)度系統(tǒng)中的兩階段動態(tài)路徑規(guī)劃[J].機器人，2005，27（3）：210-214.

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

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

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

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

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

[8]雷定猷，張?zhí)m.AGV系統(tǒng)的調(diào)度優(yōu)化模型[J].科學技術(shù)與工程，2008，8（1）：66-69.

[9]柳賽男，柯映林.自動化倉庫系統(tǒng)AGV小車優(yōu)化調(diào)度方法[J].組合機床與自動化加工技術(shù)，2008（6）：23-25.

[10]邊培瑩，李德信，包寶軍，等.粒子群算法在生產(chǎn)物流調(diào)度中的應(yīng)用研究[J].計算機工程與應(yīng)用，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.