【摘要】 隨著物流行業(yè)對于倉儲配送的柔性和魯棒性要求的提高,一種新型的自動化立體倉庫——多層穿梭車倉儲系統(tǒng)逐漸得到重視和應用。多層穿梭車倉儲系統(tǒng)是由多層貨架內的穿梭車與該巷道的提升機組成,出入庫作業(yè)時用穿梭車與提升機的組合來替代傳統(tǒng)自動化立體倉庫中的堆垛機,提高了系統(tǒng)的柔性和魯棒性。該新型倉儲系統(tǒng)根據穿梭車能否跨層運動分為單層作業(yè)和跨層作業(yè)兩種類型。本文以單層作業(yè)的多層穿梭車倉儲系統(tǒng)為研究對象,分析其出庫任務作業(yè)的運動過程和交接次序,建立出庫作業(yè)任務完成的時間模型,綜合運用開環(huán)排隊網絡、蟻群聚類算法和基于Pareto最優(yōu)解的帶精英策略的非支配排序遺傳算法(NSGA-Ⅱ),從儲位優(yōu)化和任務調度兩個方面對多層穿梭車倉儲系統(tǒng)進行優(yōu)化研究。本文的主要研究內容和成果如下：(1)分析多層穿梭車倉儲系統(tǒng)的作業(yè)流程,在考慮各個設備運動特性的基礎上,建立了基于并行取貨、串行出庫的作業(yè)時序數學模型,分析了作業(yè)時序數學模型的主要影響因素,并對其分別進行詳細闡述說明。(2)建立開環(huán)排隊網絡模型分析多層穿梭車倉儲系統(tǒng),利用分解法分析設備配合作業(yè)的空閑時間和系統(tǒng)表現,利用品項間相關性和蟻群聚類算法形成初始儲區(qū)。再設計相應存儲原則,在二維平面內排列組合相應儲區(qū)。最后將該算法應用到某配送中心的多層穿梭車倉儲系統(tǒng)的貨位分配問題中。(3)基于并行取貨、串行出庫的作業(yè)時序數學模型,分別對提升機和穿梭車進行分析,從而建立起以出庫時間、提升機空閑時間和穿梭車等待時間最小為目標的任務調度模型,運用基于Pareto最優(yōu)解的帶精英策略的非支配排序遺傳算法(NSGA-Ⅱ)進行模型求解。最后,為驗證模型及算法的有效性,本章以某省電力公司電力儀表倉庫實際出庫單據為實驗對象,確定最優(yōu)的任務調度方案。最后,本文在單層作業(yè)的多層穿梭車倉儲系統(tǒng)建模與優(yōu)化基礎上,對跨層作業(yè)的多層穿梭車倉儲系統(tǒng)進行了分析和展望。 

第一章緒論

