楊 朋，繆立新，秦 磊

（清華大學深圳研究生院現(xiàn)代物流研究中心，廣東 深圳 518055）

0 引言

多載具（multi－shuttle）自動化存取系統(tǒng)（Automated Storage and Retrieval System，AS／RS）是一種高吞吐量高柔性的新型倉儲系統(tǒng)，多載具AS／RS堆垛機一次行程可以同時存放和取出多個貨物單元。與單載具AS／RS相比，多載具AS／RS能夠有效縮短無效空載時間，提高存取貨作業(yè)效率，在當今多品種小批量的制造配送環(huán)境下具有較大的應用潛力，正得到越來越多的倉庫及配送中心的關注和應用。

多載具AS／RS按照作業(yè)周期（operation cycle）模式來處理存取貨作業(yè)，一個作業(yè)周期就是多載具堆垛機的一個子行程，該子行程從進出貨口（I／O point）裝載著待存貨物出發(fā)，分別訪問對應的存貨貨位和取貨貨位，然后載著取出的貨物返回進出貨口?；谶@一特點，多載具AS／RS存取貨作業(yè)調度優(yōu)化的關鍵就是如何將存取貨作業(yè)按照作業(yè)周期合理分組。

目前，有關多載具AS／RS的研究集中在績效評價、貨位分配和存取貨作業(yè)排序?？冃гu價方面主要通過推導行程時間模型，對雙載具（doubleshuttle）AS／RS與單載具 AS／RS［1－4］、三載具（triple－shuttle）AS／RS與單載具 AS／RS［5］的績效進行對比分析。也有文獻通過仿真分析方法對多載具AS／RS的績效進行評價［6－7］。貨位分配多關注不同情形下貨位分配模型及求解算法的設計研究。文獻［8］抽象建立了多載具AS／RS存取貨位分配的數(shù)學模型，并設計了基于修正最近鄰點策略的遺傳算法求解模型。文獻［9］提出了考慮作業(yè)路徑的多載具AS／RS貨位分配優(yōu)化問題的建模和求解方法，并設計了兩階段禁忌搜索算法來獲得單作業(yè)周期下的貨位分配方案。文獻［10］則從應用成本的角度分析了雙載具AS／RS貨位分配策略的選擇。存取貨作業(yè)排序方面，文獻［11］將給定存取貨位的多載具AS／RS存取作業(yè)排序歸納為有載貨量限制的車輛路徑問題（Capacitated Vehicle Routing Problems，CVRP），并開發(fā)了對應的精確算法對相應的線性松弛模型進行求解。文獻［12］延續(xù)了文獻［11］的研究，將禁忌算法與前述精確算法結合起來，改進了模型的下界。文獻［13］則在文獻［11］和文獻［12］的基礎上開發(fā)了基于拉格朗日松弛方法的精確算法對問題進行求解。另外，有些倉庫和配送中心中補貨操作（存貨）和貨物消耗作業(yè)（取貨）通常發(fā)生在不同的班次，文獻［14］針對這一情況，研究提出了基于班次的雙載具AS／RS作業(yè)排序方法，以提高吞吐量。

已有研究中，文獻［11－13］涉及多載具 AS／RS存取貨作業(yè)調度問題，但是只從存取貨作業(yè)排序角度進行了探討。對存取貨作業(yè)進行合理分組是多載具AS／RS存取貨作業(yè)調度優(yōu)化的關鍵。由于存在存貨和取貨兩種類型作業(yè)，對作業(yè)的分組需要考慮作業(yè)分解和作業(yè)配對問題，另外每個作業(yè)周期內需要處理多個作業(yè)，考慮多載具載貨量的限制，處理作業(yè)的順序也會有相應約束。文獻［11－13］忽略了作業(yè)分解和作業(yè)配對的影響，具有一定的局限性。本文將從作業(yè)分解、作業(yè)配對和作業(yè)排序三個子問題聯(lián)合優(yōu)化的角度對多載具AS／RS作業(yè)調度進行研究，最小化多載具AS／RS完成存取貨作業(yè)的總行程時間，以更加接近作業(yè)實際的角度來提高存取作業(yè)效率。

