隨機(jī)倉(cāng)庫(kù)布局問(wèn)題模型與算法研究

摘要：通過(guò)討論隨機(jī)條件下倉(cāng)庫(kù)布局問(wèn)題，建立了隨機(jī)倉(cāng)庫(kù)布局問(wèn)題機(jī)會(huì)約束規(guī)劃模型，并設(shè)計(jì)出基于隨機(jī)模擬的禁忌搜索算法求解模型，最后利用算例來(lái)驗(yàn)證算法的有效性。

關(guān)鍵詞：倉(cāng)庫(kù)布局問(wèn)題；禁忌搜索算法；機(jī)會(huì)約束規(guī)劃模型；隨機(jī)模擬

中圖分類(lèi)號(hào)：F715.6文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1002-3100(2008)07-0007-04

Abstract: In this paper， a warehouse layout problem under random environment is considered. We Propose chance-constrained programming model for the problem. Then we design a tabu search algorithm based on random simulation to achieve the approximate best solution of the models. Finally， a numerical example is presented to show the efficiency of the algorithm.

Key words: warehouse layout problem; tabu search algorithm; chance-constrained programming model; random simulation

0引言

倉(cāng)庫(kù)運(yùn)作是企業(yè)物料管理的重要部分，Tompkins[1]指出，貨物的存儲(chǔ)成本大約占貨物生產(chǎn)總成本的15%~70%，降低倉(cāng)庫(kù)運(yùn)作成本是減少生產(chǎn)成本，提高企業(yè)經(jīng)濟(jì)效益的重要突破口。倉(cāng)庫(kù)布局問(wèn)題旨在解決如何制定科學(xué)的貨物存儲(chǔ)計(jì)劃來(lái)合理地存儲(chǔ)各種不同型號(hào)的貨物，使總的搬運(yùn)成本最小化。科學(xué)的倉(cāng)庫(kù)布局能有效地指導(dǎo)貨物的存放與搬運(yùn)，減少貨物損傷，加速貨物周轉(zhuǎn)流通，從而降低存儲(chǔ)成本。

對(duì)于倉(cāng)庫(kù)布局問(wèn)題的研究，大部分都是基于以下四種存儲(chǔ)策略：基于類(lèi)的存儲(chǔ)策略、專(zhuān)門(mén)存儲(chǔ)策略、隨機(jī)存儲(chǔ)策略和共享存儲(chǔ)策略。Francis etal[2]對(duì)設(shè)備布局和選址問(wèn)題進(jìn)行了綜述，并詳細(xì)地探討了上述四種基本存儲(chǔ)策略；K.K. Lai etal[3－4]利用基于類(lèi)的存儲(chǔ)策略對(duì)紙卷倉(cāng)庫(kù)的布局問(wèn)題進(jìn)行了研究。他們把倉(cāng)庫(kù)的可利用空間劃分為面積大小相等的單元，在此基礎(chǔ)上，提出把遺傳算法用于兩階段迭代的啟發(fā)式方法，來(lái)分析倉(cāng)庫(kù)布局問(wèn)題，使紙卷總的搬運(yùn)成本最小化；Larson etal[5]提出把貨物根據(jù)其周轉(zhuǎn)率的不同分為不同的等級(jí)，周轉(zhuǎn)率越高的貨物堆放在離出口越近的位置，根據(jù)專(zhuān)門(mén)存儲(chǔ)策略能有效地調(diào)節(jié)存儲(chǔ)空間以滿足存儲(chǔ)作業(yè)的需求，從而降低物料管理的成本；Van Oudheusdeh etal[6]利用旅行商算法，提出了針對(duì)貨架布局的解決方法；Chang和Egbelu[7]分析了在自動(dòng)存取系統(tǒng)中，搬運(yùn)工具停放位置的規(guī)劃對(duì)減少最大反應(yīng)時(shí)間的前提作用。他們研究的問(wèn)題要求一輛搬運(yùn)機(jī)械負(fù)責(zé)系統(tǒng)中一條或者多條專(zhuān)門(mén)的通道，并且通道在系統(tǒng)中的位置不變。隨著不確定優(yōu)化理論廣泛應(yīng)用，一些學(xué)者將其應(yīng)用到對(duì)倉(cāng)庫(kù)布局問(wèn)題的研究上來(lái)。Zhang、Lai和Yang[8]研究了模糊條件下的多層倉(cāng)庫(kù)的布局問(wèn)題，并設(shè)計(jì)出針對(duì)這問(wèn)題的算法；Yang和Sun[9]對(duì)倉(cāng)庫(kù)在模糊隨機(jī)條件下的布局問(wèn)題進(jìn)行了探討和研究，考慮不同貨物的貯存要求，建立了期望值模型，并為倉(cāng)庫(kù)布局問(wèn)題設(shè)計(jì)了混合智能算法。

