隋 振, 吳 濤, 唐志國, 張?zhí)煨? 陳華銳

(吉林大學(xué) 通信工程學(xué)院, 長春 130012)

四向穿梭車倉儲系統(tǒng)(four-way shuttle storage system)是在穿梭車倉儲系統(tǒng)(shuttle storage system)的基礎(chǔ)上發(fā)展而來的一種新型自動化立體倉庫, 其主要由四向穿梭車、 導(dǎo)軌、 貨物提升機和貨架等構(gòu)成. 四向穿梭車可以在自動化立體倉儲巷道之間的導(dǎo)軌上向前、 后、 左、 右4個方向運動, 同時也可以利用倉庫貨架之間的貨物提升機實現(xiàn)上下兩個方向的垂直運動, 克服了穿梭車倉儲系統(tǒng)中穿梭車只能在一個巷道中運動及穿梭車出現(xiàn)故障后該巷道的出入庫作業(yè)無法正常進行的缺點, 提高了倉儲的作業(yè)效率.

目前, 自動化立體倉儲系統(tǒng)中相關(guān)的作業(yè)任務(wù)調(diào)度研究主要集中在堆垛機式立體倉庫及自動導(dǎo)引車(AGV)系統(tǒng), 已取得了許多研究成果. 余娜娜等[1]對自動化分揀倉庫的AGV調(diào)度問題進行分析, 將完成作業(yè)任務(wù)的最短工作時間作為目標(biāo)函數(shù), 使AGV調(diào)度和路徑規(guī)劃綜合在一起, 實現(xiàn)了自動引導(dǎo)小車的路徑規(guī)劃； 張丹露等[2]在A*算法的基礎(chǔ)上, 提出了一種交通規(guī)則和預(yù)約表下的動態(tài)加權(quán)地圖的改進算法, 解決了智能倉庫多AGV協(xié)同調(diào)度問題； Fukunari[3]通過分析RGVs(rail-guided vehiclessy stem)系統(tǒng)的存取特點, 在交叉存取的基礎(chǔ)上, 建立了RGV系統(tǒng)循環(huán)交叉存取時間模型, 使用排隊論方法對該模型進行求解研究； 方彥軍等[4]提出了一種改進的人工狼群算法, 有效解決了AGV系統(tǒng)復(fù)合作業(yè)三維空間的調(diào)度問題； Fanjul-Peyro等[5]為解決多AGV調(diào)度問題, 將其等價為無關(guān)并行機調(diào)度問題, 用精確算法對大規(guī)模問題求解； Malopolski[6]在擁有方形拓撲結(jié)構(gòu)的多AGV運輸系統(tǒng)中提出了一種防止沖突和死鎖的方法； 劉二輝等[7]針對傳統(tǒng)變異算子缺少啟發(fā)式規(guī)則導(dǎo)致變異產(chǎn)生優(yōu)質(zhì)解概率較低的缺陷, 提出了一種改進遺傳算法的AGV動態(tài)路徑規(guī)劃算法, 為增加改進遺傳算法的局部尋優(yōu)能力, 對每代的最優(yōu)解都進行了模擬退火操作； Mousavi等[8]假設(shè)AGV在執(zhí)行任務(wù)過程中不發(fā)生沖突, 提出了基于遺傳算法和粒子群優(yōu)化算法的混合算法解決調(diào)度問題. 目前的研究主要用粒子群優(yōu)化算法[9]、 遺傳算法[10-11]及多種群遺傳算法[12-13]等解決AGV系統(tǒng)及堆垛機式立體庫系統(tǒng)中單訂單任務(wù)的調(diào)度問題, 對于倉儲系統(tǒng)中同時對多個訂單任務(wù)的調(diào)度研究文獻報道較少.

