自動化立體倉庫貨位分配優(yōu)化研究

王盛明，盧秉亮

(1.沈陽航空職業(yè)技術(shù)學院，沈陽 110034;2.沈陽航空航天大學計算機學院，沈陽 110136)

1 引言

對自動化立體倉庫進行貨位優(yōu)化的意義在于［8］:根據(jù)貨物大小來確定貨物的存取位置，能夠減少當貨架出現(xiàn)空貨位進行補貨時所需的勞動;將出入庫頻率大的貨物平均分配在不同的存儲區(qū)域，能夠避免在某一存儲區(qū)域出現(xiàn)任務阻塞，進而提高效率，縮短對一批任務總的執(zhí)行時間;當出入庫貨物中有易損壞的貨物時，應該將易損壞的貨物放在運行方向的后面，將不易損壞的貨物放在運行方向的前面;相似的貨物應該分開存放，避免出現(xiàn)揀選錯誤。

2 貨位分配優(yōu)化模型

2.1 求重心的方法

設某排貨架共有p 列q 層，將距離巷道口最近的列，記為第1 列，最底層記為第1 層，處于第i 列j層的貨位記為(i，j)(i=1……p)，(j=1……q)。根據(jù)物體的重心坐標公式求物體的重心可以將物體劃分為多個小個體來求出重心，而求自動化立體倉庫貨架的重心則可以采用此種求重心的方法［1］:

Gmax——貨架上每個貨位所能承受最大重量;

Gij——任意一個貨位上貨物重量;

Xc、Yc——整體貨架的重心坐標

為滿足貨架穩(wěn)定性的需要，目標函數(shù)是使貨架的Y 軸坐標重心最小，X 軸坐標位于貨架的中心位置。

2.2 組合多目標優(yōu)化

為了提高自動化立體倉庫的出入庫效率，通常將經(jīng)常使用的出入庫頻率高的貨物擺放至靠近起始點位置。設某貨位區(qū)編號為R(R=1、2……q)，共有p種貨品，其中一種貨品的COI 值為Ii，COI為立方體索引號，Heskett 給出的COI 計算公式為:Ii=Ci/fi，其中Ci為某種貨品的存儲總量所需的庫存容量;fi為某種貨品的出庫頻率［6］。貨品的存儲總量所需的庫存容量越小，并且出入庫頻率越高，則COI值就越小。根據(jù)這個原則，將COI 值小的貨物存儲在離出入口近的貨架上，并得到下面目標條件:

為了減少貨物存取時間，根據(jù)貨物存放原則，對出入庫頻率較高的貨物，應該有更少的出入庫時間;對出入庫頻率相對較低的貨物，則可以有相對長的出入庫時間。這樣，能保證整個出入庫作業(yè)的總時間最短。因此，目標函數(shù)是對存取效率的要求，頻繁存取的物品應放在能快速取到的貨位上，建立公式(4)。

式中:tij——將第i 列j 層貨位上的物品搬運到巷道口所用的時間;

Vx、Vy——分別為堆垛機的水平、垂直運行速度(m/s);

l、h——貨位的長度、高度(m);

由于上述兩個目標條件都是以提高貨物的存取效率，減少貨物的存取時間為目的，所以可以合并為一個目標函數(shù):

可見，貨位的分配需要同時考慮貨架穩(wěn)定性和存取效率，這是一個組合多目標優(yōu)化問題。對于多目標優(yōu)化問題，許多情況下各目標是相互沖突的，一般不存在唯一的全局最優(yōu)解，而是存在一個最優(yōu)解集合，最優(yōu)解集中的元素就所有目標而言是不可比較的。使某一目標達到最優(yōu)性能的解很可能意味著其他目標的性能很差，單純追求其中某一個目標最優(yōu)化并沒有太大的實際意義，尋求使各維目標函數(shù)均較好的滿意解(這個解可能對某一目標來說并不是最優(yōu)的)具有重要的實際意義。通過比較各種算法后，選擇Pareto 算法進行求解多目標優(yōu)化問題。

Pareto 最優(yōu)解的概念廣泛應用于多目標優(yōu)化問題。對min f(X)=［f1(X)，...，fn(X)］，設其定義域為a，X*∈a，若不存在X∈a，使得fi(X)≤fi(X*)(i=1，...，n)，則稱X*是該問題的Pareto 最優(yōu)解(有效解或非劣最優(yōu)解)。

Pareto 最優(yōu)解不是“最優(yōu)的”，但可以說是“不壞的”，Pareto 最優(yōu)解一般不是一個，而是一個集合。

