于巧玉，吳耀華，王艷艷

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

1 引言

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

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

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

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

2 問題描述與分析

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

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

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

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

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

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

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

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

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

（1）每個出庫任務(wù)對應(yīng)的料箱貨位信息和穿梭車編號唯一。

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

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

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

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

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

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

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

其中：

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

2.2.2 動力學分析

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

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

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

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

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

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

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

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

2.2.3 穿梭車等待時間

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

（1）等待換層提升機服務(wù)響應(yīng)時間

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

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

（2）等待貨物提升機服務(wù)響應(yīng)時間

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

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

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

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

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

約束條件為：

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

2.3.2 料箱揀選任務(wù)超時時間

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 蟻群算法設(shè)計

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

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

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

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

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

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

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

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 粒子群算法設(shè)計

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

3.3.1 適應(yīng)度函數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法流程圖如圖4所示。

3.3.3 基于置換復(fù)雜度的粒子隨機變異

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

4 算例分析

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

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

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

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

表2 出庫任務(wù)信息

表3 仿真實驗與模型計算結(jié)果對比

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

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

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

分別以出庫任務(wù)數(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次出庫仿真實驗，將實驗結(jié)果與標準ACO、DPSO 算法進行比較，三種算法訂單超時率Rovertime、平均超時時間Tovertime以及訂單出庫總時間F(X)的比較結(jié)果如表4所示。

表4 仿真實驗結(jié)果對比

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

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

對比實驗結(jié)果，可以得出以下結(jié)論：

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

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

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

在求解小規(guī)模訂單任務(wù)調(diào)度方案(Q=50)時，三種算法優(yōu)化性能相差較小，任務(wù)出庫超時率均在5%左右，MMAS-DPSO算法求解調(diào)度方案任務(wù)超時率最低，僅為4%；當訂單規(guī)模持續(xù)增大，ACO算法和DPSO算法所得出的調(diào)度方案訂單超時率急劇增大，Q=300 時，PSO算法超時率增長至20%以上，而MMAS-DPSO算法在求解過程中具有良好的穩(wěn)定性，訂單超時率增幅較小，在Q＜250 時，任務(wù)超時率均小于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)任務(wù)調(diào)度的過程中，通過蟻群、粒子群兩層算法對調(diào)度方案進行分步求解，比單一的ACO、DPSO 算法求解所得結(jié)果具有更短的出庫時間和更低的訂單超時率，尤其在求解大規(guī)模出庫任務(wù)調(diào)度中具有良好的優(yōu)化性能，出庫效率提升10%以上；在粒子群算法中引入出庫任務(wù)時限作為尋優(yōu)條件，將訂單之間的相互關(guān)系作為優(yōu)化的性能之一，使粒子在更新過程中向著訂單出庫超時最短的調(diào)度方案演變，在Q＜300 時，訂單平均超時率為8.4%，比不考慮任務(wù)優(yōu)先級的情況下使用MMAS-DPSO 算法實驗值降低15%以上，調(diào)度方案的合理性更優(yōu)。

5 結(jié)束語

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

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