基于匈牙利算法的自動(dòng)化立體倉庫出入庫優(yōu)化調(diào)度

欒 飛， 楊 瑋

(陜西科技大學(xué)機(jī)電工程學(xué)院， 陜西 西安 710021)

0 引 言

目前，隨著經(jīng)濟(jì)危機(jī)的加劇，制造企業(yè)要生存就必須不斷地降低成本，提高企業(yè)的適應(yīng)力和競(jìng)爭(zhēng)力.立體倉庫是企業(yè)生產(chǎn)過程中的重要存儲(chǔ)設(shè)備，提高它的運(yùn)行效率可以大大減少生產(chǎn)輔助時(shí)間，降低存儲(chǔ)成本，提高生產(chǎn)效率.要提高立體倉庫的整體作業(yè)效率，必須對(duì)出入庫作業(yè)進(jìn)行合理調(diào)度，對(duì)貨位、堆垛機(jī)行走路線進(jìn)行優(yōu)化，以減少貨物搬運(yùn)次數(shù)、貨物出入庫的等待時(shí)間等.

國(guó)內(nèi)外學(xué)者在這方面進(jìn)行了廣泛的研究，并取得了一定的進(jìn)展.山東工業(yè)大學(xué)的田國(guó)會(huì)等[1]針對(duì)自動(dòng)化立體倉庫的實(shí)際運(yùn)行過程，提出了影響倉庫運(yùn)行效益的若干優(yōu)化調(diào)度問題，并分別采用時(shí)態(tài)邏輯、模擬退火、遺傳算法、神經(jīng)網(wǎng)絡(luò)等方法進(jìn)行了仿真研究；徐香玲[2]、劉韜[3]、王雯等[4]分別用專家系統(tǒng)、賦時(shí)Petri網(wǎng)、遺傳算法對(duì)自動(dòng)化立體倉庫整個(gè)出入/庫調(diào)度過程進(jìn)行了仿真研究；陳國(guó)仁等[5]用聰明蟻群算法來進(jìn)行堆垛機(jī)作業(yè)路徑調(diào)度規(guī)劃.研究結(jié)果都表明這些方法確實(shí)可以提高自動(dòng)化立體倉庫的作業(yè)效率，但其基本都是屬于集中式控制，存在著結(jié)構(gòu)僵化，系統(tǒng)適應(yīng)性差、容錯(cuò)性差等問題.

本文主要研究基于匈牙利算法的自動(dòng)化立體倉庫的出入庫調(diào)度優(yōu)化問題，而采用合理的方法和模型解決其所包含的優(yōu)化調(diào)度問題是整個(gè)問題的關(guān)鍵, 可以從根本上提高倉庫的運(yùn)行效率和企業(yè)的經(jīng)濟(jì)效益.本文主要使用的研究方法有匈牙利算法、AHP層次分析法、Petri網(wǎng).

1 自動(dòng)化立體倉庫出入庫優(yōu)化的模型建立

1.1 貨位指派問題的研究

由于倉庫所要存放的貨物種類、貨物數(shù)量出入庫頻率均有一定的范圍,因此我們可以對(duì)倉庫的庫位進(jìn)行分區(qū)規(guī)劃.在進(jìn)行貨位分區(qū)時(shí)，可作如下假設(shè)：(a)貨物的存放種類已知.(b)貨物每種類的單位時(shí)間內(nèi)存放的數(shù)量己知.(c)每一種貨物的存取頻率已知.因此建立權(quán)值矩陣，單位時(shí)間內(nèi)堆垛機(jī)取放某種貨物的工作量與該貨物的出入庫頻率和該貨物存放的位置有關(guān)，將該貨物的出入庫頻率乘以堆垛機(jī)運(yùn)行至存放位置所用時(shí)間作為權(quán)值因子，即：

Cij=fi×Tj

(1)

其中fi-i種貨物的出入庫頻率,Tj-堆垛機(jī)從原點(diǎn)到j(luò)區(qū)取放的標(biāo)準(zhǔn)時(shí)間(Tj=j×T間).

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

(2)

1.2 立體倉庫巷道指派問題的研究

自動(dòng)化立體倉庫的系統(tǒng)評(píng)價(jià)也是屬于多目標(biāo)、多判據(jù)的系統(tǒng)評(píng)價(jià).對(duì)于多巷道立體倉庫來說，各個(gè)巷道庫存狀況和堆垛機(jī)的狀態(tài)都是不同的.所以對(duì)于完成某個(gè)入/出庫任務(wù)來說，就存在一個(gè)較為優(yōu)選的巷道來完成任務(wù)更為合適.不同巷道指標(biāo)不同，不同的指標(biāo)具有的重要程度也不同.

