成均孝

(陜西國防工業(yè)職業(yè)技術學院 基礎課部， 西安 710300)

0 引言

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

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

1.1 貨架的系統(tǒng)結構

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

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

圖1 自動化存取系統(tǒng)貨架機構和設備

在自動化存取系統(tǒng)中，每個存儲巷道都是貨道，其中包括多貨位。基于密集存儲條件中，為了使物資出入庫的效率得到進一步的提高，就要降低倒庫作業(yè)的機率，每條貨道中只允許同類托盤物資的存儲。為了能夠避免多臺穿梭板在同時運行過程中出現(xiàn)路徑死鎖的情況，實現(xiàn)貨道穿梭板容量的設置，為1。

1.2 出入庫作業(yè)

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

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

2.1 基本的假設

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

2.2 符號的定義

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

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

因為堆垛機不僅有水平方向的運動，還具有垂直方向的運動，取垂直及水平的最大完成時間為運行之間，那么入庫指令i存貨時間就是：

堆垛機因為存貨和取貨的位置中間時間為：

堆垛機取貨的時間表示為：

其中指令序列完工的時間為：

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

(1)

(2)

(3)

(4)

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

3 算法的求解

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

3.1 染色體編碼

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

圖2 染色體編碼的設計

3.2 生成初始種群

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

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

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

3.4 變異算子及交叉算子

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

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

4 算法使用

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

表1 實驗數(shù)據(jù)

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

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

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

5 總結

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