基于此, 本文對四向穿梭車系統(tǒng)同時處理多個訂單的作業(yè)任務(wù)進行研究, 建立系統(tǒng)的作業(yè)時間模型, 利用改進的遺傳算法對模型求解. 首先, 針對模型特點設(shè)計一種包含多訂單作業(yè)任務(wù)的作業(yè)順序及貨物提升機選擇信息的染色體; 其次, 為解決遺傳算法易陷入局部最優(yōu)的問題, 對遺傳算法的交叉概率和變異概率進行自適應(yīng)設(shè)計, 并與模擬退火算法相融合組成自適應(yīng)遺傳退火算法; 最后, 利用實例驗證自適應(yīng)遺傳退火算法求解的有效性, 并通過解碼得到多個訂單任務(wù)的作業(yè)順序及貨物提升機的選擇信息.

1 問題描述及假設(shè)

1.1 問題描述

與傳統(tǒng)的穿梭車倉儲系統(tǒng)不同, 四向穿梭車倉儲系統(tǒng)中的四向穿梭車可以前后左右運動, 四向穿梭車在執(zhí)行跨層作業(yè)任務(wù)時需要規(guī)劃水平運動和垂直運動, 其中水平運動可由四向穿梭車自己完成, 垂直運動需要四向穿梭車與貨物提升機相互配合完成. 四向穿梭車系統(tǒng)布局如圖1所示.

圖1 四向穿梭車系統(tǒng)布局Fig.1 Four-way shuttle system layout

穿梭車倉儲系統(tǒng)的作業(yè)任務(wù)包含出庫作業(yè)、 入庫作業(yè)和復(fù)合作業(yè)3種類型. 由于系統(tǒng)的3種作業(yè)類型原理基本相同, 因此本文主要研究四向穿梭車系統(tǒng)的出庫作業(yè)任務(wù). 對于跨層任務(wù)系統(tǒng)的出庫作業(yè)任務(wù)主要分為兩個環(huán)節(jié)： 1) 貨物提升機運載四向穿梭車將其運送到出庫貨物所在層, 然后四向穿梭車運行到出庫貨物所在位置的軌道將貨物取出； 2) 四向穿梭車將需要出庫的貨物運送到貨物提升機緩存區(qū), 然后貨物提升機將運送貨物的四向穿梭車運載到貨架底層并釋放提升機. 對于底層的出庫任務(wù)則不需要貨物提升機配合四向穿梭車進行作業(yè).

因此, 該系統(tǒng)中四向穿梭車和貨物提升機的匹配問題是決定出庫作業(yè)任務(wù)效率的關(guān)鍵. 目前, 多數(shù)研究只針對單訂單的任務(wù)調(diào)度情況, 而未考慮雙訂單同時到達時的任務(wù)調(diào)度情況. 在處理四向穿梭車系統(tǒng)運行中遇到雙訂單任務(wù)到達的情況時, 通常按照訂單任務(wù)優(yōu)先級優(yōu)先處理一個訂單任務(wù). 所以, 研究四向穿梭車系統(tǒng)雙訂單作業(yè)任務(wù)的調(diào)度方案具有重要意義.

1.2 相關(guān)運行規(guī)則及假設(shè)

假設(shè)四向穿梭車系統(tǒng)中沒有沖突、 阻塞發(fā)生, 為便于研究提出以下運行規(guī)則[4]：

1) 四向穿梭車每次只能運送一個貨位的貨物；

2) 每個貨物提升機只能運載一個四向穿梭車；

3) 每兩個相鄰路徑節(jié)點之間的導(dǎo)軌只能被一個四向穿梭車占用；

4) 每個四向穿梭車取完貨物后, 在貨物提升機緩存區(qū)等待貨物提升機將其運送至底層；

5) 四向穿梭車和貨物提升機在空載狀態(tài)和滿載狀態(tài)下的運行速度及加速度相同；

6) 四向穿梭車之間沒有沖突；

7) 忽略出庫貨物與空閑四向穿梭車在提升機貨物緩存區(qū)的對接時間.

采用A*算法離線狀態(tài)下計算出在每層貨架中以貨物提升機所在位置節(jié)點為起始點到出庫貨物所在貨位節(jié)點為目標(biāo)點的最短路徑.

2 出庫時間模型

