成均孝

(陜西國(guó)防工業(yè)職業(yè)技術(shù)學(xué)院 基礎(chǔ)課部， 西安 710300)

0 引言

自動(dòng)化存取系統(tǒng)是基于普通貨架系統(tǒng)基礎(chǔ)實(shí)現(xiàn)多載具貨物存取裝置創(chuàng)建的全新自動(dòng)化存儲(chǔ)系統(tǒng)，其具備多個(gè)載具，在一次行程中能夠存放或者取出多個(gè)貨物單元。其具有較高的靈活性、較大的存儲(chǔ)量及較高的空間使用率，能夠有效滿足未來(lái)制造配送環(huán)境中高柔性、多貨種、高密度動(dòng)態(tài)貨物存取的需求。貨物動(dòng)態(tài)分配的分配數(shù)學(xué)模型創(chuàng)建是解決自動(dòng)化存取系統(tǒng)的高效運(yùn)行基礎(chǔ)問(wèn)題，自動(dòng)化存貨系統(tǒng)和傳統(tǒng)貨物分配模型創(chuàng)建的目標(biāo)相同，都是實(shí)現(xiàn)貨物出入庫(kù)移動(dòng)時(shí)間距離的最小化，使存取貨物效率得到有效的提高。本文對(duì)存貨貨位分配及取貨貨位選擇兩方面進(jìn)行了全面的優(yōu)化，將存取或時(shí)間距離最小化作為目標(biāo)，創(chuàng)建組合優(yōu)化模型，使用啟發(fā)式算法的結(jié)合實(shí)現(xiàn)算法的求解，利用數(shù)值實(shí)驗(yàn)對(duì)算法有效性進(jìn)行了全面的驗(yàn)證。

1 貨物的出入庫(kù)作業(yè)

1.1 貨架的系統(tǒng)結(jié)構(gòu)

自動(dòng)化存取系統(tǒng)主要包括穿梭板、貨架及垂直提升機(jī)構(gòu)成，如圖1所示。

系統(tǒng)貨架包括多層，各層之間的存儲(chǔ)巷道相互平行及密集排列，利用主軌道實(shí)現(xiàn)連接。主軌道相互連接成為主軌道網(wǎng)，垂直提升機(jī)和各個(gè)貨架層主軌道網(wǎng)相互連接成為貨架系統(tǒng)主干交通網(wǎng)，存儲(chǔ)巷道軌道利用主軌道與貨架主干交通網(wǎng)相互連接。在自動(dòng)化存取系統(tǒng)中，為了能夠有效避免多個(gè)穿梭板相互運(yùn)行出現(xiàn)路徑?jīng)_突的情況，利用主軌道只允許穿梭板單向運(yùn)行的設(shè)置實(shí)現(xiàn)。

圖1 自動(dòng)化存取系統(tǒng)貨架機(jī)構(gòu)和設(shè)備

在自動(dòng)化存取系統(tǒng)中，每個(gè)存儲(chǔ)巷道都是貨道，其中包括多貨位?；诿芗鎯?chǔ)條件中，為了使物資出入庫(kù)的效率得到進(jìn)一步的提高，就要降低倒庫(kù)作業(yè)的機(jī)率，每條貨道中只允許同類(lèi)托盤(pán)物資的存儲(chǔ)。為了能夠避免多臺(tái)穿梭板在同時(shí)運(yùn)行過(guò)程中出現(xiàn)路徑死鎖的情況，實(shí)現(xiàn)貨道穿梭板容量的設(shè)置，為1。

1.2 出入庫(kù)作業(yè)

