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

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

?

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

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

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

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

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

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

1 問題描述

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

合理的雙板作業(yè)組合能夠有效縮短指令序列完工時(shí)間，ETV執(zhí)行雙板作業(yè)需滿足如下條件：1) 搬運(yùn)路徑：2條指令為相鄰指令，且2個(gè)待搬運(yùn)的貨物沿巷道方向具有同向且重合的搬運(yùn)路徑；2) 搬運(yùn)順序與裝載方式：當(dāng)2個(gè)貨物同時(shí)裝載到ETV載貨臺(tái)，貨物的搬運(yùn)順序可分為4種，即“先上先下”、“先上后下”、“后上先下”和“后上后下”，貨物的裝載方式可分為2種，即“同側(cè)裝載”和“異側(cè)裝載”。在2個(gè)貨物同時(shí)搬運(yùn)的過程中，搬運(yùn)順序組合對(duì)應(yīng)關(guān)系如表1所示。表1中，若“先下”貨物離開ETV載貨臺(tái)時(shí)不與另一個(gè)貨物干涉，則可以執(zhí)行雙板作業(yè)，按照搬運(yùn)順序和裝載方式的不同組合歸納的雙板作業(yè)條件如表2所示。表2所列4種情況對(duì)應(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ùn)順序組合對(duì)應(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 符號(hào)定義

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

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

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

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

約束條件為

(3)