王進(jìn)業(yè)，宋宇博

（蘭州交通大學(xué)機(jī)電技術(shù)研究所，甘肅蘭州 730070）

旁通式自動化立體倉庫揀選作業(yè)和出口選擇的組合優(yōu)化

王進(jìn)業(yè)，宋宇博

（蘭州交通大學(xué)機(jī)電技術(shù)研究所，甘肅蘭州 730070）

自動化立體倉庫系統(tǒng)是在計算機(jī)直接控制和管理下自動存取并實(shí)現(xiàn)綜合自動化管理貨物的多層倉庫存儲系統(tǒng)。旁通式自動化立體倉庫作為一種新興的立體倉庫，越來越多地應(yīng)用在需要快捷存取的場所。其中，堆垛機(jī)作業(yè)時間長短直接影響倉庫存儲效率的高低。為了提高旁通式自動化立體倉庫作業(yè)效率，分析旁通式自動化立體倉庫堆垛機(jī)行進(jìn)路線的特點(diǎn)，建立了同時考慮堆垛機(jī)出口選擇和揀選路徑的組合優(yōu)化模型。模型以一個揀選任務(wù)指令周期內(nèi)堆垛機(jī)行進(jìn)所花費(fèi)時間為目標(biāo)，同時對遺傳算法初始種群生成方法進(jìn)行改進(jìn)，用改進(jìn)后的遺傳算法對該模型揀選路徑優(yōu)化部分求解，將該階段結(jié)果的最末貨位作為下一優(yōu)化階段的初始點(diǎn)，采用最近鄰法尋找最佳出口位置。實(shí)驗(yàn)仿真和工程實(shí)際應(yīng)用表明該模型和算法是可行的、有效的。

工業(yè)企業(yè)經(jīng)營管理學(xué)；自動化立體倉庫；堆垛機(jī)；揀選作業(yè)；遺傳算法

作為自動化立體倉庫中新興的倉儲庫型——旁通式自動化立體倉庫（見圖1）以多出口、存取貨物快捷等特點(diǎn)，越來越多地應(yīng)用在機(jī)場貨站等需要快捷存取的場所。其作業(yè)過程如下：堆垛機(jī)C從停留位置出發(fā)，經(jīng)過行進(jìn)軌道D，依次從貨架A上將貨物取出存放在周轉(zhuǎn)箱內(nèi)，通過貨位輸送帶B將貨物運(yùn)出倉庫，貨物如需臨時周轉(zhuǎn)，則將貨物臨時存放在貨物臨時存放平臺E上。旁通式自動化立體倉庫揀選作業(yè)優(yōu)化關(guān)注指令周期內(nèi)堆垛機(jī)選擇作業(yè)總時間內(nèi)最短的行進(jìn)路線，包括合理安排貨物揀選順序和合理安排堆垛機(jī)載貨后的出口位置。傳統(tǒng)貫通式自動化立體倉庫是單出入口的倉庫，優(yōu)化揀選作業(yè)路徑時無需考慮出口的選擇，只需合理安排貨物揀選順序就能取得好的效果，但是旁通式自動化立體倉庫擁有多出貨口，若只考慮貨物揀選順序、不考慮出口選擇，將難以從整體上提高出庫效率。