在確立了評(píng)價(jià)指標(biāo)的基礎(chǔ)上，結(jié)合立體倉庫的實(shí)際情況，利用層次分析法[6]建立層次分別針對(duì)入庫和出庫任務(wù)給出的各項(xiàng)標(biāo)準(zhǔn)的重要性進(jìn)行兩兩比較.最終確定了出入庫的權(quán)重,最終結(jié)果見表1、表2.

表1 入庫指標(biāo)及權(quán)重

表2出庫指標(biāo)及權(quán)重

備選方案權(quán)重巷道堆垛機(jī)累計(jì)工作時(shí)間0.229 5出庫貨物在該巷道的現(xiàn)存數(shù)量0.121 0該巷道接收任務(wù)預(yù)計(jì)完成時(shí)間0.329 0該巷道中該種類貨物的入庫時(shí)間0.166 7該巷道待出入庫任務(wù)數(shù)量0.153 8

1.3 巷道的出入庫能力計(jì)算

本課題研究所建立的模型為三巷道的立體化倉庫，因此以三巷道完成3項(xiàng)任務(wù)為例來研究匈牙利算法應(yīng)用于立體倉庫調(diào)度多任務(wù)分派問題時(shí)，效益矩陣代表的意義以及效益矩陣各項(xiàng)代表的意義.a11a21a31代表1巷道完成3項(xiàng)任務(wù)分別需要付出的代價(jià)，a12a22a32代表2巷道完成3項(xiàng)任務(wù)分別需要付出的代價(jià)，a13a23a33代表3巷道完成3項(xiàng)任務(wù)分別需要付出的代價(jià).即三巷道完成3項(xiàng)任務(wù)時(shí)，需要計(jì)算9個(gè)數(shù)值:

(3)

陣中各項(xiàng)的計(jì)算方法相同，下面以a11為例介紹各項(xiàng)的計(jì)算方法，以多任務(wù)入庫為例，各巷道入庫能力評(píng)價(jià)指標(biāo)及權(quán)重見表1所示，各個(gè)指標(biāo)的獲取方法在根據(jù)實(shí)際假設(shè)出來后，再結(jié)合各指標(biāo)對(duì)應(yīng)的權(quán)重進(jìn)行計(jì)算，計(jì)算方法如下：

a11=α×x1+β×x2+γ×x3+δ×x4+ε×x5

(4)

a11:實(shí)體巷道1接受任務(wù)的代價(jià);α，β，γ，δ：衡量巷道能力的指標(biāo)權(quán)重；x1,…,x5：入庫能力衡量指標(biāo)計(jì)算值,其他各項(xiàng)與a11的計(jì)算方法相同,最后可得到效益矩陣.

2 基于匈牙利算法的自動(dòng)化立體倉庫出入庫的調(diào)度優(yōu)化

2.1 匈牙利算法[7]的原理

一個(gè)關(guān)于矩陣中0元素的定理：系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最少直線數(shù),這種解法稱為匈牙利法.有n個(gè)實(shí)體巷道，怎樣指派n種貨物去選擇巷道；有n項(xiàng)貨位，怎樣指定n種貨物去放貨取貨,這就需要利用匈牙利算法去解決最優(yōu)指派問題.由于每個(gè)巷道出入庫能力不同，各巷道完成的任務(wù)不同(或所費(fèi)時(shí)間)，效率也不同,于是產(chǎn)生了應(yīng)指派哪個(gè)巷道去接受哪項(xiàng)任務(wù)的問題，以便使完成n項(xiàng)貨物的總效率最高(或所需的總時(shí)間最小).如何有效地指派貨物選擇的巷道，并進(jìn)行合理有效的貨位選擇，就成為自動(dòng)化立體倉庫需要解決的重要問題.

此模型也說明了第j項(xiàng)貨物只能由1個(gè)巷道去完成；第i個(gè)巷道只能接收1種貨物.解矩陣Xij中各行各列的元素之和都是1.匈牙利算法的一般流程如圖3所示.

圖3 匈牙利算法的計(jì)算流程圖

2.2 貨位優(yōu)化實(shí)例

由于多任務(wù)入庫過程與多任務(wù)出庫過程相似，因此我們只討論多任務(wù)入庫過程.在已知各個(gè)出庫指標(biāo)數(shù)據(jù)的情況下，可以得出各個(gè)巷道接收每種貨物的入庫代價(jià),見表3.利用匈牙利算法優(yōu)化效益矩陣可以得出最終優(yōu)化結(jié)果,見表4.因此，利用匈牙利算法優(yōu)化后可以得出貨物1→2巷道，貨物2→3巷道，貨物3→1巷道.