1 問題描述

n載具自動化存取系統(tǒng)下，存取貨作業(yè)需要通過配對分組，由堆垛機的多個子行程來依次處理，每個子行程對應一個作業(yè)周期。一個作業(yè)周期可同時處理小于等于n個存貨作業(yè)和小于等于n個取貨作業(yè)。為提高多載具AS／RS的利用率，在存取貨作業(yè)充足的情況下，每個作業(yè)周期往往“滿載”即對應處理n個存貨作業(yè)和n個取貨作業(yè)。多載具AS／RS作業(yè)調度優(yōu)化的目的，就是尋找最優(yōu)的作業(yè)分組方案，使得完成作業(yè)的總行程時間最短。

多載具AS／RS存取作業(yè)調度問題（Storage／Retrieval Scheduling Problem，SRSP）中，假設V＝｛1，2，…，M，M＋1，…，2 M｝為存取貨作業(yè)集合，其中Vs＝｛1，2，…，M｝為存貨作業(yè)集合，Vr＝｛M＋1，…，2 M｝為取貨作業(yè)集合，｛0｝代表進出貨口。M＝nm，其中n為載具數(shù)量，m為完成存取作業(yè)所需的作業(yè)周期數(shù)量。SRSP目標函數(shù)是尋找總行程時間最短的作業(yè)周期集合劃分方案，作業(yè)周期集合中，每個作業(yè)周期對應一個子行程，該子行程從進出貨口出發(fā)，按照順序執(zhí)行完n個存貨作業(yè)和n個取貨作業(yè)后再返回進出貨口，而且為了滿足堆垛機載貨量的限制，行程中任意時刻已完成的存貨作業(yè)都必須大于或等于已完成的取貨作業(yè)。

考慮單元貨物型（unit load）多載具AS／RS，堆垛機裝載相應貨物單元在既定貨位和進出貨口之間移動，完成存取貨作業(yè)。研究中做以下假設：貨物采用固定存儲策略（dedicated storage）存放；給定時間段內的存取貨作業(yè)已知，且對應的貨位信息已知；多載具堆垛機可以同時在垂直和水平方向移動，速度是恒定值，兩個貨架貨位間的時間距離采用切比雪夫距離，且滿足三角不等式（triangle inequality）關系；貨物裝卸時間忽略不計。

采用無向圖G＝｛V′，E｝來描述作業(yè)的集合及作業(yè)對應貨位之間可能的連接，其中V′＝｛0｝∪V，V ＝Vs∪Vr，E＝ ｛（i，j）｜i，j∈V｝。約定如下符號：dij為貨位i和貨位j的行程時間間距（i，j＝0，1，…，2 M），即先后執(zhí)行作業(yè)i，j的行程時間，dij＝dji；xij為決策變量，xij＝1表示子行程中包含i直接到j的路徑，否則xij＝0。另外，為了表達作業(yè)的集合劃分及作業(yè)的訪問順序，增加3下標索引的決策變量zilk，若作業(yè)i作為第k個子行程中的第l個點被訪問到，則zilk＝1，否則zilk＝0。多載具AS／RS存取作業(yè)調度問題可建模如下：

存取作業(yè)調度的整數(shù)規(guī)則問題（SRSP Integer Programming problem，SRSP－IP）的目標函數(shù)為

其中：約束（2）確保每個作業(yè)對應的貨位都會被訪問到；約束（3）表示每個子行程中的每個順序位都會指派貨位進行訪問；約束（4）確保每個子行程會執(zhí)行n個存貨作業(yè)，即訪問n個存貨貨位；約束（5）確保每個子行程同時會執(zhí)行n個取貨作業(yè)，即訪問n個取貨貨位；約束（6）是多載具堆垛機載貨量限制約束，即任何時刻，行程中已完成的存貨作業(yè)數(shù)量大于或等于已完成的取貨作業(yè)數(shù)量；約束（7）確保當xij＝0時vi和vj不會在子行程中順次被訪問，當xij＝1時vi和vj才有可能在在子行程中順次被訪問到；約束（8）和約束（9）確保每個子行程從進出貨口出發(fā)，并最終回到進出貨口；約束（10）表示決策變量為0－1變量。