本文采用G=(L,N,M)表示倉庫中貨物所在位置, 其中G為系統(tǒng)中貨物所在貨架的位置,L為貨物所在的行數(shù),N為貨物所在的列數(shù),M為貨物所在層數(shù).用

O≥F

(1)

表示系統(tǒng)中四向穿梭車的數(shù)量大于等于貨物提升機的數(shù)量, 其中O為系統(tǒng)中的四向穿梭車數(shù)量,F為貨物提升機數(shù)量.

設(shè)出庫貨物的坐標(biāo)為(Lq,Nq,Mq), 對應(yīng)的四向穿梭車在巷道中取貨物時的坐標(biāo)為(Lq,Nn,Mq), 貨物提升機的坐標(biāo)為(Lf,Nf,Mf), 則貨物坐標(biāo)中Nq與相鄰巷道坐標(biāo)中Nn之間的關(guān)系為

(2)

圖2 出庫作業(yè)任務(wù)時間段Fig.2 Outbound task time period

每臺貨物提升機的調(diào)用之間相互獨立, 當(dāng)一臺貨物提升機工作時不影響其他貨物提升機的工作, 所有貨物出庫都需經(jīng)過提升機與穿梭車配合實現(xiàn), 且一臺貨物提升機服務(wù)多個巷道.因此, 以貨物提升機為核心建立系統(tǒng)的工作時間模型.本文以貨物提升機作業(yè)時間為中心建立系統(tǒng)作業(yè)任務(wù)的出庫時間模型, 對出庫作業(yè)任務(wù)所需時間進行研究.系統(tǒng)中出庫作業(yè)任務(wù)可分為A,B,C三個時間階段, 其簡略流程如圖2所示.

圖3 穿梭車作業(yè)時序Fig.3 Shuttle operation sequence

A階段： 如果出庫任務(wù)在最底層則不需要提升機運載空閑穿梭車； 如果出庫任務(wù)在其他層則需要提升機從當(dāng)前所在層運行到第一層, 取空閑穿梭車將其運送到任務(wù)作業(yè)層, 然后穿梭車開始在作業(yè)任務(wù)層取貨, 提升機等待或執(zhí)行其他命令. B階段： 穿梭車被提升機釋放后沿貨架之間的導(dǎo)軌開始運行到出庫貨位前取貨, 取貨完成后運送貨物到提升機緩存區(qū), 向提升機發(fā)出調(diào)用指令, 此時若提升機閑置則提升機響應(yīng)該指令, 否則等待提升機響應(yīng). C階段： 提升機響應(yīng)穿梭車的調(diào)用申請, 從當(dāng)前所在層運行至發(fā)送調(diào)用申請的載貨穿梭車所在層, 將其運載至貨架的最底層并將其卸載.

假設(shè)一個任務(wù)訂單下達時, 系統(tǒng)隨機分配3個任務(wù)給一臺提升機執(zhí)行, 分別由1,2,3號穿梭車運送, 穿梭車作業(yè)時序簡圖如圖3所示. 由圖3可見, 當(dāng)系統(tǒng)給穿梭車發(fā)出指令時, 穿梭車開始申請調(diào)用提升機, 同時提升機在T0時刻開始按順序運送空閑穿梭車到出庫任務(wù)所在層, 在T1時刻提升機運送1號穿梭車到達出庫作業(yè)任務(wù)所在層, 穿梭車開始取貨, 提升機執(zhí)行其他任務(wù).在T1～T9時刻提升機按系統(tǒng)指令繼續(xù)執(zhí)行任務(wù), 在T2時刻運送2號穿梭車到對應(yīng)的出庫任務(wù)層； 在T3時刻提升機運送3號穿梭車到任務(wù)層, 此時3號穿梭車開始取貨, 提升機等待； 在T4時刻1號穿梭車運載出庫貨物請求調(diào)用提升機, 提升機響應(yīng)調(diào)用請求, 開始從當(dāng)前所在層運行至1號穿梭車所在層； 在T5時刻運送1號穿梭車至第一層并卸載穿梭車, 同時1號穿梭車對應(yīng)的出庫任務(wù)完成； 在T6時刻2號穿梭車運載出庫貨物請求調(diào)用提升機, 提升機響應(yīng)并在T7時刻將其運送至第一層并卸載; 在T8時刻3號穿梭車完成取貨任務(wù)運行到貨物提升機緩存區(qū)請求調(diào)用提升機, 提升機響應(yīng)3號穿梭車的請求; 在T9時刻將3號穿梭車運送至底層并釋放完成出庫任務(wù).因此, 完成訂單任務(wù)時提升機的工作時間為

