航空貨站自動(dòng)化存取系統(tǒng)作業(yè)調(diào)度優(yōu)化

宋宇博，蔣兆遠(yuǎn)，孫秉珍

（1.蘭州交通大學(xué)機(jī)電技術(shù)研究所，730070蘭州；2.蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，730070蘭州）

航空貨站自動(dòng)化存取系統(tǒng)作業(yè)調(diào)度優(yōu)化

宋宇博1，蔣兆遠(yuǎn)1，孫秉珍2

（1.蘭州交通大學(xué)機(jī)電技術(shù)研究所，730070蘭州；2.蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，730070蘭州）

為從作業(yè)調(diào)度角度提高航空貨站自動(dòng)化存取系統(tǒng)運(yùn)作效率，在分析雙板作業(yè)和防沖突避讓對(duì)指令序列完工時(shí)間影響的基礎(chǔ)上，以指令序列完工時(shí)間最短為優(yōu)化目標(biāo)，建立了航空貨站自動(dòng)化存取系統(tǒng)調(diào)度優(yōu)化模型，并設(shè)計(jì)了一種改進(jìn)的蟻群算法對(duì)模型進(jìn)行求解.為避免算法在搜索過程中陷入局部最優(yōu)，在引入權(quán)重信息素和隨機(jī)擾動(dòng)策略的基礎(chǔ)上，提出了具有變異率的狀態(tài)轉(zhuǎn)移參數(shù)，用于在尋優(yōu)過程中決定螞蟻的移動(dòng)方向.仿真結(jié)果表明：改進(jìn)的蟻群算法較基本蟻群算法和遺傳算法具有更好的全局搜索能力和求解精度，所提出的調(diào)度優(yōu)化方法獲得的指令序列完工時(shí)間較先到先服務(wù)調(diào)度策略有至少37%的改進(jìn).

航空貨站；自動(dòng)化存取系統(tǒng)；作業(yè)調(diào)度；雙板作業(yè)；死鎖；蟻群算法

隨著航空物流的發(fā)展，航空貨站的規(guī)模和吞吐量不斷擴(kuò)大，建立高效的自動(dòng)化存取系統(tǒng)（automatic storage and retrieval system，AS／RS）對(duì)滿足航空物流地面服務(wù)要求十分必要.多端口出入式AS／RS憑借其高效的出入庫效率多被航空貨站采用，該系統(tǒng)是在多端口出入式貨架系統(tǒng)基礎(chǔ)上配置兩臺(tái)可以雙板作業(yè)的升降式轉(zhuǎn)運(yùn)車（elevation transfer vehicle，ETV）而構(gòu)成的新型自動(dòng)化存取系統(tǒng)，ETV具有雙板作業(yè)能力，一次行程可以同時(shí)存放和取出多個(gè)航空集裝箱（unit load device，ULD），如圖1所示.航空貨站AS／RS與普通AS／RS作業(yè)調(diào)度的優(yōu)化目標(biāo)是一致的，主要是最小化指令序列的完工時(shí)間，提高ULD出入庫效率，但與普通AS／RS相比較，航空貨站AS／RS具有多端口出入庫、雙板作業(yè)、防沖突避讓等作業(yè)特點(diǎn)，其調(diào)度問題更加復(fù)雜.為達(dá)到指令序列完工時(shí)間最小化的目標(biāo)，需在同時(shí)考慮雙板組合和避免死鎖的前提下去選擇分組與排序方案.

圖1 ETV作業(yè)行程