關(guān)于揀選作業(yè)優(yōu)化，已有研究著重于傳統(tǒng)貫通式自動化立體倉庫的揀選優(yōu)化。熊芳敏［1］等運(yùn)用蟻群優(yōu)化算法解決物流中心揀貨路徑問題。馬清悅［2］等運(yùn)用啟發(fā)式算法解決以揀貨時間最小化為目標(biāo)的數(shù)學(xué)模型。劉劍［3］等在運(yùn)用遺傳算法［4］解決固定貨架子系統(tǒng)中堆垛機(jī)揀選作業(yè)優(yōu)化調(diào)度問題的同時，加入任務(wù)的等待時間，以解決個別任務(wù)等待時間過長的問題。楊朋［5］等建立了同時考慮貨位分配和揀選路徑優(yōu)化的集成優(yōu)化模型，并設(shè)計了兩階段禁忌搜索算法來解決該問題。楊玲［6］等利用蟻群算法結(jié)合遺傳算法來解決固定貨架揀選問題。計三有［7］等建立了以巷道堆垛機(jī)揀選作業(yè)運(yùn)行時間最短為目標(biāo)的數(shù)學(xué)模型，采用蟻群算法進(jìn)行優(yōu)化求解，得出最短運(yùn)行時間。佟芙慧［8］將貨品類別劃分不同庫區(qū)，采用啟發(fā)式動態(tài)規(guī)劃調(diào)度算法對立體倉庫問題進(jìn)行優(yōu)化研究。劉楊［9］按照貨位優(yōu)化存儲策略對貨架進(jìn)行合理分區(qū)，并通過遺傳算法對其進(jìn)行優(yōu)化。李夢婷［10］通過仿真軟件尋找立體倉儲模型的缺陷，并對立體倉庫模型進(jìn)行改進(jìn)，用遺傳算法求解，得到模型改進(jìn)后的優(yōu)化方案。CHANG［11］等對自動化立體倉庫建立多目標(biāo)優(yōu)化模型，并用遺傳算法進(jìn)行求解。de KOSTER［12］等運(yùn)用分枝定界法將需要揀選的貨物分為不同批次揀選，依次建立優(yōu)化模型。葛永國［13］等、張泉［14］、顧嘉［15］等、楊素梅［16］等也均對立體倉庫進(jìn)行了研究。以上文獻(xiàn)均是以傳統(tǒng)貫通式自動化立體倉庫為研究對象，而以類似旁通式自動化立體倉庫的多出口立體倉庫為研究對象，從組合優(yōu)化出發(fā)對貨物出口和貨物揀選路徑同時優(yōu)化的文獻(xiàn)似乎還未見報道。

本文針對多出口立體倉庫的特點(diǎn)，以旁通式自動化立體倉庫為研究對象，從組合優(yōu)化的角度對旁通式自動化立體倉庫的貨物揀選作業(yè)路徑和出庫貨口選擇問題進(jìn)行研究。

圖1 旁通式自動化立體倉庫平面簡圖Fig.1 Sketch of the bypass type automatic warehouse

1 問題描述

假設(shè)某旁通式自動化立體倉庫有m個出口，在不超過堆垛機(jī)載貨量的情況下，堆垛機(jī)經(jīng)歷n個貨位點(diǎn)并將其中所需貨物取出，以揀選作業(yè)方式完成該取貨任務(wù)后，堆垛機(jī)有m個可選擇的出口將貨物運(yùn)出倉庫，同時堆垛機(jī)在進(jìn)行揀選作業(yè)的行進(jìn)路線有n！m種選擇。每次堆垛機(jī)執(zhí)行揀選作業(yè)指令時幾乎都將面臨選擇堆垛機(jī)出口和揀選路徑設(shè)計問題，研究單條指令周期是提高存取系統(tǒng)整體效率的基礎(chǔ)。本文將同時考慮堆垛機(jī)出口選擇和揀選路徑規(guī)劃2個優(yōu)化問題，以1個揀選任務(wù)指令周期內(nèi)堆垛機(jī)的行進(jìn)路程和所花費(fèi)時間為目標(biāo)進(jìn)行優(yōu)化研究。

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

2.1 基本假設(shè)

堆垛機(jī)進(jìn)行揀選作業(yè)取貨過程如圖2所示，堆垛機(jī)依次經(jīng)過B1，B4，B6，B7，…，Bn等貨位點(diǎn)，并從am處將貨物運(yùn)出倉庫。固定貨架及堆垛機(jī)運(yùn)行參數(shù)作如下設(shè)定。

設(shè)定1：操作者對某一貨位的揀選時間固定，不隨該貨位在揀選路徑中的揀選順序不同而變化。

設(shè)定2：堆垛機(jī)在水平方向速度為vx，垂直方向速度為vy，且這2個方向上的運(yùn)動獨(dú)立，運(yùn)行速度恒定，忽略堆垛機(jī)啟動時間和制動時間。

設(shè)定3：旁通式自動化立體倉庫有m個出口，出口間距為常數(shù)w。

設(shè)定4：貨位間距為常數(shù)，貨格高度為h，貨格寬度為b。

設(shè)定5：貨物包裝規(guī)則，周轉(zhuǎn)貨箱裝箱能力僅與待裝貨物體積和周轉(zhuǎn)貨箱體積有關(guān)。

設(shè)定6：設(shè)入口處為I/0，坐標(biāo)為（0，0）。

圖2 遍歷貨位平面圖Fig.2 Sketch of ergodic space

通過圖2及以上假設(shè)可知，堆垛機(jī)由貨位點(diǎn)i運(yùn)行到貨位點(diǎn)j的時間損耗為

由貨位點(diǎn)i運(yùn)行到貨位點(diǎn)j水平方向和垂直方向走過的路程之和為