(3)

物理學(xué)中物體直線行駛的加速度與速度關(guān)系如圖4所示, 其中vmax為物體行駛的最大速度,a為行物體行駛的加速度,t為物體行駛的時間.

圖4 物體直線行駛時行駛速度與加速度的關(guān)系Fig.4 Relationship between speed and acceleration when object travels in straight line

在四向穿梭車系統(tǒng)中,vmax為提升機和穿梭車的最大運行速度,a為系統(tǒng)中提升機和穿梭車的加速度.從而可得系統(tǒng)中穿梭車和提升機的運行時間t與加速度a、 最大速度vmax及運行距離S的關(guān)系表達式為

(4)

由圖3可知, 當(dāng)進行第q個出庫任務(wù)時, 該任務(wù)在A階段所用的時間為

(5)

當(dāng)yqi=1時, 表明第q個出庫任務(wù)是提升機從第一層到第i層運送空閑穿梭車然后將其卸載.在該過程中, 提升機的工作時間由提升機的運行時間ti和卸載空閑穿梭車時間tL組成, 其中tL為固定時間.由式(5)可知,

(6)

其中Si為提升機從第一層到第i層運送空閑穿梭車行駛的距離,

Si=(i-1)h.

(7)

將式(7)代入式(6), 可得

(8)

當(dāng)yqij=1時, 表明第q個出庫任務(wù)是提升機從當(dāng)前所在第i層向下運行至第一層取空閑穿梭車, 然后向上運行至第j層并卸載空閑穿梭車.在該過程中, 提升機的工作時間由提升機的向下運行時間ti、 向上運行時間tj和取空閑穿梭車及卸載空閑穿梭車時間2tL組成.同理可得：

(9)

由圖3可知, 當(dāng)進行第q個出庫任務(wù)時, 該任務(wù)在C階段所用的時間為

(10)

(11)

其中Sij為提升機從當(dāng)前所在第i層運行到第j層行駛的距離,

Sij=|i-j|h.

(12)

將式(12)代入式(11), 可得

(13)

(14)

(15)

(16)

Bq=2×(tql+tqn)+tS,

(17)

式中Bq為四向穿梭車被貨物提升機釋放后運行到出庫貨物位置取貨到運載貨物到貨物緩存區(qū)的時間,tql為四向穿梭車縱向運行時間,tqn為四向穿梭車橫向運行時間,

(18)

Sq=|Lq-Lf|·l,

(19)

(20)

Sn=|Nn-Nf|·b,

(21)

l為貨位的長度,b為貨位的寬度.由式(3),(14),(15)可得出執(zhí)行系統(tǒng)任務(wù)時一臺提升機有Fq個出庫任務(wù)時的工作時間為

(22)

綜上可知, 當(dāng)系統(tǒng)中有f臺提升機時, 完成出庫任務(wù)訂單所需時間為

(23)

3 基于改進遺傳算法的調(diào)度優(yōu)化

3.1 遺傳算法

當(dāng)四向穿梭車系統(tǒng)進行出庫作業(yè)時, 提升機和穿梭車的相互匹配問題實際上是尋找一個最佳的出庫順序并選擇合適的提升機, 使完成出庫作業(yè)任務(wù)的時間最短.遺傳算法(GA)是根據(jù)自然界生物遺傳規(guī)律提出的一種進化算法, 該算法在每次迭代中先選擇群體中適應(yīng)度較高的個體, 再通過交叉、 變異等進行反復(fù)迭代, 最后收斂到適應(yīng)度最高的個體, 即可得到問題的最優(yōu)解. 遺傳算法具有良好的全局搜索能力, 能快速找到近似最優(yōu)解.