SRSP－IP模型決策變量數(shù)為O（M2），約束數(shù)量為O（M3），該0－1規(guī)劃問題規(guī)模隨M的增加會急劇膨脹。為便于分析問題的復雜度，以子行程的選擇為決策變量對SRSP－IP模型進行轉化。

SRSP－IP可看作在全體可行子行程集合中，所選出的最優(yōu)的m個子行程能夠覆蓋所有的存取貨作業(yè)，且行程時間最短。約定如下符號：Ω為所有可行子行程的索引集合，cr為完成第r個子行程所需的行程時間，W＝（wir）為“作業(yè)—行程”矩陣，W∈ ｛0，1｝V×Ω，其中wir＝1表示作業(yè)i在第r個行程被執(zhí)行，否則wir＝0。決策變量為yr，yr＝1表示選擇第r個子行程，否則yr＝0。以子行程的選擇為決策變量的模型可表示如下：

行程選擇的整數(shù)規(guī)劃問題（Routing Selection Integer Programming problem，RS－IP）的目標函數(shù)為

其中：約束（12）保證每個作業(yè)都會被執(zhí)行，即每個作業(yè)對應的貨位都會被訪問到；約束（13）確保被選中的子行程數(shù)量為m。

2 問題復雜度分析

由于涉及作業(yè)分解、作業(yè)配對和作業(yè)排序三個問題，多載具AS／RS存取作業(yè)調度優(yōu)化問題的解空間規(guī)模可由三類問題組合數(shù)的乘積求得。其中將

M個作業(yè)進行分解，每組劃分n個作業(yè)，這種分組的組合數(shù)可表示為

為保證堆垛機行程中不超過載貨限制，任一可行的子行程都需滿足任意時刻已完成的存貨作業(yè)都必須大于或等于已完成的取貨作業(yè)。基于此，可行子行程的數(shù)量可以通過以n為變量的卡特蘭數(shù)Cn來計算獲得：

根據(jù)計算復雜性理論，為研究優(yōu)化問題的計算復雜性，首先需要將優(yōu)化問題轉化為判定問題（decision problem）［15］。第1章已給出RS－IP問題的優(yōu)化問題形式，其對應的判定問題定義如下：

（1）參數(shù) Z＋為正整數(shù)集合。

（2）實例 存取貨作業(yè)集合V共有2M個元素，其中有M個存貨作業(yè)，M個取貨作業(yè)，M＝nm。F為集合V的子集族（即子集的集合），F(xiàn)中的每個元素Si（i＝1，2，…，H）為包含n個存貨作業(yè)和n個取貨作業(yè)的子集，即對應一個可行子行程，每個元素Si關聯(lián)一個行程時間ci，ci∈Z＋。給定一個數(shù)C∈Z＋。

（3）問題 是否存在子集F′?F，滿足存取作業(yè)集合V中的每個作業(yè)都只精確分布在F′的一個元素中，且滿足

證明RS－IP的判定問題為非確定多項式困難（Non－deterministic Polynomial hard，NP－h(huán)ard）問題，可分為以下幾步：

定理1 RS－IP問題為NP－h(huán)ard。

證明

（1）選擇一個已

知的NP－h(huán)ard問題或 NP－complete問題

精確匹配（Exact Cover，EC）問題是一個已知的 NP－complete［16］。EC 問 題 的 判 定 問 題 定 義如下：

1）實例 給定有限集合V和集合V的子集族F。

2）問題 是否存在子集F′?F，滿足集合V中的每個元素都只精確分布在F′的一個子集元素中。