表3 各巷道接收貨物所需代價(jià)表

表4 最優(yōu)指派方案

2.3 巷道優(yōu)化實(shí)例

由于本課題研究的需要，我們?cè)诖酥豢紤]一次指派問題，并把所解決的問題簡(jiǎn)單化了.在立體倉庫模型已經(jīng)建立的基礎(chǔ)上，我們把4層5列(一共300個(gè)貨位)的倉庫分為5個(gè)區(qū)域：A、B、C、D和E區(qū).根據(jù)本課題所建立的自動(dòng)化立體倉庫以及假設(shè)的參數(shù)，可以得出堆垛機(jī)的運(yùn)行時(shí)間，在其條件下可以計(jì)算出權(quán)值矩陣，并將其權(quán)值矩陣經(jīng)行優(yōu)化，得出合理的指派.因此，可以得出權(quán)值矩陣Cij,見表5.經(jīng)過一系列的匈牙利算法得到最優(yōu)指派方案,見表6.零件1→B區(qū)，零件2→D區(qū)，零件3→E區(qū)，零件4→C區(qū)，零件5→A區(qū).

表5 權(quán)值矩陣

表6 最優(yōu)指派方案

3 立體倉庫出入庫調(diào)度Petri網(wǎng)的模擬仿真

自動(dòng)化立體倉庫的出入庫執(zhí)行過程是一個(gè)離散的事件序列.在各種方法中，Petri網(wǎng)可以很好地模擬這樣的離散事件系統(tǒng),可分為6個(gè)對(duì)象模塊：入庫緩沖區(qū)模塊、入庫臺(tái)模塊、堆垛機(jī)入庫模塊、堆垛機(jī)出庫模塊、出庫臺(tái)模塊和出庫緩沖區(qū)模塊.各個(gè)模塊間相互獨(dú)立，通過過渡變遷聯(lián)系起來.因此采用Petri網(wǎng)仿真建模軟件VisObjNet來建立系統(tǒng)的自動(dòng)化立體倉庫仿真模型，并對(duì)其進(jìn)行仿真，結(jié)果顯示其效果良好.

4 結(jié)束語

本文利用指派問題對(duì)貨位劃分區(qū)域進(jìn)行貨物的指派，并結(jié)合了匈牙利算法優(yōu)化，較好地解決了貨位指派、巷道選擇的合理化問題.建立了出入庫調(diào)度問題的數(shù)學(xué)模型，并根據(jù)調(diào)度原則提出了約束條件.最后研究了運(yùn)用Petri網(wǎng)來模擬仿真自動(dòng)化立體倉庫出入庫調(diào)度過程.考慮到倉庫管理的復(fù)雜性和特殊性，純粹地?cái)?shù)學(xué)分析難免以偏概全而導(dǎo)致實(shí)用性的喪失，本文在建立模型假設(shè)研究的基礎(chǔ)上，采用的匈牙利算法并對(duì)立體倉庫調(diào)度優(yōu)化進(jìn)行了改進(jìn).

參考文獻(xiàn)

[1] 田國(guó)會(huì).自動(dòng)化立體倉庫若干優(yōu)化調(diào)度問題及其研究進(jìn)展[J]. 山東工業(yè)大學(xué)學(xué)報(bào)，2001,(2)：12-17.

[2] 徐香玲，傅衛(wèi)平，李德信,等.基于專家系統(tǒng)的自動(dòng)化立體倉庫出入庫調(diào)度研究[J]. 物流技術(shù)，2005，(2)：38-40，51.

[3] 劉 韜，傅衛(wèi)平，王 雯,等.基于面向?qū)ο筚x時(shí)Petri網(wǎng)的出入庫系統(tǒng)建模[J]. 系統(tǒng)仿真學(xué)報(bào)，2006，18(3)：537-541.

[4] Wang W, Fu W P, Ma M Y,etal.. Selection of AS/RS scheduling rules based on genetic algorithm[C]. Proceedings of the IEEE International Conference on Automation and Logistics, ICAL 2007:536-540．

[5] 陳國(guó)仁. 物流輸送系統(tǒng)的智能控制與調(diào)度研究[D]. 北京：北京機(jī)械工業(yè)自動(dòng)化研究所碩士學(xué)位論文，2004.

[6] 莊鎖法. 基于層次分析法的綜合評(píng)價(jià)模型[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2000,23(4)：582-590.

[7] 張旭輝，朱宏輝，鄭啟忠. 最優(yōu)指派問題匈牙利算法的探討與C++實(shí)現(xiàn)[J]. 物流技術(shù)，2004:(5)：67-69.