郭鵬輝， 肖 飛， 賈正榮， 芮萬智， 許 金

(海軍工程大學(xué) 艦船綜合電力技術(shù)國防科技重點(diǎn)實驗室，湖北 武漢 430033)

0 引 言

在電機(jī)智能制造領(lǐng)域，大規(guī)模自動化生產(chǎn)線極大地減少了人力成本，提高了生產(chǎn)效率，但是對企業(yè)倉儲系統(tǒng)的存儲密度和揀選出貨效率提出很高要求。倉儲系統(tǒng)是現(xiàn)代物流系統(tǒng)和供應(yīng)鏈的重要組成部分[1-2]。用于制造業(yè)的傳統(tǒng)倉儲系統(tǒng)以自動化立體倉庫[3-4]為代表，由于過道設(shè)施的存在，其存儲密度受限，進(jìn)而容易導(dǎo)致物流補(bǔ)貨滯后的現(xiàn)象。因此，現(xiàn)代電機(jī)生產(chǎn)制造企業(yè)迫切需要新型的智能倉儲技術(shù)和車間物流方案，實現(xiàn)高密度的存儲和高效智能化生產(chǎn)[5-6]。

為實現(xiàn)高密度存儲，物流領(lǐng)域研究了一種新興的網(wǎng)格式存儲(GBS)系統(tǒng)[7-8](又稱PBS系統(tǒng))。該系統(tǒng)具有存儲密度大、易于安裝布局等特點(diǎn)，已應(yīng)用于倉庫和配送中心、自動化停車庫、碼頭集裝箱等領(lǐng)域[8-10]?，F(xiàn)有文獻(xiàn)主要研究不同配置下的GBS系統(tǒng)中單個負(fù)載或多個負(fù)載揀選到系統(tǒng)出口的方法，其中配置主要指空位的數(shù)量和初始分布。多數(shù)文獻(xiàn)研究單一負(fù)載揀選問題。Gue[7]提出GBS形式的高密度存儲系統(tǒng)，研究了單一負(fù)載出庫的最優(yōu)方法，其研究假設(shè)單個空位在出口處或多個空位在出口處排成一行。Kota等[11]在文獻(xiàn)[7]的基礎(chǔ)上進(jìn)一步推導(dǎo)了單一負(fù)載揀選時間的閉合表達(dá)式，其研究假設(shè)空位隨機(jī)分布，對于單個和2個空位給出了最優(yōu)解，而對于2個以上的空位則給出一種啟發(fā)式方法。Alfieri等[12]研究了使用自動導(dǎo)引小車進(jìn)行負(fù)載移動的GBS系統(tǒng)變體，其研究假設(shè)初始時刻多個空位在出口處排成一行，并采用了與文獻(xiàn)[7]類似的啟發(fā)式方法。Yalcin等[13]則研究了更一般情況下的單一負(fù)載揀選最優(yōu)方法，適用于一定規(guī)模的GBS系統(tǒng)下多個空位任意分布的情況，采用經(jīng)典的A*搜索算法，對于較大規(guī)模的問題，則采用啟發(fā)式方法。

對于多負(fù)載揀選，Mirzaei等[14]研究了多負(fù)載聯(lián)合揀選問題，對于雙負(fù)載聯(lián)合揀選給出最優(yōu)方法，而對于更多數(shù)量負(fù)載的聯(lián)合揀選給出啟發(fā)式方法，其研究假設(shè)空位初始時刻位于系統(tǒng)出口處。

上述文獻(xiàn)的研究以單一模塊形式的GBS系統(tǒng)為對象，研究若干個負(fù)載揀選出庫的方法。與上述文獻(xiàn)不同，本文研究一種由多個回型GBS模塊連接而成的多模塊網(wǎng)格倉儲(MMGBS)系統(tǒng)，考慮系統(tǒng)全部負(fù)載揀選出庫的工況，先前的研究方法難以適用。為此，基于圖論模型將MMGBS系統(tǒng)抽象為節(jié)點(diǎn)和邊組成的倉庫結(jié)構(gòu)圖，根據(jù)不同的節(jié)點(diǎn)屬性，提出環(huán)與循環(huán)移動的概念，在此基礎(chǔ)上證明了最優(yōu)循環(huán)移動所需的動作數(shù)量以及對應(yīng)的系統(tǒng)配置，實現(xiàn)系統(tǒng)全負(fù)載的揀選出庫。

1 問題概述

