基于遺傳算法的庫位優(yōu)化問題

周興建， 劉元奇， 李 泉 ZHOU Xing-jian,LIU Yuan-qi,LI Quan

（1.武漢科技學(xué)院 經(jīng)濟(jì)管理學(xué)院，湖北 武漢 430073；2.武漢理工大學(xué) 交通學(xué)院，湖北 武漢 430063）

1 庫位優(yōu)化的提出

邯鄲交通運(yùn)輸集團(tuán)有限公司 （簡稱 “邯運(yùn)集團(tuán)”）是一家集多種業(yè)務(wù)為一體的大型綜合性物流企業(yè)。邯運(yùn)集團(tuán)的主要業(yè)務(wù)板塊有原料采購 （天信運(yùn)業(yè)及天昊、天誠、天恒等）、快遞服務(wù) （飛馬快運(yùn)）、汽貿(mào)業(yè)務(wù) （天誠汽貿(mào)）及倉儲配送 （河北快運(yùn)）等。其中，邯運(yùn)集團(tuán)的倉儲配送業(yè)務(wù)由河北快運(yùn)經(jīng)營，現(xiàn)有倉庫面積總共40 000㎡，主要的業(yè)務(wù)范圍為醫(yī)藥、日用百貨、卷煙、陶瓷、化工產(chǎn)品的配送，其中以醫(yī)藥為主。邯運(yùn)集團(tuán)庫存貨物主要涉及兩個方面：一個是大宗的供應(yīng)商貨物，如醫(yī)藥，化工產(chǎn)品等；另一方面主要是大規(guī)模的小件快遞貨物，如日用百貨等[1]。經(jīng)分析，邯運(yùn)集團(tuán)在倉儲運(yùn)作方面存在如下問題：

（1）存儲貨物繁多而分揀速度低下。倉庫每天到貨近400箱，有近200多種規(guī)格，缺乏一套行之有效的倉儲管理系統(tǒng)。

（2）貨架高度不當(dāng)而貨位分配混亂。現(xiàn)在采用的貨架高度在2米以上，而且將整箱貨物直接碼垛在貨架上，不嚴(yán)格按貨位擺放。當(dāng)需要往貨架最上層碼放貨物需要借助梯子，增加操作難度且操作效率較低。貨物在揀貨區(qū)貨架擺放是以件為單位的，分揀和搬運(yùn)速度較慢。

（3）揀貨貨架設(shè)計(jì)不當(dāng)而倉儲效率低下。發(fā)貨前裝箱工作主要由人工協(xié)同完成，出庫效率低，出錯率難以控制。

（4）存儲能力和分揀能力不能滿足需求。根據(jù)邯運(yùn)集團(tuán)的業(yè)務(wù)發(fā)展現(xiàn)狀及趨勢，現(xiàn)有的倉庫儲存和分揀能力遠(yuǎn)遠(yuǎn)達(dá)不到集團(tuán)公司對配送業(yè)務(wù)量的需求。

當(dāng)前邯運(yùn)集團(tuán)的貨位分配主要采用物理地址編碼的方式，很少考慮貨位分配對倉儲管理員工作效率的影響。對其進(jìn)行庫位優(yōu)化設(shè)計(jì)不僅直接影響到其庫存量的大小、出入庫的效率，還間接影響到邯運(yùn)集團(tuán)的整體經(jīng)營效益。本文對邯運(yùn)集團(tuán)的倉庫貨位進(jìn)行優(yōu)化時，結(jié)合考慮倉庫所存放的貨物種類、貨物數(shù)量、出入庫頻率等因素，對倉庫貨位進(jìn)行規(guī)劃，以提高倉儲效率。

2 庫位預(yù)分區(qū)規(guī)劃

在進(jìn)行倉庫貨位規(guī)劃時，作如下假設(shè)： （1）貨物的存放種類已知； （2）貨物每種類的單位時間內(nèi)存放的數(shù)量己知； （3）每一種貨物的存取頻率已知。

在倉庫貨位優(yōu)化中一個重要的環(huán)節(jié)即預(yù)分區(qū)。所謂預(yù)分區(qū)，是指沒有存放貨物時的分區(qū)，分區(qū)時只考慮倉儲作業(yè)人員的速度這一個因素。即如果對某些貨格，倉儲作業(yè)人員從原點(diǎn)到達(dá)該批貨格中的任一貨格所用的時間都相等，則這批貨格歸為一類[2]。

