于巧玉，吳耀華，王艷艷

山東大學 控制科學與工程學院，濟南 250061

1 引言

隨著近年來電子商務行業(yè)的快速穩(wěn)健發(fā)展，大量的網(wǎng)絡購物訂單涌入到企業(yè)的倉庫管理系統(tǒng)中，同時顧客對訂單履行的時效也提出了更高的要求。如何快速、準確地滿足訂單的揀選出庫要求，是電商企業(yè)面對海量訂單首先要解決的問題?？鐚哟┧筌囯p提升機系統(tǒng)（tier-totier shuttle-based storage and retrieval system with double lifts）是一種結合電商企業(yè)倉儲揀選特點，基于“貨到人”（Part-to-Picker）理念而設計，集存儲和揀選于一體的現(xiàn)代化倉儲系統(tǒng)[1]。該系統(tǒng)通過多層多巷道立體貨架實現(xiàn)密集存儲，以料箱為存儲單元，穿梭車和提升機組合代替?zhèn)鹘y(tǒng)自動化立體倉庫中的堆垛機，分別完成料箱出入庫的水平搬運和垂直搬運，通過自動化智能設備和計算機管理控制系統(tǒng)之間的雙向通信，將料箱輸送至揀選臺，待揀選完成之后將料箱輸送回立體倉庫繼續(xù)存儲[1]。將跨層穿梭車雙提升機系統(tǒng)應用到電商環(huán)境下的倉儲作業(yè)中，以自動化智能設備代替人工作業(yè)，實現(xiàn)智能、高效、可靠揀選，對實現(xiàn)海量訂單的快速、準確揀選具有重要意義。

跨層穿梭車雙提升機系統(tǒng)是一種新型的自動化倉儲設備，目前國內(nèi)外學者對于不同形式的穿梭車系統(tǒng)任務調(diào)度問題進行了研究。Zou等[2]通過分析多層穿梭車系統(tǒng)建立了Fork-join 排隊網(wǎng)絡模型，并通過最大熵法（Maximum Entropy Method，MEM）求解，分析對比了穿梭車和提升機在并行作業(yè)命令和順序作業(yè)命令兩種策略下系統(tǒng)的性能；Ekren 等[3]和 Tappia 等[4]考慮穿梭車和提升機之間的制約關系，建立了半開環(huán)排隊網(wǎng)絡模型來求得系統(tǒng)的主要性能指標；牟善棟[5]研究了多層穿梭車倉儲系統(tǒng)（Multi-tier Shuttle Warehousing System），并指出作業(yè)效率的影響因素，建立了貨位分配和任務調(diào)度優(yōu)化模型，通過蟻群算法和非支配遺傳算法分別對兩個模型進行求解；吳穎穎等[6]使用耦合因子描述訂單之間的相互關系，對“貨到人”系統(tǒng)中每個揀選臺的揀選任務進行分配和排序，使用改進的K-Means聚類算法對問題進行求解；鄒霞等[7]通過分析設備運動軌跡、設備運動時間模型、作業(yè)時間構成及多作業(yè)間的時序關系，建立多層穿梭車系統(tǒng)作業(yè)時間模型，研究貨架結構和訂單密度對系統(tǒng)效率的影響；張娜[8]使用半開環(huán)排隊網(wǎng)絡對跨層穿梭車系統(tǒng)進行建模，對其最優(yōu)設備配置及出庫任務調(diào)度進行研究；楊瑋等[9]對雙載式多層穿梭車系統(tǒng)復合作業(yè)路徑優(yōu)化問題進行了研究，使用混合植物遺傳算法實現(xiàn)調(diào)度優(yōu)化模型的求解。