1.1 MMGBS系統(tǒng)概述

GBS系統(tǒng)由多個矩形儲位單元密集排列而成，每個儲位上為負(fù)載或者空位，負(fù)載可以移動到相鄰的空位，如圖1所示。

圖1 GBS系統(tǒng)運(yùn)行示意圖

在GBS系統(tǒng)的基礎(chǔ)上，本文提出的MMGBS系統(tǒng)如圖2所示。系統(tǒng)分為揀貨區(qū)和備貨區(qū)。備貨區(qū)配置1個備貨模塊；揀貨區(qū)配置多個揀貨模塊。各存儲模塊為回型循環(huán)網(wǎng)格結(jié)構(gòu)。每個揀貨模塊都與備貨模塊相連通，各揀貨模塊的左下角為揀選點(diǎn)，因此MMGBS具有多個揀選點(diǎn)，與揀貨模塊一一對應(yīng)。負(fù)載置于可移動的托盤上，經(jīng)揀選點(diǎn)出庫時與托盤分離，因此系統(tǒng)中的托盤和空位數(shù)量保持不變。

圖2 MMGBS系統(tǒng)組成

1.2 動作規(guī)則和假設(shè)

系統(tǒng)中有以下3類動作規(guī)則。

(1)基本動作：一個負(fù)載從某一儲位移動到相鄰空位的過程，如圖1所示。

(2)塊動作：一條直線上連續(xù)的負(fù)載，可以作為一個負(fù)載塊，同時移動一步到相鄰空位，如圖3(a)所示。

(3)并行動作：移動路徑不沖突的基本動作或塊動作，可以并行發(fā)生，如圖3(b)所示。

圖3 塊動作與并行動作過程

本文的研究工作假設(shè)如下：(1)所有的基本動作、塊動作、并行動作耗時相同，為1步；(2)不考慮負(fù)載的揀選出庫時間，待揀選負(fù)載到達(dá)揀選點(diǎn)后即完成出庫。

1.3 全負(fù)載揀選

在實際應(yīng)用中，系統(tǒng)的庫存管理維護(hù)需要將系統(tǒng)全部負(fù)載揀選出庫。此時關(guān)注的問題不是揀選中單一負(fù)載或若干負(fù)載的方法，而是如何盡快地將系統(tǒng)中的各負(fù)載托盤依次移動至揀貨模塊的揀選點(diǎn)出庫。單個存儲模塊為回型結(jié)構(gòu)，可實現(xiàn)與傳統(tǒng)旋轉(zhuǎn)貨架系統(tǒng)[13]類似的循環(huán)移動，但系統(tǒng)中的備貨模塊沒有揀選點(diǎn)，無法通過自身的循環(huán)移動使負(fù)載出庫。為此，本文在1.2節(jié)所述的系統(tǒng)動作規(guī)則下，探究一種移動動作組合，使系統(tǒng)中的所有負(fù)載形成一種循環(huán)移動，從而依次從揀選點(diǎn)出庫。

2 基于圖論模型的系統(tǒng)結(jié)構(gòu)抽象

2.1 位置類型

將MMGBS系統(tǒng)中的每個儲位作為一個節(jié)點(diǎn)，儲位之間的連接關(guān)系通過邊表示，通過節(jié)點(diǎn)與邊構(gòu)成的集合描述的系統(tǒng)結(jié)構(gòu)稱為系統(tǒng)結(jié)構(gòu)圖，則圖2所示的MMGBS系統(tǒng)結(jié)構(gòu)可以抽象為圖4。

圖4 系統(tǒng)結(jié)構(gòu)圖抽象

根據(jù)節(jié)點(diǎn)的位置，可以將節(jié)點(diǎn)分為以下3種類型，如圖4。

(1)直線節(jié)點(diǎn)“1”和“2”：“1”和“2”分別代表水平和垂直方向。

(2)轉(zhuǎn)向節(jié)點(diǎn)“∧”：轉(zhuǎn)向節(jié)點(diǎn)表示轉(zhuǎn)向(90°)，在轉(zhuǎn)向節(jié)點(diǎn)兩邊的直線節(jié)點(diǎn)方向不同。轉(zhuǎn)向節(jié)點(diǎn)至多能夠連接2個節(jié)點(diǎn)。

(3)交叉節(jié)點(diǎn)“+”：交叉節(jié)點(diǎn)至少連接3個節(jié)點(diǎn)，至多連接4個節(jié)點(diǎn)。交叉節(jié)點(diǎn)表示多個節(jié)點(diǎn)的交匯。