為便于理解，給出EC問題的一個數(shù)值實例V＝ ｛1，2，3，4，5，6｝，F(xiàn) ＝ ｛｛1，4｝，｛2，4｝，｛3，5｝，｛3，6｝，｛1，5｝，｛3，4｝｝。上述EC問題的答案為“是”，可取F的子集F′＝ ｛｛2，4｝，｛3，6｝，｛1，5｝｝，滿足集合V中的每個元素都只精確分布在F′的一個子集元素中。

（2）將EC問題多項式歸約為RS－IP問題

給定存取貨作業(yè)集合V，集合V共有2 M個元素，其中有M個存貨作業(yè)，M個取貨作業(yè)，M＝nm。F為集合V的子集族，F(xiàn)中的每個元素Si（i＝1，2，…，H）為包含n個存貨作業(yè)和n個取貨作業(yè)的子集。假設存在子集F′?F，滿足存取作業(yè)集合V中的每個作業(yè)都只精確分布在F′的一個元素中，＝m。基于F′構造RS－IP問題，約定

且取C＝m。不難看出，在子集族F中，行程時間最短的子集為F′，且行程時間不超過m，如果在F′之外選擇元素，則其行程時間將至少為m＋1。顯然，基于F′構造RS－IP問題的時間為多項式時間。因此EC問題可多項式歸約為RS－IP問題。

（3）將RS－IP問題歸約為EC問題

顯然滿足。

（4）驗證RS－IP是否是NP問題

給定RS－IP問題的子行程集合，驗證該子行程集合是否能夠覆蓋每一個作業(yè)需O（Ω ）的時間，驗證對應的行程時間總和是否不超過C需要O（Ω ）的時間。Ω ＝s（M，n），由式（18）計算得到，它與M成階乘關系，不能在多項式時間內驗證子行程集合的可行性。因此不能判斷RS－IP是否為NP－h(huán)ard。

綜上，RS－IP問題為NP－h(huán)ard，定理得證。

3 算法求解

通過第2章的分析得知多載具AS／RS作業(yè)調度問題是NP－h(huán)ard，本章設計遺傳模擬退火的啟發(fā)式算法對問題進行求解。遺傳算法是借鑒生物進化規(guī)律演化而來的計算技術，強調的是兩代之間的進化關系，但其交配有可能丟失最優(yōu)解，易陷入局部極小。模擬退火算法是基于物理中固體物質的退火過程，從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，結合概率突跳特性，在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解。將模擬退火的思想融入遺傳算法，構成遺傳模擬退火算法，通過種群操作自動獲取和調整優(yōu)化的搜索空間，根據(jù)溫度變化調整適應函數(shù)的加速特性，比遺傳算法具有更大的選擇范圍，可以有效避免局部極小。遺傳模擬退火算法的設計與具體問題關聯(lián)密切，下面對求解多載具AS／RS的遺傳模擬退火算法的關鍵技術進行說明，然后給出算法流程。

染色體編碼方面，本文采用存取貨作業(yè)排序的編碼方式，且需要滿足堆垛機載貨量限制的約束條件。例如m＝2，n＝3，Vs＝｛1，2，3，4，5，6｝為存貨作業(yè)集合，Vr＝｛7，8，9，10，11，12｝為取貨作業(yè)集合，一個可行的染色體編碼示意如圖1所示。

初始種群根據(jù)編碼結構，按照滿足堆垛機載貨量限制的約束規(guī)則（任意時刻已完成的存貨作業(yè)必須大于或等于已完成的取貨作業(yè)）隨機生成。初始種群中的染色體可按以下步驟生成：

步驟1 初始化已完成的存貨作業(yè)數(shù)量Cur＿storage＝0，已完成的取貨作業(yè)數(shù)量Cur＿retrieval＝0，已完成的子行程數(shù)量Num＿tour＝1，子行程內作業(yè)的索引index＝1，Vs，Vr，m和n分別為存貨作業(yè)集合、取貨作業(yè)集合、子行程數(shù)和載具數(shù)。數(shù)組Chrom代表染色體，索引i＝1。

