發(fā)布時(shí)間：2014-07-22 22:41

摘要：為了提高多載具自動(dòng)化存取系統(tǒng)整體進(jìn)出庫(kù)效率，分析了多載具自動(dòng)化存取系統(tǒng)的運(yùn)作特點(diǎn)，建立了同時(shí)考慮貨位分配和揀選路徑的集成優(yōu)化模型。模型以最小化單位指令周期的行程時(shí)間為優(yōu)化目標(biāo)，最后設(shè)計(jì)了兩階段禁忌搜索算法求解該問(wèn)題。不同貨位規(guī)模和不同載具數(shù)量的數(shù)值實(shí)驗(yàn)結(jié)果表明兩階段禁忌算法獲得的行程時(shí)間較初始解有至少40%的改善，而且與分別優(yōu)化的方法相比行程時(shí)間也能降低7%~23%。
關(guān)鍵詞：集成優(yōu)化；多載具；自動(dòng)化存取系統(tǒng)；貨位分配；揀選路徑
中圖分類號(hào)：TP391     文獻(xiàn)標(biāo)識(shí)碼：A
Integrated optimization of storage location assignment and routing planning in a multi-shuttle automated storage and retrieval system
YANG Peng, MIAO Lixin, QI Mingyao
(Research Center for Modern Logistics, Graduate School at Shenzhen, Tsinghua University, Shenzhen518055, China)
Abstract: The patterns of operating the multi-shuttle automated storage and retrieval system (AS/RS) are analyzed to improve the overall efficiency of multi-shuttle AS/RS. The integrated optimization model of storage location assignment and routing planning is established to minimize the travel time of performing corresponding storage and retrieval operations in command cycle. To solve this complicated problem, a two-phase tabu algorithm is developed. According to numerical experiments combined with different location sizes and various shuttle numbers, at least 40% reduction for travel time can be obtained relative to the initial solutions using this algorithm. Additionally comparison to the result using the separate optimization method shows that the travel time is reduced by 7%~23%.
Key words: integrated optimization; multi-shuttle; automated storage and retrieval system; storage location assignment; routing planning
 
配送領(lǐng)域中自動(dòng)化存取系統(tǒng)（Automated Storage and Retrieval System,簡(jiǎn)稱AS/RS）貨位分配優(yōu)化關(guān)注指令周期內(nèi)為待存貨物分配合適空貨位以及為待取貨物選擇合適取貨貨位（待取的貨物可能存放在多個(gè)貨位上），以提高出入庫(kù)效率。單載具AS/RS一次行程最多訪問(wèn)兩個(gè)貨位，貨位分配和揀選路徑（行程內(nèi)貨位訪問(wèn)的順序）的關(guān)聯(lián)度較弱，單獨(dú)優(yōu)化貨位分配即能取得較好成效，但是多載具（multi-shuttle）AS/RS擁有多個(gè)載具（大于等于2個(gè)），一次行程可以同時(shí)存放和取出多個(gè)貨物單元，行程內(nèi)訪問(wèn)的貨位數(shù)將大大增加。如果仍然單獨(dú)優(yōu)化貨位分配，將難以從整體上提高進(jìn)出庫(kù)效率。
貨位分配的已有研究著重于單載具AS/RS貨位分配優(yōu)化^[1,2]和man-on-board(person-on-board)系統(tǒng)（即揀選人員在存取設(shè)備上完成存取貨作業(yè)，存取設(shè)備可以穿越不同的通道行走）貨位分配優(yōu)化研究^[3-5]，但僅關(guān)注為入庫(kù)貨物尋找最優(yōu)貨位存放，主要考慮貨物周轉(zhuǎn)率、保持貨架穩(wěn)定上輕下重、貨物相關(guān)性等因素，少量文獻(xiàn)^{[6, 7]}同時(shí)考慮了存貨貨位和取貨貨位的優(yōu)化，但大部分忽略了取貨貨位的分配優(yōu)化。多載具AS/RS控制優(yōu)化文獻(xiàn)較少，集中在存取指令作業(yè)調(diào)度排序^{[8, 9]}和吞吐能力仿真^[10]上，從集成角度對(duì)多載具AS/RS貨位分配和揀選路徑規(guī)劃的優(yōu)化還未見研究。
本文針對(duì)多載具AS/RS的特點(diǎn)，以配送領(lǐng)域?yàn)閼?yīng)用背景，從集成優(yōu)化的角度對(duì)多載具AS/RS的貨位分配和揀選路徑問(wèn)題進(jìn)行研究。