式中：（xi，yi）和（xj，yj）分別為貨位點(diǎn)i和貨位點(diǎn)j的位置坐標(biāo)。

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

優(yōu)化旁通式自動化立體倉庫揀選出庫作業(yè)任務(wù)的目標(biāo)是堆垛機(jī)運(yùn)行時間最短，需考慮2個過程：揀選作業(yè)路徑優(yōu)化和堆垛機(jī)出庫口的選擇。在任何一條揀選作業(yè)任務(wù)指令周期j內(nèi)，旁通式自動化立體倉庫揀選作業(yè)路徑優(yōu)化和出貨口的確定屬于組合優(yōu)化問題，增加若干條件可抽象為下述整數(shù)規(guī)劃模型，待取貨位確定后，將待確定出口和堆垛機(jī)入口連接，將其虛擬為堆垛機(jī)最后所走路線，模型即轉(zhuǎn)化為求解一個考慮取貨路線和出口選擇的旅行售貨商問題（TSP）。

決策變量：

目標(biāo)函數(shù)：

約束條件：

式中：Tj為堆垛機(jī)完成指令周期j的行程時間；Dj為堆垛機(jī)完成指令周期j所走路程；p為第p個貨位；n為貨位總個數(shù)；qi為第i個貨位中存放的貨物體積，0＜qi≤Q；Q為周轉(zhuǎn)箱總體積。

式（3）可確定堆垛機(jī)運(yùn)行時間最短；式（4）可確定水平方向和垂直方向走過的總路程最短；式（5）可保證分配的貨物全部遍歷到；式（6）可保證訪問某一貨位（I/0除外）后，必須要從該貨位離開；式（7）可保證每次作業(yè)揀選的貨物體積不能大于周轉(zhuǎn)貨箱的體積；式（8）是消除子環(huán)。

根據(jù)取貨隊(duì)列情況劃分的指令周期集合中，上述模型在每一個指令周期都需要求解1次，相鄰指令周期序列取貨貨位集合和最佳出口位置會不斷的更新，受限于篇幅，多指令周期的優(yōu)化將另文描述，本文只集中在基本優(yōu)化單元中單個指令周期的路徑優(yōu)化和出口選擇的優(yōu)化上。

3 算法選擇

通過對堆垛機(jī)揀選路徑優(yōu)化的數(shù)學(xué)模型分析，采用遺傳算法可較快地獲得堆垛機(jī)作業(yè)路徑優(yōu)化問題的最優(yōu)或次優(yōu)解，但是遺傳算法的局部搜索能力較差，導(dǎo)致單純的遺傳算法比較費(fèi)時，在進(jìn)化后期搜索效率低，易產(chǎn)生早熟收斂的問題，對初始種群很敏感，初始種群的選擇常常直接影響解的質(zhì)量和算法效率。針對以上問題，本文采用遺傳算法來求解上述模型，結(jié)合自適應(yīng)鄰域法（adaptive neighborhood method，ANM）對遺傳算法的初始化種群形成和部分選擇進(jìn)行改進(jìn)［17］。對于最佳出口選擇問題，則以上階段優(yōu)化結(jié)果為初始點(diǎn)，采用最近鄰法尋找最佳出口位置。

3.1 自適應(yīng)鄰域法

針對類似TSP問題的堆垛機(jī)揀選路徑優(yōu)化問題，最自然的啟發(fā)尋優(yōu)方式應(yīng)該是最近鄰法。圖3顯示了從貨位點(diǎn)C8出發(fā)，采用最近鄰法形成的路徑，其中包含了貨位點(diǎn)C3－C2－C6－C5的局部最短路徑信息，但路徑中存在交叉路徑，因此該種方法求得的路徑并非最優(yōu)路徑。但是，就選擇出貨口而言，每臺堆垛機(jī)在完成一個指令周期j后會從眾多出口中尋找一個最近出口，選擇最近鄰法將會很好地滿足這一優(yōu)化。

圖3 從C8出發(fā)的最近鄰法路徑Fig.3 Path of nearest neighbor method starting fromC8