步驟2 如果index＝2×n＋1，Num＿tour＝Num＿tour＋1，index＝1；否則轉步驟4。

步驟3 如果Num＿tour＝m＋1，則結束；否則轉步驟4。

步驟4 如果Cur＿storage＝Cur＿retrieval，則從Vs隨機選取作業(yè)k，Chrom（i）＝k，Vs＝Vs－｛k｝，Cur＿storage＝Cur＿storage＋1，i＝i＋1；否則從Vs∪Vr中隨機選取作業(yè)k，Chrom（i）＝k，i＝i＋1，如果k∈Vs，則Vs＝Vs－｛k｝，Cur＿storage＝Cur＿storage＋1，否則Vr＝Vr－｛k｝，Cur＿retrieval＝Cur＿retrieval＋1。

步驟5 index＝index＋1，轉步驟2。

考慮到計算代價及后續(xù)選擇交配操作的方便性，種群規(guī)模取編碼長度的2或4等偶數(shù)倍。結合模擬退火和輪盤賭的方法對種群進行選擇操作。交叉操作采用部分匹配交叉方法，先隨機產生兩個交叉點，定義兩個點之間的部分為匹配區(qū)域，將兩個父串的匹配區(qū)域交叉（如圖2），然后再遍歷重復，根據(jù)匹配區(qū)域內的位置映射關系逐一進行交換，最后再進行子串解的可行性檢查。

為避免早熟，增加遍歷性，算法在個體染色體中隨機選取兩個交叉位進行交換變異，為保證個體為可行解，隨機選取兩個交叉位對應的作業(yè)應同屬一種類型的作業(yè)集合，如同屬存貨作業(yè)集合或同屬取貨作業(yè)集合。算法流程如下：

步驟1 給定種群規(guī)模MAXPOP，k＝0；初始溫度tk＝t0，種群POP（k）。

步驟2 若k達到最大種群迭代次數(shù)MaxIteration，則停止計算；否則，對種群POP（k）中每一個染色體i∈POP（k）的鄰域隨機選狀態(tài)j∈N（i）（染色體的鄰域采用在保證解可行的前提下隨機交換兩個作業(yè)點的方法生成），計算Δfij＝f（j）－f（i），其中f（i）為狀態(tài)i的目標值。若Δfij≤0，則接受j，否則若exp（－Δfij／tk）＞random（0，1）則接受j，否則拒絕j。重復這一過程，選出新種群NewPOP1（k＋1）。

步驟3 在NewPOP1（k＋1）中計算適應度函數(shù)fi（tk）＝exp（－（f（i）－fmin）／tk），其中fmin是NewPOP1（k＋1）中的最小值，按照輪盤賭方法由適應度函數(shù)決定的概率分布，從NewPOP1（k＋1）中隨機選MAXPOP個染色體，形成種群New－POP2（k＋1）。

步驟4 按遺傳算法方法對NewPOP2（k＋1）進行交配，得到CrossPOP（k＋1），再變異得到MutPOP（k＋1）。

步驟5 tk＋1＝0.8tk，k＝k＋1，POP（k）＝Mut－POP（k＋1），轉步驟2。

4 數(shù)值實驗

為評價算法性能，設計一系列具有不同參數(shù)場景的問題進行數(shù)值實驗。設W和H 分別為貨架的長度和高度，堆垛機水平方向的速度和垂直方向的速度分別為vx和vy，堆垛機分別在水平方向和垂直方向遍歷整個貨架所需的行程時間為th＝W／vx和tv＝H／vy。設Z＝max｛th，tv｝，b＝min｛th／Z，tv／Z｝分別表示遍歷貨架所需的行程時間和貨架形狀因子?？紤]到通用性，設Z＝1，對貨架比例進行歸一化。每個貨位關聯(lián)一對水平行程時間和垂直行程時間（hk，vk），任意兩個貨位間的行程時間為

式中Δ為足夠大的正數(shù)。