目前，關(guān)于AS／RS調(diào)度問題的研究集中在兩個(gè)方面，分別為基本調(diào)度問題的研究和擴(kuò)展調(diào)度問題的研究.基本調(diào)度問題是在單一作業(yè)模式和復(fù)合作業(yè)模式下，優(yōu)化堆垛機(jī)的作業(yè)過程，實(shí)現(xiàn)總的作業(yè)時(shí)間最短或總的運(yùn)行距離最短.相關(guān)研究有，文獻(xiàn)［1］在單一作業(yè)模式和復(fù)合作業(yè)模式都有效的情況下，對(duì)指令序列完工時(shí)間進(jìn)行了計(jì)算和比較.文獻(xiàn)［2］將單一作業(yè)模式和復(fù)合作業(yè)模式同時(shí)融合在作業(yè)調(diào)度過程中，提出了混合作業(yè)調(diào)度策略，該策略要求堆垛機(jī)在滿足復(fù)合作業(yè)條件時(shí)進(jìn)行復(fù)合作業(yè)，否則執(zhí)行單一作業(yè)，該調(diào)度策略有效地提高了堆垛機(jī)的作業(yè)效率.文獻(xiàn)［3］將AS／RS調(diào)度問題轉(zhuǎn)化為TSP問題，并通過改進(jìn)的遺傳算法進(jìn)行求解.文獻(xiàn)［4］認(rèn)為在一般情況下，給定指令序列的優(yōu)化調(diào)度問題是NP-hard問題，并將問題的復(fù)雜性歸結(jié)為有效的存儲(chǔ)位置隨著入庫指令的占用和出庫指令的騰空在不斷變化，但是在一些特殊情況下，一些排序問題可以在多項(xiàng)式時(shí)間內(nèi)解決.在上述基本調(diào)度問題中加入用戶個(gè)性化的使用需求，便產(chǎn)生了擴(kuò)展的調(diào)度問題.例如文獻(xiàn)［5］研究了存儲(chǔ)位置不確定條件下的調(diào)度優(yōu)化問題，得出了計(jì)算時(shí)間代價(jià)較高的結(jié)論.文獻(xiàn)［6］在存儲(chǔ)位置和出庫位置均不確定的情況下，通過出入庫位置選擇來獲取符合用戶出入庫要求的最佳調(diào)度方案.文獻(xiàn)［7］提出了一個(gè)指令排序的數(shù)學(xué)模型，該模型解決了滿足用戶需求約束的排序優(yōu)化問題.文獻(xiàn)［8］充分利用AS／RS的閑置時(shí)間進(jìn)行托盤預(yù)先部署，將下一個(gè)階段期望被用到的托盤存放在靠近出／入庫端口的位置，以此來減少實(shí)際出庫的運(yùn)行時(shí)間.另一類擴(kuò)展的調(diào)度問題是由于AS／RS結(jié)構(gòu)的不斷創(chuàng)新而產(chǎn)生的，例如多載具堆垛機(jī)的研發(fā)，使堆垛機(jī)在一個(gè)作業(yè)周期內(nèi)可以訪問多個(gè)存儲(chǔ)位置，調(diào)度過程出現(xiàn)了更多的路徑選擇.文獻(xiàn)［9］基于歐洲機(jī)械搬運(yùn)協(xié)會(huì)標(biāo)準(zhǔn)建立了一個(gè)分析模型，用來評(píng)估雙載具AS／RS的作業(yè)時(shí)間.文獻(xiàn)［10］基于類型存儲(chǔ)策略，應(yīng)用遺傳算法對(duì)三載具堆垛機(jī)調(diào)度問題進(jìn)行了求解.文獻(xiàn)［11］將傳統(tǒng)堆垛機(jī)的復(fù)合運(yùn)動(dòng)在水平和垂直方向進(jìn)行了拆分，由多個(gè)水平運(yùn)動(dòng)和垂直運(yùn)動(dòng)的平臺(tái)代替，并設(shè)計(jì)了平臺(tái)作業(yè)調(diào)度算法，適用于具有出庫時(shí)間約束的出庫作業(yè).文獻(xiàn)［12-13］研究了同一巷道內(nèi)兩臺(tái)堆垛機(jī)并行作業(yè)過程中的協(xié)同調(diào)度問題，通過規(guī)劃堆垛機(jī)移動(dòng)軌跡來實(shí)現(xiàn)協(xié)同作業(yè).文獻(xiàn)［14］在文獻(xiàn)［12-13］基礎(chǔ)上提出了一種快速的作業(yè)調(diào)度方法，解決同一巷道內(nèi)多個(gè)堆垛機(jī)的協(xié)同作業(yè).

綜上所述，在已有文獻(xiàn)描述的AS／RS各種作業(yè)調(diào)度問題中，大多數(shù)文獻(xiàn)著重考慮的是同端出入式AS／RS中堆垛機(jī)的調(diào)度優(yōu)化問題，而多端口出入式AS／RS中多個(gè)堆垛設(shè)備的調(diào)度問題幾乎沒有得到關(guān)注.本文將從作業(yè)指令分組和排序兩個(gè)子問題聯(lián)合優(yōu)化的角度，對(duì)具有雙板作業(yè)和防沖突避讓特點(diǎn)的多端口出入式AS／RS雙ETV調(diào)度問題進(jìn)行研究.