1.1引言
自動化立體倉庫（Automated Storage and Retrieval System, AS/RS)是信息技術和工業(yè)生產飛速發(fā)展的產物，是物流作業(yè)全流程中具有重要意義的節(jié)點�，F階段，大多數自動化立體倉庫是由負責存儲貨物單元（Stock Keeping Unit，SKU)的幾層、十幾層乃至幾十層高層貨架系統(tǒng)和能在二維空間按歐式軌線高速運行的堆操機組成。自動化立體倉庫具有占地小、容量大、周轉率強、準確率高、自動化程度高、環(huán)境適應能力強等特點，在機械、冶金、煙草、電子、醫(yī)藥等行業(yè)得到廣泛應用，成為現代物流業(yè)倉儲與配送不可缺少的重要組成部分[1]。
然而在傳統(tǒng)自動化立體倉庫中，這種由堆操機負責貨物存取的方式存在兩方面的不足。一方面是魯棒性不強，，當堆躲機發(fā)生故障時，其所服務的巷道隨即處于癱瘓狀態(tài)，無法繼續(xù)進行相應的出入庫作業(yè)，且一般不存在備用設備，只能停機維修造成停工。另一方面是柔性不足，當傳統(tǒng)堆躲機式的自動化立體倉庫設計建造完成后，其出入庫能力隨之固定。隨著電子商務的發(fā)展和定制化服務的深入，產品生命周期不斷縮短，小批量、多批次、多品種、高時效特點的訂單不斷增多，使得現代企業(yè)的生產需求原則從“可靠性第一”逐漸轉變成“柔性第一”。
此情況下，一種由負責水平運動的軌道導引車輛(Rail Guided Vehicle, RGV)和負責垂直運動的提升機（Lift)共同組成的新型倉儲系統(tǒng)一一自動小車存取系統(tǒng)（Autonomous Vehicle Storage and Retrieval Systems, AVS/RS)于 2000 年左右在歐洲、美國等地開始陸續(xù)投入使用。該系統(tǒng)融合了自動導引車輛系統(tǒng)(Automated Guided Vehicle, AGV)的柔性和傳統(tǒng)堆垛機式自動化立體倉庫的高速出入能力，被認為是自動化立體倉庫的發(fā)展方向[2]。在自動小車存取系統(tǒng)中，其每一層貨架均有一輛或多輛軌道導引車輛，因此系統(tǒng)不會由于某輛車的故障而全線停機，使其柔性要遠高于傳統(tǒng)堆垛機式的自動化立體倉庫[3]。
但是，自動存取小車系統(tǒng)也存在著其相應的弊端。一方面，該自動小車存取系統(tǒng)更適用于標準托盤化的貨物倉儲，即單次出入的貨物單元內存貨數量多，難以應對以周轉箱為主要存儲單元的小規(guī)格、多頻次的存取需求；另一方面，每層貨架上均有一輛或多輛小車，對車輛管理系統(tǒng)的調度、控制、防堵塞等方面要求高，存在著控制系統(tǒng)繁復、成本巨大等問題。因此，上述原因也限制自動小車存取系統(tǒng)的大量應用。
為了解決上述難題，在自動存取小車系統(tǒng)的基礎上，另一種新興的簡化的自動化倉儲系統(tǒng)應運而生，這就是多層穿梭車倉儲系統(tǒng)（Multi-tier ShuttleWarehousing System, MSWS)。該系統(tǒng)既很好的解決自動存取小車系統(tǒng)難以適應以周轉箱為主的小規(guī)格貨物高頻次存取問題，其簡潔的系統(tǒng)設計又能使控制調度系統(tǒng)易于實現，降低信息管理系統(tǒng)與設備控制系統(tǒng)的開發(fā)難度以及設備調度過程中可能的出錯率。隨著顧客的訂單日趨呈現多批次、小批量、多頻次的趨勢以及電子商務環(huán)境下對高效顧客訂單履行的迫切需求，物流行業(yè)對于倉儲配送的柔性化要求的日漸提高，該系統(tǒng)得到越來越多物流廠商的重視，并在醫(yī)藥、煙草等領域得到應用，例如Dematic公司的Multishuttle、Knapp公司的OSR Shuttle以及 Vanderlande 集團的 QUICKSTORE HDS shuttle system 等。
............................

1.2多層穿梭車倉儲系統(tǒng)簡介
由于多層穿梭車倉儲系統(tǒng)是由自動小車存取系統(tǒng)簡化演變而來，所以有必要首先介紹自動小車存取系統(tǒng)。如圖1-1所示，自動小車存取系統(tǒng)是由高層貨架、軌道導引車輛、提升機以及鋪滿貨架間隙的軌道組成。在傳統(tǒng)自動化立體倉庫中，出入庫作業(yè)是由巷道中一個能夠同時進行垂直運動和水平運動的堆操機完成，到達出庫貨位的時間為提升機垂直運動和水平運動分別所用時間的最大值。而在自動小車存取系統(tǒng)中，貨物出入庫所需的垂直運動和水平運動被分開成依次執(zhí)行。從水平方向看，用軌道導引車輛來代替堆燥機完成巷道內的水平運動作業(yè)，利用車輛自身裝置完成叉取/出貨物作業(yè)；從垂直方向看，由一臺或多臺提升機完成貨物或者軌道導引車輛的垂直方向移動。自動小車存取系統(tǒng)從一定意義上弱化了巷道的概念，每兩排貨架之間不再強制性要求設置一個巷道，當軌道導引車輛需要跨巷道作業(yè)，可以利用排與排之間的橫向巷道來完成，以此來實現貨物的密集存儲。提升機的設計既可以用來運輸貨物單元，也可以將載貨狀態(tài)的軌道導引車輛運輸到出入站臺，又可以將空載狀態(tài)的軌道導引車輛運送到某缺少軌道導引車輛的層內。因此，根據自動小車存取系統(tǒng)中軌道導引車輛是否能夠借助提升機實現跨層作業(yè)，將其劃分為單層作業(yè)和跨層作業(yè)兩類。