1 問(wèn)題描述

實(shí)際配送環(huán)境下存取系統(tǒng)不停進(jìn)行出入庫(kù)作業(yè)，連續(xù)到達(dá)的存取貨指令分別形成入庫(kù)隊(duì)列和存貨隊(duì)列，多載具自動(dòng)化存取系統(tǒng)按照指令周期（command cycle）模式進(jìn)行運(yùn)作，根據(jù)單位時(shí)間內(nèi)存貨隊(duì)列和取貨隊(duì)列的長(zhǎng)度，可組合劃分為多個(gè)指令周期，假設(shè)堆垛機(jī)有n個(gè)載具(n≥2) ，一個(gè)指令周期內(nèi)最多可以完成n個(gè)貨物單元的存貨操作和n個(gè)貨物單元的取貨操作。根據(jù)系統(tǒng)存貨隊(duì)列和取貨隊(duì)列的情況，堆垛機(jī)可以進(jìn)行復(fù)合式和單一任務(wù)式兩種指令周期作業(yè)方式，其中復(fù)合式指令周期指堆垛機(jī)一次行程同時(shí)完成m₁(0<m₁≤n）個(gè)貨物單元存貨操作和m₂(0<m₂≤n）個(gè)貨物單元取貨操作，單一任務(wù)式指令周期指堆垛機(jī)一次行程只完成m(0<m≤n)個(gè)貨物單元的存貨或取貨操作。指令周期是多載具自動(dòng)化存取系統(tǒng)運(yùn)作的最小單元，同時(shí)也是提高存取系統(tǒng)進(jìn)出庫(kù)效率的基本優(yōu)化單元。每個(gè)指令周期幾乎都將面臨選擇存取貨位及貨位訪問(wèn)順序設(shè)計(jì)（揀選路徑）問(wèn)題，對(duì)基本單元內(nèi)對(duì)應(yīng)優(yōu)化問(wèn)題的研究將是提高存取系統(tǒng)整體效率的基礎(chǔ)。本文同時(shí)考慮存取貨位分配和揀選路徑規(guī)劃兩個(gè)優(yōu)化問(wèn)題，以最小化指令周期內(nèi)存取貨物的時(shí)間距離為目標(biāo)進(jìn)行集成優(yōu)化研究。

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

2.1 基本假設(shè)

考慮單元負(fù)載式(unit-load)自動(dòng)化存取系統(tǒng)，以托盤為存取單元，貨物從同一出口進(jìn)出，進(jìn)出貨口(input/output point，I/O point)位于貨架左下方，每個(gè)貨位只能存放一個(gè)托盤單一種類的貨物，貨架上貨位具有相同尺寸，每個(gè)托盤都可以存放貨架上任一貨位；堆垛機(jī)有n個(gè)載具(n≥2)，各個(gè)載具的操作互相獨(dú)立，堆垛機(jī)在水平方向上和垂直方向上同時(shí)運(yùn)動(dòng)，假設(shè)水平方向和垂直方向均做勻速運(yùn)動(dòng)，速度已知且為常數(shù)，不受堆垛機(jī)載物與否影響；不考慮堆垛機(jī)在貨位處取貨和存貨(pickup/deposit)的時(shí)間；系統(tǒng)存貨隊(duì)列和取貨隊(duì)列無(wú)容量限制，規(guī)劃時(shí)間內(nèi)存貨隊(duì)列和取貨隊(duì)列貨物種類已知，且兩個(gè)隊(duì)列無(wú)相同種類貨物，否則直接從存貨隊(duì)列將貨物取走，不用進(jìn)入存儲(chǔ)區(qū)，存貨隊(duì)列和取貨隊(duì)列的指令均按照先到先服務(wù)（FCFS）的原則處理。

2.2 符號(hào)定義

根據(jù)規(guī)劃時(shí)間內(nèi)存取貨隊(duì)列情況，按照FCFS規(guī)則劃分指令周期集合，不失一般性，任選集合中任一指令周期j作為研究對(duì)象，假設(shè)單位時(shí)間內(nèi)取貨隊(duì)列長(zhǎng)度為LR，存貨隊(duì)列長(zhǎng)度為LS，則，其中是指令周期總個(gè)數(shù)；為便于建模，補(bǔ)充定義如下符號(hào)：
I為貨物種類集合，數(shù)量N^I,索引i, i’；L為貨位集合，數(shù)量N^L，索引k,k’,l，其中貨位0代表I/O；n為堆垛機(jī)載具數(shù)量；為指令周期j執(zhí)行前空貨位集合；為指令周期j執(zhí)行前存儲(chǔ)貨物i的貨位集合，；S_j為指令周期j內(nèi)需存貨物集合；R_j為指令周期j內(nèi)需取貨物集合，滿足；AL_j為指令周期j內(nèi)可能訪問(wèn)到的貨位集合，；c_kl為貨位k到貨位l的時(shí)間距離，；(W_k,H_k)為貨位k的坐標(biāo)，，（0,0）代表I/O；w為相鄰貨位水平方向距離；h為相鄰貨位垂直方向距離；v_x為堆垛機(jī)水平方向速度；v_y為堆垛機(jī)垂直方向速度；T(cc_j)為堆垛機(jī)完成指令周期j的行程時(shí)間；q_klj為在j指令周期內(nèi)，訪問(wèn)完貨位k后在訪問(wèn)貨位l前堆垛機(jī)的負(fù)載量；d_kj為j指令周期貨位k可存貨的數(shù)量；p_kj為j指令周期貨位k 可取貨的數(shù)量，其中，系統(tǒng)為單元式負(fù)載，負(fù)載量1代表1貨物單元。
集成優(yōu)化模型的決策變量為，取1表示指令周期j內(nèi)，貨物i存放在貨位k處，，否則取0；，取1表示指令周期j內(nèi)，從貨位處取出貨物，，否則取0；，取1表示指令周期j內(nèi)，訪問(wèn)貨位k后立即訪問(wèn)貨位l。另外為了建模方便，設(shè)置補(bǔ)充變量，取1表示貨位k在指令周期j內(nèi)將被訪問(wèn)，，其中滿足。

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

在任一指令周期j（復(fù)合式或單一任務(wù)式指令周期均可）內(nèi)，多載具AS/RS存取貨位分配和路徑規(guī)劃的確定屬于組合優(yōu)化問(wèn)題，可抽象為下述整數(shù)規(guī)劃模型，待存取貨位確定后，模型即轉(zhuǎn)化為求解一個(gè)混合考慮存貨和取貨的TSP/PD(Travel Salesman Problem with Pickups and Deliveries)問(wèn)題。該模型類似于宏觀層面的配送中心選址-路徑問(wèn)題(Location Routing Problem，簡(jiǎn)稱LRP)，但貨位的備選集合的規(guī)模較LRP更大且更復(fù)雜，路徑問(wèn)題需考慮存貨取貨兩種操作，其約束條件也較LRP只考慮取貨操作情況更嚴(yán)格。
目標(biāo)函數(shù)約束條件
                  
                  
                 
        
               
               


             
           
             
兩個(gè)貨位間的時(shí)間距離采用切比雪夫距離表示為：
其中約束（1）和（2）確保指令周期j內(nèi)指定一個(gè)空貨位供貨物存放，約束（3）確保指令周期j內(nèi)從一個(gè)存有貨物i’的貨位上取貨以滿足取貨需求，約束（4）確保指令周期j 內(nèi)只訪問(wèn)被分配的存取貨位，約束（5）（6）確保被分配的存取貨位全部遍歷到，約束（7）使訪問(wèn)某一貨位（I/O除外）后，必須要從該貨位離開，約束（8）反映堆垛機(jī)訪問(wèn)貨位l后所載貨物數(shù)量的變化，約束（9）確保使堆垛機(jī)從I/O點(diǎn)出發(fā)時(shí)的載貨量滿足指令周期內(nèi)的存貨需求，約束（10）確保堆垛機(jī)返回I/O點(diǎn)的載貨量滿足指令周期內(nèi)取貨需求，約束（11）保證堆垛機(jī)在運(yùn)行過(guò)程中負(fù)載不超過(guò)其最大負(fù)載限制。
單位時(shí)間根據(jù)存取貨隊(duì)列情況劃分的指令周期集合中，上述模型在每一個(gè)指令周期都需求解一次，相鄰指令周期序列中空貨位和存貨貨位集合會(huì)發(fā)生不斷的更新，模型中貨位的初始分布狀態(tài)由上一次指令周期模型的求解結(jié)果決定，但限于篇幅，多指令周期的優(yōu)化將另文描述，本文只集中在基本優(yōu)化單元中單個(gè)指令周期的貨位分配和路徑規(guī)劃的集成優(yōu)化上。
TSP/PD和LRP已被證明為NP-hard問(wèn)題，上述模型嵌套TSP/PD，而且約束較LRP更加嚴(yán)格，雖然現(xiàn)實(shí)多載具系統(tǒng)配置的載具數(shù)量有限（一般為2-6個(gè)），TSP/PD節(jié)點(diǎn)數(shù)的規(guī)模較小，存在采用精確算法求解TSP/PD問(wèn)題的可能性，但是對(duì)貨位分配階段大規(guī)模禁忌搜索中每一個(gè)可行解精確求解一個(gè)TSP/PD問(wèn)題，其計(jì)算代價(jià)將大大增加，另外上述集成優(yōu)化模型需要考慮貨位分配優(yōu)化和揀選路徑優(yōu)化之間的反饋關(guān)系，因此單獨(dú)采用貨位指派算法和路徑規(guī)劃算法也難以有效求解，本文設(shè)計(jì)兩階段的禁忌搜索（Tabu Search）算法進(jìn)行求解，通過(guò)兩階段禁忌搜索的反饋獲得多載具AS/RS貨位分配和揀選路徑的最優(yōu)方案。

3 算法實(shí)現(xiàn)

禁忌算法是求解組合優(yōu)化問(wèn)題的性能較優(yōu)的啟發(fā)式算法，其主要思想是用禁忌表記錄已經(jīng)到達(dá)過(guò)的局部最優(yōu)點(diǎn)或達(dá)到局部最優(yōu)的過(guò)程，在下次搜索中不再搜索這些點(diǎn)，以跳出局部最優(yōu)點(diǎn)，以提高算法性能，最終達(dá)到全局最優(yōu)。其中兩階段禁忌算法是適用于集成優(yōu)化問(wèn)題的多階段啟發(fā)式算法，已成功應(yīng)用求解配送中心選址－路徑問(wèn)題^[11]和集裝箱碼頭卸貨堆存位置選擇－集卡調(diào)度問(wèn)題^[12]，其算法思想有效反映了不同優(yōu)化層面的反饋?zhàn)饔藐P(guān)系。
本文設(shè)計(jì)兩階段禁忌搜索算法求解多載具AS/RS貨位分配和揀選路徑集成優(yōu)化模型，算法流程如圖1。貨位分配階段，通過(guò)禁忌算法搜索貨物的存取貨位分配方案，基于貨位分配優(yōu)化方案，在路徑規(guī)劃階段，執(zhí)行另一禁忌算法求解貨位訪問(wèn)的最優(yōu)路徑，在路徑優(yōu)化結(jié)果基礎(chǔ)上計(jì)算指令周期的總行程時(shí)間，并將此結(jié)果反饋到貨位分配優(yōu)化階段，從而影響貨位分配優(yōu)化階段的禁忌搜索過(guò)程，通過(guò)兩階段搜索過(guò)程的互相反饋獲得模型最優(yōu)解。下面對(duì)兩階段禁忌搜索算法的幾個(gè)關(guān)鍵技術(shù)作一介紹。

圖1 兩階段禁忌算法流程

3.1 初始解的構(gòu)建

貨位分配階段禁忌算法的初始解從可行解集中通過(guò)隨機(jī)方法生成，以“空貨位集合＋取貨貨位集合1＋取貨貨位集合2＋···”序列的0-1碼形式表示貨位分配方案；路徑規(guī)劃階段的禁忌算法初始解則通過(guò)改進(jìn)的最近鄰點(diǎn)法（Nearest Neighbor，簡(jiǎn)稱NN）生成，在改進(jìn)的最近鄰點(diǎn)法中，每次的搜索范圍由是否存在空載具決定，有空載具最近鄰點(diǎn)從空貨位和待取貨物貨位的并集中搜尋，無(wú)空載具則只能從空貨位集合中搜尋。

3.2 貨位分配階段的鄰域搜索策略

由于貨位分配涉及存取貨位的選擇，如果采用簡(jiǎn)單貨位交換方法生成鄰域，勢(shì)必會(huì)產(chǎn)生大量的不可行解，影響算法的執(zhí)行，本文設(shè)計(jì)一種基于片段的貨位交換方法來(lái)生成當(dāng)前解的鄰域，例如3載具AS/RS指令周期內(nèi)需要存放A，B，C貨物各一，取出D，E，F(xiàn)貨物各一，貨位分配方案采用“空貨位集合＋存放貨物D貨位集合＋存放貨物E貨位集合＋存放貨物F貨位集合”序列的0-1碼表示，其中可行解應(yīng)該滿足空貨位序列中三個(gè)碼位為“1”，表示選擇三個(gè)空貨位，存放貨物D，E，F(xiàn)貨位序列中各有一個(gè)碼位為“1”，從四個(gè)片段中以一定概率選擇某一片段，在片段內(nèi)進(jìn)行0-1交換來(lái)構(gòu)造貨位分配階段的鄰域，以同時(shí)滿足解的可行性和搜索覆蓋面，鄰域規(guī)模視備選貨位分配備選集合規(guī)模而定，去除鄰域中被禁忌的對(duì)象，生成候選集合，采用改進(jìn)的NN方法評(píng)價(jià)候選集合中解的性能，選擇最優(yōu)貨位分配方案作為本次迭代的最優(yōu)解，同時(shí)更新貨位分配階段的禁忌表，另外設(shè)置貨位分配階段允許無(wú)改進(jìn)迭代次數(shù)的閾值MaxNonImp_L，當(dāng)連續(xù)迭代次數(shù)達(dá)到MaxNonImp_L時(shí)，解的性能仍無(wú)改進(jìn)，貨位分配階段的鄰域搜索終止。

3.3 路徑規(guī)劃階段的鄰域搜索策略

貨位分配方案每次更新后，路徑規(guī)劃階段要在現(xiàn)有貨位分配方案基礎(chǔ)上，搜索其最優(yōu)的貨位訪問(wèn)路徑方案。路徑規(guī)劃階段采用交換貨位順序方法構(gòu)造當(dāng)前解的鄰域，即已選貨位集合中兩個(gè)貨位進(jìn)行對(duì)換，由于存取貨操作并行存在，需對(duì)鄰域的解作可行性驗(yàn)證，剔除不滿足堆垛機(jī)載貨容量約束的不可行解，同樣設(shè)置路徑規(guī)劃階段允許無(wú)改進(jìn)迭代次數(shù)的閾值MaxNonImp_R，當(dāng)連續(xù)迭代次數(shù)達(dá)到MaxNonImp_R時(shí)，解的性能仍無(wú)改進(jìn)，路徑規(guī)劃階段的鄰域搜索終止，整個(gè)兩階段禁忌算法也同時(shí)終止。

3.4 禁忌表

貨位分配階段和路徑規(guī)劃階段均選擇解本身作為禁忌對(duì)象，禁忌表由矩陣表示，矩陣的每一行代表禁忌對(duì)象，行標(biāo)代表禁忌長(zhǎng)度，每迭代一次，矩陣各行上移一位，代表對(duì)應(yīng)禁忌長(zhǎng)度減一，原首行解禁忌解除，將新加入禁忌對(duì)象寫入尾行，禁忌長(zhǎng)度的選擇有賴于問(wèn)題規(guī)模和禁忌表存儲(chǔ)所需內(nèi)存空間的考量，一般貨位分配階段備選貨位集合規(guī)模較大，可選15-20較長(zhǎng)禁忌長(zhǎng)度為宜，路徑規(guī)劃階段可行解集合規(guī)模較小，可選5-10較短禁忌長(zhǎng)度為宜。實(shí)際計(jì)算中，為提高計(jì)算效率，可對(duì)禁忌表參數(shù)動(dòng)態(tài)調(diào)整，多次搜索后沒(méi)有改進(jìn)時(shí)，可以適當(dāng)增加禁忌表的長(zhǎng)度，當(dāng)所有解均被禁忌后，采用基于評(píng)價(jià)值的特赦規(guī)則，其中貨位分配階段采用改進(jìn)的NN方法對(duì)解進(jìn)行評(píng)價(jià)，路徑規(guī)劃階段則直接計(jì)算行程時(shí)間評(píng)價(jià)，選取評(píng)價(jià)較優(yōu)的解，提前解除禁忌。

4 算例分析

假設(shè)相鄰貨位水平方向間距w=1.5 m，垂直方向間距h=1.5 m，堆垛機(jī)水平方向速度v_x=2 m/s，垂直方向的速度為v_y=0.5 m/s，選擇40（5層×8列）、80（8層×10列）、120（10層×12列）、160（10層×16列）和200（10層×20列）五種貨架貨位數(shù)規(guī)模，選擇2-6 載具數(shù)量，存貨取貨所涉及的貨物共20種，初始貨位分布隨機(jī)生成，其中每種算例方案取10組計(jì)算，結(jié)果取10組平均值，貨位分配階段允許最大無(wú)改進(jìn)迭代次數(shù)MaxNonImp_L=100，禁忌表長(zhǎng)度取20，路徑規(guī)劃階段允許最大無(wú)改進(jìn)次數(shù)MaxNonImp_R=100，禁忌表長(zhǎng)度取5，采用Matlab 7.0為計(jì)算仿真工具，處理器AMD 2.30 GHz和內(nèi)存1GB的個(gè)人計(jì)算機(jī)作為計(jì)算平臺(tái)進(jìn)行數(shù)值實(shí)驗(yàn)。
選擇3載具AS/RS，對(duì)不同貨位規(guī)模的兩階段禁忌算法進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如表1，結(jié)果表明與初始解相比，兩階段禁忌算法所得的行程時(shí)間有明顯改善，改進(jìn)程度平均達(dá)到60%，算法的計(jì)算時(shí)間隨著貨位規(guī)模的增大而緩慢增加，但都能夠在合理時(shí)間內(nèi)有效收斂，可以滿足多載具AS/RS實(shí)際操作中的調(diào)度決策需求。
表1 兩階段禁忌搜索算法計(jì)算結(jié)果

貨位數(shù)	初始行程時(shí)間/s	兩階段禁忌算法得到的行程時(shí)間/s	兩階段禁忌算法的計(jì)算時(shí)間/s
40	34.12	15.97	4.82
80	49.27	17.32	4.97
120	56.17	22.05	5.04
160	56.70	23.25	5.17
200	69.22	24.75	5.21

取10層12列共120貨位規(guī)模的貨架，對(duì)不同載具數(shù)量的兩階段禁忌算法進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如表2，結(jié)果表明算法在不同載具數(shù)量情況下均能有效改進(jìn)解的性能，改進(jìn)程度則隨載具數(shù)量的增加有所降低，2載具時(shí)改進(jìn)64%，6載具時(shí)只有49%，但改進(jìn)效果仍然明顯，隨著載具數(shù)量增多，算法計(jì)算時(shí)間顯著增加，這與存取貨的周期變長(zhǎng)及搜索復(fù)雜性大大增加有關(guān)，但計(jì)算時(shí)間均處在可承受范圍內(nèi)。
表2 載具數(shù)量對(duì)兩階段禁忌搜索算法的影響

載具數(shù)	初始行程時(shí)間/s	兩階段禁忌算法得到的行程時(shí)間/s	兩階段禁忌算法的計(jì)算時(shí)間/s
2	45.52	18.82	2.93
3	57.82	22.27	5.03
4	59.70	29.77	7.39
5	72.97	34.20	9.97
6	79.20	40.05	12.88

為檢驗(yàn)本文模型和算法集成優(yōu)化的性能，取3載具AS/RS，針對(duì)不同貨位規(guī)模，對(duì)貨位分配－揀選路徑分別優(yōu)化方法和本文的集成優(yōu)化方法進(jìn)行仿真比較，其中分別優(yōu)化方法中貨位分配采用遺傳算法，最大迭代100代，揀選路徑采用改進(jìn)NN法，比較結(jié)果如表3。結(jié)果表明無(wú)論貨位規(guī)模大小，兩階段禁忌算法在計(jì)算結(jié)果性能上和計(jì)算速度上都全面優(yōu)于分別優(yōu)化方法，計(jì)算結(jié)果最大改進(jìn)程度達(dá)到23.22％，計(jì)算時(shí)間的改進(jìn)程度隨著貨位規(guī)模增大快速增加，最大改進(jìn)甚至達(dá)到90.70%。比較結(jié)果有效驗(yàn)證了集成優(yōu)化模型和算法的優(yōu)越性，為多載具AS/RS實(shí)際作業(yè)調(diào)度提供了決策工具。
表3 兩階段禁忌算法與分別優(yōu)化法比較

貨位數(shù)	分別優(yōu)化法		兩階段禁忌算法			兩階段禁忌算法較分別優(yōu)化法的改進(jìn)程度
	行程時(shí)間/s	計(jì)算時(shí)間/s	行程時(shí)間/s	計(jì)算時(shí)間/s		行程時(shí)間		計(jì)算時(shí)間
40	17.70	6.03	15.90		4.79	10.17%	20.56%
80	22.27	12.45	17.10		5.01	23.22%	59.76%
120	25.27	19.12	22.27		4.98	11.87%	73.95%
160	29.02	32.05	24.15		5.07	16.78%	84.18%
200	27.82	55.46	25.87		5.16	7.01%	90.70%

5 結(jié)論

多載具AS/RS指令周期內(nèi)可訪問(wèn)多個(gè)貨位進(jìn)行存取貨操作，統(tǒng)一考慮貨位分配和揀選路徑才能有效縮短行程時(shí)間，提高系統(tǒng)整體進(jìn)出庫(kù)效率。集成優(yōu)化模型中優(yōu)化問(wèn)題互相嵌套增加了模型復(fù)雜性，本文設(shè)計(jì)兩階段禁忌算法對(duì)模型求解，求解過(guò)程體現(xiàn)了兩個(gè)優(yōu)化問(wèn)題的相互反饋關(guān)系。兩階段禁忌算法在不同貨位規(guī)模和載具數(shù)量下能夠顯著改善解的質(zhì)量，而且與分別優(yōu)化方法相比，能夠?qū)⑿谐虝r(shí)間平均降低15%左右，進(jìn)而相應(yīng)提高系統(tǒng)出入庫(kù)效率。未來(lái)應(yīng)該進(jìn)一步對(duì)規(guī)劃時(shí)間內(nèi)的多指令周期動(dòng)態(tài)貨位分配和揀選路徑進(jìn)行優(yōu)化，以便于多載具AS/RS實(shí)際作業(yè)調(diào)度中靈活使用。