1 問題描述

航空貨站AS／RS作業(yè)過程中，到達(dá)的出入庫作業(yè)指令形成指令序列，系統(tǒng)按照指令周期運(yùn)作，每個(gè)周期內(nèi)對(duì)當(dāng)前未執(zhí)行的指令序列進(jìn)行調(diào)度優(yōu)化，其優(yōu)化結(jié)果作為下一指令周期的執(zhí)行方案，指令周期為ETV取下ULD的作業(yè)時(shí)間.航空貨站AS／RS雙ETV調(diào)度優(yōu)化問題可描述為：指令周期內(nèi)，到達(dá)的n條作業(yè)指令｛O1，O2，O3，…，On｝構(gòu)成指令序列O，每條指令的源地址和目的地址已知；n條作業(yè)指令由兩臺(tái)ETV逐條完成；兩臺(tái)ETV共用同一巷道，一臺(tái)ETV不能越過另一臺(tái)ETV進(jìn)行作業(yè)；ETV1能夠訪問全部貨位，ETV2不能訪問指定范圍內(nèi)的貨位；兩臺(tái)ETV并行作業(yè)過程中有安全作業(yè)距離限制；每臺(tái)ETV最多可以同時(shí)裝載兩個(gè)ULD；作業(yè)指令一旦開始執(zhí)行就必須將ULD從源地址搬運(yùn)到目的地址，不能中途卸載；貨架單元格橫縱尺寸均為定值；假設(shè)無論在裝載或空載情況下，ETV在水平和垂直方向均作勻速運(yùn)動(dòng)且速度已知；忽略ETV取貨和存貨耗時(shí).問題是n條作業(yè)指令如何合理地派送給不同的ETV，并為每臺(tái)ETV指派的作業(yè)指令排序，在滿足約束條件的前提下，使得n條作業(yè)指令的完工時(shí)間達(dá)到最小.

作業(yè)指令 i源地址 （Soi，Woi，Hoi）和目的地址（Sdi，Wdi，Hdi）已知的情況下，其完成時(shí)間表示為，其中S為側(cè)方向坐標(biāo)（區(qū)分地址在巷道的那一側(cè)），W為列方向坐標(biāo)，H為層方向坐標(biāo)，P為貨位寬度，Q為貨位高度，Vw為ETV水平方向速度，Vh為ETV垂直方向速度.若指令j為指令i的緊前指令，第k臺(tái)ETV從指令j的目的地址運(yùn)行到指令i的源地址所需時(shí)間為，則單臺(tái) ETV 的 指 令 序 列 完 工 時(shí) 間 為 Tk=，其中 Ok為指派給第 k臺(tái)ETV的作業(yè)指令集合，Yjik= 0，1{ }，取1表示指令j是指令i的緊前作業(yè)指令，否則取0.

當(dāng)指令i、j滿足雙板作業(yè)條件時(shí)，若以雙板作業(yè)的方式完成指令i、j，ETV訪問路徑節(jié)點(diǎn)的路線如圖2（a）所示；若以單板作業(yè)的方式完成指令i、j，ETV訪問路徑節(jié)點(diǎn)的路線有兩種可能，分別如圖2（b）和圖2（c）所示.

由圖2可知，雙板作業(yè)通過合并相鄰指令的重合路徑，消除了單板作業(yè)過程中的空載運(yùn)行路段（指令i目的地址?指令j源地址），有效地縮短了指令序列的完工時(shí)間.圖2（b）、2（c）所示情況下雙板作業(yè)可以節(jié)省時(shí)間分別為

圖2 ETV作業(yè)路線

單臺(tái)ETV的指令序列完工時(shí)間中加入雙板作業(yè)的影響，則轉(zhuǎn) 化 為，其中Ujik= ｛0，1｝，取1表示作業(yè)指令i和j執(zhí)行雙板作業(yè)，否則取0.