本文討論了隨機(jī)條件下倉(cāng)庫(kù)布局問(wèn)題，建立機(jī)會(huì)約束規(guī)劃模型，并設(shè)計(jì)出基于隨機(jī)模擬的禁忌搜索算法求解模型，最后設(shè)計(jì)算例來(lái)驗(yàn)證模型的正確性與算法的有效性。

1倉(cāng)庫(kù)布局問(wèn)題概述

當(dāng)貨物到達(dá)倉(cāng)庫(kù)時(shí)，被卸放在進(jìn)出口外，決策者決定其存放位置后，由叉車(chē)把這些貨物搬運(yùn)至存放位置，相應(yīng)的倉(cāng)庫(kù)存貨清單將隨之更新，當(dāng)有訂單時(shí)將執(zhí)行相反的作業(yè)過(guò)程。在這個(gè)過(guò)程中，不考慮搬運(yùn)機(jī)械的能力限制。在給倉(cāng)庫(kù)布局的過(guò)程中，需要最大化地減少貨物總的搬運(yùn)成本。

本文假定倉(cāng)庫(kù)只有一個(gè)進(jìn)出口，且為單層結(jié)構(gòu)。倉(cāng)庫(kù)被分為面積大小相等幾列，每列又分為大小相等的單元，貨物將存儲(chǔ)在這些小單元中，某些單元將用于停放叉車(chē)等工具。同時(shí)設(shè)置一定數(shù)量的叉車(chē)通道以便貨物搬運(yùn)，通道位于每?jī)闪写鎯?chǔ)單元之間。

為了方便叉車(chē)在存儲(chǔ)單元的存取作業(yè)，更好地利用倉(cāng)庫(kù)的存儲(chǔ)空間，應(yīng)對(duì)貨物進(jìn)行分類(lèi)。貨物分類(lèi)方式多種多樣，可根據(jù)其性質(zhì)、體積、重量或周轉(zhuǎn)率等進(jìn)行分類(lèi)。例如根據(jù)體積分類(lèi)，一類(lèi)貨物包括某一體積范圍內(nèi)的所有型號(hào)的貨物，如體積在2m~2.5m范圍內(nèi)的所有型號(hào)的貨物，這樣，每類(lèi)貨物又包含不同的型號(hào)。為了方便操作，本文規(guī)定每個(gè)存儲(chǔ)單元只能存儲(chǔ)同一類(lèi)貨物，并且最多只能堆放同類(lèi)中兩種不同型號(hào)的貨物。當(dāng)某存儲(chǔ)單元堆放有兩種不同型號(hào)的同類(lèi)貨物時(shí)，必須按照一定的次序擺放，比如同一型號(hào)的貨物堆放在同一柱面上，周轉(zhuǎn)率高的貨物堆放在靠近通道的位置，比重大的貨物堆放的底層等。

當(dāng)貨物到達(dá)時(shí)，決策者將決定貨物的存儲(chǔ)位置，同時(shí)根據(jù)到達(dá)的貨物量安排一定的存儲(chǔ)空間，這樣便形成了貨物的存儲(chǔ)需求，即貨物對(duì)存儲(chǔ)空間的需求。到達(dá)的每種型號(hào)的貨物都有一定的存儲(chǔ)需求，本文假定在布局決策之前，各型號(hào)貨物的存儲(chǔ)需求已經(jīng)確定，它用來(lái)決定分配給各型號(hào)貨物的存儲(chǔ)空間。在本文中，只考慮各型號(hào)貨物的月需求量，以此作為貨物的搬運(yùn)量，各型號(hào)貨物月需求量為一個(gè)隨機(jī)變量。