3.1.1 編碼與解碼

在遺傳算法中每個染色體都是所求問題的解, 因此染色體的編碼對求解問題的最優(yōu)解至關(guān)重要. 常見的染色體編碼[14]主要有二進制編碼、 實數(shù)編碼等. 本文采用整數(shù)編碼對任務(wù)序列及出庫所對應(yīng)的提升機序號進行求解, 設(shè)染色體個體表達方式為X=(x1,l1,x2,l2,…,xi,li), 其中xi為出庫訂單中的任務(wù)序列,li為執(zhí)行任務(wù)時運載出庫貨物的提升機編號, 如X=(1,1,3,2,4,2,2,1,5,2,7,2,9,1,8,1,6,1,10,2), 奇數(shù)位的數(shù)字為一個出庫訂單中的出庫任務(wù)號, 偶數(shù)位的數(shù)字為執(zhí)行出庫任務(wù)時對應(yīng)的提升機編號, 系統(tǒng)按照(1,3,4,2,5,7,9,8,6,10)的任務(wù)序號執(zhí)行出庫任務(wù), 出庫貨物分別由第1,2,2,1,2,2,1,1,1,2號提升機緩存區(qū)出庫, 其中1號提升機按1,2,9,8,6的任務(wù)序列執(zhí)行任務(wù), 2號提升機按3,4,5,7,10的任務(wù)序列執(zhí)行任務(wù).

3.1.2 初始種群

圖5 染色體重組示意圖Fig.5 Schematic diagram of chromosome recombination

根據(jù)染色體編碼方式生成兩個包含出庫任務(wù)序列與貨物提升機選擇信息的染色體個體.將兩個包含出庫任務(wù)序列與貨物提升機選擇信息的染色體基因?qū)ο嗷ュe位連接重組, 構(gòu)成一個新染色體個體, 如圖5所示.由圖5可見, 染色體1包含3個出庫任務(wù), 執(zhí)行順序為2,1,3, 分別選擇第1,2,2號貨物提升機執(zhí)行任務(wù).染色體2包含3個出庫任務(wù), 執(zhí)行順序為4,6,5, 分別選擇第1,1,2號貨物提升機執(zhí)行任務(wù).新染色體個體包含2個出庫任務(wù)序列的出庫順序及貨物提升機的選擇信息, 包含6個出庫任務(wù), 執(zhí)行順序分別為2,4,1,6,3,5, 分別選擇第1,1,2,1,2,2號貨物提升機執(zhí)行任務(wù).根據(jù)新的染色體個體構(gòu)成規(guī)則, 隨機生成NP個新染色體, 即為一個初始種群.

3.1.3 適應(yīng)度函數(shù)

本文針對系統(tǒng)出庫任務(wù)需要的時間建模, 研究系統(tǒng)完成一個出庫訂單任務(wù)所需的作業(yè)時間, 因此執(zhí)行出庫任務(wù)所用最短時間適合做適應(yīng)度函數(shù).

fitness=min{T}.

(24)

3.1.4 選擇

在遺傳算法中染色體根據(jù)個體的適應(yīng)度遺傳給子代, 染色體個體適應(yīng)度越高遺傳給子代的概率越大.本文采用輪盤賭的方式選擇適應(yīng)度高的染色體個體作為父代遺傳給子代, 從而使子代繼承父代的優(yōu)秀基因, 通過不斷選擇得到最高適應(yīng)度的染色體個體.

3.1.5 交叉

交叉是指兩個染色體通過交換部分基因片段重組為新染色體的過程.由于創(chuàng)建的染色體中部分片段含有出庫順序的基因和提升機選擇信息, 因此本文采用隨機調(diào)換基因組的方式對初始種群中的染色體進行重組, 構(gòu)成一個新的染色體個體, 如圖6所示.將包含兩個訂單的出庫任務(wù)序列與貨物提升機選擇信息的基因片段作為一個基因組, 隨機選取兩個基因組互換位置.

