金　鑫，于亮亮，金成明，張海全，粘中元JIN Xin，　YU Liang-liang，　JIN Cheng-ming，　ZHANG Hai-quan，　NIAN Zhong-yuan（. 中央財(cái)經(jīng)大學(xué) 信息學(xué)院，北京 0008；.國(guó)網(wǎng)遼寧省電力有限公司信息通信分公司，沈陽 0006；.國(guó)網(wǎng)內(nèi)蒙古東部電力有限公司信息通信分公司，呼和浩特 0000）

基于GA遺傳算法的國(guó)家電網(wǎng)倉(cāng)儲(chǔ)分揀業(yè)務(wù)優(yōu)化

金鑫1，于亮亮2，金成明2，張海全3，粘中元3
JIN Xin1，YU Liang-liang2，JIN Cheng-ming2，ZHANG Hai-quan3，NIAN Zhong-yuan3
（1. 中央財(cái)經(jīng)大學(xué) 信息學(xué)院，北京 100081；2.國(guó)網(wǎng)遼寧省電力有限公司信息通信分公司，沈陽 110006；3.國(guó)網(wǎng)內(nèi)蒙古東部電力有限公司信息通信分公司，呼和浩特 010020）

國(guó)家電網(wǎng)倉(cāng)儲(chǔ)業(yè)務(wù)的優(yōu)化對(duì)于建立國(guó)網(wǎng)現(xiàn)代化物資管理體系、優(yōu)化物資配送效率意義重大。為了提高倉(cāng)儲(chǔ)業(yè)務(wù)的工作效率，針對(duì)倉(cāng)儲(chǔ)業(yè)務(wù)中分揀環(huán)節(jié)存在的諸多問題，提出一種基于GA遺傳算法的倉(cāng)儲(chǔ)分揀業(yè)務(wù)優(yōu)化策略，通過建立倉(cāng)儲(chǔ)分揀業(yè)務(wù)模型，進(jìn)行基于遺傳算法的倉(cāng)儲(chǔ)分揀業(yè)務(wù)優(yōu)化實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，采用GA算法優(yōu)化后，揀貨時(shí)間、距離相較于優(yōu)化前大為縮短，揀貨工作效率得到顯著提升，充分證明了本優(yōu)化策略的可靠性?；贕A遺傳算法的分揀業(yè)務(wù)優(yōu)化策略，為國(guó)網(wǎng)倉(cāng)儲(chǔ)業(yè)務(wù)的優(yōu)化提供了參考依據(jù)，為提高國(guó)網(wǎng)倉(cāng)儲(chǔ)運(yùn)營(yíng)效率，構(gòu)建智能化倉(cāng)儲(chǔ)管理系統(tǒng)，建設(shè)現(xiàn)代化電網(wǎng)物資管理體系做了理論鋪墊；同時(shí)，該策略對(duì)優(yōu)化其他倉(cāng)儲(chǔ)類業(yè)務(wù)同樣具有積極借鑒意義。

遺傳算法；國(guó)家電網(wǎng)；倉(cāng)儲(chǔ)業(yè)務(wù)；分揀業(yè)務(wù)；優(yōu)化

0　引言

國(guó)家電網(wǎng)對(duì)物資倉(cāng)儲(chǔ)的管理非常重視，尤其是倉(cāng)儲(chǔ)管理的信息化建設(shè)。根據(jù)國(guó)家電網(wǎng)關(guān)于倉(cāng)儲(chǔ)管理的相關(guān)規(guī)定，電網(wǎng)公司將以總部“虛擬倉(cāng)庫(kù)”為信息中心，自有倉(cāng)儲(chǔ)和供應(yīng)商倉(cāng)促相結(jié)合，構(gòu)建中心庫(kù)、區(qū)域庫(kù)、周轉(zhuǎn)庫(kù)科學(xué)合理布局的智能化倉(cāng)儲(chǔ)網(wǎng)絡(luò)。智能化庫(kù)房是國(guó)網(wǎng)提倡構(gòu)建的庫(kù)房類型之一，其利用計(jì)算機(jī)、信息通信等方面的先進(jìn)技術(shù)進(jìn)行管理，提高了倉(cāng)儲(chǔ)配送能力和運(yùn)營(yíng)效率。管理和優(yōu)化庫(kù)區(qū)業(yè)務(wù)是國(guó)家電網(wǎng)打造精益高效物資管理體系的重要環(huán)節(jié)，貨物的入庫(kù)、分揀等業(yè)務(wù)都關(guān)聯(lián)著電網(wǎng)物資的流動(dòng)效率，尤其是分揀業(yè)務(wù)直接關(guān)聯(lián)著后期物流配送環(huán)節(jié)和優(yōu)化倉(cāng)儲(chǔ)業(yè)務(wù)。目前，物資管理分散、倉(cāng)庫(kù)利用率低是影響電力公司提高倉(cāng)儲(chǔ)管理水平的關(guān)鍵問題，鑒于此，合理優(yōu)化倉(cāng)儲(chǔ)分揀業(yè)務(wù)，構(gòu)建智能化倉(cāng)儲(chǔ)管理系統(tǒng)，對(duì)于建設(shè)現(xiàn)代化電網(wǎng)物資管理體系具有重大意義［1，2］。