自動(dòng)化存取系統(tǒng)的主要功能就是實(shí)現(xiàn)物資的出入庫(kù)作業(yè)，其作業(yè)流程通過(guò)管理系統(tǒng)實(shí)現(xiàn)統(tǒng)一調(diào)度及監(jiān)控。在物資入庫(kù)上架作業(yè)過(guò)程中，托盤(pán)物資就從貨架的端口進(jìn)入到貨架中，管理系統(tǒng)能夠?qū)崿F(xiàn)穿梭板的調(diào)度，使其到貨架端口托盤(pán)物資，將物資運(yùn)輸?shù)焦芾硐到y(tǒng)制定貨位中。在物資下架出庫(kù)的過(guò)程中，穿梭板就會(huì)通過(guò)管理系統(tǒng)的制定貨位將貨物裝盤(pán)，實(shí)現(xiàn)下架出庫(kù)。所以，托盤(pán)物資入庫(kù)上架及下架出庫(kù)簡(jiǎn)單來(lái)說(shuō)就是系統(tǒng)對(duì)貨架端口和存儲(chǔ)貨位的往返控制，在每次入庫(kù)上架作業(yè)過(guò)程中，將貨架端口作為起點(diǎn)，將存儲(chǔ)貨位作為重點(diǎn)。在每次下架過(guò)程中，出庫(kù)貨位屬于起點(diǎn)，貨架端口屬于終點(diǎn)。如果托盤(pán)物資存儲(chǔ)貨位為貨架的一層，那么穿梭板就能夠自動(dòng)實(shí)現(xiàn)托盤(pán)物資轉(zhuǎn)載運(yùn)輸。如果托盤(pán)物資存儲(chǔ)貨位不處于貨架一層，那么穿梭板在運(yùn)行過(guò)程中需要根據(jù)垂直提升機(jī)實(shí)現(xiàn)換層[1]。

2 數(shù)學(xué)模型的創(chuàng)建

2.1 基本的假設(shè)

航空貨站的散貨區(qū)自動(dòng)化存取系統(tǒng)都是同端出入式結(jié)構(gòu)，其存取單元為網(wǎng)箱，網(wǎng)箱利用貨架坐下端出入口進(jìn)入并且離開(kāi)自動(dòng)存取系統(tǒng)。貨架中的每個(gè)貨位尺寸相同，每個(gè)網(wǎng)箱能夠存儲(chǔ)所有貨位，每個(gè)貨位只能夠存儲(chǔ)同個(gè)網(wǎng)箱。巷道中具有一臺(tái)堆垛機(jī)，堆垛機(jī)能夠在垂直及水平的運(yùn)動(dòng)。假如堆垛機(jī)在水平及垂直兩個(gè)方向進(jìn)行勻速運(yùn)動(dòng)，并且負(fù)載空載速度相同。

2.2 符號(hào)的定義

為了方便系統(tǒng)模型的創(chuàng)建，就要對(duì)模型中使用的符號(hào)進(jìn)行定義：入庫(kù)指令集合表示為Cs，入庫(kù)指令索引表示為i，出庫(kù)指令集合表示為Cr，出庫(kù)指令索引表示為k?？肇浳患媳硎緸長(zhǎng)e，空貨位索引表示為k。貨位列表示為W，貨位層表示為H，貨架寬度表示P，貨架高度表示為Q。決策變量表示為Xik={0,1}。

2.3 數(shù)學(xué)模型的創(chuàng)建

因?yàn)槎讯鈾C(jī)不僅有水平方向的運(yùn)動(dòng)，還具有垂直方向的運(yùn)動(dòng)，取垂直及水平的最大完成時(shí)間為運(yùn)行之間，那么入庫(kù)指令i存貨時(shí)間就是：

堆垛機(jī)因?yàn)榇尕浐腿∝浀奈恢弥虚g時(shí)間為：

堆垛機(jī)取貨的時(shí)間表示為：

其中指令序列完工的時(shí)間為：

自動(dòng)化存活系統(tǒng)貨位動(dòng)態(tài)分配的數(shù)學(xué)優(yōu)化模型為式(1)～式(4)。

(1)

(2)

(3)

(4)

其中式(1)中屬于目標(biāo)函數(shù)，其能夠縮短堆垛機(jī)指令序列的完工時(shí)間，式(2)能夠保證每個(gè)入庫(kù)的指令指令實(shí)現(xiàn)空貨位，式(3)和式(4)能夠保證每隔入庫(kù)指令都實(shí)現(xiàn)一個(gè)空貨位的分配。以上模型能夠在指令序列規(guī)模及空貨位規(guī)模不斷增加的過(guò)程中，可行貨位分配方案也會(huì)增加，無(wú)法利用精確算法實(shí)現(xiàn)模型求解，本文使用單親遺傳算法實(shí)現(xiàn)問(wèn)題求解[2]。