因此，倉儲作業(yè)人員執(zhí)行一批指令 （n條）需要的作業(yè)時間T為：

式中，T1——倉儲作業(yè)人員執(zhí)行第一條指令所需時間，T2——倉儲作業(yè)人員從當(dāng)前庫位到下一庫位所需時間，T3——倉儲作業(yè)人員從當(dāng)前庫位到原點(diǎn)來回所需時間，T4——倉儲作業(yè)人員送回庫位后從該庫位回到原點(diǎn)所需時間。

圖1 邯運(yùn)倉庫貨格分配圖

3 預(yù)分區(qū)步驟及數(shù)學(xué)模型

在上面的分析基礎(chǔ)上，具體的庫位預(yù)分區(qū)步驟如下[3]：

第一步：設(shè)倉儲作業(yè)人員從原點(diǎn)到某一貨格所需時間為t，其中i為貨格編碼號。設(shè)某一時間值t（t的大小與分區(qū)數(shù)目有關(guān)）。該貨格所處的區(qū)由下式 （2）確定：

如果i貨格滿足上式，則i貨格位于k區(qū)。

第二步：經(jīng)過第一步得到的分區(qū)可能各個小區(qū)所包含的貨格數(shù)目不相等。如果各區(qū)的貨數(shù)相差很大則需進(jìn)行修正，修正的原則 “就近取多補(bǔ)少”，即如果某個區(qū)的貨格數(shù)較少，則從含貨格數(shù)較多相鄰區(qū)取貨格。取貨格時，如果是從高區(qū)取貨格，則在高區(qū)內(nèi)先取運(yùn)行時間較少的。如果是從低區(qū)取的話，則先取運(yùn)行時間較多的。無須強(qiáng)求所有區(qū)內(nèi)的貨格相同。

第三步：將貨物按照出入庫頻率分類，其數(shù)目等于倉庫分區(qū)的數(shù)目。

第四步：建立權(quán)值矩陣，單位時間內(nèi)堆垛機(jī)取放某種貨物的工作量與該貨物的出入庫頻率不該貨物存放的位置有關(guān)，將該貨物的出入庫頻率乘以倉儲作業(yè)人員到達(dá)存放位置所用時間作為權(quán)值因子，即：

式中，i——i種貨物的出入庫頻率，j——倉儲作業(yè)人員從原點(diǎn)到j(luò)區(qū)取放的標(biāo)準(zhǔn)時間ti=j×tij（ ）。

經(jīng)過以上處理，倉庫的初始分區(qū)及第一次開始存放變?yōu)橐粋€區(qū)內(nèi)放入一種貨物，某一種貨物放入某一區(qū)后即不能再放入其他區(qū)，某一區(qū)放入某一貨物后也不能再放其他貨物，即變成為指派問題，其數(shù)學(xué)模型如下[4]。

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

約束條件：

考慮到倉庫中不同重量的貨物放在不同的位置，因此還要考慮貨物的出入庫頻率及貨物重量問題，這時可以將倉庫貨位分配問題建立為二次指派問題。設(shè)aijkl為相關(guān)因子，即當(dāng)i類貨物分配給j區(qū)，k類貨物分配給1區(qū)時的對貨架重力的影響系數(shù)。則該庫位優(yōu)化問題數(shù)學(xué)模型的目標(biāo)函數(shù)為：

4 遺傳算法優(yōu)化方案

邯運(yùn)集團(tuán)倉庫中的貨物種類很多，各類貨物的出入庫頻率也不一樣，這時相應(yīng)分區(qū)的數(shù)目就很大。對于此類問題再利用前面的方法來求解最優(yōu)分配貨物時就相當(dāng)復(fù)雜，往往無法求解。由于遺傳算法在解決組合優(yōu)化問題時操作簡便、尋優(yōu)能力強(qiáng)，本文用遺傳算法對邯運(yùn)集團(tuán)的倉庫貨位優(yōu)化問題進(jìn)行研究[5]。

4.1 算法步驟

第一步：編碼

