基于遺傳算法的高架立體倉庫揀選路徑優(yōu)化

夏賢康

（蘭州交通大學(xué) 交通運輸學(xué)院，甘肅 蘭州 730070 ）

基于遺傳算法的高架立體倉庫揀選路徑優(yōu)化

夏賢康

（蘭州交通大學(xué) 交通運輸學(xué)院，甘肅 蘭州 730070 ）

在闡述高架立體倉庫揀選路徑優(yōu)化模型的基礎(chǔ)上，以揀選時間最小為優(yōu)化目標(biāo)，將目標(biāo)進行量化建立數(shù)學(xué)模型，并且采用遺傳算法對優(yōu)化模型進行求解，最后選用Matlab軟件設(shè)計算法求解最優(yōu)解。在揀選路徑優(yōu)化求解過程中，通過設(shè)定模擬參數(shù)，選用S-shape策略、混合型策略和遺傳算法分別對20種貨物進行仿真求解，最后進行結(jié)果比較以驗證揀貨優(yōu)化模型的有效性。

揀選路徑優(yōu)化；遺傳算法；Matlab；仿真

隨著機械化和計算機技術(shù)信息化的快速發(fā)展，倉庫管理已經(jīng)成為現(xiàn)代企業(yè)物流管理系統(tǒng)的重要組成部分[1]。為提高倉庫管理效率，一方面可以優(yōu)化貨位設(shè)置，另一方面應(yīng)考慮盡量提高揀選貨物效率。在貨物的揀選過程中，路徑的選取至關(guān)重要。因此，以提高倉儲作業(yè)效率、節(jié)約倉儲成本為目標(biāo)，對貨物揀選路徑進行優(yōu)化以降低物流成本、提高經(jīng)濟效益的研究非常必要。目前國內(nèi)關(guān)于貨物揀選路徑優(yōu)化的研究很多，大部分以時間最少為目標(biāo)[2]，選用的優(yōu)化方法有啟發(fā)式算法[3]、神經(jīng)網(wǎng)絡(luò)法、遺傳算法、禁忌搜索法、蟻群算法及模擬退火算法等[4]，而在解決優(yōu)化問題時，大部分學(xué)者會選擇遺傳算法來建立優(yōu)化模型，通過采用遺傳算法可以實現(xiàn)對倉庫揀選路徑的優(yōu)化，提高揀貨作業(yè)效率[5]，減少揀貨作業(yè)時間。

1 數(shù)學(xué)模型的建立

1.1 模型的描述和假設(shè)

在分析模型目的和特征的基礎(chǔ)上，對模型進行描述和假設(shè)。①在生成揀貨訂單過程中，有 1 種或多種貨物合并為 1 批的訂單，需要通過 1 個高位叉車進行揀選。②需要揀選的貨物總?cè)莘e和質(zhì)量不會超過高位叉車的最大承載質(zhì)量和最大揀選能力。③倉庫中存儲區(qū)的貨架為雙排型連接，并且為水平排列。④貨架每層垂直間距為 h，忽略叉車取貨時間，已知揀選貨物的品種和貨位位置并且叉車勻速行駛。

1.2 建立揀選路徑優(yōu)化模型

揀選路徑優(yōu)化過程是以揀選時間最短為目標(biāo)，通過降低揀選路程來提高揀選作業(yè)效率。假設(shè)高位叉車 1 次需要揀選 L 種貨物，根據(jù)假設(shè)建立揀選路徑優(yōu)化模型如下。揀選完 i 后立即揀選 j否則

ci＞0 并且為整數(shù)

2 遺傳算法的設(shè)計

在解決一般路徑優(yōu)化問題時，遺傳算法可以發(fā)揮較好的效果[6]。遺傳算法的主要步驟包括編碼設(shè)計、適應(yīng)度函數(shù)確定、選擇操作、交叉操作及變異操作等[7]。通過采用遺傳算法求解上述模型最優(yōu)解，找出高架倉庫揀選的最優(yōu)路徑，算法步驟如下。

（1）采用整數(shù)編碼，每條染色體有 L 段基因表示L 種貨物，染色體上每個基因表示 1 個貨位 (x，y，z)。

[8]。

（3）選擇操作，所有個體按照適應(yīng)度值從小到大排列，選擇中間和尾部的個體進行復(fù)制，保留優(yōu)秀個體。

（4）交叉操作，采用單點交叉，只互換 2 個染色體的一個交叉點的基因。

（5）變異操作，隨機選擇父代個體染色體的 2 個位置，將處于二者間的基因順序顛倒，形成新個體。

（6）終止條件，設(shè)種群規(guī)模為 50，交叉概率為 0.85，變異概率為 0.05，當(dāng)?shù)螖?shù)達到 1 000時，算法終止。

3 揀選路徑優(yōu)化仿真過程

3.1 模擬參數(shù)設(shè)定

通過對揀選路徑優(yōu)化模型的分析，根據(jù)高架倉庫的整體布局進行模擬參數(shù)設(shè)定，選取 20 種不同類別的貨物作為研究對象，在這 20 種貨物總質(zhì)量不超過叉車最大負(fù)荷的情況下，分別選用 S 型揀選方法、混合揀選方法和遺傳算法對 20 種貨物揀選最優(yōu)路徑進行求解，然后進行比較分析，選出最佳揀選方案。參數(shù)設(shè)定的初始化貨物貨位信息如表 1 所示。

表 1 貨物貨位信息