實(shí)體庫(kù)倉(cāng)儲(chǔ)的庫(kù)區(qū)業(yè)務(wù)主要包括入庫(kù)、上下架、分揀、盤點(diǎn)等內(nèi)容，在整個(gè)物流體系中分揀業(yè)務(wù)是其中十分重要的一環(huán)。分揀作業(yè)的目的在于能夠正確且迅速地集合用戶所訂購(gòu)的物資產(chǎn)品，目前系統(tǒng)采取的分揀策略是完全順序分揀作業(yè)策略，即：按照隨機(jī)獲取到的物資訂單，除考慮揀貨車的體積容量不進(jìn)行任何優(yōu)化，直接順序組單由揀貨人員揀取。該策略具有很大的隨機(jī)性，若組單碰巧包含揀貨位置集中的商品則揀貨速度快，否則可能橫跨多個(gè)區(qū)域揀貨，造成揀貨效率低下。除了分揀策略隨機(jī)性問題外，貨品儲(chǔ)位未合理化存放、找不到貨品或缺貨率太高、無效走動(dòng)等［3］問題同樣會(huì)導(dǎo)致揀貨效率低下。因此，利用合理高效的優(yōu)化策略對(duì)倉(cāng)儲(chǔ)分揀業(yè)務(wù)問題進(jìn)行優(yōu)化亟待進(jìn)行。

針對(duì)倉(cāng)儲(chǔ)業(yè)務(wù)中分揀環(huán)節(jié)存在的諸多問題，本研究以分揀業(yè)務(wù)為例，提出一種基于GA遺傳算法的倉(cāng)儲(chǔ)業(yè)務(wù)優(yōu)化策略，通過建立倉(cāng)儲(chǔ)分揀業(yè)務(wù)模型，進(jìn)行基于遺傳算法的倉(cāng)儲(chǔ)分揀業(yè)務(wù)優(yōu)化實(shí)驗(yàn)。遺傳算法在諸多行業(yè)中都有應(yīng)用，其優(yōu)點(diǎn)是在使用概率搜索技術(shù)的同時(shí)，進(jìn)行解空間的多點(diǎn)搜索，避免了陷入局部最小值，增加了搜索的靈活性，提高了系統(tǒng)的計(jì)算速度［4～6］。本研究針對(duì)國(guó)家電網(wǎng)倉(cāng)儲(chǔ)分揀業(yè)務(wù)進(jìn)行策略優(yōu)化，旨在合理優(yōu)化倉(cāng)儲(chǔ)分揀業(yè)務(wù)，提高國(guó)網(wǎng)倉(cāng)儲(chǔ)運(yùn)營(yíng)效率，為構(gòu)建智能化倉(cāng)儲(chǔ)管理系統(tǒng)，建設(shè)現(xiàn)代化電網(wǎng)物資管理體系做鋪墊。

1　基于GA算法的倉(cāng)儲(chǔ)分揀業(yè)務(wù)優(yōu)化設(shè)計(jì)

1.1業(yè)務(wù)場(chǎng)景描述和優(yōu)化建模

假設(shè)在某一個(gè)倉(cāng)庫(kù)內(nèi)，共有s個(gè)擺放貨物的貨架（貨架編號(hào)y=0，1，··，s-1）。其中，每?jī)蓚€(gè)貨架為一組放置在一起，可撿取貨物的一面朝外。兩組貨架之間有可供行走的通道，通道寬為h。每個(gè)貨架長(zhǎng)為b，寬為w，由n×m個(gè)大小相同的格子組成，每個(gè)格子都放有不同的貨物，則第y個(gè)貨架上的第z行第x列的貨物的位置為（z，x，y），0＜z≤n，0＜x≤m。揀貨員在橫向方向上的速度為Vx，在縱向方向上的速度為Vy。貨架擺放模型示意圖如圖1所示。

圖1　貨架擺放模型示意圖

假設(shè)揀貨員拿取同一列的貨物的時(shí)間相同，那么在實(shí)際計(jì)算過程中，貨物的編號(hào)可簡(jiǎn)化為（x，y）。假設(shè)tij為揀貨員從貨物i的位置到貨物j的時(shí)間，dij是從貨物i的位置到貨物j的距離，則tij和dij的計(jì)算公式如下：

其中，xij和yij為貨物i到貨物j的橫向和縱向距離，ya=y/2，yb=y%2。