遺傳算法應(yīng)用的瓶頸之一是編碼問題，本方案中編碼采用順序表達(dá)法。以邯運(yùn)集團(tuán)河北快運(yùn)倉庫為例，倉庫分為9個區(qū)存放9類貨物，采用順序表達(dá)法時的某個染色體為 [923547681]，該染色體表示第1個區(qū)放第9類的貨物，第2個區(qū)放第2類貨物，依次類推。

第二步：適應(yīng)度函數(shù)。如貨格分成n個區(qū)時，相應(yīng)的權(quán)值矩陣仍用下式建立：

式中：cij——權(quán)值矩陣i行j列的元素，是出入庫頻率與員工從原點(diǎn)到j(luò)區(qū)的時間之積；f1——i種貨物的出入庫頻率；t1——倉儲作業(yè)人員從原點(diǎn)到j(luò)區(qū)取放的標(biāo)準(zhǔn)時間t1=j×t間（ ）。

第三步：初始種群

初始種群的產(chǎn)生和選擇機(jī)制，重復(fù)上面的三步直到產(chǎn)生規(guī)定數(shù)目的染色體為止。選擇過程采用轉(zhuǎn)輪選擇機(jī)制，適應(yīng)度函數(shù)采用當(dāng)前代中評估函數(shù)的最大值減去該評估函數(shù)值。

第四步：遺傳算子交叉

步驟1：任何在雙親中指派到相同位置的貨物在后代中仍占據(jù)這個位置；步驟2：對于剩下的位置由雙親中指派到該位置的兩類貨物中隨機(jī)選一類貨物，從左到右進(jìn)行；步驟3：將剩下的未指派的貨物分派給尚空閑的位置。

4.2 實(shí)現(xiàn)過程

根據(jù)以上算法步驟，其求解實(shí)現(xiàn)過程為：

（1）建立有n個元素的數(shù)組，對每個元素都賦給一個隨機(jī)數(shù) （隨機(jī)數(shù)值范圍從1到:1）。程序如下：

（2）計(jì)算數(shù)組各元素在數(shù)組中按照大小所處的位置。如果有些元素相等，則按數(shù)組下標(biāo)排序，下標(biāo)值小的元素位置在前面，大的在后面。

（3）將數(shù)組b[i]中的值按下標(biāo)順序排列，組成一個染色體。

重復(fù)上面的三步直到產(chǎn)生規(guī)定數(shù)目的染色體為止。

以上過程用圖2說明：

（4）利用MATLAB進(jìn)行編程計(jì)算并得出最優(yōu)劃分方案，最后得到優(yōu)化后的結(jié)果并利用MATLAB里面的仿真工具箱畫出仿真圖像。

圖2 遺傳算法實(shí)現(xiàn)過程

[1] 教育部高等學(xué)校物流類專業(yè)教學(xué)指導(dǎo)委員會. “邯運(yùn)杯”第二屆全國大學(xué)生物流設(shè)計(jì)大賽案例[M].北京：北京交通大學(xué)出版社，2008.

[2] 銀光球，何福英，盛冬發(fā).自動化立體倉庫中庫位優(yōu)化模型研究[J].福建工程學(xué)院學(xué)報(bào)，2006(3):347－351.

[3] 邱建東，唐定普，高博,等.重力式立體倉庫管理系統(tǒng)核心模塊設(shè)計(jì)[J].起重運(yùn)輸機(jī)械，2008(4):37－41.

[4] 衛(wèi)軍朝，任建平，王宗彥.自動化倉庫模塊化單元式貨架的優(yōu)化設(shè)計(jì)[J].起重運(yùn)輸機(jī)械，2008(6):60－63.

[5] 玄光男，程潤偉.遺傳算法與工程優(yōu)化[M].北京：清華大學(xué)出版社，2004.

[6] ZHOU Xing－jian,DU Cheng－xiang.A Model of Cost－oriented Price－Making for Logistics Service[C]//International Conference of Production and Operation Management.SPRINGER Press,2008.

[7] J.A.Erskine,M.R.Leenders,L.A.Mauffette,Leenders.Teaching with Case[M].Research and Publication division,School Business Administration,the university of western Ontrario,London,Canada,1981:150.

[8] Bloom,B.S.The Search for Methods of Group Instruction as Effective as One－to－one Tutoring[J].Educational Leadership,1986(10):4－8.