雙ETV并行作業(yè)模式下，作業(yè)路徑?jīng)_突是不可避免的，防沖突避讓是避免沖突的有效途徑，根據(jù)避讓方向可將防沖突避讓分為前進(jìn)避讓、后退避讓和等待避讓3種類型，如圖3所示.無論哪種類型的避讓都會(huì)中斷ETV的當(dāng)前作業(yè)進(jìn)程，從中斷當(dāng)前作業(yè)進(jìn)程到恢復(fù)至中斷點(diǎn)繼續(xù)作業(yè)所花費(fèi)的時(shí)間為防沖突避讓時(shí)間，可以表示為其中為避讓開始時(shí)刻，Eaik為避讓結(jié)束時(shí)刻.

圖3 ETV防沖突避讓類型

雙ETV并行作業(yè)模式下，加入防沖突避讓的影響，單臺(tái) ETV的指令序列完工時(shí)間轉(zhuǎn)化為 Tk=其中Zik= {0，1}，取1表示執(zhí)行作業(yè)指令i時(shí)第k臺(tái)ETV執(zhí)行避讓，否則取0.

2 數(shù)學(xué)模型

2.1 符號(hào)定義

ETV集合M，k，k′為 ETV集合索引.第 k臺(tái)ETV在任意時(shí)刻同時(shí)作業(yè)的指令數(shù)量qk.兩臺(tái)ETV之間最小作業(yè)距離l.Xik=｛0，1｝，取1表示作業(yè)指令i分配給第k臺(tái)ETV，否則取0.另外為了建模方便，設(shè)置補(bǔ)充變量 Dijk，Mijk，Nijk和 Gij.Dijk可取0或1，取1表示第k臺(tái)ETV執(zhí)行的兩條相鄰指令i、j，其作業(yè)路徑沿巷道方向同向且有重合，否則取0.Mijk可取0或1，取1表示由第k臺(tái)ETV執(zhí)行的兩條相鄰指令i、j滿足Soj≠Sdi，否則取0.Nijk可取0或1，取1表示指令i、j是由第k臺(tái)ETV執(zhí)行的兩條相鄰指令，且指令j，滿足Soj=Sdj，否則取0.Gij可取0或1，取1表示分別由不同ETV執(zhí)行的兩條作業(yè)指令i和j，其作業(yè)區(qū)域有重合，否則取0.

2.2 調(diào)度模型

機(jī)場(chǎng)貨運(yùn)站AS／RS雙ETV調(diào)度優(yōu)化問題的整數(shù)規(guī)劃模型的目標(biāo)函數(shù)為模型中式（1）為目標(biāo)函數(shù)，表示最小化指令序列的完工時(shí)間，其中表示將花費(fèi)時(shí)間最多的ETV所需的作業(yè)時(shí)間作為指令序列的完工時(shí)間，約束（2）確保每條作業(yè)指令都能由ETV執(zhí)行，約束（3）確保每條作業(yè)指令只能由一臺(tái)ETV執(zhí)行，約束（4）確保分配給ETV的指令按照排列的順序依次執(zhí)行，約束（5）確保在存在ETV調(diào)度死鎖的情況下首先執(zhí)行ETV避讓，再執(zhí)行當(dāng)前作業(yè)指令，當(dāng)出庫指令的目的地址與入庫指令的源地址相同時(shí)，約束（6）確保入庫指令優(yōu)先執(zhí)行，約束（7）確保每臺(tái)ETV最多只能同時(shí)執(zhí)行兩條作業(yè)指令，約束（8）確保指令i，j能夠由第k臺(tái)ETV執(zhí)行雙板作業(yè)，約束（9）確保在作業(yè)過程中，兩個(gè)ETV之間的距離大于等于安全距離l，約束（10）確保源地址或目的地址在指定區(qū)域的出入庫作業(yè)指令由指定的ETV（該ETV能訪問全部貨架地址）執(zhí)行，約束（11）確保任意一條作業(yè)指令最多只能有一條緊后執(zhí)行的作業(yè)指令，約束（12）確保任意一條作業(yè)指令最多只能有一條緊前執(zhí)行的作業(yè)指令.

3 算法實(shí)現(xiàn)

為了避免基本蟻群算法易陷入局部最優(yōu)的弊端，本文在算法尋優(yōu)過程中引入權(quán)重信息素和擾動(dòng)策略，在保障基本蟻群算法確定性選擇的基礎(chǔ)上，增添探索新路徑的概率，來提高算法的全局搜索能力.

3.1 權(quán)重信息素