模擬的立體倉庫倉儲區(qū)的長為 32 000 mm、寬為 30 000 mm，有貨架 12 排 12 列 6 層，每個貨位長2 300 mm、寬 1 200 mm、高 1 500 mm，揀貨通道寬2 300 mm，有高位叉車 1 臺，叉車水平運行速度 vx= 1 000 mm/s，垂直運行速度 vy=250 mm/s，根據(jù)表 1 的貨位信息繪制倉庫揀選區(qū)的簡易布局如圖 1 所示，其中從左至右為 1—12 列，從上至下為 1—12 排，黑色方格為 20 種貨物所在位置，白色方格為非選取貨位。

3.2 仿真結(jié)果分析

選用 S-shape 策略、混合型策略和遺傳算法分別對 20 種貨物進行仿真求解，通過 Matlab 軟件設(shè)計算法求解結(jié)果如下。

（1）S-shape 策略。S-shape 策略是指穿越策略[9]，需要把每個通道都走一遍，然后揀選出所需要的貨物。首先對 20 種貨物進行編碼，通過 S-shape 策略優(yōu)化后所需要的揀選時間為 848.8 s，得到揀選路徑：14→12→16→13→20→17→9→2→1→15→18→6→11→7→4→3→5→8→10→19。

圖 1 倉庫揀選區(qū)的簡易布局

（2）混合型策略。混合型策略是指退回策略和S-shape策略相結(jié)合的策略[10]，通過混合型策略優(yōu)化后所需要的揀選時間為 856 s，得到揀選路徑：14→12→16→13→20→6→11→19→5→10→8→3→4→7→18→15→1→17→9→2。

（3）遺傳算法。采用 Matlab 軟件對揀選路徑優(yōu)化模型進行求解[11]，設(shè)種群規(guī)模為 50，交叉概率為0.85，變異概率為 0.05，迭代次數(shù)為 1 000 次。通過遺傳算法優(yōu)化后所需要的揀選時間為 827.3 s，得到揀選路徑：14→12→16→13→20→6→11→7→4→3→8→10→5→19→18→15→1→17→9→2。

比較這 3 種方法得到的優(yōu)化結(jié)果如表 2 所示。

表 2 3 種揀選方法優(yōu)化結(jié)果對比 s

通過表 2 可以看出，相對于混合型策略和 S-shape策略而言，采用遺傳算法對倉儲貨物揀選路徑優(yōu)化可以有效減少揀選時間，提高揀選工作效率。

4 結(jié)束語

通過改進貨物揀選路徑優(yōu)化模型，采用遺傳算法進行求解，并且使用 Matlab 軟件對揀選路徑優(yōu)化進行仿真設(shè)計。為驗證模型的有效性，采用混合型策略、S-shape 策略和遺傳算法分別求解，得出最優(yōu)解即揀貨作業(yè)時間和揀選路徑最優(yōu)，對優(yōu)化結(jié)果進行比較可以看出遺傳算法求解模型優(yōu)于其他算法，實現(xiàn)揀選路徑優(yōu)化的目的。由于所建立的模型適用于小件貨物揀選，如果在大型倉庫，隨著揀選貨物量和貨物體積質(zhì)量的增加，模型優(yōu)化結(jié)果將不明顯。此外，建立模型時僅考慮叉車水平和垂直方向的位移，而沒有將揀貨時間和尋找貨物時間考慮在內(nèi)，還有待繼續(xù)深入研究。

[1]吳耀華，王瑩，肖際偉，等.現(xiàn)代物流系統(tǒng)技術(shù)的研究現(xiàn)狀及發(fā)展趨勢[J].機械工程學(xué)報，1999，35(4)：1-5.

[2]王占磊.配送中心訂單分批及揀選路徑優(yōu)化問題研究[D].長春：吉林大學(xué)，2013.

[3]王夢楠.基于遺傳算法的物流中心貨位優(yōu)化研究[D].大連：大連海事大學(xué)，2012.

[4]DukicG，OluicC.Order-pickingRoutingPolicies：SimpleHeuirstics，AdvancedHeuirstics orPrimalAlgorithrn[J].JournalofMachenicalEnginnering，2004，50(11)：530-535.

[5]石夢竹.基于動力貫穿式貨架的自動化立體倉庫的入庫調(diào)度優(yōu)化研究[D].濟南：山東大學(xué)，2013.

[6]別文群，李擁軍.遺傳算法在立體倉庫貨位優(yōu)化分配中的研究[J].計算機工程與運用，2009，45(29)：211-213.

[7]劉寶碇，趙瑞清，王綱.不確定規(guī)劃及應(yīng)用[M].北京：清華大學(xué)出版社，2003.

[8]劉思佳.A公司倉儲中心出庫作業(yè)優(yōu)化研究[D].長春：吉林大學(xué)，2014.

[9]白寅.基于偏離度的倉庫揀選路徑優(yōu)化方法及應(yīng)用[D].武漢：華中科技大學(xué)，2012.

[10]高亮，張國輝，王曉娟.柔性作業(yè)車間調(diào)度智能算法及其應(yīng)用[M].武漢：華中科技大學(xué)出版社，2012.

[11]吳婷.基于遺傳算法的倉儲系統(tǒng)多目標(biāo)貨位優(yōu)化的研究[D].武漢：武漢理工大學(xué)，2011.

責(zé)任編輯：吳文娟

1004-2024(2015)09-0039-04

：U291.5+2

：B

10.16669/j.cnki.issn.1004-2024.2015.09.10

2015-09-08