如圖1-2所示，多層穿梭車倉儲系統(tǒng)是在自動小車存取系統(tǒng)基礎上演變而來，其用穿梭車（shuttle)來代替能夠在整個水平平面運動的軌道導引車輛，保留了傳統(tǒng)堆採機式的自動化立體倉庫中巷道概念。在多層穿梭車倉儲系統(tǒng)內，每一層只有一輛穿梭車，每臺提升機只負責一個巷道內垂直運動，穿梭車不能跨巷道運動，用組合式的“穿梭車+提升機”來代替了堆探機。

與自動小車存取系統(tǒng)的分類方式相同，多層穿梭車倉儲系統(tǒng)根據其穿梭車能否在提升機的幫助下實現換層作業(yè)，可以分為以下兩類：
單層作業(yè)的多層穿梭車倉儲系統(tǒng)（Tier-captive Multi-tier ShuttleWarehousing System, TCMSWS ）
跨層作業(yè)的多層穿梭車倉儲系統(tǒng)（Tier-to-tier Multi-tier ShuttleWarehousing System, TTMSWS ）
在單層作業(yè)的多層穿梭車倉儲系統(tǒng)中，每一層均有一輛穿梭車。以執(zhí)行出庫作業(yè)為例，該層的穿梭車首先水平運行到相應出庫貨位，利用自身的貨叉取出貨物單元，然后再水平運行至該層首列向提升機申請調度服務，該服務請求被加入提升機的任務隊列。如提升機當前沒有執(zhí)行其他相應任務，提升機將響應該調度服務請求，垂直運動至該層，進而與穿梭車完成貨物單元交換，再由提升機將貨物單元運送到I/O站臺，而穿梭車則執(zhí)行下一條該層出庫任務，循環(huán)往復。
..............................

第二章多層穿梭車倉儲系統(tǒng)建模

多層穿梭車倉儲系統(tǒng)的運行設備與傳統(tǒng)的自動化、):體倉庫有著很大的區(qū)別，尤其是出入庫任務調度方面。因此，本章以單層作業(yè)的多層穿梭車倉儲系統(tǒng)完成出庫任務為例進行分析，建立出庫作業(yè)時間模型，分析影響作業(yè)效率的重要因素。

2.1系統(tǒng)描述與作業(yè)流程
單層作業(yè)的多層穿梭車倉儲系統(tǒng)的作業(yè)模式不同于傳統(tǒng)堆採機式的自動化立體倉庫，其每層均由穿梭車來完成貨物的水平移動和貨位存取，再統(tǒng)一經由提升機來實現貨物單元的垂直方向移動，如圖2-1。在該系統(tǒng)中，出入庫作業(yè)由并行運動的穿梭車和順序執(zhí)行的提升機共同完成，在一定程度上提高了作業(yè)效率。

如同傳統(tǒng)的自動化、y.體倉庫一樣，多層穿梭車倉儲系統(tǒng)也存在簡單作業(yè)模式和復合作業(yè)模式。在簡單作業(yè)模式下，該型倉儲系統(tǒng)只執(zhí)行出庫任務或只執(zhí)行入庫任務；在復合作業(yè)模式下，該型倉儲系統(tǒng)可以在某一層實現入庫作業(yè)，而同時在另一層實現出庫作業(yè)。在實際倉儲作業(yè)中，入庫作業(yè)和出庫作業(yè)往往存在不同的時間窗，因此，本文的所有分析均基于簡單作業(yè)模式，即在該型倉儲系統(tǒng)的分析過程巾，只存在出庫作業(yè)或者入庫作業(yè)。此外，項0運營中存在不同的設備調度規(guī)則，例如：“先到先服務”、“優(yōu)先權服務”、“隨機服務”和“后到先服務”等。本文以穿梭車和提升機雙方均遵循“先到先服務”（First Come FirstService, FCFS)的調度原則。
在此基礎上，以出庫作業(yè)為例，多層穿梭車倉儲系統(tǒng)出庫作業(yè)流程如圖2-2:

