宋宇博，蔣兆遠，孫秉珍

?

多端口出入式自動化存取系統(tǒng)作業(yè)集成優(yōu)化

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

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

為了提高具有雙板作業(yè)運作特點的多端口出入式自動化存取系統(tǒng)(AS/RS)整體作業(yè)效率，在統(tǒng)籌考慮貨位分配和指令序列排序?qū)ψ鳂I(yè)時間影響的基礎(chǔ)上，提出以最小化指令序列完工時間為優(yōu)化目標的集成優(yōu)化模型。引入交換和插入思想構(gòu)建貨位分配和指令排序的搜索鄰域，并分析2種鄰域構(gòu)建方法對指令序列完工時間的影響。最后，設(shè)計二階段禁忌搜索算法對問題進行求解，利用貨位分配和指令排序2個階段禁忌搜索過程的反饋獲得模型最優(yōu)解，其求解過程體現(xiàn)貨位分配和指令排序2個優(yōu)化方面在鄰域搜索過程中互相影響、互相嵌套的復(fù)雜關(guān)系。研究結(jié)果表明：二階段禁忌搜索算法在不同的貨位規(guī)模和指令序列規(guī)模下均能獲得滿意解，具有較好的魯棒性和計算效率；相比“先到先服務(wù)”和“最近鄰”調(diào)度規(guī)則，本文優(yōu)化方法能夠有效縮短指令序列完工時間。

自動化存取系統(tǒng)；多端口出入式；集成優(yōu)化；貨位分配；指令序列排序；雙板作業(yè)

多端口出入式(multiple-I/O points)自動化存取系統(tǒng)(automatic storage and retrieval system, AS/RS)是一種高柔性、高吞吐量的新型倉儲系統(tǒng)。由于該系統(tǒng)配置多個出入庫端口，因此可以并發(fā)執(zhí)行多個出入庫作業(yè)。與同/兩端出入式AS/RS相比，多端口出入式AS/RS可以縮短存取貨行程，增加指令并發(fā)作業(yè)數(shù)量，有效縮短空載運行時間。多端口出入式AS/RS通過升降式轉(zhuǎn)運車(elevation transfer vehicle, ETV)來處理存取貨作業(yè)，ETV在巷道內(nèi)依次訪問作業(yè)指令的源地址和目的地址，通過左右2個獨立控制的載貨臺進行存取貨操作，最多可同時裝載2件貨物。ETV從巷道一端到另一端可以訪問多個出入庫端口以及貨位，執(zhí)行多個作業(yè)任務(wù)，貨位分配和指令執(zhí)行順序具有較強的關(guān)聯(lián)度，單獨優(yōu)化哪方面都很難縮短指令序列完工時間?；谏鲜鎏卣鳎喽丝诔鋈胧紸S/RS作業(yè)優(yōu)化任務(wù)是，從集成優(yōu)化角度考慮貨位分配和指令序列排序，實現(xiàn)指令序列完工時間最小化。在已有文獻中，關(guān)于貨位分配策略的研究多以同端出入式AS/RS為背景，關(guān)注如何尋找符合約束條件的貨物最優(yōu)存放位置，主要考慮貨物流通率、貨物類別以及貨物屬性相關(guān)性等影響因素[1]。KOVáCS等[2]在假定需求概率已知的情況下，通過混合整數(shù)規(guī)劃模型研究了貨位分配問題，最大限度地縮短了作業(yè)時間。柳賽男等[3]同時考慮了貨物周轉(zhuǎn)率和貨架穩(wěn)定性，通過貨品鏈與貨位鏈的耦合關(guān)系進行庫區(qū)分配和貨位分配。MUPPANI等[4]應(yīng)用非線性整數(shù)規(guī)劃模型分析了基于貨物類別的貨位分配策略對存儲空間和物料搬運成本的影響，并與固定貨位分配策略進行了對比。ENE等[5]采用隨機進化算法分兩個階段對基于貨物類別的貨位分配問題、配料問題和作業(yè)路徑規(guī)劃問題進行了研究。GAGLIARDI等[6]對隨機存儲策略、基于類型的存儲策略和基于流通率的存儲策略進行了對比，其研究結(jié)果表明，存儲策略的確定與貨物類型劃分的方法、貨物類型的規(guī)模以及工業(yè)環(huán)境等因素有關(guān)，基于周轉(zhuǎn)率的存儲策略不是適用各種類型AS/RS的最優(yōu)存儲策略。李英德等[7]針對物流配送中心提出了基于貨物屬性相關(guān)性的貨位指派算法?？偟膩碚f，在已有文獻中，多數(shù)學(xué)者研究的是單個出入口的AS/RS貨位分配策略，其他配置類型(例如，多端口出入式AS/RS)的貨位分配策略幾乎沒有涉及。部分關(guān)于AS/RS作業(yè)指令排序的文獻中描述了各種使總/空行駛距離最小化的存取請求處理方法，包括Petri網(wǎng)[8]、遺傳算法[9?10]、模擬退火算法[11]、蟻群算法[12]等，這些方法可應(yīng)用于具有很高的不確定性和很少信息量的情況。此外，這些方法都能夠?qū)W習(xí)和適應(yīng)環(huán)境的變化，優(yōu)化結(jié)果可以由存儲貨位分配、取貨位置選擇、排隊選擇和指令排序組合而成。然而大多數(shù)文獻著重考慮的仍是單個出入口的AS/RS，關(guān)于多端口出入式AS/RS的貨位分配和作業(yè)指令調(diào)度排序的優(yōu)化研究少見涉及。本文作者從集成優(yōu)化的角度對多端口出入式AS/RS貨位分配和指令序列排序進行研究，以最小化指令序列完工時間為目標，建立具有雙板作業(yè)約束條件的集成優(yōu)化數(shù)學(xué)模型，設(shè)計二階段禁忌搜索算法對模型進行求解，通過貨位分配和指令排序2個階段禁忌搜索過程的反饋獲得模型最優(yōu)解。

