王盛明，盧秉亮

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

1 引言

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

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

2.1 求重心的方法

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

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

Gij——任意一個(gè)貨位上貨物重量;

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

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

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

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

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

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

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

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

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

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

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

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

3 組合多目標(biāo)優(yōu)化實(shí)例

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

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

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

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

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

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

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

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

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

由上面兩個(gè)目標(biāo)函數(shù)的各自最優(yōu)解得出結(jié)論，當(dāng)貨物的縱坐標(biāo)重心最小，橫坐標(biāo)重心接近中間時(shí)，貨架最穩(wěn)定。但此時(shí)存放貨物的方式就不能以COI值小的貨物靠近出入庫(kù)口的方式存放(第二個(gè)目標(biāo)函數(shù)的最優(yōu)結(jié)果)。所以Pareto 多目標(biāo)優(yōu)化問題只能得出最優(yōu)解的集合，難以得出一個(gè)滿足所有目標(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)化后，在降低貨架重心的同時(shí)，總體出入庫(kù)時(shí)間有較大幅度的減少，顯著提高了貨架的穩(wěn)定性，并且提高了貨物的存取效率。

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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