另外，節(jié)點(diǎn)具有實節(jié)點(diǎn)和空節(jié)點(diǎn)2種屬性。如果一個節(jié)點(diǎn)對應(yīng)的儲位上放置有托盤，該節(jié)點(diǎn)被占用，稱為實節(jié)點(diǎn)；對應(yīng)地，沒有托盤的節(jié)點(diǎn)稱為空節(jié)點(diǎn)。實節(jié)點(diǎn)上的負(fù)載能夠向空節(jié)點(diǎn)移動，一次只能移動至相鄰的節(jié)點(diǎn)。

2.2 環(huán)與循環(huán)移動

2.2.1 環(huán)

定義1：在系統(tǒng)結(jié)構(gòu)圖(節(jié)點(diǎn)與邊的集合)中，由若干個節(jié)點(diǎn)和邊構(gòu)成一個子集，如果有：(1)子集中任意一個節(jié)點(diǎn)均有子集中的2個其他節(jié)點(diǎn)與之相連；(2)在該子集內(nèi)，所有轉(zhuǎn)向節(jié)點(diǎn)與交叉節(jié)點(diǎn)數(shù)量之和為4的正整數(shù)倍；(3)該子集的真子集均不滿足條件(1)和(2)，則該子集稱為環(huán)。

當(dāng)子集有任意真子集滿足上述條件(1)和(2)時，該子集并非環(huán)，而是多個環(huán)的并集。

圖5所示均為環(huán)。

圖5 環(huán)的示例

另外，環(huán)作為倉庫結(jié)構(gòu)圖的子集，其中交叉節(jié)點(diǎn)只保留2個邊，因此對于環(huán)而言，原本的系統(tǒng)結(jié)構(gòu)圖中的交叉節(jié)點(diǎn)變換為在環(huán)內(nèi)的直線節(jié)點(diǎn)或轉(zhuǎn)向節(jié)點(diǎn)。

因此，圖5所示環(huán)的示例應(yīng)當(dāng)變?yōu)閳D6所示。

圖6 改變交叉節(jié)點(diǎn)后的環(huán)示例

經(jīng)過變換后，環(huán)內(nèi)轉(zhuǎn)向節(jié)點(diǎn)的數(shù)量總為4的正整數(shù)倍。

2.2.2 循環(huán)移動

引入環(huán)的概念后，期望在環(huán)內(nèi)形成一種特殊的動作組合，執(zhí)行該動作組合后，可以實現(xiàn)環(huán)內(nèi)負(fù)載的快速循環(huán)，從而提高調(diào)度效率。

定義2：經(jīng)過一定的動作，使每一負(fù)載移動至其所在實節(jié)點(diǎn)后(或前)的第一個實節(jié)點(diǎn)位置，稱為一次循環(huán)移動。

證明：假設(shè)(x(t),y(t),u(t),v(t))T為系統(tǒng)(1.1)的解，由系統(tǒng)(1.1)的第一個方程得，則由引理2.1的結(jié)果，易知

循環(huán)移動如圖7所示。圖中有字母標(biāo)注的節(jié)點(diǎn)為帶有負(fù)載的實節(jié)點(diǎn)，無字母標(biāo)注的為空節(jié)點(diǎn)。

圖7 循環(huán)移動

一次循環(huán)移動所需的動作數(shù)量決定了倉庫系統(tǒng)的調(diào)度效率。

3 最優(yōu)循環(huán)移動

循環(huán)移動通過1.2節(jié)所述的系統(tǒng)動作規(guī)則實現(xiàn)，因此其一次循環(huán)移動所需的動作數(shù)量≥1。如果能夠找到動作數(shù)量最少的循環(huán)移動動作組合，且該動作組合中的實節(jié)點(diǎn)數(shù)量最多，則該循環(huán)移動是最優(yōu)的，對應(yīng)最優(yōu)調(diào)度效率。

引理1：不存在動作數(shù)量為1的循環(huán)移動。

證明：

采用反證法。

假設(shè)存在動作數(shù)量為1的循環(huán)移動，由于每個負(fù)載只能動作1次，且動作只能移動至相鄰的節(jié)點(diǎn)，根據(jù)循環(huán)移動的定義(定義2)，對于每一個實節(jié)點(diǎn)處的負(fù)載，其相鄰的前一個位置上必然存在負(fù)載，是實節(jié)點(diǎn)。