3 組合多目標優(yōu)化實例

由于Pareto 多目標優(yōu)化問題不具有唯一解。而是具有一組解的集合，在盡可能滿足各種約束條件的同時，得到的多個最優(yōu)解。實例的自動化立體倉庫與［3］完全相同。

矩陣(6)為平面貨架存儲貨物矩陣，矩陣中每一個元素代表每個貨位存儲貨物的重量。

初始擺放貨物重心為:Xc=3.06，Yc=2.85

通過Pareto 算法進行重心優(yōu)化后的重心為:Xc=3.01，Yc=2.00，得到矩陣(7)。

矩陣(8)表示初始的每一個貨位上貨物的出入庫頻率。

假設每個貨位所裝載的貨物種類各不相同，則貨物的COI 值為矩陣(9)所示。

通過Pareto 算法根據(jù)COI 值進行貨位優(yōu)化的最優(yōu)結(jié)果見矩陣(10)。

假設單位貨位貨架的長、寬各為1m，且不計堆垛機啟動后的加速運動和停止前的減速運動，堆垛機的水平勻速速度和垂直速度各為1m/s。起始點和終點在右下角。矩陣(11)為堆垛機到達各貨位所用的時間，單位是秒。

由于第二個目標函數(shù)的最優(yōu)解為貨物的COI值和貨物出入庫時間的乘積，所以根據(jù)上面解，可以得出第二個目標函數(shù)的最優(yōu)結(jié)果，用矩陣(12)表示。

由上面兩個目標函數(shù)的各自最優(yōu)解得出結(jié)論，當貨物的縱坐標重心最小，橫坐標重心接近中間時，貨架最穩(wěn)定。但此時存放貨物的方式就不能以COI值小的貨物靠近出入庫口的方式存放(第二個目標函數(shù)的最優(yōu)結(jié)果)。所以Pareto 多目標優(yōu)化問題只能得出最優(yōu)解的集合，難以得出一個滿足所有目標函數(shù)的最優(yōu)解。

如果采用傳統(tǒng)順序存放的方式［3］，則S=3210kg，T=621s;優(yōu)化后，S=3013kg，T=505s。從優(yōu)化結(jié)果進行分析，貨位優(yōu)化后，在降低貨架重心的同時，總體出入庫時間有較大幅度的減少，顯著提高了貨架的穩(wěn)定性，并且提高了貨物的存取效率。

4 結(jié)束語

對貨位可移動式自動化立體倉庫貨位優(yōu)化方法進行了研究。貨位優(yōu)化問題是自動化立體倉庫運行的關(guān)鍵問題，對提高倉庫工作效率起著舉足輕重的作用。依據(jù)倉庫工作情況，建立了優(yōu)化問題的數(shù)學模型，通過Pareto 算法對貨位優(yōu)化問題進行了研究，方便了用戶對倉庫的管理，并提高了倉庫系統(tǒng)的出入庫效率和貨架系統(tǒng)的運行穩(wěn)定性。

［1］商允偉，裘聿皇，劉長有.自動化倉庫貨位分配優(yōu)化問題研究［J］.計算機工程與應用，2004(26)，16－17，23.

［2］鄒暉華，胡吉全，楊艷芳.自動化立體倉庫貨位分配策略優(yōu)化研究［J］.湖北工業(yè)大學學報，2008，23(3):43－45.

［3］吳鐘鳴，盧軍鋒，智淑亞.自動化立體倉庫貨位優(yōu)化研究［J］.裝備制造技術(shù)，2011(12):23－25，28.

［4］朱耀明.自動化立體倉庫優(yōu)化調(diào)度研究［D］.濟南:山東大學，2006.

［5］程二九，方慶琯.非等概率條件下自動化立體倉庫出入庫周期計算［J］.起重運輸，2008(7):19－21.

［6］柳賽男，柯映林，李江雄，等.基于調(diào)度策略的自動化倉庫系統(tǒng)優(yōu)化問題研究［J］.計算機集成與制造技術(shù)，2006(9):1438－1443.

［7］Leandro N de Castro，Jon Timmis.Artificial Immune Systems:A Novel Computational Intelligence ［J］.Approach.Springer－Verlag，2002，5(5):25－34

［8］CaronF，Marchet G，Perego.A Layout design in manual picking system:a simulation approach［J］.Integrated Manufacturing System 2000，11(2):55－59

［9］蘭舟，孫世新.基于關(guān)鍵路徑知識的任務調(diào)度遺傳算法［J］.計算機應用，2008(2):272－274.