具體的參數(shù)場景設置為：載具數(shù)量n＝2，3，4；貨架形狀因子b＝0.2，0.4，0.6，0.8，1；作業(yè)周期（子行程）數(shù)量m＝1，2，3，4。每個貨位關聯(lián)一對水平行程時間和垂直行程時間（hk，vk），hk和vk分別按照正態(tài)分布U（0，1）和U（0，b）隨機生成。啟發(fā)式算法采用 MATLAB 7.1軟件來編程實現(xiàn)，采用CPLEX 12.2軟件求解問題的最優(yōu)解。數(shù)值實驗在AMD 2.30GHz CPU和1GHz內存的個人計算機環(huán)境下運行。

表1給出了不同貨架形狀因子（b＝0.2，0.4，0.6，0.8，1）情況下，遺傳算法和本文所提遺傳模擬退火算法在求解中小規(guī)模問題（n＝2，m＝3）下的精確度和計算效率，也給出了采用CPLEX求解最優(yōu)解的計算時間。每個實驗場景隨機生成10組數(shù)據(jù)，分別記錄兩種算法求得的最優(yōu)解數(shù)量（Num＿opt）和與最優(yōu)解之間的偏差。從實驗結果可見，遺傳模擬退火算法在不同貨架形狀因子下對遺傳算法都具有較大的改進，算法的精確度和計算時間受貨架形狀因子b的影響微小，不具有顯著的敏感度。

表2給出了貨架形狀因子固定時，遺傳算法和本文所提遺傳模擬退火算法在求解中小規(guī)模問題下的精確度和計算效率，同時給出了CPLEX求解最優(yōu)解的計算時間。同樣地，每個實驗場景隨機生成10組數(shù)據(jù)，分別記錄兩種算法求得的最優(yōu)解數(shù)量（Num＿opt）和與最優(yōu)解之間的偏差?？梢姡趩栴}規(guī)模變大時，CPLEX求解最優(yōu)解的計算時間急劇增加。在計算結果的質量方面，遺傳模擬退火算法對遺傳算法具有較大的改進，與最優(yōu)解的偏差為0%～0.83%，具有較穩(wěn)定的精確度。隨著問題規(guī)模的增大，遺傳模擬退火算法的計算時間隨之增加，但都在10s以內，具有較高的求解效率。

在大規(guī)模問題情形下（m≥5），本文比較了遺傳算法和本文所提遺傳模擬退火算法的計算結果質量和計算時間。同樣，每個實驗場景隨機生成10組數(shù)據(jù)，表3記錄了采用兩種算法所獲得的平均行程時間和平均耗費的計算時間。從實驗結果可見，遺傳模擬退火算法耗費的計算時間稍高于遺傳算法，但計算結果質量均優(yōu)于遺傳算法，根據(jù)問題規(guī)模的不同，計算結果有2%～17%的改進。

表1 不同貨架形狀因子情況下的算法性能分析（n＝2，m＝3）

表2 不同問題規(guī)模情況下的算法性能分析（b＝0.8）

表3 大規(guī)模問題情況下的算法性能分析（b＝0.8）

5 結束語

本文在多載具AS／RS存取貨作業(yè)排序研究的基礎上，增加考慮了作業(yè)分解和作業(yè)配對的影響。從作業(yè)分解、作業(yè)配對和作業(yè)排序三個子問題聯(lián)合優(yōu)化的角度，探討了多載具AS／RS的作業(yè)調度優(yōu)化問題。對問題的復雜度進行了分析，證明了問題為NP－h(huán)ard，設計了遺傳模擬退火算法對問題進行求解。通過數(shù)值實驗驗證了算法的有效性，實驗結果表明在不同規(guī)模問題下，算法都能夠在合理的時間內獲得高質量的調度方案，從而有效縮短了完成存取貨作業(yè)的行程時間。算法具有較好的精確度和求解效率，而且算法的性能對貨架形狀因子參數(shù)不敏感。下一步研究可以考慮貨位分配和貨物停留時間因素影響，在共享貨位存儲策略下，按照貨物停留時間精確地調度每個指令的貨位分配及作業(yè)順序，以保證在指令執(zhí)行不發(fā)生干涉的前提下達到行程時間最短的優(yōu)化目的。