故環(huán)內(nèi)每個節(jié)點(diǎn)均是實節(jié)點(diǎn)，且能夠進(jìn)行塊動作移動，因此環(huán)應(yīng)當(dāng)如圖8所示。

圖8 動作數(shù)量為1的循環(huán)移動對應(yīng)的環(huán)

顯然，該“環(huán)”不符合環(huán)的定義，其轉(zhuǎn)向節(jié)點(diǎn)數(shù)量為0，而不是4的正整數(shù)倍，假設(shè)不成立。證畢。

根據(jù)引理1，循環(huán)移動所需的動作數(shù)量≥2，因此，如果存在動作數(shù)量為2的循環(huán)移動，則該動作組合為效率最優(yōu)。

注意到在一個環(huán)內(nèi)只存在直線節(jié)點(diǎn)與轉(zhuǎn)向節(jié)點(diǎn)。轉(zhuǎn)向節(jié)點(diǎn)將直線節(jié)點(diǎn)集隔開，因此可以根據(jù)環(huán)對應(yīng)的實際倉庫儲位和轉(zhuǎn)運(yùn)路徑，簡化環(huán)的結(jié)構(gòu)，如圖9所示，將環(huán)內(nèi)的轉(zhuǎn)向節(jié)點(diǎn)用頂點(diǎn)表示，被轉(zhuǎn)向節(jié)點(diǎn)隔開的直線節(jié)點(diǎn)集用點(diǎn)劃線表示。

圖9 環(huán)結(jié)構(gòu)的簡化

結(jié)合環(huán)的簡化，引入環(huán)的頂點(diǎn)的概念。

定義3：在環(huán)內(nèi)，轉(zhuǎn)向節(jié)點(diǎn)是頂點(diǎn)，2個頂點(diǎn)之間為直線節(jié)點(diǎn)集或者沒有任何節(jié)點(diǎn)。

當(dāng)2個頂點(diǎn)之間為直線節(jié)點(diǎn)集時，直線節(jié)點(diǎn)集連同與之相連的2個頂點(diǎn)可以執(zhí)行1.2節(jié)所述的塊動作；2個頂點(diǎn)之間沒有任何節(jié)點(diǎn)可以視為直線節(jié)點(diǎn)集的特殊情形(即2個頂點(diǎn)之間為空節(jié)點(diǎn)集)，此時2個頂點(diǎn)可以執(zhí)行1.2節(jié)所述的基本動作。

定理1：對于頂點(diǎn)數(shù)量為偶數(shù)的環(huán)，最優(yōu)循環(huán)移動需要2步并行動作，如圖10所示。

圖10 最優(yōu)循環(huán)移動

圖10中，環(huán)外的實線表示對應(yīng)的頂點(diǎn)之間的直線節(jié)點(diǎn)上均有負(fù)載，實線轉(zhuǎn)折處的頂點(diǎn)也有負(fù)載。并且，對應(yīng)最優(yōu)循環(huán)移動的各節(jié)點(diǎn)初始布置為：(1)所有非頂點(diǎn)的節(jié)點(diǎn)放置負(fù)載；(2)相鄰的2個頂點(diǎn)，一個為空節(jié)點(diǎn)，另一個為實節(jié)點(diǎn)。

那么，以上初始的倉庫負(fù)載布置稱為最優(yōu)負(fù)載布置。

進(jìn)而，設(shè)環(huán)內(nèi)節(jié)點(diǎn)數(shù)量為nnode，頂點(diǎn)數(shù)量為nvertex，在最優(yōu)負(fù)載布置下，所需的空節(jié)點(diǎn)數(shù)量為nvertex/2，可以放置的負(fù)載數(shù)量ncap為

ncap=nnode-nvertex/2

(1)

最優(yōu)負(fù)載布置下環(huán)內(nèi)可以放置的負(fù)載數(shù)量ncap稱為環(huán)的載貨量。

證明：

最優(yōu)性包含2個層面。第1層面為循環(huán)移動所需的動作數(shù)量最優(yōu)；第2層面為在最優(yōu)循環(huán)移動的基礎(chǔ)上使環(huán)內(nèi)的負(fù)載數(shù)量(即實節(jié)點(diǎn)數(shù)量)最大化。

首先證明循環(huán)移動動作數(shù)量最優(yōu)。

最優(yōu)循環(huán)移動的動作數(shù)量為2。