權(quán)重信息素與普通信息素不同，該信息素用來描述各個(gè)子路徑在最優(yōu)路徑中的權(quán)重，是根據(jù)全局信息進(jìn)行更新.ξij表示指令節(jié)點(diǎn)i到j(luò)的權(quán)重信息素值，該信息素釋放在指令節(jié)點(diǎn)上.與普通信息素的更新規(guī)則不同，權(quán)重信息素不揮發(fā)，也不疊加，其數(shù)值更新在每次螞蟻完成遍歷之后進(jìn)行.假定在當(dāng)前的路徑尋優(yōu)圖中，指令節(jié)點(diǎn)i到j(luò)的權(quán)重信息素值為ξij（t），則按照下式對(duì)權(quán)重信息素進(jìn)行更新，即

由式（13）可知，較長的子路徑可以得到權(quán)重信息素的二次強(qiáng)化，以增加該子路徑被選擇的概率，提高算法的全局收斂性.

3.2 轉(zhuǎn)移策略的改進(jìn)

基本蟻群算法中螞蟻根據(jù)路徑上的信息素殘留值決定移動(dòng)方向，螞蟻k從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的轉(zhuǎn)移概率計(jì)算公式為

式中：τij（t）為t時(shí)刻節(jié)點(diǎn)i到節(jié)點(diǎn)j的信息素殘留值；ηij（t）為τij（t）的倒數(shù)，表示由節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的期望程度；α為螞蟻在路徑選擇過程中殘留信息素的受重視程度；β為螞蟻在路徑選擇過程中啟發(fā)信息所起的作用；Ak為螞蟻k當(dāng)前可以訪問的指令節(jié)點(diǎn)集合.

從基本蟻群算法的轉(zhuǎn)移概率公式可以看出，節(jié)點(diǎn)之間的信息素殘留值越大、時(shí)間越短的路徑對(duì)應(yīng)的轉(zhuǎn)移概率值就越大，被螞蟻選中的概率越大.基于這一選擇思想，將轉(zhuǎn)移概率公式進(jìn)行簡(jiǎn)化，引入更為簡(jiǎn)潔的轉(zhuǎn)移參數(shù)公式為

普通信息素反映的是局部路徑的選擇概率，權(quán)重信息素反映的是全局信息，雖然兩種信息素在螞蟻路徑搜索的過程中都是對(duì)最優(yōu)信息起到正反饋?zhàn)饔?，但是兩者在轉(zhuǎn)移系數(shù)公式中應(yīng)該有不同的啟發(fā)因子.基于轉(zhuǎn)移參數(shù)公式的簡(jiǎn)化思想，式（15）可改進(jìn)為

式中γ為權(quán)重信息素在路徑選擇過程中的受重視程度.

為了避免搜索停滯現(xiàn)象，增加了隨機(jī)擾動(dòng)策略，以一定的概率去探索殘留信息素不是最多的路徑，提高路徑搜索的全局性.同時(shí)為防止最優(yōu)路徑被漏選，對(duì)殘留信息素值最大的路徑單獨(dú)計(jì)算其轉(zhuǎn)移系數(shù).綜上考慮，本文設(shè)計(jì)了具有隨機(jī)變異率的轉(zhuǎn)移參數(shù)，其計(jì)算公式為

式中：pm為隨機(jī)變異率，在區(qū)間（0，1）服從均勻分布的隨機(jī)變量；p1，p2為常數(shù).

3.3 算法仿真步驟

改進(jìn)的蟻群算法求解航空貨站AS／RS雙ETV調(diào)度優(yōu)化模型的基本思路：路徑尋優(yōu)圖由源地址和目的地址構(gòu)成的指令節(jié)點(diǎn)組成（ETV的待命位作為螞蟻的起點(diǎn)），生成等于指令序列規(guī)模兩倍數(shù)量的螞蟻，每組兩只，每只螞蟻代表1個(gè)ETV，從待命位出發(fā)；每只螞蟻在路徑尋優(yōu)圖中未被訪問的節(jié)點(diǎn)中篩選滿足約束（6）、（10）的節(jié)點(diǎn)，作為當(dāng)前螞蟻下一步可以訪問的節(jié)點(diǎn)備選集合；螞蟻在確定下一個(gè)訪問節(jié)點(diǎn)時(shí)，通過式（17）計(jì)算轉(zhuǎn)移參數(shù)，選擇轉(zhuǎn)移參數(shù)值最大的節(jié)點(diǎn)作為當(dāng)前螞蟻的下一個(gè)訪問節(jié)點(diǎn)；每只螞蟻經(jīng)過的節(jié)點(diǎn)代表分配給該ETV的作業(yè)指令，每只螞蟻經(jīng)過節(jié)點(diǎn)的先后順序代表指令執(zhí)行的先后順序，兩只螞蟻遍歷全部節(jié)點(diǎn)形成兩組路徑，該路徑作為ETV的一個(gè)調(diào)度方案，具體流程見圖4.