1 問題描述

多端口出入式AS/RS貨位分配和指令排序集成優(yōu)化問題可描述為：出庫指令源地址、目的地址以及入庫指令的源地址均已確定；空貨位集合是為申請入庫的貨物提供的存儲位置集合，同時約定每個空貨位最多存儲1個貨物；出入庫指令組成作業(yè)指令序列，由ETV逐條執(zhí)行；ETV具有雙板作業(yè)能力，即同時執(zhí)行指令數(shù)小于等于2；作業(yè)指令一旦開始執(zhí)行便不能中斷，即必須將貨物從源地址搬運到目的地址；貨位空閑/占用狀態(tài)已知；貨架單元格橫縱長度為定值；假設(shè)無論在裝載或空載情況下，ETV在水平和垂直方向均做勻速運動且速度已知，忽略ETV取貨和存貨耗時。需解決的問題是：如何確定申請入庫貨物存儲位置分配方案并安排出入庫指令執(zhí)行順序，在滿足約束條件的前提下，使指令序列的完成時間最小。

合理的雙板作業(yè)組合能夠有效縮短指令序列完工時間，ETV執(zhí)行雙板作業(yè)需滿足如下條件：1) 搬運路徑：2條指令為相鄰指令，且2個待搬運的貨物沿巷道方向具有同向且重合的搬運路徑；2) 搬運順序與裝載方式：當(dāng)2個貨物同時裝載到ETV載貨臺，貨物的搬運順序可分為4種，即“先上先下”、“先上后下”、“后上先下”和“后上后下”，貨物的裝載方式可分為2種，即“同側(cè)裝載”和“異側(cè)裝載”。在2個貨物同時搬運的過程中，搬運順序組合對應(yīng)關(guān)系如表1所示。表1中，若“先下”貨物離開ETV載貨臺時不與另一個貨物干涉，則可以執(zhí)行雙板作業(yè)，按照搬運順序和裝載方式的不同組合歸納的雙板作業(yè)條件如表2所示。表2所列4種情況對應(yīng)圖示如圖1所示。滿足條件1)和條件2)的2條作業(yè)指令可由ETV執(zhí)行雙板作業(yè)。2條指令是否滿足雙板作業(yè)條件由來描述，=1表示滿足雙板作業(yè)條件，=0表示不滿足雙板作業(yè)條件。

(a) 同側(cè)裝載，先上先下；(b) 異側(cè)裝載，先上先下；(c) 同側(cè)裝載，后上先下；(d) 異側(cè)裝載，后上先下

表1 搬運順序組合對應(yīng)關(guān)系

Table 1 Corresponding relationship of transport sequence combination

表2 雙板作業(yè)條件

Table 2 Double cargo transport conditions

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

2.1 符號定義

貨位分配涉及到的集合有入庫作業(yè)指令集合和空貨位集合，分別表示為s和e，指令序列排序涉及到的集合有出入庫指令序列集合a，s與a中的元素有所區(qū)別，s中的指令′和′只有源地址，沒有目的地址，a中的指令和既有源地址又有目的地址。c為ETV完成全部作業(yè)指令所需時間；若T為作業(yè)指令執(zhí)行時間，B為指令開始作業(yè)時間，E為指令結(jié)束作業(yè)時間，則有T=E?B；作業(yè)指令的執(zhí)行時間T=E?B，其中B為指令開始作業(yè)時間，E為指令結(jié)束作業(yè)時間。T為指令執(zhí)行準備時間，即ETV從前1條指令的目的地址移動到當(dāng)前指令的源地址所需時間，T=B?E，對指令序列當(dāng)中的第1條指令而言，T為ETV從待命位移動到第1條指令源地址所用時間。(di，di，di)為指令的目的地址，其中di，di和di分別為指令的目的地址的側(cè)方向坐標、列方向坐標和層方向坐標；(oj，oj，oj)為指令的源地址，oj，oj和oj分別為指令的源地址的側(cè)方向坐標、列方向坐標和層方向坐標。q為ETV執(zhí)行指令之后，后續(xù)指令未執(zhí)行之前載貨臺載貨數(shù)量。為貨位寬度；為貨位高度。w為ETV列方向速度；h為ETV層方向速度。作業(yè)指令開始時間B和結(jié)束時間E均采用相對時間，ETV完成單條指令所需作業(yè)時間表示為

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

上述問題屬于集成優(yōu)化問題，涉及到貨位分配和指令序列排序2個方面的優(yōu)化內(nèi)容，該問題可以抽象為下述整數(shù)規(guī)劃模型。在貨位分配階段以ETV作業(yè)時間最短為優(yōu)化目標，考慮雙板作業(yè)的約束條件，確定入庫貨物貨位分配方案；在指令序列排序階段，待存貨地址確定后，指令執(zhí)行順序的確定即轉(zhuǎn)化為多起點多終點的車輛路徑規(guī)劃問題(vehicle routing problems，VRP)。VRP問題已經(jīng)被證明是NP?hard問題，本文模型中空貨位備選集合的規(guī)模較VRP更大且更復(fù)雜，ETV訪問地址順序規(guī)劃需考慮地址訪問的可行性、雙板作業(yè)條件等因素，其約束條件比VRP模型更嚴格。

該數(shù)學(xué)模型的目標函數(shù)為

約束條件為

(3)