揀貨路徑優(yōu)化目標(biāo)是拾取所有貨物的時(shí)間和路徑最小，因?yàn)樗呗窂胶蜁r(shí)間是線性正相關(guān)，所以可以組合描述如下：α，β是函數(shù)修正系數(shù)。

1.2基于GA遺傳算法的模型優(yōu)化求解

遺傳算法模擬自然選擇，將自然界的遺傳進(jìn)化理念運(yùn)用到解決實(shí)際工程問題中。所謂自然選擇通過優(yōu)勝劣汰的方式使得逐代進(jìn)行遺傳進(jìn)化，從而最終存活下來的物種具有最佳適應(yīng)性。在具體實(shí)現(xiàn)上，先進(jìn)行遺傳算法種群初始化編碼，將問題解集初始化，接著對(duì)種群進(jìn)行遺傳算法基本操作，計(jì)算個(gè)體適應(yīng)度值。最后循環(huán)操作直至找到相對(duì)最優(yōu)適應(yīng)度值對(duì)應(yīng)的個(gè)體即為問題的最優(yōu)解。遺傳算法基本操作包括：選擇、交叉、變異。

求解優(yōu)化目標(biāo)的算法操作主要包括遺傳算法中包含的種群編碼、遺傳操作、適應(yīng)度計(jì)算等。

1）遺傳編碼與適應(yīng)度函數(shù)

在求解上述優(yōu)化問題時(shí)，多采用遍歷貨物的次序排列進(jìn)行編碼。例如編碼123456表示自貨物序號(hào)1開始，依次拾取貨物2，3，4，5，6，最后返回出發(fā)點(diǎn)1。由于在可行解群體的初始化、交叉操作、變異操作均隱含求解的合法性約束條件，所以適應(yīng)度函數(shù)取目標(biāo)函數(shù)的倒數(shù)，即f=1/Z，無懲罰函數(shù)。

2）遺傳算法操作

遺傳算法操作主要包括：選擇、交叉和變異。

交叉操作：第k個(gè)染色體ak和第l個(gè)染色體al在j位的交叉操作方法如下：

式中，b是［0，1］間的隨機(jī)數(shù)。

變異操作：選取第i個(gè)體的第j個(gè)基因aij進(jìn)行變異的操作方法如下：

式中，amax為基因aij的上界；amin為基因aij的下界；為一個(gè)隨機(jī)數(shù)；g為當(dāng)前迭代次數(shù)；Gmax是最大進(jìn)化次數(shù)；r為［0，1］間的隨機(jī)數(shù)。

遺傳算法的優(yōu)點(diǎn)是在使用概率搜索技術(shù)的同時(shí)，進(jìn)行解空間的多點(diǎn)搜索，增加了搜索的靈活性，避免了陷入局部最小值；此外，遺傳算法具有并行計(jì)算的特點(diǎn)，可通過大規(guī)模并行計(jì)算來提高計(jì)算速度。

2　倉(cāng)儲(chǔ)揀貨業(yè)務(wù)優(yōu)化仿真實(shí)驗(yàn)

2.1仿真實(shí)驗(yàn)數(shù)據(jù)準(zhǔn)備

隨機(jī)產(chǎn)生30個(gè)貨物（編號(hào)為i=1，2，…，30），第i個(gè)貨物為（xi，yi）。將所有的貨物分為3組，揀貨員需要往返3次才能取到所有貨物。揀貨員每次往返都從原點(diǎn)出發(fā)，依次拿取某一組中的貨物，然后返回原點(diǎn)。假設(shè)所有貨物都已包裝，體積固定設(shè)為1；推車的體積為10。因此，揀貨員每次至多拿取10個(gè)貨物就要返回原處（0，0）。

根據(jù)前述的實(shí)驗(yàn)假設(shè)，列出如下所示的已知數(shù)據(jù)常量表和隨機(jī)生成的貨物數(shù)據(jù)表。

2.2實(shí)驗(yàn)計(jì)算與結(jié)果分析

基于前述的假設(shè)和仿真數(shù)據(jù)，本研究分別計(jì)算了優(yōu)化前、順序優(yōu)化、GA遺傳算法優(yōu)化的結(jié)果，結(jié)果如表3所示。表中列出了優(yōu)化的揀貨路徑和所需消耗的時(shí)間和路程。

1）未優(yōu)化（優(yōu)化前）的計(jì)算結(jié)果

根據(jù)前述tij和dij的計(jì)算公式，對(duì)于隨機(jī)生成的30件貨物全部貨物撿取完畢的時(shí)間和距離分別為：時(shí)間=673，距離=1216。

2）順序優(yōu)化求解

所謂順序優(yōu)化是將待揀的貨物分為三組，每組中揀貨員從初始位置（0，1）從近到遠(yuǎn)揀貨，此種方式與當(dāng)前實(shí)際采用的揀貨方式類似。采用順序優(yōu)化后的結(jié)果為：時(shí)間=448，距離=846。