圖4 改進(jìn)蟻群算法流程

4 算例分析

以國內(nèi)某國際機(jī)場(chǎng)集裝區(qū)AS／RS為例進(jìn)行仿真.該AS／RS配置兩臺(tái)ETV，ETV垂直方向的運(yùn)行速度為0.4 m／s，ETV水平方向的運(yùn)行速度為2 m／s，ETV之間的安全作業(yè)距離為4列列寬，ETV1可以訪問全部地址，ETV2不能訪問貨架第1列至第8列范圍內(nèi)的地址.貨架規(guī)模為2排5層45列，貨位寬度為2.8 m，層高為2.4 m.沿巷道方向設(shè)置23個(gè)出入庫端口，其中空側(cè)13個(gè)，陸側(cè)10個(gè)，作業(yè)指令序列按照要求規(guī)模隨機(jī)生成.仿真工具為MATLAB7.0，運(yùn)算的計(jì)算機(jī)配置：處理器Intel（R）Core（TM）i5＠2.5 GHz，內(nèi)存4.00 GB.算法中最大循環(huán)代數(shù)為200，殘留信息素影響因子α=1，殘留信息素影響因子β=10，權(quán)重信息素影響因子γ= 25，信息素?fù)]發(fā)系數(shù)ρ=0.1，選擇概率p1=1／4，p2= 2／3.

為了驗(yàn)證改進(jìn)的蟻群算法對(duì)航空貨站AS／RS雙ETV調(diào)度問題求解的有效性，將該算法分別與基本蟻群算法和遺傳算法進(jìn)行性能對(duì)比.圖5為不同問題規(guī)模下蟻群算法改進(jìn)前后的優(yōu)化結(jié)果對(duì)比曲線，圖中的指令序列完工時(shí)間為每種問題規(guī)模下10次仿真結(jié)果的平均值.圖6為改進(jìn)蟻群算法與遺傳算法針對(duì)問題規(guī)模為30的指令序列的算法收斂曲線對(duì)比圖.

圖5 蟻群算法改進(jìn)前后對(duì)比

圖6 改進(jìn)蟻群算法與遺傳算法收斂對(duì)比曲線

由圖5、6可見，改進(jìn)的蟻群算法獲得的最優(yōu)解均優(yōu)于基本蟻群算法和遺傳算法，這是由于改進(jìn)蟻群算法中引入了權(quán)重信息素和隨機(jī)擾動(dòng)策略.權(quán)重信息素的引入使信息素的更新通過全局更新和局部更新相結(jié)合的方法進(jìn)行，這種方法不但能增強(qiáng)最優(yōu)信息的正反饋，同時(shí)也在一定程度上抑制停滯現(xiàn)象.另外，隨機(jī)擾動(dòng)策略對(duì)路徑選擇形成干擾，以一定的概率去探索殘留信息素不是最多的路徑，螞蟻對(duì)新路徑的探索概率大大增加，避免了尋優(yōu)過程過早陷入局部最優(yōu).同時(shí)確定性選擇又保證了螞蟻總是選擇轉(zhuǎn)移參數(shù)最大的路徑，保證了改進(jìn)的蟻群算法收斂到全局最優(yōu)解.

在小規(guī)模問題情形下，針對(duì)指令序列規(guī)模為5、6、8分別隨機(jī)生成5組數(shù)據(jù)，每組數(shù)據(jù)采用枚舉算法和改進(jìn)蟻群算法分別求解，仿真結(jié)果如表1～3所示，表中tEA對(duì)應(yīng)數(shù)據(jù)為不同指令序列規(guī)模下枚舉算法得到的指令序列完工時(shí)間，tIACO對(duì)應(yīng)數(shù)據(jù)為不同指令序列規(guī)模下改進(jìn)蟻群算法10次仿真實(shí)驗(yàn)的平均指令序列完工時(shí)間，Nopt為改進(jìn)蟻群算法求得最優(yōu)解和次優(yōu)解的次數(shù).

