多模塊網格倉儲系統最優循環揀選方法*

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

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

0 引 言

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

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

對于多負載揀選，Mirzaei等[14]研究了多負載聯合揀選問題，對于雙負載聯合揀選給出最優方法，而對于更多數量負載的聯合揀選給出啟發式方法，其研究假設空位初始時刻位于系統出口處。

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

1 問題概述

1.1 MMGBS系統概述

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

圖1 GBS系統運行示意圖

在GBS系統的基礎上，本文提出的MMGBS系統如圖2所示。系統分為揀貨區和備貨區。備貨區配置1個備貨模塊；揀貨區配置多個揀貨模塊。各存儲模塊為回型循環網格結構。每個揀貨模塊都與備貨模塊相連通，各揀貨模塊的左下角為揀選點，因此MMGBS具有多個揀選點，與揀貨模塊一一對應。負載置于可移動的托盤上，經揀選點出庫時與托盤分離，因此系統中的托盤和空位數量保持不變。

圖2 MMGBS系統組成

1.2 動作規則和假設

系統中有以下3類動作規則。

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

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

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

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

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

1.3 全負載揀選

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

2 基于圖論模型的系統結構抽象

2.1 位置類型

將MMGBS系統中的每個儲位作為一個節點，儲位之間的連接關系通過邊表示，通過節點與邊構成的集合描述的系統結構稱為系統結構圖，則圖2所示的MMGBS系統結構可以抽象為圖4。

圖4 系統結構圖抽象

根據節點的位置，可以將節點分為以下3種類型，如圖4。

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

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

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

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

2.2 環與循環移動

2.2.1 環

定義1：在系統結構圖(節點與邊的集合)中，由若干個節點和邊構成一個子集，如果有：(1)子集中任意一個節點均有子集中的2個其他節點與之相連；(2)在該子集內，所有轉向節點與交叉節點數量之和為4的正整數倍；(3)該子集的真子集均不滿足條件(1)和(2)，則該子集稱為環。

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

圖5所示均為環。

圖5 環的示例

另外，環作為倉庫結構圖的子集，其中交叉節點只保留2個邊，因此對于環而言，原本的系統結構圖中的交叉節點變換為在環內的直線節點或轉向節點。

因此，圖5所示環的示例應當變為圖6所示。

圖6 改變交叉節點后的環示例

經過變換后，環內轉向節點的數量總為4的正整數倍。

2.2.2 循環移動

引入環的概念后，期望在環內形成一種特殊的動作組合，執行該動作組合后，可以實現環內負載的快速循環，從而提高調度效率。

定義2：經過一定的動作，使每一負載移動至其所在實節點后(或前)的第一個實節點位置，稱為一次循環移動。

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

循環移動如圖7所示。圖中有字母標注的節點為帶有負載的實節點，無字母標注的為空節點。

圖7 循環移動

一次循環移動所需的動作數量決定了倉庫系統的調度效率。

3 最優循環移動

循環移動通過1.2節所述的系統動作規則實現，因此其一次循環移動所需的動作數量≥1。如果能夠找到動作數量最少的循環移動動作組合，且該動作組合中的實節點數量最多，則該循環移動是最優的，對應最優調度效率。

引理1：不存在動作數量為1的循環移動。

證明：

采用反證法。

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

故環內每個節點均是實節點，且能夠進行塊動作移動，因此環應當如圖8所示。

圖8 動作數量為1的循環移動對應的環

顯然，該“環”不符合環的定義，其轉向節點數量為0，而不是4的正整數倍，假設不成立。證畢。

根據引理1，循環移動所需的動作數量≥2，因此，如果存在動作數量為2的循環移動，則該動作組合為效率最優。

注意到在一個環內只存在直線節點與轉向節點。轉向節點將直線節點集隔開，因此可以根據環對應的實際倉庫儲位和轉運路徑，簡化環的結構，如圖9所示，將環內的轉向節點用頂點表示，被轉向節點隔開的直線節點集用點劃線表示。

圖9 環結構的簡化

結合環的簡化，引入環的頂點的概念。

定義3：在環內，轉向節點是頂點，2個頂點之間為直線節點集或者沒有任何節點。

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

定理1：對于頂點數量為偶數的環，最優循環移動需要2步并行動作，如圖10所示。

圖10 最優循環移動

圖10中，環外的實線表示對應的頂點之間的直線節點上均有負載，實線轉折處的頂點也有負載。并且，對應最優循環移動的各節點初始布置為：(1)所有非頂點的節點放置負載；(2)相鄰的2個頂點，一個為空節點，另一個為實節點。

那么，以上初始的倉庫負載布置稱為最優負載布置。

進而，設環內節點數量為nnode，頂點數量為nvertex，在最優負載布置下，所需的空節點數量為nvertex/2，可以放置的負載數量ncap為

ncap=nnode-nvertex/2

(1)

最優負載布置下環內可以放置的負載數量ncap稱為環的載貨量。

證明：

最優性包含2個層面。第1層面為循環移動所需的動作數量最優；第2層面為在最優循環移動的基礎上使環內的負載數量(即實節點數量)最大化。

首先證明循環移動動作數量最優。

最優循環移動的動作數量為2。

根據引理1，不存在動作數量為1的循環移動，因此定理1中，通過2步動作實現循環移動即為最優的動作數量。

然后證明環內的負載數量最大。

定理1對應的最優負載配置中，相鄰的2個頂點一個為空節點、一個為實節點，其余所有節點也為實節點。在此基礎上增加負載，則負載只能放置于空的頂點處，無論放置于哪個頂點，環內至少存在3個相鄰的頂點均為實節點，如圖11所示。對于圖11中的情況，任選一個方向，3個相鄰頂點中必然存在一個節點，其移動到下一實節點位置至少需要3步，即該情況下循環移動所需的動作數量≥3。

圖11 3個相鄰頂點均為實節點的情況

可見，環內負載數量更多的情況，其循環移動的動作數量并非最優。

證畢。

4 實例分析

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

根據系統的連接關系，構建經過系統所有負載的環，并確定環的轉向節點(即頂點)，如圖12所示。則由定理1，可確定系統最優循環移動所需的初始負載配置以及循環移動的過程，如圖13所示。圖13(a)為環簡圖表示的循環移動過程，圖13(b)為實際的循環移動過程。

圖12 系統環構建示意圖

圖13 系統最優循環過程

圖13所示的循環移動過程中，nnode=14+6+6=26，nvertex=12，則實現最優循環移動對應的系統負載容量為

ncap=nnode-nvertex/2=20

(2)

每次循環移動經過2步動作，將2個負載移動至揀選點然后出庫，則經過10次循環移動后，系統中的負載全部經由揀選點出庫。

5 結 語

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