參考文獻(xiàn)  (References)
 [1] 柳賽男, 柯映林, 李江雄,等. 基于調(diào)度策略的自動(dòng)化倉(cāng)庫(kù)系統(tǒng)優(yōu)化問(wèn)題研究[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2006, 12(9): 1438-1443.
LIU Sainan, KE Yinglin, LI Jiangxiong, et al. Optimazation for automated warehouse based on scheduling policy[J]. Computer Integrated Manufacturing Systems, 2006, 12,(9): 1438-1443.(in Chinese).
 [2] 商允偉, 裘聿皇, 劉長(zhǎng)有. 自動(dòng)化倉(cāng)庫(kù)貨位分配優(yōu)化問(wèn)題研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2004(26): 16-21.
SHANG Yunwei, QIU Yuhuang, LIU Changyou. Optimization of goods locations assignment of automated warehouse [J]. Computer Engineering and Applications, 2004(26): 16-21.(in Chinese).
 [3] 肖建, 鄭力. 檢修備品庫(kù)的貨位優(yōu)化模型[J]. 清華大學(xué)學(xué)報(bào):自然科學(xué)版, 2008, 48(11): 1883-1886.
XIAO Jian, ZHENG Li. Slotting optimization model for overhaul warehouses[J]. Journal of Tsinghua University:Science and Technology, 2008, 48,(11): 1883-1886.(in Chinese).
 [4] XIAO Jian, ZHENG Li. A correlated storage location assignment problem in a single-block-multi- aisles warehouse considering BOM information[J]. International Journal of Production Research, 2010, 48(5): 1321-1338.
 [5] Lee M. A storage assignment policy in a man-on-board automated storage/retrieval system[J]. International Journal of Production Research, 1992, 30(10): 2281.
 [6] 賈煜亮, 繆立新. 自動(dòng)化立體倉(cāng)庫(kù)中貨位實(shí)時(shí)分配優(yōu)化問(wèn)題研究[J]. 北京交通大學(xué)學(xué)報(bào):社會(huì)科學(xué)版, 2007, 6(4): 18-24.
JIA Yuliang, MIAO Lixin. Optimization of real-time storage location assignment in automated storage and retrieval system[J]. Journal of Beijing Jiaotong University:Social Science Edition, 2007, 6,(4): 18-24.(in Chinese).
 [7] Chen Lu, Langevin A, Riopel D. The storage location assignment and interleaving problem in an automated storage/retrieval system with shared storage[J]. International Journal of Production Research, 2010, 48(4): 991-1011.
 [8] Tanaka S. A hybrid algorithm for the input/output scheduling problem of multi-shuttle AS/RSs[C]//Proc Society of Instrument and Control Engineers Annual Conference 2007. Kagawa,Japan: IEEE Press, 2007:2643-2648.
 [9] Dooly D. R, Lee H. F. A shift-based sequencing method for twin-shuttle automated storage and retrieval systems.[J]. IIE Transactions, 2008, 40(6): 586-594.
[10] 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.
[11] Liu S. C, Lee S. B. A two-phase heuristic method for the multi-depot location routing problem taking inventory control decisions into consideration[J]. The International Journal of Advanced Manufacturing Technology, 2003, 22(11): 941-950.
[12] 曾慶成, 楊忠振. 集裝箱碼頭卸船作業(yè)調(diào)度方案的兩階段禁忌搜索算法[J]. 交通運(yùn)輸工程學(xué)報(bào), 2007, 7(2): 109-112.
ZENG Qingcheng, YANG Zhongzhen. Two-phase tabu search algorithm of unloading operation scheduling project in container wharf[J]. Journal of Traffic and Transportation Engineering, 2007, 7,(2): 109-112.(in Chinese).
 



本文編號(hào)：4150