表1 指令序列規(guī)模為5的算法對(duì)比結(jié)果

表2 指令序列規(guī)模為6的算法對(duì)比結(jié)果

表3 指令序列規(guī)模為8的算法對(duì)比結(jié)果

表1～3中改進(jìn)蟻群算法的10次求解結(jié)果中，求得最優(yōu)解和次優(yōu)解的次數(shù)均超過7次，具有較高的求解精度.

為了驗(yàn)證本文優(yōu)化方法的有效性，仿真對(duì)比了不同指令序列規(guī)模下先到先服務(wù)調(diào)度策略和本文優(yōu)化方法的調(diào)度效果.仿真實(shí)驗(yàn)針對(duì)每種問題規(guī)模下的指令序列均求解10次，結(jié)果如表4所示.表中tFCFS對(duì)應(yīng)數(shù)據(jù)為先到先服務(wù)調(diào)度策略下的平均指令序列完工時(shí)間，tmin為10次仿真中本文優(yōu)化方法得到的最短指令序列完工時(shí)間，tmax為10次仿真中本文優(yōu)化方法得到的最長指令序列完工時(shí)間，tavg為本文優(yōu)化方法10次仿真的平均指令序列完工時(shí)間.

表4 不同調(diào)度策略的仿真結(jié)果

由表4可知，在不同指令序列規(guī)模下，本文的優(yōu)化方法得到的完工時(shí)間均優(yōu)于先到先服務(wù)調(diào)度策略，改進(jìn)率分別為 53.61%、37.35%、40.66%、46.30%、44.48%.先到先服務(wù)調(diào)度策略在作業(yè)調(diào)度過程中同樣需滿足作業(yè)流程約束，符合雙板作業(yè)條件的相鄰指令同樣執(zhí)行雙板作業(yè)，但其調(diào)度過程缺少對(duì)分組結(jié)果的調(diào)配，對(duì)雙板組合方案的對(duì)比，對(duì)調(diào)度死鎖的避讓選擇，對(duì)指派給每臺(tái)ETV的指令排序等方面的集成優(yōu)化，所以導(dǎo)致指令序列完工時(shí)間中包括了大量不合理的ETV避讓時(shí)間和ETV空載運(yùn)行時(shí)間.

5 結(jié) 論

1）在作業(yè)指令源地址和目的地址已知的情況下，研究了具有雙板組合和防沖突避讓特點(diǎn)的航空貨站AS／RS雙ETV調(diào)度優(yōu)化問題.以最小化指令序列完工時(shí)間為優(yōu)化目標(biāo)，建立了航空貨站AS／RS雙ETV調(diào)度整數(shù)規(guī)劃模型，并設(shè)計(jì)了改進(jìn)的蟻群算法進(jìn)行求解.仿真結(jié)果表明，在不同問題規(guī)模下，本文優(yōu)化方法均能獲得較高質(zhì)量的調(diào)度方案，在避免死鎖的同時(shí)能有效縮短ETV的空載運(yùn)行時(shí)間.

2）改進(jìn)蟻群算法中引入了權(quán)重信息素和隨機(jī)擾動(dòng)策略，并對(duì)轉(zhuǎn)移概率公式進(jìn)行了修正，提出了具有變異率的狀態(tài)轉(zhuǎn)移參數(shù)，用于尋優(yōu)過程中決定螞蟻的移動(dòng)方向.仿真結(jié)果表明，改進(jìn)蟻群算法能夠較好地克服過早收斂到局部最優(yōu)的缺點(diǎn)，在相同的循環(huán)代數(shù)下，改進(jìn)的蟻群算法較基本蟻群算法和遺傳算法具有更高的求解精度.

［1］GRAVES S C，HAUSMAN W H，SCHWARZ L B.Storageretrieval interleaving in automatic warehousing systems［J］. Management Science，1977，23（9）：935-945.

［2］EBEN-CHAIME M，PLISKIN N.An integrative model for automatic warehousing systems［J］.International Journal of Computer Integrated Manufacturing，1996，9（4）：286-292.

［3］FANG J F，WANG Y，LEI C L，et al.The way of solving traveling salesman problem the research on scheduling in AS／RS［J］.Procedia Engineering，2011，16：601-607.