在單條出庫任務執(zhí)行時，首先進入對應層的穿梭車任務隊列等待空閑狀態(tài)的穿梭車。當穿梭車按照FCFS規(guī)則執(zhí)行該任務后，首先水平運動到相應出庫貨位，利用自身貨叉從貨位上取出對應貨物，再水平運行到該層首列向提升機申請調度服務并等待提升機響應。若提升機此時空閑則會立即響應服務并前往該層與穿梭車完成貨物交接。交接完成后的穿梭車再次進入空閑狀態(tài)等待任務分配，而提升機則繼續(xù)垂直運動將貨物運送到I/O站臺，兩者間的貨物交接見圖2-3。
...........................

2.2作業(yè)效率影響因素
通過上文分析，我們可以將影響多層穿梭車倉儲系統(tǒng)作業(yè)效率的主要因素為兩個部分：（1）硬件設計方面，包括穿梭車最大速度Vp提升機最大速度TV和貨架層列比等；（2）運營管理方面，包括儲位分配和任務調度。下文對影響倉儲管理水平和作業(yè)效率的因素進行理論性概要分析。
(1).穿梭車最大速度vA
多層穿梭車倉儲系統(tǒng)出庫作業(yè)可以類比成流水線作業(yè)調度，增加穿梭車最大速度，能夠縮短第一個出庫任務申請?zhí)嵘龣C調度服務的時間。同時，穿梭車提速后使得申請?zhí)嵘龣C調度任務的時刻提前，在其他因素不變的前提下有助減少提升機的空閑時間。
(2).提升機最大速度Vy
所有的出庫任務均需要提升機完成最后一步，因此提升機的運行速度與整體作業(yè)效率有著重要意義。提升機提速后能夠減少完成單次任務完成時間，從而有效的提高單位時間內所服務的穿梭車申請任務數。
(3).貨架層列
比在總庫存量一定的情況下，貨架系統(tǒng)的不同的層列比也對作業(yè)效率有著影響。在傳統(tǒng)自動化立體倉庫中，立庫貨架長高比為SIT (Square in Time)時堆燥機出入庫效率最高，此時堆操機的到達最遠端貨位的水平方向用時與垂直方向的用時相同[5]。但是，對于多層穿梭車倉儲系統(tǒng)而言，一方面，隨著層數（穿梭車數量）的增多，一定時間段內提升機調度服務的申請數量增多，能夠減少提升機的空閑時間；另一方面，隨著列數的增多，不同層穿梭車完成水平運動的時間差值會增大，防止較短時間內出現多輛穿梭車申請?zhí)嵘龣C調度服務的情況，減少穿梭車等待時間。
(4).儲位分配
在傳統(tǒng)堆躲機式旳自動化立體倉庫中，常見儲位分配策略有共享存儲、分類存儲、隨機存儲和定位存儲等，大多基于貨物全周轉率或者訂單體積指數的分配原則。在多層穿梭車倉儲系統(tǒng)中，這些原則并不完全適合。一方面，高頻率貨物均靠近I/O點會造成穿梭車申請?zhí)嵘龣C任務時刻集中，造成穿梭車等待時間變長，車輛利用率降低；另一方面，僅僅考慮貨物自身屬性而忽略了品種間關聯性，也會影響貨物分配的效果。因此，在多層穿梭車倉儲系統(tǒng)中，儲位分配是依據最小化提升機空閑時間和最大化穿梭車利用率的原則進行。
(5).任務調度
傳統(tǒng)堆垛機式的自動化立體倉庫的任務調度研究大多將此類問題歸結為旅行商問題，即如何在復合作業(yè)模式下有效的將兩個或多個貨位出庫任務進行組合，從而減少堆躲機行駛路程。在多層穿梭車倉儲系統(tǒng)中，減少提升機的空閑時間要求兩個或多個穿梭車申請?zhí)嵘龣C調度的時刻差正好滿足提升機完成上一任務，而不是簡單的兩個出庫任務路徑之和最短。
..............................