目前，對于穿梭車系統(tǒng)任務調(diào)度和訂單排序的研究都以一批訂單出庫時間最短為優(yōu)化目標，缺乏對于訂單交貨時間限制的研究。柳賽男[10]在自動導引車系統(tǒng)的調(diào)度方法中加入優(yōu)先級策略，采用云模型對調(diào)度任務進行優(yōu)先級評價，并設計了基于文化算法的優(yōu)化算法對問題進行了求解；胡建偉[11]分析環(huán)形穿梭車系統(tǒng)運行原理和倉庫任務調(diào)度原則，對調(diào)度管理系統(tǒng)進行開發(fā)，并在調(diào)度過程中對任務優(yōu)先級的評估體系和評價方法進行了研究。

基于以上研究，在跨層穿梭車雙提升機系統(tǒng)的調(diào)度策略中引入交貨時間限制，以穿梭車為服務節(jié)點建立了出庫調(diào)度時間模型。針對穿梭車系統(tǒng)出庫任務作業(yè)方式，提出使用蟻群-粒子群雙層智能算法將任務調(diào)度問題分兩步進行求解，并使用隨機變異改進粒子群算法，提高了算法的求解性能。最后，通過對比實驗，證明了模型和算法的有效性。

2 問題描述與分析

2.1 跨層穿梭車雙提升機系統(tǒng)模型

跨層穿梭車雙提升機系統(tǒng)采用料箱為存儲和揀選單元，系統(tǒng)構成如圖1所示，由穿梭車換層提升機、貨物提升機、巷道穿梭車、高層貨架、料箱輸送線以及揀選臺組成[12]，實現(xiàn)庫存料箱存儲和揀選出庫作業(yè)。

圖1 跨層穿梭車雙提升機系統(tǒng)側面圖

該系統(tǒng)采用穿梭車并行作業(yè)，貨物提升機串行作業(yè)出庫的協(xié)作方式，首先由穿梭車從指定貨位拿取料箱，送到巷道首端，然后由貨物提升機將料箱送到一層Input/Output 站臺（I/O 口），完成一次料箱揀選出庫任務。系統(tǒng)出庫作業(yè)流程如圖2所示。

圖2 跨層穿梭車雙提升機系統(tǒng)訂單出庫流程

定義1O={(1,l1),(2,l2),…,(i,li),…,(Q,lQ)}表示出庫任務集合，其中，i表示任務序號，li表示待出庫任務料箱貨位信息。

定義 2S={(1,q1),(2,q2),…,(j,qj),…,(m,qm)} 表示巷道穿梭車集合，其中，j表示穿梭車序號，qj表示該穿梭車的任務量。

本文所要求解的任務調(diào)度問題可以描述為一種分配方案問題A={o→s}，其中o∈O,s∈S，所得到的分配方案即為所求最優(yōu)任務調(diào)度方案。

穿梭車系統(tǒng)在執(zhí)行出庫任務時，應滿足以下條件：

（1）每個出庫任務對應的料箱貨位信息和穿梭車編號唯一。

（2）穿梭車執(zhí)行出庫任務時每次只能拿取一個料箱，送至巷道首端后申請貨物提升機調(diào)度，將料箱交接給貨物提升機之后才可離開，繼續(xù)執(zhí)行下一任務。

（3）跨層提升機、貨物提升機的調(diào)度遵循先到先服務的原則（First-Come，F(xiàn)irst-Served，F(xiàn)CFS），若有多于一輛穿梭車同時提出調(diào)度申請，則提升機優(yōu)先響應編號較小的穿梭車申請。

（4）系統(tǒng)初始時間記為0，跨層提升機和貨物提升機都在第一層，穿梭車位置隨機初始化。

（5）為防止碰撞和死鎖現(xiàn)象，每層只允許一輛穿梭車進入，該層鎖定，穿梭車離開后解鎖，允許其他穿梭車進入。

2.2 訂單揀選出庫作業(yè)流程分析

2.2.1 穿梭車執(zhí)行出庫作業(yè)時間建模