［4］HAN M H，MCGINNIS L F，SHIEH J S，et al.On sequencing retrievals in an automated storage／retrieval system［J］.IIE Transactions，1987，19（1）：56-66.

［5］LEE H F，SCHAEFER S K.Retrieval sequencing for unitload automated storage and retrieval systems with multiple openings［J］.International Journal of Production Research，1996，34（10）：2943-2962.

［6］HACHEMI K，SARI Z，GHOUALI N.A step-by-step dual cycle sequencing method for unit-load automated storage and retrievalsystems［J］.Computersand Industrial Engineering，2012，63（4）：980-984.

［7］GAGLIARDI J P，RENAUD J，RUIZ A.On sequencing policiesforunit-load automated storage and retrieval systems［J］.International Journal of Production Research，2014，52（4）：1090-1099.

［8］JAIKUMAR R，SOLOMON M M.Dynamic operational policies in an automated warehouse［J］.IIE Transactions，1990，22（4）：370-376.

［9］AZZI A，BATTINI D，F(xiàn)ACCIO M，et al.Innovative travel time model for dual-shuttle automated storage／retrieval systems［J］.Computers and Industrial Engineering，2011，61（3）：600-607.

［10］POPOVIC D，VIDOVIC M，BJELIC N.Application of genetic algorithms for sequencing of AS／RS with a tripleshuttle module in class-based storage［J］.Flexible Services and Manufacturing Journal，2014，26（3）：432-453.

［11］HU Y H，ZHU Z D，HSU W J.Load shuffling algorithms for split-platform AS／RS［J］.Robotics and Computer-Integrated Manufacturing，2010，26（6）：677-685.

［12］HINO H，KOBAYASHI Y，HIGASHI T，et al.Motion planning method for two stacker cranes in an automated storage and retrieval system［J］.International Journal of Automation Technology，2012，6（6）：792-801.

［13］KUNG Y，KOBAYASHI Y，HIGASHI T，et al.Motion planning of two stacker cranes in a large-scale automated storage／retrieval system ［C］／／IEEE International Conference on Robotics and Biomimetics. Phuket，Thailand：IEEE，2011：168-173.

［14］KUNG Y，KOBAYASHI Y，HIGASHI T，et al.Order scheduling of multiple stacker cranes on common rails in an automated storage／retrievalsystem ［J］. International Journal of Production Research，2014，52（4）：1171-1187.

（編輯 魏希柱）

Job scheduling optimization of automatic storage and retrieval system at air freight station

SONG Yubo1，JIANG Zhaoyuan1，SUN Bingzhen2

（1.Institute of Mechatronic Technology，Lanzhou Jiaotong University，730070 Lanzhou，China；2.School of Traffic and Transportation，Lanzhou Jiaotong University，730070 Lanzhou，China）

To improve the operation efficiency of automatic storage and retrieval system （AS／RS）at air freight station in term of job scheduling，on the basis of analyzing the effect of double unit load device（ULD）transport combination and anti-collision avoidance to the completion time of command sequences，a scheduling optimization model of AS／RS whose objective was to minimize the completion time of command sequences was established，and an improved ant colony algorithm was given to solve this model.To avoid trapping in local optimum in the search process，weight pheromone and random perturbation strategy were introduced.Besides，a state transfer parameter with a mutation probability was proposed to decide the moving direction of ants in the optimization process. Simulation results indicate that comparing with basic ant colony algorithm and genetic algorithm，the improved algorithm has better global search ability and solution precision.In comparison with the first-come-first-served scheduling strategy，the completion time of command sequences obtained by the scheduling optimization method proposed in this paper is improved by 37%at least.

airfreight station；automatic storage and retrieval system；job scheduling；double ULD transport；deadlock；ant colony algorithm

TP391

A

0367-6234（2015）09-0112-07

10.11918／j.issn.0367-6234.2015.09.021

2014-10-16.

國家自然科學(xué)基金（71161016）；國家科技支撐計(jì)劃（2012BAH20F05）；蘭州交通大學(xué)青年基金（2011012）.

宋宇博（1977—），男，講師，博士研究生；蔣兆遠(yuǎn)（1954—），男，教授，博士生導(dǎo)師.

宋宇博，songyubo＠m(xù)ail.lzjtu.cn.