第三章多層穿梭車倉儲系統(tǒng)儲位優(yōu)化........................................ 19
3.1問題描述........................................ 19
3.2開環(huán)排隊網絡........................................ 20
3.3基于蟻群聚類的儲位分配........................................ 25
3.3.1存儲策略........................................ 25
3.3.2傳統(tǒng)自動化立體倉庫儲位優(yōu)化模型........................................ 26
3.3.3基于聚類分析的儲區(qū)劃分........................................ 27
3.3.4蟻群聚類算法........................................ 28
3.3.5儲位分配........................................ 32
3.4實例分析........................................ 33
3.5本章小結........................................ 37

第四章多層穿梭車倉儲系統(tǒng)任務調度

4.1問題描述
在多層穿梭車倉儲系統(tǒng)中，提升機和穿梭車的服務規(guī)則為“先到先服務”(First-Come-First-Serve, FCFS)。當執(zhí)行出庫作業(yè)時，由不同層上的穿梭車并行完成取貨任務，再由提升機串行順序將貨物出庫到I/O站臺。當多個穿梭車與一個提升機進行任務交接時，會出現兩種不同類型的交接時間：穿梭車的等待時間和提升機的空閑時間。當穿梭車完成水平取貨作業(yè)后，將會申請?zhí)嵘龣C調度服務，若此時提升機正在執(zhí)行其他任務，則此穿梭車申請的調度5艮務將會放入提升機任務隊列中，穿梭車處于等待服務狀態(tài)直到提升機響應該申請，此段時間為穿梭車的等待時間；若此時提升機處于空閑狀態(tài)，會立即響應穿梭車申請的調度服務，但是提升機從上一次響應服務到本次響應服務的這段時間內處于空閑狀態(tài)，此段時間為提升機的空閑時間。
由于所有出庫任務最終均由提升機順序串行完成，依前文分析，多層穿梭車倉儲系統(tǒng)執(zhí)行出庫任務作業(yè)時可看作流水線作業(yè)模式，其總出庫任務完成時長等于出庫開始時刻到第一個穿梭車申請?zhí)嵘龣C調度服務的時長與提升機執(zhí)行完所有出庫任務的時長之和，即與提升機總工作時間長度和第一個完成出庫任務的穿梭車用時之和。
以上三種作業(yè)時間長度分別反映了多層穿梭車倉儲系統(tǒng)在完成出庫任務任務時的各類設備表現，既有相互促進的效果，也有相互矛盾的地方。一方面，較長時間的提升機空閑時間降低了提升機的利用率，延長了出庫任務作業(yè)總時長；另一方面，較長時間的穿梭車等待時間造成該層出庫任務排隊等待，影響了穿梭車利用率。
對于以存儲為重點的面向倉儲行業(yè)的多層穿梭車倉儲系統(tǒng)而言，其出庫作業(yè)任務往往是根據出庫單據中的各品種貨物出庫數量，按照貨物“先進先出”(First-In-First-Out, FIFO)原則選擇出庫貨位，形成出庫任務隊列。這與前文所述的面向準時生產制（JIT)的生產性或訂單分揀性的多層穿梭車倉儲系統(tǒng)有著較大的區(qū)別。其出庫任務次序不再是由生產系統(tǒng)或訂單分揀系統(tǒng)“拉動”形成，而是對一個固定時間窗（Time Window)內所有出庫貨物的數量形成任務隊列，該任務隊列的次序是可以根據實際情況進行調整的。
面向倉儲行業(yè)的多層穿梭車倉儲系統(tǒng)，可以通過對一個時間窗口內的任務隊列進行次序調度，從而能有效的減少穿梭車等待時間和提升機空閑時間，增加穿梭車和提升機的利用率，提高貨物出入效率�；诖�，本章將從任務調度方面進行研究，以出庫完成時間、提升機空閑時間和穿梭車等待時間最短三個目標進行綜合優(yōu)化，建立出庫任務調度優(yōu)化模型，并釆用帶精英策略的非支配排序遺傳算法（NSGA-II)進行求解，某電力儀表倉庫驗證了該模型和算法。
..............................

第五章總論與展望