跨層穿梭車雙提升機系統(tǒng)由倉庫管理系統(tǒng)（Warehouse Management System，WMS）將一個時間窗內(nèi)的出庫任務進行匯總，倉庫控制系統(tǒng)（Warehouse Control System，WCS）將這些出庫任務進行排序優(yōu)化，最終下發(fā)給硬件設備完成出庫任務。通過對穿梭車和跨層提升機、貨物提升機的配合作業(yè)流程進行分析和優(yōu)化，提高系統(tǒng)的作業(yè)效率，減小時間窗內(nèi)訂單出庫總時間，同時降低揀選任務出庫超時率。三者之間的配合作業(yè)如圖3所示。

圖3 穿梭車與提升機配合作業(yè)流程

穿梭車接到料箱出庫任務后，由待命狀態(tài)進入接受任務狀態(tài)，此時穿梭車需判斷是否需進行跨層作業(yè)。如果穿梭車與出庫料箱不在同一層，穿梭車首先水平運動至巷道尾端，申請跨層提升機調(diào)度服務并等待提升機響應，若此時跨層提升機空閑，會立即響應穿梭車申請并前往該層完成穿梭車交接，將穿梭車垂直運輸?shù)匠鰩炝舷渌趯樱嵘龣C進入待命狀態(tài)；如果穿梭車與出庫料箱在同一層，穿梭車水平運動至出庫料箱所在貨位，利用自身貨叉完成取料箱動作。

載有出庫料箱的穿梭車水平運動至巷道首端，申請貨物提升機調(diào)度，提升機按照FCFS 原則響應穿梭車申請，前往至穿梭車所在層完成貨物交接，此時穿梭車進入待命狀態(tài)。貨物提升機將料箱送至出庫站臺，完成I/O 交接，料箱出庫任務完成。此時貨物提升機進入待命狀態(tài)，直到響應下一輛穿梭車調(diào)度服務申請。

將穿梭車看作服務節(jié)點，則固定時間窗內(nèi)的任務出庫總時間可定義為最大穿梭車工作時間與貨物提升機最后一個任務執(zhí)行時間之和。根據(jù)任務執(zhí)行過程建立穿梭車j完成所分配的qj個出庫任務所需時間數(shù)學模型Tj：

其中：

式中，Xij和δij為指示決策變量，當指定穿梭車j執(zhí)行任務i的出庫任務時，Xij為1，否則為0；當穿梭車需要執(zhí)行跨層取貨任務時，δij為1，否則為0。為穿梭車j執(zhí)行任務i出庫時換層所用的時間；為穿梭車j執(zhí)行任務i出庫時在取貨層水平運動所用的時間；為穿梭車j執(zhí)行任務i出庫時等待貨物提升機響應的時間；tsp為穿梭車取料箱或者放料箱的時間；tH為穿梭車從巷道首端運動到巷道尾端所用的時間，為固定常數(shù)；為穿梭車j執(zhí)行任務i出庫時等待換層提升機響應的時間；為穿梭車j執(zhí)行任務i出庫時，載有穿梭車的提升機垂直運動到出庫訂單所在層所用的時間；tcp為換層提升機裝載或者卸載穿梭車的時間。

2.2.2 動力學分析

設穿梭車系統(tǒng)貨架層高為rh，貨架列寬為rw，貨架層數(shù)為Ln，貨架列數(shù)為Rn，出庫任務i的貨位坐標為(mi,ni)，mi=1,2,…,Ln，ni=1,2,…,Rn，mi表示貨架層數(shù)編號，ni為貨架列數(shù)編號。穿梭車水平運行最大速度vh，提升機垂直運行最大速度vv，穿梭車水平運行加速度ah，提升機垂直運行加速度av。通過運動特性對設備運行時間進行具體分析。

（1）穿梭車在執(zhí)行跨層出庫任務時，首先要從巷道首端運動到巷道尾端，其運動時間為一固定值tH：

（2）假設出庫貨物距離巷道口的距離為S1(S1=mi×rw)，根據(jù)動力學運動公式，穿梭車執(zhí)行同層取貨任務時，穿梭車在取貨層水平運動所用的時間th：

同理，可以得到穿梭車執(zhí)行跨層取貨任務時在取貨層水平運動所用的時間。