3 算法的求解

遺傳算法是根據(jù)生物進(jìn)化規(guī)律實(shí)現(xiàn)的計(jì)算技術(shù)，能夠利用種群進(jìn)行自動(dòng)獲取及調(diào)整優(yōu)化搜索空間的操作，并且實(shí)現(xiàn)空間多解的搜索，并且以不同解之間性能的差別實(shí)現(xiàn)自適應(yīng)搜索方向的調(diào)整。對(duì)自動(dòng)化存貨系統(tǒng)大規(guī)模貨位分配的問(wèn)題，要全面考慮問(wèn)題特殊性及遺傳算法隨機(jī)性，假如繼續(xù)使用基本的遺傳算法，就會(huì)使迭代次數(shù)及不可行解可能性得到增加，以此就不能夠產(chǎn)生滿意解。那么針對(duì)此問(wèn)題，本文就基于多種方式實(shí)現(xiàn)模型解。

3.1 染色體編碼

染色體編碼屬于遺傳算法編碼空間中的模型解空間映射，其屬于遺傳算法最基本的工作，編碼能夠?qū)徊?、選擇及變異的過(guò)程造成影響。本文所研究的染色體使用備選貨位集合耦合映射二進(jìn)制編碼的方式，使編碼能夠分割成為多個(gè)片段，使用空貨位和取貨貨位相互結(jié)合的順序進(jìn)行排列，編碼主要通過(guò)兩層構(gòu)成。上層屬于備選貨位集合編碼，下層屬于是否選擇相應(yīng)貨位碼值。編碼長(zhǎng)度指的是指令周期中空貨位數(shù)量與需要取貨物的占有數(shù)量集合。需要存取的貨物數(shù)量及載具數(shù)與貨位數(shù)量具有密切的聯(lián)系。圖2為染色體編碼的設(shè)計(jì)，其中A、B、C指的是需要取的貨物，為了能夠有效滿足貨物存取的約束，就要保證空貨位中能夠具有三個(gè)空貨位，在貨物中選擇貨位，實(shí)現(xiàn)貨物的取出[3]。

圖2 染色體編碼的設(shè)計(jì)

3.2 生成初始種群

因?yàn)橐陨纤枋龅木幋a結(jié)構(gòu)和值具有特殊的約束，所以初始種群無(wú)法按使用隨機(jī)方式生成，要不然會(huì)產(chǎn)生不可行的解，無(wú)法繼續(xù)實(shí)現(xiàn)算法。所以針對(duì)自動(dòng)化存取系統(tǒng)中的貨位分配，可以使用基于分片段貨位數(shù)量限制隨機(jī)的方法實(shí)現(xiàn)初始種群的生成。在選擇種群規(guī)模中，一般表示越多越好，但是要全面考慮計(jì)算代價(jià)及后續(xù)選擇交配操作便捷性，可以選擇編碼程度2或者4等一系列的偶數(shù)倍作為種群規(guī)模[4]。

3.3 種群及適應(yīng)度函數(shù)

遺傳算法通過(guò)對(duì)生物遺傳進(jìn)化過(guò)程中的優(yōu)勝劣汰模擬實(shí)現(xiàn)問(wèn)題求解，其中的適應(yīng)度函數(shù)屬于對(duì)個(gè)體優(yōu)劣進(jìn)行衡量的指標(biāo)。本文所使用的使用度函數(shù)指的是使用原本模型中改進(jìn)策略實(shí)現(xiàn)目標(biāo)函數(shù)的生成，并且以經(jīng)典輪盤(pán)賭的方式選擇種群個(gè)體，根據(jù)相應(yīng)的概率分布到下一代實(shí)現(xiàn)染色體的遺傳。為了能夠促進(jìn)算法收斂，使用精英保存策略，是每代數(shù)量最有個(gè)體到下一代遺傳，從而提高父體選擇壓力，使選擇最優(yōu)個(gè)體概率得到進(jìn)一步的提高。

3.4 變異算子及交叉算子