5.1工作總結與創(chuàng)新點
本文以多層穿梭車倉儲系統(tǒng)為研究對象，詳細闡述了傳統(tǒng)堆操機式的自動化立體倉庫在“柔性第一”的企業(yè)需求下的弊端和多層穿梭車倉儲系統(tǒng)的發(fā)展和應用，分析了多層穿梭車倉儲系統(tǒng)的設計原理和思路，建立了出庫作業(yè)時序模型，確定了影響倉儲作業(yè)效率的影響因素。在此基礎上，綜合運用開環(huán)排隊網絡、蟻群聚類算法、NSGA-II算法等工具，從儲位分配和任務調度兩個方面優(yōu)化多層穿梭車倉儲系統(tǒng)，對于提高多層穿梭車倉儲系統(tǒng)作業(yè)效率有重要意義，能夠為物流倉儲系統(tǒng)設計人員提供理論指導。本文主要的研宄內容和創(chuàng)新點如下：
1、描述了多層穿梭車倉儲系統(tǒng)的作業(yè)流程，建立了基于并行取貨、串行出庫的作業(yè)時序數學模型。通過對模型的分析，得到了影響出庫作業(yè)總時間的多個因素，并對其進行詳細闡述說明。
2、建立了多層穿梭車倉儲系統(tǒng)的開環(huán)排隊網絡模型，利用分解法分析穿梭車與提升機配合作業(yè)的各設備空閑時間長度和系統(tǒng)表現。建立了各品項的相關性矩陣并用其表示品項間距離。利用蟻群聚類方法對貨物進行聚類分析確定儲區(qū)劃分。再依照儲位優(yōu)化原則在二維平面內將儲區(qū)排列組合，解決多層穿梭車倉儲系統(tǒng)儲位分配優(yōu)化問題。
3、建立了以出庫作業(yè)時間、提升機空閑時間和穿梭車等待時間最短為目標的多層穿梭車倉儲系統(tǒng)的任務調度模型，將任務調度問題轉化為流水線并行多機成組調度問題，利用NSGA-II算法進行多目標優(yōu)化求解。 
...............................
參考文獻:

[1] 羅鍵,蘇海墩,何善君,吳長慶.  基于改進遺傳算法的自動小車存取系統(tǒng)升降機調度建模與優(yōu)化控制[J]. 廈門大學學報(自然科學版). 2010(03)
[2] 吳長慶,羅鍵,陳火國,莊進發(fā),彭彥卿.  基于Petri網的RGVs系統(tǒng)中環(huán)路死鎖研究[J]. 計算機科學. 2009(04)
[3] 羅鍵,鐘壽桂,吳長慶.  基于離散粒子群算法的AVS/RS貨位優(yōu)化[J]. 廈門大學學報(自然科學版). 2009(02)
[4] 羅鍵,程勇,吳長慶.  基于著色賦時Petri網的堆垛機建模與調度研究[J]. 計算機工程與應用. 2009(01)
[5] 吳長慶,何善君,羅鍵.  自動小車存取系統(tǒng)中軌道導引小車環(huán)路死鎖控制的研究[J]. 計算機集成制造系統(tǒng). 2008(09)
[6] 倪慶劍,邢漢承,張志政,王蓁蓁.  蟻群算法及其應用研究進展[J]. 計算機應用與軟件. 2008(08)
[7] Ya-hong HU1, Zheng-dong ZHU2, Wen-jing HSU3 (1College of Information Engineering, Zhejiang University of Technology, Hangzhou 310032, China) (2Department of Computer Science, Xi’an Jiaotong University, Xi’an 710049, China) (3School of Computer Engineering, Nanyang Technological University, Singapore 639798, Singapore).  AS/RS based yard and yard planning[J]. Journal of Zhejiang University(Science A:An International Applied Physics & Engineering Journal). 2008(08)
[8] 宋存利,時維國,黃明.  遺傳算法在并行多機調度問題中的應用[J]. 大連鐵道學院學報. 2004(02)
[9] 衣楊,汪定偉.  并行多機成組工作總流水時間調度問題[J]. 計算機集成制造系統(tǒng)-CIMS. 2001(07)
[10] 田國會,劉長有,林家恒,常發(fā)亮,賈磊,路飛,李曉磊,商允偉,李國鋒.  自動化立體倉庫若干優(yōu)化調度問題及其研究進展[J]. 山東工業(yè)大學學報. 2001(01)

 

 


本文編號：11735