（3）假設出庫貨物距離第一層的距離為S2(S2=(ni-1)×rh)，則貨物提升機執(zhí)行一個出庫任務垂直運動的時間tv：

（4）穿梭車執(zhí)行跨層出庫任務時，假設穿梭車與空載換層提升機之間的距離為S3(S3=|nj-nc|×rh)，則空載換層提升機垂直運動到穿梭車所在層的時間：

其中，nj表示穿梭車所在層編號，nc表示換層提升機所在層編號。

（5）假設穿梭車與待出庫貨物之間的垂直距離為S4(S4=|ni-nj|×rh)，則載有穿梭車的換層提升機垂直運動到貨物所在層所用時間：

2.2.3 穿梭車等待時間

按照FCFS原則，當穿梭車申請?zhí)嵘龣C進行服務時，如果提升機的上一個任務未完成，則穿梭車需等待提升機響應。根據(jù)申請服務類型的不同，可以將穿梭車等待時間分為等待換層提升機服務響應時間和等待貨物提升機服務響應時間。

（1）等待換層提升機服務響應時間

假設當前穿梭車服務申請為換層提升機的第h個任務，則等待時間：

其中，表示穿梭車提出申請換層提升機服務的時間，Tc表示換層提升機完成任務的時間。

（2）等待貨物提升機服務響應時間

假設當前穿梭車服務申請為貨物提升機的第l個任務，則等待時間：

其中，表示穿梭車提出申請貨物提升機服務的時間，Ts表示貨物提升機完成出庫任務的時間。

2.3 料箱揀選出庫任務調(diào)度優(yōu)化模型

2.3.1 固定時間窗內(nèi)料箱揀選出庫總時間

在跨層穿梭車雙提升機系統(tǒng)的運行環(huán)境中，所有的穿梭車都是以并行模式運行，分配到同一穿梭車的出庫訂單將在等待隊列中順序執(zhí)行，因此，在整個任務調(diào)度的過程中，建立出庫總時間模型：

約束條件為：

公式（13）表示完成訂單出庫任務的總時間不得小于第一個訂單水平作業(yè)時間與所有訂單的貨物提升機連續(xù)作業(yè)時間之和，即貨物提升機等待時間為零時，完成訂單出庫任務所用總時間；公式（14）表示穿梭車執(zhí)行跨層出庫任務時，必須先申請換層提升機服務再申請貨物提升機服務，且兩次申請調(diào)度的時間差不得小于穿梭車到目標層取料箱所用時間；公式（15）表示穿梭車完成出庫任務i的時間不得早于貨物提升機響應該出庫任務的時間加上貨物提升機到達出庫貨物所在層所用時間以及與貨物交接所需時間；公式（16）表示每個出庫訂單任務對應的穿梭車編號唯一。

2.3.2 料箱揀選任務超時時間

已知出庫任務集合O和調(diào)度方案A，經(jīng)出庫過程仿真后得到該調(diào)度方案各揀選任務的出庫完成時間集合，任務出庫時限集合。

此時，則稱任務i出庫超時。其中，表示出庫任務i實際完成時間，表示出庫任務i的出庫時限。

將任務出庫的超時率Rtimeout和平均超時時間Ttimeout引入到任務調(diào)度模型中，給出計算公式：

χi表示決策變量，χi={0,1},i=1,2,…,Q，任務i超時出庫時記為1，否則記為0。

結合公式（12），將出庫任務調(diào)度數(shù)學模型轉(zhuǎn)換為如下形式：

其中，θ1、θ2為權重系數(shù)，θ1+θ2=1?；谑剑?9）的任務調(diào)度模型充分考慮了出庫任務完成總時間和出庫任務時限的要求，符合穿梭車系統(tǒng)的任務調(diào)度特點及要求。

3 蟻群-粒子群雙層智能優(yōu)化算法設計