3.1.6 變異

變異是指染色體個體的某個基因或部分基因發(fā)生突變, 變成新染色體的過程.本文將包含訂單任務(wù)序列和貨物提升機選擇信息的基因片段作為一個基因?qū)? 隨機選取兩個基因?qū)Σ捎秒S機調(diào)換位置的方式使這兩個基因?qū)φ{(diào)換位置, 對染色體上的基因進行變異, 如圖7所示.

圖6 染色體交叉示意圖Fig.6 Schematic diagram of chromosome crossing

圖7 染色體變異示意圖Fig.7 Schematic diagram of chromosome variation

3.1.7 終止

本文通過設(shè)置最大迭代次數(shù)終止遺傳算法的搜索, 當(dāng)?shù)螖?shù)達到設(shè)定值時, 輸出最大適應(yīng)度的染色體個體視為最優(yōu)解.

3.2 自適應(yīng)遺傳退火算法

雖然遺傳算法的全局搜索能力較強, 能在解空間中快速搜索出全體解, 但其局部搜索能力較差, 易產(chǎn)生早熟收斂的現(xiàn)象.模擬退火算法(SA)[15-16]是根據(jù)固體退火原理模擬組合優(yōu)化問題, 采用隨機搜索的方法從概率的角度上找出目標(biāo)函數(shù)的最優(yōu)解, 可在某種程度上避免搜索結(jié)果陷入局部最優(yōu)值. 在遺傳算法中交叉概率越大, 群體中新個體產(chǎn)生的速度越快, 算法的搜索能力越強, 當(dāng)達到某種程度后種群中適應(yīng)度較高的個體結(jié)構(gòu)會遭到破壞, 種群中最優(yōu)個體不會被保留； 變異概率達到某種程度后, 算法即變成了隨機搜索算法[17]. 在標(biāo)準遺傳算法中交叉概率和變異概率都是固定值, 不會隨種群中個體適應(yīng)度的大小發(fā)生變化, 限制了算法的搜索能力. 本文對遺傳算法中的交叉概率Pc和變異概率Pm進行自適應(yīng)度調(diào)整設(shè)計, 并與模擬退火算法相結(jié)合, 提出一種自適應(yīng)遺傳退火算法(adaptive genetic simulated annealing algorithm, AGSAA), 以確保該算法擁有較強的搜索能力, 有效解決遺傳算法局部搜索能力不足及產(chǎn)生早熟現(xiàn)象的問題, 提高算法的收斂性能. 其自適應(yīng)度設(shè)計結(jié)果可表示為

(25)

其中:fmax為當(dāng)前種群中目標(biāo)函數(shù)的最大適應(yīng)度值；favg為當(dāng)前種群適應(yīng)度值的平均值；f′為選中的交叉?zhèn)€體中的較大適應(yīng)度值；f為變異個體的適應(yīng)度值； 固定參數(shù)取值為c1=c2=0.9,m1=m2=0.5.其算法流程如圖8所示, 算法步驟如下：

1) 初始化種群數(shù)量、 迭代次數(shù)、 溫度及退溫系數(shù)等；

2) 根據(jù)設(shè)置的編碼方式生成初始種群；

3) 計算染色體個體的適應(yīng)度, 選擇染色體個體對其進行交叉與變異操作；

4) 判斷是否迭代到設(shè)置的最大次數(shù), 如果是則程序結(jié)束, 退出程序; 否則, 對染色體進行降溫處理,T′=aT, 其中a為降溫系數(shù), 降溫處理后返回步驟3)；

5) 輸出所求的最優(yōu)解, 結(jié)束程序.

圖8 自適應(yīng)遺傳退火算法流程Fig.8 Flow chart of adaptive genetic annealing algorithm

4 仿真實驗與結(jié)果分析

4.1 初始化

以某灌裝公司開發(fā)的四向穿梭車倉儲系統(tǒng)為例, 該系統(tǒng)的參數(shù)列于表1.系統(tǒng)隨機產(chǎn)生兩個出庫任務(wù)數(shù)量為10的訂單任務(wù)列表, 如表2和表3所示.

