基于GA遺傳算法的國家電網倉儲分揀業務優化

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

基于GA遺傳算法的國家電網倉儲分揀業務優化

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

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

遺傳算法；國家電網；倉儲業務；分揀業務；優化

0　引言

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

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

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

1　基于GA算法的倉儲分揀業務優化設計

1.1業務場景描述和優化建模

假設在某一個倉庫內，共有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　貨架擺放模型示意圖

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

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

揀貨路徑優化目標是拾取所有貨物的時間和路徑最小，因為所走路徑和時間是線性正相關，所以可以組合描述如下：α，β是函數修正系數。

1.2基于GA遺傳算法的模型優化求解

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

求解優化目標的算法操作主要包括遺傳算法中包含的種群編碼、遺傳操作、適應度計算等。

1）遺傳編碼與適應度函數

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

2）遺傳算法操作

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

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

式中，b是［0，1］間的隨機數。

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

式中，amax為基因aij的上界；amin為基因aij的下界；為一個隨機數；g為當前迭代次數；Gmax是最大進化次數；r為［0，1］間的隨機數。

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

2　倉儲揀貨業務優化仿真實驗

2.1仿真實驗數據準備

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

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

2.2實驗計算與結果分析

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

1）未優化（優化前）的計算結果

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

2）順序優化求解

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

3）GA優化求解

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

表1　常量數據

表2　隨機生成的貨物數據

表3　揀貨過程的優化

根據前述計算結果，得到圖2所示優化結果。

圖2　優化前后效果比較

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

3　結論

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

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

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

［3］ 蘆遷琨.國網冀北電力有限公司倉儲配送管理優化［J］.現代商貿工業，2014，26（7）:168-168.

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

［5］ 金鑫，潘宜安，吳靖.基于優化GA-BP神經網絡的金融產品營銷預測［J］.通信學報，2014，（Z2）:20-25.

［6］ 蘇晨，李成義.基于遺傳算法和BP神經網絡的服裝銷售預測［J］.經營與管理，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

國家自然科學基金（U1509214）；國網科技部項目（SGTYHT/14-JS-188）

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