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

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

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

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

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

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

0　引言

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

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

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

1　基于GA算法的倉儲分揀業(yè)務(wù)優(yōu)化設(shè)計

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

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

圖1　貨架擺放模型示意圖

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

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

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

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

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

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

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

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

2）遺傳算法操作

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

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

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

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

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

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

2　倉儲揀貨業(yè)務(wù)優(yōu)化仿真實驗

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

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

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

2.2實驗計算與結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

3　結(jié)論

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

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

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

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

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

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

［6］ 蘇晨，李成義.基于遺傳算法和BP神經(jīng)網(wǎng)絡(luò)的服裝銷售預(yù)測［J］.經(jī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

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

金鑫（1974 -），男，教授，博士，研究方向為商務(wù)智能。