在為倉(cāng)庫(kù)布局的過(guò)程中，會(huì)出現(xiàn)某型號(hào)貨物的存儲(chǔ)需求大于一個(gè)存儲(chǔ)單元存儲(chǔ)能力的現(xiàn)象，這時(shí)貨物會(huì)占用兩個(gè)或兩個(gè)以上的單元，這種貨物被稱(chēng)為“分割型貨物”。為了方便表述，把這型號(hào)的貨物根據(jù)其月需求量和存儲(chǔ)需求按比例分為不同的部分，并視為幾種不同的相互獨(dú)立的型號(hào)。例如，一種分割型貨物需要2.8個(gè)存儲(chǔ)單元來(lái)堆放，則這型號(hào)的貨物將按比例被分為三個(gè)部分，每部分占初始需求量和存儲(chǔ)需求的1/2.5、1/2.5、0.8/2.5。為了簡(jiǎn)化問(wèn)題，本文假定要布局決策前貨物已經(jīng)完成了上述的分割，這樣，每種型號(hào)貨物的存儲(chǔ)需求不會(huì)超出存儲(chǔ)單元的存儲(chǔ)能力。

假定倉(cāng)庫(kù)擁有足夠的存儲(chǔ)空間來(lái)存放貨物，同時(shí)不考慮叉車(chē)的能力限制，倉(cāng)庫(kù)布局問(wèn)題研究的目的是使貨物總的搬運(yùn)費(fèi)用最小化。貨物搬運(yùn)費(fèi)用可看作是搬運(yùn)的貨物量與其搬運(yùn)距離的乘積，貨物搬運(yùn)的總費(fèi)用就是各型號(hào)的貨物搬運(yùn)費(fèi)用之和。其中的搬運(yùn)的貨物量由各型號(hào)貨物的月需求量計(jì)算得出，搬運(yùn)距離為叉車(chē)搬運(yùn)貨物時(shí)的行走距離。事實(shí)上，叉車(chē)不可能?chē)?yán)格的按照直線路程行走，其行走距離的計(jì)算是不精確的，它的值可以利用存儲(chǔ)單元中心到進(jìn)出口的水平距離來(lái)估計(jì)得出。

2隨機(jī)倉(cāng)庫(kù)布局問(wèn)題的機(jī)會(huì)約束規(guī)劃模型

3基于隨機(jī)模擬的禁忌搜索算法

Liu[10]指出可以利用混合智能算法來(lái)解決不確定規(guī)劃問(wèn)題，受這種思想的啟發(fā)，本文將用禁忌搜索算法和隨機(jī)模擬技術(shù)相結(jié)合的混合智能算法來(lái)求解前面所建立的模型。

3.1隨機(jī)模擬

3.2禁忌搜索算法

3.2.1解的表示形式

3.2.3特赦規(guī)則

本文的特赦規(guī)則為：設(shè)x'為當(dāng)前最優(yōu)解，x為候選集合中的最優(yōu)解，如果x的變化被禁且滿足x所對(duì)應(yīng)的目標(biāo)值優(yōu)于x'對(duì)應(yīng)的目標(biāo)值，則將對(duì)應(yīng)x的禁忌變化解禁。

3.2.4算法步驟

Step1：生成一個(gè)可行解x，設(shè)當(dāng)前的迭代步數(shù)presentiter=0，當(dāng)前最優(yōu)解所在的迭代步數(shù)bestiter=0，當(dāng)前解presentsol=x，當(dāng)前最優(yōu)解bestsol=x，初始化禁忌表；

Step2：由presentsol生成候選集合V，其中集合中的元素要求為非禁忌的或是特赦的，令presentiter=presentiter+1；

Step4：求出候選集合中解所對(duì)應(yīng)的目標(biāo)值；

Step5：在V中找出目標(biāo)值的最優(yōu)解x'；

Step6：若x'對(duì)應(yīng)的目標(biāo)值由于bsetsol對(duì)應(yīng)的目標(biāo)值，則bestsol=x'，presentsol=x'，bestiter=presentiter，否則，presentsol=x'；

Step7：更新禁忌表；

Step8：若presentiter

Step9：輸出最優(yōu)解，結(jié)束計(jì)算。

4算例分析

本文采用圖1所示的倉(cāng)庫(kù)結(jié)構(gòu)，此倉(cāng)庫(kù)中有38個(gè)存儲(chǔ)單元，假定倉(cāng)庫(kù)中每個(gè)存儲(chǔ)單元的面積為8×8m2，通道寬度為4m。