［1］ SARKER 段 ，SABAPATHY A，LAL S B，et al.Performance evaluation of a double shuttle automated storage and retrieval system［J］.Production Planning ＆Control：The Management of Operations，1991，2（3）：207－213.

［2］ KESERLA A，PETERS 段 .Analysis of dual－shuttle automated storage／retrieval systems［J］.Journal of Manufacturing Systems，1994，13（6）：424－434.

［3］ MALMBORG 段 .Interleaving models for the analysis of twin shuttle automated storage and retrieval systems［J］.International Journal of Production Research，2000，38（18）：4599－4610.

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

［5］ MELLER 段 ，MUNGWATTANA A.Multi－shuttle automated storage／retrieval systems［J］.IIE Transactions，1997，29（10）：925－938.

［6］ LERHER T，SRAML M，POTRC I.Simulation analysis of mini－load multi－shuttle automated storage and retrieval systems［J］.The International Journal of Advanced Manufacturing Technology，2011，54（1／2／3／4）：337－348.

［7］ POTRC I，LERHER T，KRAMBERGER J，et al.Simulation model of multi－shuttle automated storage and retrieval systems［J］.Journal of Materials Processing Technology，2004，157／158（20）：236－244.

［8］ YANG Peng，MIAO Lixin，QI Mingyao.Slotting optimization in a multi－shuttle automated storage and retrieval system［J］.Computer Integrated Manufacturing Systems，2011，17（5）：1050－1055（in Chinese）.［楊 朋，繆立新，戚銘堯.多載具自動化存取系統(tǒng)貨位分配優(yōu)化［J］.計算機集成制造系統(tǒng)，2011，17（5）：1050－1055.］

［9］ YANG Peng，MIAO Lixin，QI Mingyao.Integrated optimization of storage location assignment and routing planning in a multi－shuttle automated storage and retrieval system［J］.Journal of Tsinghua University：Science and Technology，2011，51（2）：261－266（in Chinese）.［楊 朋，繆立新，戚銘堯.多載具自動化存取系統(tǒng)貨位分配和揀選路徑集成優(yōu)化［J］.清華大學學報：自然科學版，2011，51（2）：261－266.］

［10］ GUO 段 ，LIU L U.An evaluation of storage assignment policies for twin shuttle AS／RS［C］／／Proceedings of 2010 IEEE International Conference on Management of Innovation and Technology.Washington，D.C.，USA：IEEE Computer Society，2010.

［11］ TANAKA S，ARAKI M.An exact algorithm for the input／output scheduling problem in an end－of－aisle multi－shuttle automated storage／retrieval system with dedicated storage［J］.Transactions of the Society of Instrument and Control Engineers，2006，42（9）：1058－1066.

［12］ TANAKA S.A hybrid algorithm for the input／output scheduling problem of multi－shuttle AS／RSs［C］／／Proceedings of the Society of Instrument and Control Engineers Society of Instrument and Control Engineers.Washington，D.C.，USA：IEEE，2007.

［13］ KUBOTA Y，NUMATA K.An exact algorithm based on Lagrangian relaxation for the input－output scheduling problem in automated warehouses［C］／／Proceedings of the ICCAS－SICE.Washington，D.C.，USA：IEEE，2009：753－758.

［14］ DOOLY 段 ，LEE L E.A shift－based sequencing method for twin－shuttle automated storage and retrieval systems［J］.IIE Transactions，2008，40（6）：586－594.

［15］ XIE Jinxing，XING Wenxun，WANG Zhenbo.Network optimization［M］.Beijing：Tsinghua University Press，2009（in Chinese）.［謝金星，刑文訓，王振波.網絡優(yōu)化［M］.北京：清華大學出版社，2009.］.

［16］ RICHARD 段 .Reducibility among combinatorial problems［M］／／Complexity of Computations.New York，N.Y.，USA：Plenum，1972：85－103.