跨層穿梭車系統(tǒng)的任務調(diào)度問題，可以分解為兩部分進行求解：一是對穿梭車指派出庫任務；二是對特定穿梭車進行出庫任務排序。針對這一特點，使用蟻群-粒子群雙層智能優(yōu)化算法，首先利用蟻群算法將出庫任務分配給各穿梭車，再將分配結果輸入粒子群算法，對每輛穿梭車的出庫任務進行排序，結合系統(tǒng)過程仿真尋找最優(yōu)調(diào)度方案。

3.1 針對跨層穿梭車雙提升機系統(tǒng)的算法編碼

解決跨層穿梭車雙提升機系統(tǒng)的任務調(diào)度問題，根據(jù)2.1 節(jié)中對調(diào)度方案的定義，構造了基于訂單的編碼方式，編碼長度為，其粒子構成為(p1,p2,…,pn-1,pn)，其中pi表示一個出庫任務編號。以9個訂單，3輛可調(diào)度穿梭車為例，編碼C=(3,4,6,2,5,8,1,7,9)即為一種可行編碼，C(1)=3 表示訂單3是穿梭車1的第一個出庫任務，C(6)=8 表示訂單8是穿梭車2的第三個出庫任務，以此類推。解碼時將各穿梭車對應的所有出庫任務分解出來，例如，穿梭車1 對應的訂單序列為{3，4，6}。以矩陣形式表示調(diào)度方案，通過跨層穿梭車雙提升機系統(tǒng)過程仿真計算該出庫方案的出庫總時間。具體描述如下：

其中，Task代表一個任務調(diào)度方案，ajs表示訂單編號ajs的訂單為穿梭車j出庫順序中第s個出庫任務。根據(jù)編碼規(guī)則及調(diào)度原則，上述矩陣應有這樣的性質(zhì)：

（1）由于穿梭車的任務量不確定，矩陣的列數(shù)n=max{1,2,…,qm}。

（2）矩陣列數(shù)n=max(qj),j=1,2,…,m。當qj ＜n時，ajqj之后的元素記為0。

對于解碼過程中產(chǎn)生的非可行解，采用罰函數(shù)的方法減小其適應度值，逐漸淘汰產(chǎn)生的非可行解。

3.2 蟻群算法設計

算法第一層將出庫任務分配給不同的穿梭車，即確定穿梭車j的任務量qj以及相應的出庫任務編號i。使用最大最小蟻群算法（Max-Min Ant System，MMAS）[14]，對每條路徑信息素濃度設置最大最小值，每次循環(huán)中只對最優(yōu)螞蟻所走路線進行信息素增強。

MMAS 算法的目標是使各穿梭車的換層距離最短，即按照算法得出的分配方案穿梭車換層次數(shù)最少，從而減小訂單出庫任務總時間。在算法中，把出庫任務看作螞蟻要游歷的結點，按照轉(zhuǎn)移概率為每輛穿梭車選擇出庫任務，當所有出庫任務所需穿梭車選擇完畢，將分配結果作為輸入值，形成粒子群算法的初始粒子。

穿梭車的總換層距離采用公式（21）進行計算：

其中，Ls表示穿梭車j的第s個出庫任務所在層。

3.2.1 狀態(tài)轉(zhuǎn)移概率

螞蟻在轉(zhuǎn)移過程中，從任務i1移動到任務i2的轉(zhuǎn)移概率[14]為：

公式（21）表示穿梭車j的出庫任務中訂單i2與訂單i1的垂直距離越短，即穿梭車的換層時間越短，則選擇訂單i2作為訂單i1之后出庫任務的概率越大。

3.2.2 信息素更新

初始信息素濃度τi1,i2(0)=τmax，螞蟻完成一次訂單遍歷后對最佳路徑上的信息素濃度進行增強[15]，更新公式為：

其中，ρ為信息素揮發(fā)系數(shù)，ρ∈(0,1)，M為信息素濃度系數(shù)，D為最優(yōu)分配方案的穿梭車跨層總距離。τi1,i2(j)∈[τmin,τmax]，當τi1,i2(j)＞ τmax，取τi1,i2(j)=τmax；當τi1,i2(j)＜τmin，取τi1,i2(j)=τmin。

3.3 粒子群算法設計