在圖4中仍假定選擇從貨位點(diǎn)C8出發(fā)為例說明自適應(yīng)鄰域法。與貨位點(diǎn)C8最近的貨位點(diǎn)是C3。此時把C8設(shè)為圓心，以半徑r（C8到C3的距離）形成內(nèi)圓，以半徑βr形成外圓（βr＞r），構(gòu)成一環(huán)形區(qū)域（見圖4陰影區(qū)），這個區(qū)域成為貨位點(diǎn)C8的鄰域。在圖4中，C8鄰域中有C3，C4和C73個貨位點(diǎn)，為了克服最近鄰法的缺陷，C8后一個貨位點(diǎn)將在這3個貨位點(diǎn)中隨機(jī)選擇。以此類推，直到所有的貨位點(diǎn)都去過，這種方法稱為鄰域法（neighborhood method，NM），圖5為應(yīng)用鄰域法求解上例的結(jié)果之一。

在鄰域法中，βr的數(shù)值對形成路徑的樣本多樣性會產(chǎn)生很大的影響：從局部路徑上看，β值越小，越符合眼前利益，但從全局來看可能會遠(yuǎn)遠(yuǎn)偏離最優(yōu)路徑；從全局來看，β值越大，數(shù)量龐大的可選擇的樣本會擁有多樣性，但是會丟失很多可進(jìn)行局部優(yōu)化的信息。

為了平衡局部缺陷和全局缺陷，讓表示鄰域范圍的外圓半徑系數(shù)在1和β之間隨機(jī)變化，就形成了自適應(yīng)鄰域法。在樣本數(shù)量充足時，由ANM初始化種群所產(chǎn)生的樣本中既存在局部優(yōu)化的路徑信息，又存在全局優(yōu)化的路徑信息，這些優(yōu)化信息被智能優(yōu)化算法捕獲，有助于智能算法收斂得到全局最優(yōu)解。

ANM算法在堆垛機(jī)揀選路徑優(yōu)化中的描述如下。

圖4 鄰域法原理圖Fig.4 NM principle diagram

圖5 從C8出發(fā)的鄰域的優(yōu)化路徑之一Fig.5 One of the optimization path of the neighborhood method starting fromC8

1）隨機(jī)選擇堆垛機(jī)從貨位點(diǎn)i出發(fā)。

2）形成未到過的貨位點(diǎn)集合Z＝｛1，2，…，i－1，i＋1，…，n｝。

3）在集合Z中尋找貨位點(diǎn)k，滿足di，k＝min｛dij∶j∈Z｝。

4）在集合Z中尋找子集合G，G中元素滿足di，k≤di，m≤rand（1，β）di，k，m∈M；其中rand（1，β）表示在1和β之間產(chǎn)生的隨機(jī)數(shù)。

5）在集合Z中隨機(jī)抽取選擇貨位點(diǎn)f，作為下一個貨位點(diǎn)，將G清空，從Z中移除貨位點(diǎn)t。

6）如果Z集合不空，令i＝t，跳回3）；否則搜索結(jié)束。

3.2 遺傳算法

3.2.1 染色體編碼設(shè)計

染色體編碼是遺傳算法的基礎(chǔ)工作，是問題的狀態(tài)空間與遺傳算法的碼空間的映射，編碼方法的選擇將直接影響遺傳算子運(yùn)算方法。本文染色體采用與備選貨位集合耦合映射的二進(jìn)制編碼方法，編碼分多個片段，由2層組成，上層是需揀選貨位集合的編號，下層采用0-1編碼，編號0為不需要訪問的貨位，編號1為需訪問揀選的貨位，編碼的長度為周期指令所有貨位的數(shù)量總和。貨位選擇的數(shù)量（即編碼值為1的個數(shù)）由堆垛機(jī)周轉(zhuǎn)箱的容積確定，即需要滿足約束條件（7）。圖6所示例子中表示堆垛機(jī)在單位指令周期的貨位選擇方案，堆垛機(jī)要遍歷所有編碼為1的貨物并取出所需貨物量。

圖6 染色體的編碼設(shè)計Fig.6 Code for design of chromosomes

3.2.2 種群初始化

為了避免因隨機(jī)法初始化種群而產(chǎn)生大量不可行解，同時考慮了上述編碼結(jié)構(gòu)和編碼取值的約束，本文采用ANM法初始化種群。在3.1小節(jié)中已詳細(xì)介紹ANM方法，其初始化種群的思想如下：首先隨機(jī)生成第1個需揀選的貨位點(diǎn)i，從i出發(fā)尋找最近的一個貨位點(diǎn)i＋1，以貨位點(diǎn)i為圓心，di＋1，i為半徑，作一個內(nèi)圓，以βdi＋1，i為半徑作外圓，在這個（β－1）di＋1，i的圓環(huán)內(nèi)隨機(jī)選擇一個貨位點(diǎn)j，再從貨位點(diǎn)j出發(fā)按上述方法選擇下一個貨位點(diǎn)，直到形成一個遍歷的路徑。對于β的取值，本文參照汪金剛［18］等的β取值方法，取經(jīng)驗(yàn)值為1.25。