3）GA優(yōu)化求解

GA算法將問題的求解過程看成一個(gè)在候選解空間尋找滿足問題要求的解或近似解的搜索過程，GA算法求解最優(yōu)化問題的計(jì)算效率比較高、適用范圍相當(dāng)廣?；谏弦还?jié)中提出的優(yōu)化策略，采用GA遺傳算法進(jìn)行優(yōu)化求解。在GA求解中，我們?cè)O(shè)置種群規(guī)模為4，交叉率為0.99，變異率為0.01，適應(yīng)度函數(shù)為f=1/ （0.08t+0.01d）。通過GA求解，GA第一代的求解結(jié)果為：時(shí)間=345，距離=618；GA第5代的求解結(jié)果為：時(shí)間=293，距離=538。

表1　常量數(shù)據(jù)

表2　隨機(jī)生成的貨物數(shù)據(jù)

表3　揀貨過程的優(yōu)化

根據(jù)前述計(jì)算結(jié)果，得到圖2所示優(yōu)化結(jié)果。

圖2　優(yōu)化前后效果比較

從圖2可以直觀看出，采用GA遺傳算法優(yōu)化后，揀貨時(shí)間、距離相較于優(yōu)化前大為縮短，揀貨工作效率得到顯著提高，充分證明了本優(yōu)化策略的可靠性。

3　結(jié)論

針對(duì)倉(cāng)儲(chǔ)業(yè)務(wù)中分揀環(huán)節(jié)存在的諸多問題，本研究以分揀業(yè)務(wù)為例，提出一種基于GA遺傳算法的倉(cāng)儲(chǔ)業(yè)務(wù)優(yōu)化策略，通過建立倉(cāng)儲(chǔ)分揀業(yè)務(wù)模型，進(jìn)行基于遺傳算法的倉(cāng)儲(chǔ)分揀業(yè)務(wù)優(yōu)化實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果顯示：優(yōu)化前t=673，d=1216；順序優(yōu)化后，t=448，d=846；GA遺傳算法優(yōu)化一代后，t=345，d=618。結(jié)果表明，采用GA算法優(yōu)化后，揀貨時(shí)間、距離相較于優(yōu)化前大為縮短，揀貨工作效率得到顯著提升，充分證明了本研究?jī)?yōu)化策略的可靠性?；贕A遺傳算法的分揀業(yè)務(wù)優(yōu)化策略，為國(guó)網(wǎng)倉(cāng)儲(chǔ)業(yè)務(wù)的優(yōu)化提出了參考依據(jù)，為提高國(guó)網(wǎng)倉(cāng)儲(chǔ)運(yùn)營(yíng)效率，構(gòu)建智能化倉(cāng)儲(chǔ)管理系統(tǒng)，建設(shè)現(xiàn)代化電網(wǎng)物資管理體系做好了理論鋪墊；同時(shí)，該策略對(duì)優(yōu)化其他倉(cāng)儲(chǔ)類業(yè)務(wù)同樣具有積極借鑒意義。

［1］ 李懷湘.倉(cāng)儲(chǔ)管理實(shí)務(wù)［M］.北京:北京大學(xué)出版社，2011:35-37.

［2］ 史建偉.淺析電力企業(yè)物資倉(cāng)儲(chǔ)的優(yōu)化管理［J］.城市建設(shè)理論研究（電子版），2015.10.

［3］ 蘆遷琨.國(guó)網(wǎng)冀北電力有限公司倉(cāng)儲(chǔ)配送管理優(yōu)化［J］.現(xiàn)代商貿(mào)工業(yè)，2014，26（7）:168-168.

［4］ 陳國(guó)良，等.遺傳算法機(jī)器應(yīng)用［M］.北京:人民郵電出版社，2001:137-149.

［5］ 金鑫，潘宜安，吳靖.基于優(yōu)化GA-BP神經(jīng)網(wǎng)絡(luò)的金融產(chǎn)品營(yíng)銷預(yù)測(cè)［J］.通信學(xué)報(bào)，2014，（Z2）:20-25.

［6］ 蘇晨，李成義.基于遺傳算法和BP神經(jīng)網(wǎng)絡(luò)的服裝銷售預(yù)測(cè)［J］.經(jīng)營(yíng)與管理，2012，2:052.

The optimization of state grid storage sorting based on Genetic Algorithm

F252；TP315

A

1009-0134（2016）06-0127-04

2016-04-25

國(guó)家自然科學(xué)基金（U1509214）；國(guó)網(wǎng)科技部項(xiàng)目（SGTYHT/14-JS-188）

金鑫（1974 -），男，教授，博士，研究方向?yàn)樯虅?wù)智能。