假定有20種型號(hào)（用1~20的數(shù)字分別編號(hào)）的貨物需要存放在此倉(cāng)庫(kù)中，貨物都是立方體形狀，各型號(hào)貨物的邊長(zhǎng)分別為：1.00， 1.00， 1.10， 1.15， 1.20， 1.20， 1.30， 1.40， 1.45， 1.45， 1.50， 1.60， 1.60， 1.65， 1.65， 1.70， 1.90， 1.90， 1.95， 2.00。根據(jù)邊長(zhǎng)把這些貨物分為三類(lèi)，[1.00，1.30]為第一類(lèi)，包括前七種型號(hào)的貨物；第二類(lèi)的邊長(zhǎng)范圍為(1.30，1.60），包含第八種到第十三種型號(hào)的貨物； (1.60，2.00）為第三類(lèi)，包含后七種型號(hào)的貨物。對(duì)于每類(lèi)貨物，搬運(yùn)單位該類(lèi)貨物行走單位距離所需的費(fèi)用分別為0.05，0.06，0.08。各型號(hào)貨物相應(yīng)的存儲(chǔ)需求分別為36， 36， 36， 30， 36， 11， 25， 25， 25， 9， 16， 25， 19， 16， 14， 16， 16， 10， 9， 7。

本算例把叉車(chē)搬運(yùn)貨物的行走距離和貨物的月需求量都視為三角隨機(jī)數(shù)。首先測(cè)定存儲(chǔ)單元中心到進(jìn)出口的最短直線距離為x，則其隨機(jī)距離可視為T(mén)x，x+4，x+2。各型號(hào)貨物的月需求量如表1：

利用隨機(jī)模擬來(lái)求解模型的目標(biāo)函數(shù)值，其中的β取值為0.95（決策者可以根據(jù)需要調(diào)節(jié)β值），模擬樣本數(shù)的抽取由決策者選擇。在處理器為賽揚(yáng)2.4，內(nèi)存256MB的計(jì)算機(jī)上運(yùn)算可得算例的結(jié)果如表2。

經(jīng)過(guò)4 000次模擬，131次迭代后，本例得到近似最優(yōu)解2 889.85，最大誤差不超過(guò)0.07%，目標(biāo)值和誤差的平均值分別是2 889.34和0.019%。相應(yīng)的貨物的布局形式如圖2。

5總結(jié)

本文探討了隨機(jī)條件下的倉(cāng)庫(kù)布局問(wèn)題，在對(duì)介紹倉(cāng)庫(kù)布局相關(guān)問(wèn)題后，建立的隨機(jī)倉(cāng)庫(kù)布局問(wèn)題的機(jī)會(huì)約束規(guī)劃模型，分析了該模型的數(shù)學(xué)性質(zhì)，并設(shè)計(jì)了基于隨機(jī)模擬的禁忌搜索算法來(lái)求解模型，最后通過(guò)算例驗(yàn)證所設(shè)計(jì)算法的有效性。計(jì)算結(jié)果表明，本文提出的模型與算法是有效的。

參考文獻(xiàn)：

[1]J.A. Tompkins， J. A. White， Y. A. Bozer， E. H. Frazelle， J. M. A. Tanchoco， J. Trvino， Facilities Planning[M]. New York: Wiley， 1996.

[2]R. L. Francis， L. F. McGinnis Jr.， J. A. While， Facility Layout and Location: An Analytical Approach[M]. Prentice-Hall， Englewood Cliffs， NJ， 1992.

[3]Lai K. K.， Xue J. and Zhang G.Q.. Layout design for a paper reel warehouse: A two-stage heuristic approach[J]. International Journal of Production Economics， 2002，75:231-243.

[4]Zhang G. Q.， Xue J.， Lai K. K.. A genetic algorithm based heuristic for adjacent paper-reel layout problem[J]. International Journal of Production Research， 2000，20:3343-3356.

[5]T. N. Larson， H.March， A.Kusiak， A heuristic approach to warehouse layout with class-based storage[J]. IIE Transactions， 1997(29):337-348.

[6]Van Oudheusdeh， D. L.， Sharma， D.， and Tzen， Y. J.， An evaluation of storage policies for the assignment of facilities to location[J]. International Journal of Production Economics， 1968，16:150-173.

[7]S. H. Chang， P. J. Egbelu， Relative pre-positioning of storage/Retrieval machines in automated storage/retrieval systems to minimize maximum system response time[J]. IIE Transactions， 1997(29):303-312.

[8]Zhang G. Q.， Lai K. K. and Lixing Yang. A fuzzy multiple-level warehouse layout problem[C] // Proceedings of the 9th Bellman Continuum International Workshop on Uncertain Systems and Soft Computing， 2002:236-239.

[9]Yang. L. X.， Sun. Y. B. Expected Value Model for A Fuzzy Random Warehouse Layout Problem[J]. IEEE International Conference on Fuzzy Systems， 2004，25(29):751-756.

[10]Liu B. Theory and Practice of Uncertain Programming[M]. Physica-Verlay: Heidelberg， 2002.