自動化存取系統下的貨位動態分配數學模型構建

成均孝

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

0 引言

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

1 貨物的出入庫作業

1.1 貨架的系統結構

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

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

圖1 自動化存取系統貨架機構和設備

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

1.2 出入庫作業

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

2 數學模型的創建

2.1 基本的假設

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

2.2 符號的定義

為了方便系統模型的創建，就要對模型中使用的符號進行定義：入庫指令集合表示為Cs，入庫指令索引表示為i，出庫指令集合表示為Cr，出庫指令索引表示為k。空貨位集合表示為Le，空貨位索引表示為k。貨位列表示為W，貨位層表示為H，貨架寬度表示P，貨架高度表示為Q。決策變量表示為Xik={0,1}。

2.3 數學模型的創建

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

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

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

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

自動化存活系統貨位動態分配的數學優化模型為式(1)～式(4)。

(1)

(2)

(3)

(4)

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

3 算法的求解

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

3.1 染色體編碼

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

圖2 染色體編碼的設計

3.2 生成初始種群

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

3.3 種群及適應度函數

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

3.4 變異算子及交叉算子

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

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

4 算法使用

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

表1 實驗數據

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

表2 貨架1-10的分配優化結果

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

5 總結

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