表1 系統(tǒng)參數(shù)

表2 訂單1出庫作業(yè)任務(wù)

表3 訂單2出庫作業(yè)任務(wù)

4.2 算例分析

圖9 出庫時間最優(yōu)值迭代曲線Fig.9 Iterative curves of optimal values of outbound time

為驗證自適應(yīng)遺傳退火算法求解模型最優(yōu)值的有效性, 對出庫作業(yè)任務(wù)的時間進行求解驗證. 遺傳算法參數(shù)設(shè)置如下： 種群規(guī)模NP=40, 最大迭代次數(shù)maxgen=500, 交叉概率Pc=0.8, 變異概率Pm=0.2, 精英保留概率PGap=0.1. 自適應(yīng)遺傳退火算法的參數(shù)如下： 初始溫度D0=1 000 ℃, 結(jié)束溫度Df=900 ℃, 溫度下降比例a=0.99, 種群規(guī)模NP=40, 最大迭代次數(shù)maxgen=500, 精英保留概率PGap=0.1. 兩種算法運行的出庫時間最優(yōu)值迭代過程如圖9所示, 對應(yīng)的1號貨物提升機出庫時間迭代過程如圖10所示, 對應(yīng)的2號貨物提升機出庫時間迭代過程如圖11所示.

圖10 1號提升機作業(yè)時間迭代曲線Fig.10 Iterative curves of operation time of number one elevator

圖11 2號提升機作業(yè)時間迭代曲線Fig.11 Iterative curves of operation time of number two elevator

由圖9～圖11可見, 圖9中的系統(tǒng)出庫時間為1號提升機和2號提升機工作時間中的最大值, 隨著迭代次數(shù)的增加, 1號提升機和2號提升機的工作時間趨于穩(wěn)定, 同時系統(tǒng)的作業(yè)時間也趨于穩(wěn)定. 由圖9可見: GA算法在尋找最優(yōu)解的過程中易陷入局部最優(yōu)解, 不易從局部最優(yōu)解中跳出, 且后期收斂過程緩慢； AGSAA算法能從局部最優(yōu)解中跳出, 比GA算法的求解結(jié)果更好. 表4為兩種算法分別運行10次最優(yōu)值的結(jié)果.

表4 兩種算法運行結(jié)果

圖12 四向穿梭車執(zhí)行出庫作業(yè)任務(wù)時的出庫路徑Fig.12 Outbound path of four-way shuttle when performing outbound tasks

由表4可見, GA的最優(yōu)解為244.333 3 s, AGSAA的最優(yōu)解為231.333 3 s； GA解的平均值為244.773 3 s, GA解的標(biāo)準偏差為0.440 2%； AGSAA解的平均值為231.666 7 s, AGSAA解的標(biāo)準偏差為0.415 7%. 因此, AGSAA的求解結(jié)果比GA的求解結(jié)果優(yōu)化了4.533 4 s, 且AGSAA最優(yōu)解的標(biāo)準偏差比GA的小, 證明了AGSAA求解最優(yōu)值的有效性, 比GA求解的結(jié)果更穩(wěn)定. 經(jīng)過AGSAA運算可以得到一條最優(yōu)解的染色體X=(2,1,11,1,5,1,13,2,8,1,17,1,6,2,12,1,9,2,20,2,7,2,18,2,10,2,16,2,1,1,19,1,3,2,14,1,4,2,15,1).對該染色體進行解碼, 可知系統(tǒng)按2,11,5,13,8,17,6,12,9,1,20,7,18,10,16,1,19,3,14,4,15的任務(wù)序列執(zhí)行訂單1與訂單2的出庫作業(yè)任務(wù), 訂單1的出庫任務(wù)按2,5,8,6,9,7,10,1,3,4的出庫順序執(zhí)行, 分別使用第1,1,1,2,2,2,2,1,2,2號貨物提升機執(zhí)行出庫任務(wù)； 訂單2的出庫任務(wù)按11,13,17,12,20,18,16,19,14,15的出庫順序執(zhí)行, 分別使用第1,2,1,1,2,2,2,1,1,1號貨物提升機執(zhí)行出庫任務(wù), 完成出庫任務(wù)所需時間為231.333 3 s. 自適應(yīng)遺傳退火算法求解的最優(yōu)解可在三維坐標(biāo)系中表示, 將穿梭車視為一個質(zhì)點, 如圖12所示, 其中藍色軌跡為四向穿梭車通過1號貨物提升機調(diào)度執(zhí)行出庫作業(yè)任務(wù)時的路徑, 紅色軌跡為四向穿梭車通過2號貨物提升機調(diào)度執(zhí)行出庫作業(yè)任務(wù)時的路徑. 四向穿梭車執(zhí)行出庫作業(yè)任務(wù)時的路徑如下：