3.2.3 適應(yīng)度函數(shù)

遺傳算法滿意解的產(chǎn)生過程是模擬生物遺傳進(jìn)化中優(yōu)勝劣汰的過程，用適應(yīng)度值作為其優(yōu)勝劣汰的指標(biāo)。適應(yīng)度函數(shù)通常是所求問題的目標(biāo)函數(shù)做一定轉(zhuǎn)換而來，本文的目標(biāo)函數(shù)為式（3）和式（4），為了突出運(yùn)行時間和行進(jìn)路程在適應(yīng)度中的不同比例，在設(shè)定適應(yīng)度函數(shù)時加入相應(yīng)的系數(shù)W1和W2。

計算每個個體的適應(yīng)度通過式（9）確定。

式中：

式（9）中W1和W2分別表示堆垛機(jī)的運(yùn)行時間和行進(jìn)路程在適應(yīng)值函數(shù)中的重要性比例，式（10）表示堆垛機(jī)執(zhí)行完指令周期j的運(yùn)行時間，式（11）表示堆垛機(jī)執(zhí)行完指令周期j的行進(jìn)路程。

3.2.4 種群選擇

選擇方法：采用輪盤賭方式選擇上代90%的個體，剩下10%采用ANM產(chǎn)生新個體進(jìn)行補(bǔ)充［19］。本步驟中選擇算子的改進(jìn)對于發(fā)揮ANM的作用是至關(guān)重要的。若僅僅在種群初始化時采用ANM法，其產(chǎn)生的樣本數(shù)是有限的，種群所包含的優(yōu)化路徑信息量也是有限的。而在每代加入的10%ANM生成個體，其線路長度未必優(yōu)于被替換個體的，這個策略就增加了種群的多樣性，充分的ANM樣本才能挖掘局部和全局最優(yōu)路徑信息。這一操作彌補(bǔ)了種群規(guī)模受限、信息量不足的缺點(diǎn)，也可以預(yù)防遺傳算法過早收斂。

3.2.5 交叉算子和變異算子

交叉操作是模擬生物界有性繁殖中基因重組的過程，也是種群進(jìn)化的核心步驟，其作用是將父代的優(yōu)良基因通過有性繁殖遺傳到子代種群中，是產(chǎn)生優(yōu)良新個體的主要手段，是決定遺傳算法全局搜索能力的關(guān)鍵因素。交叉算子設(shè)計的主要內(nèi)容是交叉點(diǎn)位置的確定和部分基因信息的交換。常見的交叉方法有單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉和均勻交叉等［12］，為了避免產(chǎn)生不可行解，本文采取多點(diǎn)交叉方式，如圖7所示。首先，每隔4個貨位劃分1個基因片段，共可劃分R個，然后將待交配的2個父代每隔1個基因片段與對應(yīng)片段進(jìn)行交換，剩余基因片段不變，產(chǎn)生2個子代。

圖7 交叉操作Fig.7 Crossover operation

變異操作是模擬自然界生物進(jìn)化中個體基因突變情況，是遺傳算法中保持種群多樣性的一個重要途徑。變異操作的主要內(nèi)容是變異點(diǎn)位置的確定和基因值的替換，其作用是能增加遍歷性，防止遺傳算法早熟。常見的變異算子有倒位、插入、移位等［20］。本文采用倒位變異的方法，隨機(jī)選擇R個基因片段中的1個，倒位排列對應(yīng)片段的基因值，在保證個體可行的前提下實(shí)現(xiàn)變異操作（如圖8所示）。

圖9為遺傳算法的流程圖，由圖9可知遺傳算法的基本步驟和所需參數(shù)。

以上述算法得到的結(jié)果的最末貨位點(diǎn)為初始點(diǎn)，采用最近鄰法尋找最佳出口位置。

圖8 變異操作Fig.8 Mutation operation

圖9 遺傳算法流程圖Fig.9 Genetic algorithm flow chart

4 仿真試驗(yàn)結(jié)果

仿真環(huán)境（個人計算機(jī)）如下。

操作系統(tǒng)：Windows 7；

內(nèi)存：4GB；

CPU：2.5GHz；

仿真工具：matlab 7.0。

驗(yàn)證不同貨位量的情況下本文所建模型和所選用算法的有效性。