離散粒子群算法（Discrete Particle Swarm Optimization，DPSO）作為算法第二層對穿梭車的訂單任務進行排序，以出庫總時間最短為優(yōu)化目標，借鑒遺傳算法中的交叉變異原理，使用置換序列對粒子進行更新，對調(diào)度問題進行優(yōu)化求解。在調(diào)度求解的過程中，對基本DPSO算法進行以下改進：（1）在初始解產(chǎn)生方面，采用蟻群算法分配結果作為初始解，而不是采用隨機產(chǎn)生初始解的方式；（2）在粒子更新過程中加入隨機置換，增加粒子的種群多樣性，避免算法早熟收斂于局部最優(yōu)；（3）提出置換復雜度的概念，通過設置不同的置換復雜度，合理控制算法的全局搜索能力和局部搜索能力。

3.3.1 適應度函數(shù)

結合公式（19），給出DPSO 算法的適應度函數(shù)的形式：

3.3.2 粒子的速度和位置更新方法

穿梭車任務排序問題屬于整數(shù)組合優(yōu)化問題，DPSO算法重新定義更新公式對粒子進行更新[16]。

（1）置換因子：粒子的位置記為X，置換因子ch(p1,p2)表示交換粒子中p1和p2的位置，由一個或者多個置換因子組成的序列構成置換序列，記為CH=(ch1,ch2,ch3,…,chn)。稱置換因子的數(shù)量為置換序列的復雜度。

（2）加法算子⊕：矩陣與置換序列進行相加表示粒子按照置換序列進行變換。

（3）減法算子：矩陣運算A-B=CH表示粒子A可以通過置換序列CH變換為粒子B，由于粒子A變換到粒子B可以由多個不同的置換序列完成，因此將含有置換因子最少的置換序列作為最簡置換序列CHsim。

（4）乘法算子?：數(shù)字與粒子相乘表示該粒子的每一個元素都乘數(shù)字。

給出粒子的速度和位置更新公式[17]：

其中，ω為慣性權重，c1為自我學習因子，c2為群體學習因子，r1、r2為（0，1）之間的隨機數(shù)，為局部最優(yōu)解，為全局最優(yōu)解。

已知局部最優(yōu)粒子Pid=(p1d,p2d,…,p(n-1)d,pnd) ，隨機生成復雜度為N的置換序列，對該粒子進行置換變異。其中置換因子ch(px,py)，px,py?P*。

置換復雜度能夠很大程度上影響種群的多樣性，較大的置換復雜度能夠?qū)αＷ赢a(chǎn)生很大的擾動，從而增加種群的多樣性，算法能夠在全局范圍內(nèi)尋優(yōu)，避免早熟收斂；隨著置換復雜度的減小，種群多樣性趨于穩(wěn)定，算法收斂速度加快，局部搜索能力增強，粒子逐步向最優(yōu)解靠近。因此，提出使用自適應技術控制置換復雜度，對粒子進行隨機置換。其計算公式如下：

其中，fmin為所有粒子的最小適應度值，favg為所有粒子的平均適應度值。

3.3.4 慣性權重的調(diào)整

采用慣性權重隨迭代次數(shù)減小的策略，使算法獲得較快的收斂速度和良好的搜索性能。

其中，ωmax為初始權重值，ωmin為最終權重值，itermax為最大迭代次數(shù)，iter為當前迭代次數(shù)。

3.4 蟻群-粒子群雙層智能優(yōu)化算法流程

使用蟻群-粒子群雙層智能優(yōu)化算法求解出庫任務調(diào)度問題的步驟如下：

步驟1初始化蟻群、粒子群算法各參數(shù)，iter=0，將生成的螞蟻隨機放入待出庫任務節(jié)點。

步驟2對螞蟻計算狀態(tài)轉(zhuǎn)移概率，選擇下一個出庫任務，并將放入已游歷任務列表中。

步驟3螞蟻游歷完所有待出庫任務節(jié)點，更新信息素；否則返回步驟2。

