王盛明，盧秉亮

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

1 引言

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

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

2.1 求重心的方法

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

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

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

Xc、Yc——整體貨架的重心坐標(biāo)

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

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

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

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

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

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

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

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

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

Pareto 最優(yōu)解的概念廣泛應(yīng)用于多目標(biāo)優(yōu)化問題。對min f(X)=［f1(X)，...，fn(X)］，設(shè)其定義域為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 組合多目標(biāo)優(yōu)化實例

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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

［6］柳賽男，柯映林，李江雄，等.基于調(diào)度策略的自動化倉庫系統(tǒng)優(yōu)化問題研究［J］.計算機(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)鍵路徑知識的任務(wù)調(diào)度遺傳算法［J］.計算機(jī)應(yīng)用，2008(2):272－274.