宋宇博，蔣兆遠，孫秉珍

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

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

宋宇博1，蔣兆遠1，孫秉珍2

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

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

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

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

圖1 ETV作業(yè)行程

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

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

1 問題描述

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

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

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

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

圖2 ETV作業(yè)路線

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

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

圖3 ETV防沖突避讓類型

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

2 數(shù)學模型

2.1 符號定義

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

2.2 調(diào)度模型

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

3 算法實現(xiàn)

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

3.1 權(quán)重信息素

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

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

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

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

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

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

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

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

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

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

3.3 算法仿真步驟

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

圖4 改進蟻群算法流程

4 算例分析

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

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

圖5 蟻群算法改進前后對比

圖6 改進蟻群算法與遺傳算法收斂對比曲線

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

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

［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.

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

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

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