步驟4蟻群算法達到終止條件，輸出最佳路徑，并將結果輸入粒子群算法，作為初始解；否則返回步驟2。

步驟5在初始解的范圍內(nèi)，隨機生成初始粒子，并計算各粒子適應度值f 。

步驟6比較各粒子的適應度值，更新各粒子局部最優(yōu)值和全局粒子最優(yōu)值。

步驟7更新粒子位置和速度，并根據(jù)3.3.3 小節(jié)中方法對局部最優(yōu)粒子進行隨機變異。

步驟8若達到算法終止條件，輸出任務調(diào)度最優(yōu)解；否則返回步驟5。

算法流程圖如圖4所示。

3.3.3 基于置換復雜度的粒子隨機變異

圖4 蟻群-粒子群雙層智能優(yōu)化算法流程圖

4 算例分析

為了驗證本文提出的模型和算法的有效性，基于某電子商務企業(yè)的真實訂單數(shù)據(jù)，使用MATLAB 軟件進行仿真測試，求解其最優(yōu)的出庫任務調(diào)度方案。

該電商企業(yè)的穿梭車儲分一體系統(tǒng)共有24 個巷道，每個巷道2 400個貨位，其設備運行參數(shù)如表1所示。

表1 設備運行參數(shù)

為驗證本文所提出模型的有效性，選取該系統(tǒng)中10 組出庫任務進行仿真實驗，每組實驗包含50 個出庫任務，部分出庫任務信息在表2 中列出。將仿真結果與本文提出的模型計算結果進行比較，實驗對比如表3所示。

表2 出庫任務信息

表3 仿真實驗與模型計算結果對比

由表中實驗數(shù)據(jù)可知，對50 個出庫任務進行出庫仿真實驗的平均出庫時間為666.44 s，本文所提出模型的計算結果657.75 s，平均誤差為6.84%，可以認為本文所提出的數(shù)學模型能夠較為準確地對穿梭車系統(tǒng)的出庫過程進行描述。

為驗證本文提出的任務調(diào)度優(yōu)化算法的有效性，隨機選取該電商企業(yè)某一時間窗內(nèi)6 組料箱揀選出庫任務數(shù)據(jù)，對出庫任務進行調(diào)度分配，搜索最優(yōu)的出庫任務調(diào)度方案。

在使用蟻群-粒子群雙層智能優(yōu)化算法尋找出庫任務調(diào)度的最優(yōu)出庫方案時，算法參數(shù)采用“三步法”[18]方式進行配置：首先確定算法的種群規(guī)模，即蟻群算法的螞蟻數(shù)和粒子群算法的粒子數(shù)num；粗調(diào)參數(shù)，即對取值范圍較大的信息素權重系數(shù)α、啟發(fā)式信息權重系數(shù)β、學習因子c1和c2參數(shù)等進行調(diào)整；微調(diào)參數(shù)，即對取值范圍較小的信息素揮發(fā)系數(shù)ρ、慣性權重ω等參數(shù)進行調(diào)整。

分別以出庫任務數(shù)量50、100、150進行算法參數(shù)調(diào)整測試，最終參數(shù)取值為：MMAS算法螞蟻個數(shù)Ma/Q=2/3，τmax=1，τmin=0.1，α=1，β=5，ρ=0.9，M=10；DPSO 算法種群規(guī)模num/Q=0.2，ωmax=0.96，ωmin=0.26，c1=0.5，c2=0.7。兩層算法均迭代200次，在CPU為1.80 GHz，運行內(nèi)存8 GB的計算機上進行100次出庫仿真實驗，將實驗結果與標準ACO、DPSO 算法進行比較，三種算法訂單超時率Rovertime、平均超時時間Tovertime以及訂單出庫總時間F(X)的比較結果如表4所示。

表4 仿真實驗結果對比

圖5 為三種算法不同訂單數(shù)量下跨層穿梭車系統(tǒng)料箱揀選出庫作業(yè)任務超時率趨勢圖，包括ACO算法、DPSO算法、MMAS-DPSO算法實驗結果。

