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

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

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

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

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

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

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

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

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

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

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

圖1 旁通式自動(dòng)化立體倉(cāng)庫(kù)平面簡(jiǎn)圖Fig.1 Sketch of the bypass type automatic warehouse

1 問(wèn)題描述

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

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

2.1 基本假設(shè)

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

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

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

設(shè)定3：旁通式自動(dòng)化立體倉(cāng)庫(kù)有m個(gè)出口，出口間距為常數(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

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

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

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

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

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

決策變量：

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

約束條件：

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

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

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

3 算法選擇

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

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

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

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

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

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

為了平衡局部缺陷和全局缺陷，讓表示鄰域范圍的外圓半徑系數(shù)在1和β之間隨機(jī)變化，就形成了自適應(yīng)鄰域法。在樣本數(shù)量充足時(shí)，由ANM初始化種群所產(chǎn)生的樣本中既存在局部?jī)?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）形成未到過(guò)的貨位點(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，作為下一個(gè)貨位點(diǎn)，將G清空，從Z中移除貨位點(diǎn)t。

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

3.2 遺傳算法

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

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

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

3.2.2 種群初始化

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

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

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

計(jì)算每個(gè)個(gè)體的適應(yīng)度通過(guò)式（9）確定。

式中：

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

3.2.4 種群選擇

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

3.2.5 交叉算子和變異算子

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

圖7 交叉操作Fig.7 Crossover operation

變異操作是模擬自然界生物進(jìn)化中個(gè)體基因突變情況，是遺傳算法中保持種群多樣性的一個(gè)重要途徑。變異操作的主要內(nèi)容是變異點(diǎn)位置的確定和基因值的替換，其作用是能增加遍歷性，防止遺傳算法早熟。常見(jiàn)的變異算子有倒位、插入、移位等［20］。本文采用倒位變異的方法，隨機(jī)選擇R個(gè)基因片段中的1個(gè)，倒位排列對(duì)應(yīng)片段的基因值，在保證個(gè)體可行的前提下實(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)境（個(gè)人計(jì)算機(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個(gè)貨位、30個(gè)貨位、40個(gè)貨位、50個(gè)貨位、60個(gè)貨位的貨單各1條，每條貨單分別以隨機(jī)揀選作業(yè)方式和改進(jìn)后的遺傳算法揀選作業(yè)方式各運(yùn)行30次，計(jì)算優(yōu)化前后的平均運(yùn)行時(shí)間和平均運(yùn)行路程，所得結(jié)果見(jiàn)表1。結(jié)果表明，算法在貨位量不同的情況下均能有效縮短堆垛機(jī)的運(yùn)行時(shí)間Tj、運(yùn)行路程Dj和計(jì)算時(shí)間，計(jì)算時(shí)間為改進(jìn)后的遺傳算法計(jì)算時(shí)間，是判斷算法改進(jìn)是否合理的度量單位。當(dāng)貨位數(shù)為20時(shí)，堆垛機(jī)運(yùn)行時(shí)間約能改進(jìn)36.6%，運(yùn)行路程約能改進(jìn)32.8%，計(jì)算時(shí)間約能改進(jìn)31.5%。當(dāng)貨位數(shù)量增加至60時(shí)，堆垛機(jī)運(yùn)行時(shí)間約能改進(jìn)15.7%，運(yùn)行路程約能改進(jìn)17.3%，計(jì)算時(shí)間約能改進(jìn)69.5%。結(jié)果表明，隨著貨位增加，運(yùn)行時(shí)間和運(yùn)行路程的改進(jìn)量度隨貨位量的增加有所降低，這與取貨周期變長(zhǎng)以及搜索范圍增大導(dǎo)致搜索的復(fù)雜性增加有關(guān)。計(jì)算時(shí)間的改進(jìn)比例隨著貨位量的增加而大大增加，表明了本文所用的改進(jìn)算法非常適用于旁通式自動(dòng)化立體倉(cāng)庫(kù)揀選作業(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個(gè)貨位、30個(gè)貨位、40個(gè)貨位、50個(gè)貨位、60個(gè)貨位的貨單各1條，分別用隨機(jī)法和ANM法初始化遺傳算法的種群，以揀選作業(yè)方式將以上各貨單運(yùn)行30次，計(jì)算優(yōu)化前后的平均運(yùn)行時(shí)間，所得結(jié)果見(jiàn)表2。當(dāng)貨位數(shù)量為60的時(shí)候，計(jì)算時(shí)間的改進(jìn)量能達(dá)到73.2%，表明改進(jìn)后的算法在貨位量不同的情況下均能有效縮短堆垛機(jī)的運(yùn)行時(shí)間和計(jì)算時(shí)間，計(jì)算時(shí)間的改進(jìn)效果隨著貨位的增加而愈加顯著。對(duì)比結(jié)果有效地驗(yàn)證了改進(jìn)算法的實(shí)用性和優(yōu)越性，為旁通式自動(dòng)化立體倉(cāng)庫(kù)實(shí)際的揀選作業(yè)作業(yè)調(diào)度提供了有效的決策工具。

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

5 結(jié) 語(yǔ)

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

［1］ 熊芳敏，岑宇森，曾碧清.運(yùn)用蟻群算法解決物流中心揀選貨路徑問(wèn)題［J］.華南師范大學(xué)學(xué)報(bào)，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ì)會(huì)，宋曉鵬，等.基于啟發(fā)式算法的自動(dòng)化立體倉(cāng)庫(kù)揀貨路徑優(yōu)化研究［J］.青島大學(xué)學(xué)報(bào)，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］ 劉劍，王鑫，張冬梅，等.基于遺傳算法的立體倉(cāng)庫(kù)堆垛機(jī)路徑優(yōu)化［J］.沈陽(yáng)建筑大學(xué)學(xué)報(bào)，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é)報(bào)，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］ 楊朋，繆立新，戚銘堯，等.多載具自動(dòng)化存取系統(tǒng)貨位分配和揀選路徑集成優(yōu)化［J］.清華大學(xué)學(xué)報(bào)，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)志偉.自動(dòng)化立體倉(cāng)庫(kù)揀選路徑優(yōu)化問(wèn)題研究［J］.中國(guó)制造業(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］ 計(jì)三有，陳厚松.基于蟻群算法的立體倉(cāng)庫(kù)揀選作業(yè)優(yōu)化［J］.武漢理工大學(xué)學(xué)報(bào)，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］ 佟芙慧.自動(dòng)化立體倉(cāng)庫(kù)的貨位優(yōu)化與管理［D］.沈陽(yáng)：沈陽(yáng)大學(xué)，2013.TONG Fuhui.Slotting Optimization and Management of Automated Warehouse［D］.Shenyang：Shenyang University，2013.

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

［10］李夢(mèng)婷.自動(dòng)化立體倉(cāng)庫(kù)物流系統(tǒng)仿真與優(yōu)化研究［D］.沈陽(yáng)：沈陽(yáng)工業(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］葛永國(guó)，韓提文，吳愛(ài)國(guó).AS/RS中輸送系統(tǒng)的PLC程序設(shè)計(jì)［J］.河北科技大學(xué)學(xué)報(bào)，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］張泉.淺談自動(dòng)化立體倉(cāng)庫(kù)管理系統(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］顧嘉，張華，李順，等.立體倉(cāng)庫(kù)出入庫(kù)仿真與優(yōu)化技術(shù)［J］.南昌大學(xué)學(xué)報(bào)（工科版），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］楊素梅，馬百雪.立體倉(cāng)庫(kù)PLC控制系統(tǒng)設(shè)計(jì)［J］.可編程控制器與工廠自動(dòng)化，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初始化種群?jiǎn)栴}的鄰域法［J］.重慶大學(xué)學(xué)報(bào)，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問(wèn)題的自適應(yīng)鄰域遺傳算法［J］.計(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é)任編輯：馮 民

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

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

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

王進(jìn)業(yè)，宋宇博.旁通式自動(dòng)化立體倉(cāng)庫(kù)揀選作業(yè)和出口選擇的組合優(yōu)化［J］.河北科技大學(xué)學(xué)報(bào)，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.