夏賢康

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

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

夏賢康

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

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

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

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

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

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

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

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

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

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

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

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

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

[8]。

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

（4）交叉操作，采用單點(diǎn)交叉，只互換 2 個(gè)染色體的一個(gè)交叉點(diǎn)的基因。

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

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

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

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

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

表 1 貨物貨位信息

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

3.2 仿真結(jié)果分析

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

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

圖 1 倉(cāng)庫(kù)揀選區(qū)的簡(jiǎn)易布局

（2）混合型策略?；旌闲筒呗允侵竿嘶夭呗院蚐-shape策略相結(jié)合的策略[10]，通過混合型策略優(yōu)化后所需要的揀選時(shí)間為 856 s，得到揀選路徑：14→12→16→13→20→6→11→19→5→10→8→3→4→7→18→15→1→17→9→2。

（3）遺傳算法。采用 Matlab 軟件對(duì)揀選路徑優(yōu)化模型進(jìn)行求解[11]，設(shè)種群規(guī)模為 50，交叉概率為0.85，變異概率為 0.05，迭代次數(shù)為 1 000 次。通過遺傳算法優(yōu)化后所需要的揀選時(shí)間為 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é)果對(duì)比 s

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

4 結(jié)束語

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

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

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

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

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

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

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

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

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

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

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

[11]吳婷.基于遺傳算法的倉(cāng)儲(chǔ)系統(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