航空貨站自動化存取系統作業調度優化

宋宇博，蔣兆遠，孫秉珍

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

航空貨站自動化存取系統作業調度優化

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

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

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

航空貨站；自動化存取系統；作業調度；雙板作業；死鎖；蟻群算法

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

圖1 ETV作業行程

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

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

1 問題描述

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

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

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

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

圖2 ETV作業路線

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

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

圖3 ETV防沖突避讓類型

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

2 數學模型

2.1 符號定義

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

2.2 調度模型

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

3 算法實現

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

3.1 權重信息素

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

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

3.2 轉移策略的改進

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

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

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

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

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

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

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

3.3 算法仿真步驟

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

圖4 改進蟻群算法流程

4 算例分析

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

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

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

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

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

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

表1 指令序列規模為5的算法對比結果

表2 指令序列規模為6的算法對比結果

表3 指令序列規模為8的算法對比結果

表1～3中改進蟻群算法的10次求解結果中，求得最優解和次優解的次數均超過7次，具有較高的求解精度.

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

表4 不同調度策略的仿真結果

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

5 結 論

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

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

［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，FACCIO 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—），男，教授，博士生導師.

宋宇博，songyubo＠mail.lzjtu.cn.