圖6 對三種算法在求解穿梭車系統(tǒng)任務調(diào)度方案時的出庫作業(yè)總時間進行了分析，其中對比1 表示MMAS-DPSO 算法對比ACO 算法的出庫效率提升率，對比2 表示MMAS-DPSO 算法相對于DPSO 算法的出庫效率提升率。

對比實驗結果，可以得出以下結論：

圖5 不同訂單數(shù)量下料箱出庫任務超時率

圖6 不同訂單數(shù)量下出庫效率提升對比圖

在加入出庫時限優(yōu)化條件之后，三種算法出庫任務超時率均優(yōu)于未考慮出庫時限時的實驗結果，且MMAS-DPSO的優(yōu)化效果最為明顯。

在求解小規(guī)模訂單任務調(diào)度方案(Q=50)時，三種算法優(yōu)化性能相差較小，任務出庫超時率均在5%左右，MMAS-DPSO算法求解調(diào)度方案任務超時率最低，僅為4%；當訂單規(guī)模持續(xù)增大，ACO算法和DPSO算法所得出的調(diào)度方案訂單超時率急劇增大，Q=300 時，PSO算法超時率增長至20%以上，而MMAS-DPSO算法在求解過程中具有良好的穩(wěn)定性，訂單超時率增幅較小，在Q＜250 時，任務超時率均小于5%。

隨著訂單規(guī)模持續(xù)增大，ACO算法和DPSO算法與MMAS-DPSO 算法求解調(diào)度方案的出庫總時間差值逐漸增大，這是因為ACO 和DPSO 算法均使用訂單隨機平均分配給穿梭車的調(diào)度策略，未對穿梭車跨層距離進行優(yōu)化，穿梭車換層次數(shù)多，從而增加了出庫作業(yè)總時間，其中ACO 算法增幅最大，當Q=200 時，與MMASDPSO算法的出庫時間差值已超過500 s。

MMAS-DPSO 算法在求解跨層穿梭車系統(tǒng)任務調(diào)度的過程中，通過蟻群、粒子群兩層算法對調(diào)度方案進行分步求解，比單一的ACO、DPSO 算法求解所得結果具有更短的出庫時間和更低的訂單超時率，尤其在求解大規(guī)模出庫任務調(diào)度中具有良好的優(yōu)化性能，出庫效率提升10%以上；在粒子群算法中引入出庫任務時限作為尋優(yōu)條件，將訂單之間的相互關系作為優(yōu)化的性能之一，使粒子在更新過程中向著訂單出庫超時最短的調(diào)度方案演變，在Q＜300 時，訂單平均超時率為8.4%，比不考慮任務優(yōu)先級的情況下使用MMAS-DPSO 算法實驗值降低15%以上，調(diào)度方案的合理性更優(yōu)。

5 結束語

本文對跨層穿梭車雙提升機系統(tǒng)進行了建模與優(yōu)化，建立了出庫任務調(diào)度數(shù)學模型，并將出庫任務期限引入任務調(diào)度策略；提出使用改進的蟻群-粒子群雙層智能優(yōu)化算法對任務調(diào)度問題進行求解，通過仿真實驗證明了模型和算法的有效性。最后，將MMAS-DPSO算法與標準ACO 算法、DPSO 算法進行實驗比較，結果表明本文所用算法在求解大規(guī)模出庫任務調(diào)度的問題中具有明顯的優(yōu)勢，得到更為高效的調(diào)度方案，更能適應電商環(huán)境下海量訂單揀選出庫要求，為跨層穿梭車系統(tǒng)的研究和應用提供了借鑒意義。

穿梭車系統(tǒng)在運行過程中，穿梭車同時接收訂單入庫和出庫任務，而本文給出的調(diào)度策略只考慮了出庫任務對穿梭車系統(tǒng)進行單一指令調(diào)度優(yōu)化，進一步的研究可以同時考慮入庫和出庫任務對系統(tǒng)進行雙指令調(diào)度優(yōu)化。