自然界中的生物交配之后后代屬于種群進(jìn)化核心步驟，遺傳算法利用交叉算法相互配對(duì)的方式實(shí)現(xiàn)其中基因片段的交換，從而形成全新個(gè)體。交叉算子能夠?qū)z傳算法的全局搜索能力決定，一般常見(jiàn)的交叉規(guī)則包括單親遺傳、雙親雙子及多位交配。為了能夠避免出現(xiàn)不可行解的情況，本文就使用基于固定交配位雙親雙子方式實(shí)現(xiàn)交叉，交叉操作，如圖3所示。

為了能夠避免出現(xiàn)早熟情況，遺傳算法就利用變異算法使個(gè)體染色體中的某個(gè)位置基因使用其他等位基因進(jìn)行替換，以此形成全新的個(gè)體，提高遍歷性。本文使用倒位變異方式，隨機(jī)選擇1-t之間的某基因片段，之后將相應(yīng)片段中的基因值實(shí)現(xiàn)逆序倒位排列，不僅能夠保證個(gè)體可行，還能夠進(jìn)行變異操作。

4 算法使用

將所收集的數(shù)據(jù)以以上所描述，使用Matlb軟件，實(shí)現(xiàn)貨位分配數(shù)學(xué)模型的求解。現(xiàn)在需要對(duì)一批貨物進(jìn)行入庫(kù)作業(yè)，在實(shí)現(xiàn)貨物ABC分類(lèi)之后得到各種貨物在貨架中需要的入庫(kù)數(shù)量，并且利用基礎(chǔ)專(zhuān)家知識(shí)庫(kù)數(shù)據(jù)的調(diào)用，能夠有效得到各種貨物出入庫(kù)頻率，實(shí)驗(yàn)數(shù)據(jù)，如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)

在迭代次數(shù)不斷增加的過(guò)程中，時(shí)間函數(shù)及適應(yīng)度值在不斷的降低，在迭代為150的時(shí)候，適應(yīng)度的值不變，時(shí)間函數(shù)值從原本7 500降低為4 300。在迭代為200次的時(shí)候，雖然適應(yīng)度值不發(fā)生變化，時(shí)間函數(shù)也會(huì)不斷降低成為4 100,而且不發(fā)生變化，在滿足收斂條件的過(guò)程中，就結(jié)束迭代。因?yàn)樨浳环峙鋽?shù)學(xué)模型中已經(jīng)實(shí)現(xiàn)了均衡作業(yè)，也就是每個(gè)巷道需要作業(yè)的次數(shù)相同，選擇其中的一排貨架貨位分配優(yōu)化如表2所示。

表2 貨架1-10的分配優(yōu)化結(jié)果

通過(guò)優(yōu)化結(jié)果表示，貨物1在貨架1-4行中，其屬于A類(lèi)貨物，利用貨物編碼創(chuàng)建基礎(chǔ)專(zhuān)家知識(shí)庫(kù)用戶(hù)界面，能夠搜索知識(shí)庫(kù)數(shù)據(jù)，查詢(xún)待入庫(kù)類(lèi)別及存儲(chǔ)區(qū)域，通過(guò)以上結(jié)果表式，自學(xué)習(xí)粒子群算法得到的貨物分類(lèi)及貨位分區(qū)結(jié)果和基礎(chǔ)專(zhuān)家知識(shí)庫(kù)相同，表示本文所設(shè)計(jì)的算法求解結(jié)果可行[5]。

5 總結(jié)

本文對(duì)貨位分配進(jìn)行了分析，根據(jù)貨位分配的原則，將企業(yè)年數(shù)據(jù)作為根據(jù)創(chuàng)建了自動(dòng)化存取系統(tǒng)中貨位動(dòng)態(tài)分配的數(shù)學(xué)模型。通過(guò)某煙草配送中心為例，實(shí)現(xiàn)貨物動(dòng)態(tài)分類(lèi)及分區(qū)。全面考慮均衡作業(yè)約束條件，實(shí)現(xiàn)貨位動(dòng)態(tài)分配。通過(guò)模型求解結(jié)果表示，本文所設(shè)計(jì)的數(shù)學(xué)模型能夠有效解決庫(kù)容量較大的時(shí)候自動(dòng)化立體倉(cāng)庫(kù)系統(tǒng)能力問(wèn)題，滿足實(shí)際需求。