貨架及堆垛機(jī)運(yùn)行參數(shù)隨機(jī)設(shè)定如下：

b＝1m，h＝1m，vx＝1m/s，vy＝2m/s，Q＝80m3，n＝100，m＝9，w＝6m，Pc＝0.4，Pm＝0.07，最大迭代次數(shù)MaxGeneration＝ 1 000，W1＝0.07，W2＝0.01。保證的情況下，隨機(jī)生成需揀選的20個貨位、30個貨位、40個貨位、50個貨位、60個貨位的貨單各1條，每條貨單分別以隨機(jī)揀選作業(yè)方式和改進(jìn)后的遺傳算法揀選作業(yè)方式各運(yùn)行30次，計算優(yōu)化前后的平均運(yùn)行時間和平均運(yùn)行路程，所得結(jié)果見表1。結(jié)果表明，算法在貨位量不同的情況下均能有效縮短堆垛機(jī)的運(yùn)行時間Tj、運(yùn)行路程Dj和計算時間，計算時間為改進(jìn)后的遺傳算法計算時間，是判斷算法改進(jìn)是否合理的度量單位。當(dāng)貨位數(shù)為20時，堆垛機(jī)運(yùn)行時間約能改進(jìn)36.6%，運(yùn)行路程約能改進(jìn)32.8%，計算時間約能改進(jìn)31.5%。當(dāng)貨位數(shù)量增加至60時，堆垛機(jī)運(yùn)行時間約能改進(jìn)15.7%，運(yùn)行路程約能改進(jìn)17.3%，計算時間約能改進(jìn)69.5%。結(jié)果表明，隨著貨位增加，運(yùn)行時間和運(yùn)行路程的改進(jìn)量度隨貨位量的增加有所降低，這與取貨周期變長以及搜索范圍增大導(dǎo)致搜索的復(fù)雜性增加有關(guān)。計算時間的改進(jìn)比例隨著貨位量的增加而大大增加，表明了本文所用的改進(jìn)算法非常適用于旁通式自動化立體倉庫揀選作業(yè)優(yōu)化。

表1 揀選作業(yè)優(yōu)化前后性能比較Tab.1 Performance indexes before and after the order picking optimization

驗(yàn)證ANM改進(jìn)遺傳算法初始化種群和部分選擇的有效性：取Pc＝0.5，Pm＝0.03，MaxGeneration＝ 1 000，Q＝100m3。為了便于比較，不考慮路徑優(yōu)化，取W1＝0.02，W2＝0，保證的情況下，隨機(jī)生成需揀選的20個貨位、30個貨位、40個貨位、50個貨位、60個貨位的貨單各1條，分別用隨機(jī)法和ANM法初始化遺傳算法的種群，以揀選作業(yè)方式將以上各貨單運(yùn)行30次，計算優(yōu)化前后的平均運(yùn)行時間，所得結(jié)果見表2。當(dāng)貨位數(shù)量為60的時候，計算時間的改進(jìn)量能達(dá)到73.2%，表明改進(jìn)后的算法在貨位量不同的情況下均能有效縮短堆垛機(jī)的運(yùn)行時間和計算時間，計算時間的改進(jìn)效果隨著貨位的增加而愈加顯著。對比結(jié)果有效地驗(yàn)證了改進(jìn)算法的實(shí)用性和優(yōu)越性，為旁通式自動化立體倉庫實(shí)際的揀選作業(yè)作業(yè)調(diào)度提供了有效的決策工具。

表2 種群初始化方法性能比較Tab.2 Performance comparison of population initialization methods

5 結(jié) 語

由于揀選作業(yè)和堆垛機(jī)出口的選擇直接影響旁通式自動化立體倉庫的工作效率，本文詳細(xì)分析了旁通式自動化立體倉庫堆垛機(jī)揀選作業(yè)路徑和出口選擇的特點(diǎn)，合理地建立了模型，并通過對初始種群改進(jìn)后的遺傳算法來計算堆垛機(jī)的最優(yōu)揀選路線，以所得到的最優(yōu)路線的最末貨位為下一階段優(yōu)化的起始點(diǎn)，用最近鄰法尋找到最佳出口位置。經(jīng)仿真證明，本文所采取的優(yōu)化方法是穩(wěn)定有效的，能極大地縮短堆垛機(jī)揀選作業(yè)的運(yùn)行時間和運(yùn)行路程，并能尋找到最佳的出口位置，為提高旁通式自動化立體倉庫的工作效率提供了保障。