F1(0.5,4.5,0),(0.5,4.5,4),(0.5,9.5,4)； (0.5,4.5,0),(0.5,4.5,4),(0.5,10.5,4),(12.5,10.5,4)； (0.5,4.5,0),(0.5,4.5,7),(0.5,1.5,7),(5.5,1.5,7)； (0.5,4.5,0),(0.5,4.5,7),(16.5,1.5,7)； (0.5,4.5,0),(0.5,4.5,7),(0.5,10.5,7),(5.5,10.5,7)； (0.5,4.5,0),(0.5,4.5,9),(0.5,1.5,9),(2.5,4.5,9)； (0.5,4.5,0),(0.5,4.5,9),(0.5,7.5,9),(10.5,7.5,9)； (0.5,4.5,0),(0.5,4.5,14), (0.5,1.5,14),(7.5,1.5,14)； (0.5,4.5,14),(0.5,4.5,14),(12.5,4.5,14)； (0.5,4.5,14),(0.5,4.5,14),(0.5,10.5,14),(14.5,10.5,14)；

F2(0.5,13.5,0),(0.5,13.5,4),(0.5,7.5,4),(3.5,7.5,4)； (0.5,13.5,0),(0.5,13.5,4),(7.5,13.5,4)； (0.5,13.5,0),(0.5,13.5,7),(0.5,7.5,7),(18.5,7.5,7)； (0.5,13.5,0),(0.5,13.5,7),(0.5,16.5,7),(8.5,16.5,7)； (0.5,13.5,0),(0.5,13.5,9),(0.5,4.5,9),(8.5,4.5,9)； (0.5,13.5,0),(0.5,13.5,9),(0.5,10.5,9),(1.5,10.5,9)； (0.5,13.5,0),(0.5,13.5,9),(15.5,13.5,9)； (0.5,13.5,0),(0.5,13.5,9),(0.5,16.5,9),(17.5,16.5,9)； (0.5,13.5,0),(0.5,13.5,14),(0.5,7.5,14),(19.5,10.5,14)； (0.5,13.5,0),(0.5,13.5,14),(19.5,13.5,14).

綜上所述, 本文針對四向穿梭車倉儲系統(tǒng)無法同時處理多訂單作業(yè)任務(wù)的問題, 以貨物提升機為時間軸建立了系統(tǒng)出庫作業(yè)任務(wù)的時間模型, 并設(shè)計了一種包含多個訂單作業(yè)任務(wù)順序和貨物提升機選擇信息的染色體, 采用遺傳算法對模型求解. 為解決遺傳算法易陷入局部最優(yōu)解的問題, 提出了一種自適應(yīng)遺傳退火算法, 對遺傳退火算法中的變異概率和交叉概率進行自適應(yīng)調(diào)整, 同時融合模擬退火算法增加算法的搜索范圍. 通過實驗證明了自適應(yīng)遺傳退火算法與遺傳算法相比搜索能力更強； 通過運用自適應(yīng)遺傳退火算法得到一個最優(yōu)的染色體并對其解碼, 得到多個訂單任務(wù)的出庫順序及選擇的貨物提升機信息, 實現(xiàn)了對出庫貨物的最優(yōu)路徑規(guī)劃.