根據(jù)引理1，不存在動作數(shù)量為1的循環(huán)移動，因此定理1中，通過2步動作實現(xiàn)循環(huán)移動即為最優(yōu)的動作數(shù)量。

然后證明環(huán)內(nèi)的負(fù)載數(shù)量最大。

定理1對應(yīng)的最優(yōu)負(fù)載配置中，相鄰的2個頂點(diǎn)一個為空節(jié)點(diǎn)、一個為實節(jié)點(diǎn)，其余所有節(jié)點(diǎn)也為實節(jié)點(diǎn)。在此基礎(chǔ)上增加負(fù)載，則負(fù)載只能放置于空的頂點(diǎn)處，無論放置于哪個頂點(diǎn)，環(huán)內(nèi)至少存在3個相鄰的頂點(diǎn)均為實節(jié)點(diǎn)，如圖11所示。對于圖11中的情況，任選一個方向，3個相鄰頂點(diǎn)中必然存在一個節(jié)點(diǎn)，其移動到下一實節(jié)點(diǎn)位置至少需要3步，即該情況下循環(huán)移動所需的動作數(shù)量≥3。

圖11 3個相鄰頂點(diǎn)均為實節(jié)點(diǎn)的情況

可見，環(huán)內(nèi)負(fù)載數(shù)量更多的情況，其循環(huán)移動的動作數(shù)量并非最優(yōu)。

證畢。

4 實例分析

根據(jù)上述理論結(jié)果，對MMGBS系統(tǒng)案例進(jìn)行分析驗證。為使循環(huán)移動的過程圖描述清晰，以一個簡化的MMGBS系統(tǒng)為對象構(gòu)建循環(huán)移動，其基本模塊配置為：1個備貨模塊，共2×7=14個儲位；2個揀貨模塊，每個模塊有2×3=6個儲位。對于更大的MMGBS系統(tǒng)，構(gòu)建原理相同。

根據(jù)系統(tǒng)的連接關(guān)系，構(gòu)建經(jīng)過系統(tǒng)所有負(fù)載的環(huán)，并確定環(huán)的轉(zhuǎn)向節(jié)點(diǎn)(即頂點(diǎn))，如圖12所示。則由定理1，可確定系統(tǒng)最優(yōu)循環(huán)移動所需的初始負(fù)載配置以及循環(huán)移動的過程，如圖13所示。圖13(a)為環(huán)簡圖表示的循環(huán)移動過程，圖13(b)為實際的循環(huán)移動過程。

圖12 系統(tǒng)環(huán)構(gòu)建示意圖

圖13 系統(tǒng)最優(yōu)循環(huán)過程

圖13所示的循環(huán)移動過程中，nnode=14+6+6=26，nvertex=12，則實現(xiàn)最優(yōu)循環(huán)移動對應(yīng)的系統(tǒng)負(fù)載容量為

ncap=nnode-nvertex/2=20

(2)

每次循環(huán)移動經(jīng)過2步動作，將2個負(fù)載移動至揀選點(diǎn)然后出庫，則經(jīng)過10次循環(huán)移動后，系統(tǒng)中的負(fù)載全部經(jīng)由揀選點(diǎn)出庫。

5 結(jié) 語

針對傳統(tǒng)倉儲系統(tǒng)存儲密度與現(xiàn)代電機(jī)智能制造生產(chǎn)線不匹配的問題，本文提出了一種MMGBS系統(tǒng)，并針對MMGBS系統(tǒng)中全負(fù)載揀選的實際應(yīng)用需求，提出了一種最優(yōu)循環(huán)移動方法。建立了系統(tǒng)結(jié)構(gòu)的圖模型，提出了環(huán)和循環(huán)移動的概念，通過構(gòu)建經(jīng)過系統(tǒng)所有負(fù)載的環(huán)，得到了系統(tǒng)最優(yōu)循環(huán)的移動動作方案和負(fù)載配置。最后，以一個MMGBS系統(tǒng)實例為對象，實現(xiàn)了本文所提最優(yōu)循環(huán)移動的構(gòu)建，滿足了系統(tǒng)全負(fù)載快速揀選出庫的工況需求。此外，本文所提出的最優(yōu)循環(huán)移動方法，可給出多模塊網(wǎng)格倉儲系統(tǒng)的總體出庫效率上界，評估不同配置系統(tǒng)的性能，為系統(tǒng)的性能分析和設(shè)計優(yōu)化提供一定的理論依據(jù)。