［1］ 熊芳敏，岑宇森，曾碧清.運(yùn)用蟻群算法解決物流中心揀選貨路徑問題［J］.華南師范大學(xué)學(xué)報，2010，4（2）：50-54.XIONG Fangmin，CEN Yusen，ZENG Biqing.Using ant colony algorithm to solve path choose goods logistics center［J］.Journal of South China Normal University，2010，4（2）：50-54.

［2］ 馬清悅，張紀(jì)會，宋曉鵬，等.基于啟發(fā)式算法的自動化立體倉庫揀貨路徑優(yōu)化研究［J］.青島大學(xué)學(xué)報，2012，27（3）：31-34.MA Qingyue，ZHANG Jihui，SONG Xiaopeng，et al.The research of automatic warehouse picking route optimization based on heuristic algorithm［J］.Journal of Qingdao University，2012，27（3）：31-34.

［3］ 劉劍，王鑫，張冬梅，等.基于遺傳算法的立體倉庫堆垛機(jī)路徑優(yōu)化［J］.沈陽建筑大學(xué)學(xué)報，2010，26（5）：1006-1011.LIU Jian，WANG Xin，ZHANG Dongmei，et al.Stacker path optimization based on genetic algorithm［J］.Journal of Shenyang Construction University，2010，26（5）：1006-1011.

［4］ 解丹蕊，薛惠鋒，韓建新.基于遺傳算法的西安郵政配送路線優(yōu)化研究［J］.河北科技大學(xué)學(xué)報，2008，29（3）：214-218.XIE Danrui，XUE Huifeng，HAN Jianxin.Study on optimization of Xi＇an post logistics distribution routing by genetic algorithm［J］.Journal of Hebei University of Science and Technology，2008，29（3）：214-218.

［5］ 楊朋，繆立新，戚銘堯，等.多載具自動化存取系統(tǒng)貨位分配和揀選路徑集成優(yōu)化［J］.清華大學(xué)學(xué)報，2011，51（2）：261-266.YANG Peng，MIAO Lixin，QI Mingyao，et al.With automatic access system storage location assignment and picking path integrated optimization of multi carrier［J］.Journal of Tsinghua University，2011，51（2）：261-266.

［6］ 楊玲，關(guān)志偉.自動化立體倉庫揀選路徑優(yōu)化問題研究［J］.中國制造業(yè)信息化，2011，40（7）：47-50.YANG Ling，GUAN Zhiwei.Automated warehouse picking path optimization problem research［J］.China Manufacturing Informatization，2011，40（7）：47-50.

［7］ 計三有，陳厚松.基于蟻群算法的立體倉庫揀選作業(yè)優(yōu)化［J］.武漢理工大學(xué)學(xué)報，2010，32（23）：69-71.JI Sanyou，CHEN Housong.Optimize the warehouse order picking based on ant colony algorithm［J］.Journal of Wuhan University ofTechnology，2010，32（23）：69-71.

［8］ 佟芙慧.自動化立體倉庫的貨位優(yōu)化與管理［D］.沈陽：沈陽大學(xué)，2013.TONG Fuhui.Slotting Optimization and Management of Automated Warehouse［D］.Shenyang：Shenyang University，2013.

［9］ 劉揚(yáng).自動化立體倉庫調(diào)度的優(yōu)化研究［D］.西安：長安大學(xué)，2013.LIU Yang.Study on Optimization of Automated Warehouse Scheduling［D］.Xi’an：Chang’an University，2013.

［10］李夢婷.自動化立體倉庫物流系統(tǒng)仿真與優(yōu)化研究［D］.沈陽：沈陽工業(yè)大學(xué)，2014.LI Mengting.Study on the Simulation and Optimization of Automated Warehouse Logistics System［D］.Shenyang：Shenyang University of Technology，2014.

［11］CHANG Faliang，LIU Zengxiao.Research on order picking optimization problem of automated warehouse［J］.Systems Engineering Theory ＆Practice，2007，27（2）：139-143.

［12］DE KOSTER R，le DUC T，ROODBERGEN K J.Design and control of warehouse order picking：A literature review［J］.European Journal of Operational Research，2007，182（2）：481-501.

［13］葛永國，韓提文，吳愛國.AS/RS中輸送系統(tǒng)的PLC程序設(shè)計［J］.河北科技大學(xué)學(xué)報，2003，24（4）：35-39.GE Yongguo，HAN Tiwen，WU Aiguo.PLC program design of the transporting system in AS/RS［J］.Journal of Hebei University of Science and Technology，2003，24（4）：35－39.

［14］張泉.淺談自動化立體倉庫管理系統(tǒng)［J］.河北工業(yè)科技，2006，23（2）：82-84.ZHANG Quan.Explaination on the automatic solid warehouse management system［J］.Hebei Journal of Industrial Science and Technology，2006，23（2）：82-84.

［15］顧嘉，張華，李順，等.立體倉庫出入庫仿真與優(yōu)化技術(shù)［J］.南昌大學(xué)學(xué)報（工科版），2013，35（4）：369-374.GU Jia，ZHANG Hua，LI Shun，et al.Simulation and optimization techniques of storage and retrieval of AS/RS［J］.Journal of Nanchang University（Engineering ＆Technology），2013，35（4）：369-374.

［16］楊素梅，馬百雪.立體倉庫PLC控制系統(tǒng)設(shè)計［J］.可編程控制器與工廠自動化，2013（5）：102-104.YANG Sumei，MA Baixue.Design of multi-layered warehouse PLC control device［J］.Programmable Controller ＆Factory Automation，2013（5）：102-104.

［17］羅辭勇，盧斌，劉飛.一種求解TSP初始化種群問題的鄰域法［J］.重慶大學(xué)學(xué)報，2009，32（11）：1311-1315.LUO Ciyong，LU Bin，LIU Fei.Neighborhood method for population initialization of TSP［J］.Journal of Chongqing University，2009，32（11）：1311-1315.

［18］汪金剛，羅辭勇.求解TSP問題的自適應(yīng)鄰域遺傳算法［J］.計算機(jī)工程與應(yīng)用，2010，46：20-24.WANG Jingang，LUO Ciyong.Adaptive neighborhood genetic algorithm for solving TSP problem［J］.Computer Engineering and Applications，2010，46：20-24.

［19］LIU G Y，HE Y，F(xiàn)ANG Y H，et al.A novel adaptive search strategy of intensification and diversification in tabu search［J］.Proceedings of 2003International Conference On Neural Networks＆Signal Processing Proceedings，2003（1/2）：428-431.

［20］李彬彬.基于遺傳算法的多目標(biāo)生產(chǎn)作業(yè)調(diào)度研究［D］.上海：東華大學(xué)，2014.LI Binbin.Research on Multi Objective Scheduling Based on Genetic Algorithm［D］.Shanghai：Donghua University，2014.

Combinatorial optimization of order picking and export choosing for bypass type automatic stereoscopic warehouse

WANG Jinye，SONG Yubo
（Mechanical and Electronic Technology Institute，Lanzhou Jiaotong University，Lanzhou，Gansu 730070，China）

The automatic stereo warehouse system is a storage system with multi-storey warehouse，by which the automation access and integrated automation management are realized in the computer＇s direct control and management.The emerging，bypass automatic stereo warehouse has gained more and more application in rapid access.The stacker＇s working time directly affects the efficiency of the warehouse.To improve the bypass automatic warehouse efficiency and analyze the stacker route，an integrated optimization model considering the export selection and the path picking is established.The model aims to the picking task cycle and develops the population＇s generating method of genetic algorithm，then solves the optimization model.The last section in this stage is the initial point of the next optimization stage，using the nearest neighbor method to find the optimal export location.Simulation and practical application show that the model and the algorithm are feasible and effective.

industrial enterprise operation management；automatic stereoscopic warehouse；stacker；order picking；genetic algorithm

TH692；F253

A

1008-1542（2015）01-0036-09

10.7535/hbkd.2015yx01009

2014-06-23；

2014-09-16；責(zé)任編輯：馮 民

國家科技支撐計劃項(xiàng)目（2012BAH20F05）；甘肅省自然科學(xué)基金（1310RJZA056）

王進(jìn)業(yè)（1989—），男，河北衡水人，碩士研究生，主要從事機(jī)電設(shè)備控制與監(jiān)測技術(shù)方面的研究。

宋宇博講師。E-mail：495662041＠qq.com

王進(jìn)業(yè)，宋宇博.旁通式自動化立體倉庫揀選作業(yè)和出口選擇的組合優(yōu)化［J］.河北科技大學(xué)學(xué)報，2015，36（1）：36-44.

WANG Jinye，SONG Yubo.Combinatorial optimization of order picking and export choosing for bypass type automatic stereoscopic warehouse［J］.Journal of Hebei University of Science and Technology，2015，36（1）：36-44.