耿 賽，王 雷，李東東

（安徽工程大學(xué)機(jī)械工程學(xué)院，蕪湖 241000）

自動化倉儲系統(tǒng)（Automated storage and re?trieval system，AS/RS）是一種新型的倉儲技術(shù)，作為現(xiàn)代物流系統(tǒng)的核心部分，正越來越多地應(yīng)用于各個行業(yè)［1?3］。倉庫的出入庫效率直接影響到整個物流系統(tǒng)的效率，因此出入庫路徑的優(yōu)化就成為提高整個物流系統(tǒng)效率的關(guān)鍵。堆垛機(jī)是AS/RS中運(yùn)輸和存取貨物的主要設(shè)備，其中堆垛機(jī)揀選出入庫貨物的時間占其整個作業(yè)周期的50%左右，因此解決堆垛機(jī)行駛路徑優(yōu)化問題是提高自動化倉庫效率的有效手段［4］。

國內(nèi)外學(xué)者對立體化倉庫出入庫堆垛機(jī)路徑優(yōu)化問題做了大量的研究。Liu 等［5］、李媛媛等［6］、楊姣等［7］主要針對I/O 設(shè)在貨架同一側(cè)的情況，對堆垛機(jī)的不同工作模式建立了相關(guān)的數(shù)學(xué)模型，并分別結(jié)合遺傳禁忌搜索算法、近似動態(tài)規(guī)劃算法和遺傳模擬退火算法對模型進(jìn)行優(yōu)化求解，提高了最優(yōu)解的收斂速度。Emanuele 等［8］以倉庫設(shè)計、存儲策略和耗能作為重點(diǎn)對堆垛機(jī)進(jìn)行路徑優(yōu)化。Bortolini 等［9］建立了分析模型來評估堆垛機(jī)在單一作業(yè)和復(fù)合作業(yè)中的預(yù)期時間。韓東亞等［10］以堆垛機(jī)出入庫的復(fù)合作業(yè)和任務(wù)順序為研究方向，根據(jù)問題的特點(diǎn)設(shè)計了兩階段啟發(fā)式算法求解此問題，有效地提高了倉庫揀選效率和堆垛機(jī)的作業(yè)方式。Lerher［11］對跨巷道堆垛機(jī)倉儲系統(tǒng)進(jìn)行研究，建立單、雙指令情況下堆垛機(jī)的行程時間模型，并對時間模型進(jìn)行性能分析。Torabizadeh 等［12］和Hao 等［13］建立新型的模型來研究倉儲系統(tǒng)的可持續(xù)性可以通過存儲策略、堆垛機(jī)停頓點(diǎn)策略和出入庫調(diào)度策略等來有效地提高自動化立體倉庫的效率。卞和營等［14］提出將I/O 分別設(shè)在貨架兩側(cè)，并建立堆垛機(jī)的單一、復(fù)合作業(yè)模型，結(jié)合一種改進(jìn)的遺傳算法對模型進(jìn)行優(yōu)化求解。上述研究雖然最終取得了不錯的貨物出入庫優(yōu)化結(jié)果，但僅僅局限于算法上的優(yōu)化，并沒有對傳統(tǒng)立體化倉庫I/O臺以及堆垛機(jī)的數(shù)量和位置布局上提出改良。蔡安江等［15?16］在碼頭雙堆碼起重機(jī)調(diào)度的構(gòu)思下，提出兩端式I/O 同軌雙車模式的雙堆垛機(jī)調(diào)度模型，并結(jié)合防碰撞原則，用改進(jìn)的化學(xué)反應(yīng)優(yōu)化算法進(jìn)行求解，有效地提高了立體倉庫貨物出入庫的調(diào)度效率。雖然該方法避免了兩堆垛機(jī)在工作時發(fā)生碰撞，但防碰撞原則實現(xiàn)方法較繁瑣且最終的任務(wù)分配也非最優(yōu)，優(yōu)化效果仍存在較大改進(jìn)空間?；诖?，本文以兩端式雙堆垛機(jī)模式下的立體倉庫為基礎(chǔ)，提出改進(jìn)的防碰撞原則和最優(yōu)防碰撞邊界檢驗機(jī)制，并運(yùn)用新型改進(jìn)遺傳算法（New improved genetic algorithm，NIGA）進(jìn)行優(yōu)化求解，最大限度提高大型立體倉庫的出入庫調(diào)度效率。

1 問題描述

1.1 兩端式雙堆垛機(jī)問題描述

在一般倉庫的運(yùn)輸調(diào)度中，一般采取單端I/O、單堆垛機(jī)的調(diào)度模型，通過對單一作業(yè)、復(fù)合作業(yè)出入庫任務(wù)的優(yōu)化，來提高調(diào)度效率。但隨著科學(xué)技術(shù)的發(fā)展，現(xiàn)代企業(yè)倉庫規(guī)模不斷擴(kuò)大，這種傳統(tǒng)模式下，倉庫的優(yōu)化效果往往不盡如人意。為了縮短堆垛機(jī)的最大工作行程、提高存取貨物效率，蔡安江等［15］提出兩端式雙堆垛機(jī)模型。圖1 為兩端式雙堆垛機(jī)立體倉庫模型的結(jié)構(gòu)圖，在貨架兩端都設(shè)立相同規(guī)格的I/O 位置，貨架之間的巷道上放置了兩臺規(guī)格相同的堆垛機(jī)。將堆垛機(jī)的最大行駛距離“一分為二”，左右兩堆垛機(jī)分別負(fù)責(zé)自己的“工作區(qū)域”，極大地縮短了堆垛機(jī)的行駛路程，提高了大型倉庫的出入庫調(diào)度效率。

圖1 中的堆垛機(jī)選用單立柱堆垛機(jī)，兩堆垛機(jī)貨叉相向，貨叉可以左右伸縮，以便向兩側(cè)的貨架存取貨物。當(dāng)兩堆垛機(jī)同時工作時，要保證兩堆垛機(jī)始終不會發(fā)生碰撞。即左端堆垛機(jī)處于貨架第I列，右端堆垛機(jī)處于貨架第I+1 列存取貨物時，此時兩堆垛機(jī)處于臨界安全距離，仍可正常工作不會發(fā)生碰撞。

圖1 兩端式雙堆垛機(jī)立體倉庫模型結(jié)構(gòu)圖Fig.1 Structure diagram of the warehouse model with two?end double stacker

立體倉庫兩端式雙堆垛機(jī)的調(diào)度模型下，兩堆垛機(jī)分別從對應(yīng)的I/O 臺完成出入庫任務(wù)的存取，工作時互不干預(yù)，僅負(fù)責(zé)自己工作區(qū)的任務(wù)。所以完成一批貨物存取所需的時間取決于兩臺堆垛機(jī)中耗時更長的一方。

式中TL和TR分別為同一巷道左端堆垛機(jī)和右端堆垛機(jī)完成各自任務(wù)所花費(fèi)的時間。

堆垛機(jī)存取貨物的工作方式有兩種：（1）堆垛機(jī)每次從I/O 臺出發(fā)，僅執(zhí)行一個出庫任務(wù)指令或者入庫任務(wù)指令，稱為單一作業(yè)（Single operation cycle，SC）；（2）堆垛機(jī)從I/O 臺出發(fā)，先執(zhí)行一個入庫任務(wù)指令，然后緊接著馬上執(zhí)行出庫任務(wù)指令，稱為復(fù)合作業(yè)（Double operation cycle，DC）。因為復(fù)合作業(yè)能夠減少堆垛機(jī)往返I/O 臺的次數(shù)，提高堆垛機(jī)的運(yùn)行效率，因此優(yōu)先選用復(fù)合作業(yè)方式。

若立體倉庫為兩端式布局，同一巷道上有兩臺堆垛機(jī)負(fù)責(zé)貨物的出入庫調(diào)度。現(xiàn)僅分析左堆垛機(jī)完成所有的單一作業(yè)任務(wù)，復(fù)合作業(yè)任務(wù)所用的時間為

式中：TSCi為左端堆垛機(jī)完成第i個SC 作業(yè)時所運(yùn)行的時間，TDCj為左端堆垛機(jī)完成第j個DC 作業(yè)時運(yùn)行的時間。其中

式中：除TSCi和TDCj外，T表示堆垛機(jī)從一個貨位到另一個貨位所用時間；IOL為左側(cè)出/入庫臺；Xi為堆垛機(jī)執(zhí)行第i個單一任務(wù)時，出庫/入庫貨位的位置；Xj1、Xj2分別為堆垛機(jī)執(zhí)行第j個復(fù)合作業(yè)時，入庫貨位的位置和出庫貨位的位置。

式（2～6）僅分析了左端堆垛機(jī)存取貨物的工作模型，右端堆垛機(jī)同理。當(dāng)倉庫接收到一批出入庫混合任務(wù)指令時，需要兩堆垛機(jī)協(xié)同工作揀取完所有的貨物。因此要根據(jù)實際的工作情況，將一批出入庫貨物合理地分配給兩堆垛機(jī)，在保證兩堆垛機(jī)同時運(yùn)行無碰撞的前提下，取得最優(yōu)的調(diào)度效率。

因此，針對兩堆垛機(jī)運(yùn)行時無碰撞和任務(wù)分配最優(yōu)兩個關(guān)鍵問題，本文提出了改進(jìn)防碰撞原則以及最優(yōu)防碰撞邊界檢驗機(jī)制，并運(yùn)用NIGA 算法對包含SC、DC 兩種工作模式的立體倉庫雙堆垛機(jī)模型進(jìn)行出入庫調(diào)度優(yōu)化。

1.2 相關(guān)參數(shù)的基本假設(shè)

對于本文中的兩端式雙堆垛機(jī)立體倉庫模型布局，為了研究更具有普遍性以及實用價值，參考文獻(xiàn)［9］中的相關(guān)參數(shù)，現(xiàn)假設(shè)堆垛機(jī)作業(yè)時勻速運(yùn)行，加速和制動時間忽略不計，不考慮貨叉存取貨物時間，設(shè)貨位的長度和高度分別為l和h。根據(jù)上述假定參數(shù)可知，堆垛機(jī)從貨位（x1，y1）到貨位（x2，y2）的運(yùn)行時間為

2 出入庫調(diào)度模型

兩端式雙堆垛機(jī)出入庫調(diào)度模式下，首要問題就是避免兩堆垛機(jī)執(zhí)行任務(wù)時發(fā)生碰撞以及合理分配左、右兩堆垛機(jī)執(zhí)行任務(wù)。因此本節(jié)首先提出了改進(jìn)的防碰撞原則，并以此為約束條件，建立相關(guān)的雙堆垛機(jī)調(diào)度模型，最后嵌入最優(yōu)防碰撞邊界檢驗機(jī)制。

2.1 改進(jìn)的防碰撞原則

當(dāng)接收到一批出入庫貨物混合訂單時，把出庫貨物、入庫貨物對應(yīng)貨位的橫坐標(biāo)提取出來構(gòu)成集合U。為了防止兩端堆垛機(jī)在揀選、存放貨物時發(fā)生碰撞，將這批貨物分為兩組，各組任務(wù)對應(yīng)貨位的橫坐標(biāo)分別構(gòu)成集合L＝｛xi1，xi2，…，xil｝和R＝｛xj1，xj2，…，xjr｝，在保證集合L中各元素均小于集合R中各元素外，為了方便后續(xù)優(yōu)化算法的操作，將集合L和集合R中的貨物橫坐標(biāo)元素xi1，xi2，…，xil以及xj1，xj2，…，xjr按從小到大的順序依次排列。集合L中元素對應(yīng)的出/入庫任務(wù)交由左端堆垛機(jī)執(zhí)行，集合R中元素對應(yīng)的出/入庫任務(wù)交由右端堆垛機(jī)執(zhí)行。以此來劃分兩臺堆垛機(jī)的工作區(qū)域，使左端堆垛機(jī)執(zhí)行的出/入庫任務(wù)對應(yīng)貨位的橫坐標(biāo)均小于右端堆垛機(jī)執(zhí)行出/入庫任務(wù)對應(yīng)貨位的橫坐標(biāo)，從而實現(xiàn)左右堆垛機(jī)在相同巷道同時作業(yè)時不會發(fā)生碰撞干預(yù)現(xiàn)象。

改進(jìn)的防碰撞原則數(shù)學(xué)表達(dá)式為

采用式（8，9）表示的改進(jìn)的防碰撞原則，可將左、右兩堆垛機(jī)負(fù)責(zé)執(zhí)行的出/入庫貨物，根據(jù)其所處貨位的列坐標(biāo)從左往右按大小排列，劃分為沒有重疊部分的左、右兩工作區(qū)域。

2.2 雙堆垛機(jī)調(diào)度模型

雖然該調(diào)度模型下堆垛機(jī)型號完全一致，但是左、右堆垛機(jī)被分配的出庫任務(wù)、入庫任務(wù)的數(shù)目可能完全不同。假設(shè)左側(cè)堆垛機(jī)需要執(zhí)行n1個入庫任務(wù)，m1個出庫任務(wù)，右側(cè)堆垛機(jī)需要執(zhí)行n2個入庫任務(wù)，m2個出庫任務(wù)，取

由式（12）可知，兩端式雙堆垛機(jī)模式下，左側(cè)堆垛機(jī)要執(zhí)行Q1個DC 作業(yè)和Q2-Q1個SC 作業(yè)，右側(cè)堆垛機(jī)要執(zhí)行P1個DC 作業(yè)和P2-P1個SC 作業(yè)，結(jié)合式（2～6），參考文獻(xiàn)［10］的相關(guān)內(nèi)容，可得左、右兩側(cè)堆垛機(jī)完成各自任務(wù)所運(yùn)行的總時間為

式中：TL為左側(cè)堆垛機(jī)完成任務(wù)所用的時間；TR為右側(cè)堆垛機(jī)完成任務(wù)所用的時間；IOR為右端貨物出/入庫臺。

兩端式雙堆垛機(jī)模式下，堆垛機(jī)運(yùn)輸完一批出入庫任務(wù)的總時間應(yīng)該取決于兩堆垛機(jī)中耗時較長的一方，綜上所述，兩堆垛機(jī)完成一批出/入庫貨物訂單的總時間如式（1）所示。則兩端式雙堆垛機(jī)模式下完成這批出入庫作業(yè)，雙堆垛機(jī)的最優(yōu)路徑模型為

2.3 最優(yōu)防碰撞邊界檢驗機(jī)制

雖然上述改進(jìn)的防碰撞原則可以將貨架分為左、右工作區(qū)域，避免了兩堆垛機(jī)在執(zhí)行各自任務(wù)時發(fā)生碰撞。但如果左右區(qū)域劃分不當(dāng)，就會出現(xiàn)兩堆垛機(jī)工作量差異較大的狀況，導(dǎo)致任務(wù)量較少的堆垛機(jī)過早地完成任務(wù)，而任務(wù)量較大的堆垛機(jī)仍要“加班”工作的情況，極大降低了堆垛機(jī)的利用效率，與本文提出的雙堆垛機(jī)提高貨物出入庫效率的想法相悖。于是為了解決這個問題，在改進(jìn)的防碰撞原則的基礎(chǔ)上，提出最優(yōu)防碰撞邊界檢驗機(jī)制。

最優(yōu)防碰撞邊界檢驗機(jī)制判斷依據(jù)如下：根據(jù)改進(jìn)的防碰撞原則得到左、右工作區(qū)分界線e；左、右堆垛機(jī)執(zhí)行完各自分配任務(wù)所運(yùn)行的時間TL、TR。

（1）當(dāng)TL≥TR時，左、右工作區(qū)分界線左移取e左邊較小元素，enew=U（i-1），將［enew，e］區(qū)間內(nèi)橫坐標(biāo)對應(yīng)的任務(wù)從左堆垛機(jī)負(fù)責(zé)的任務(wù)集合L中刪去添加進(jìn)右端堆垛機(jī)負(fù)責(zé)的集合R中，重新計算任務(wù)更新后，左、右堆垛機(jī)執(zhí)行各自任務(wù)的運(yùn)行時間TLnew，TRnew。比較兩者大小：

①當(dāng)TLnew≤TRnew時，此時分界線enew必為最優(yōu)的防碰撞邊界線。因為工作總時間T=max（TL，TR），所以比較TL與TRnew大小，若TL≥TRnew則保留最新的出入庫任務(wù)分配結(jié)果，記錄最優(yōu)解Tbest=TRnew；反之保留原出入庫任務(wù)分配結(jié)果，記錄最優(yōu)解Tbest=TL。

②當(dāng)TLnew>TRnew時，令TL=TLnew，更新左、右堆垛機(jī)出入庫任務(wù)分配結(jié)果，邊界enew繼續(xù)左移取U中最近的較小元素……按上述規(guī)則繼續(xù)循環(huán)判斷，直 至TLnew≤TRnew時，比 較TL與TRnew大 小，若TL≥TRnew則保留最新的出入庫任務(wù)分配結(jié)果，記錄最優(yōu)解Tbest=TRnew；反之保留原出入庫任務(wù)分配結(jié)果，記錄最優(yōu)解Tbest=TL。

（2）當(dāng)TL

①當(dāng)TLnew≥TRnew時，此時分界線enew必為最優(yōu)的防碰撞邊界線。比較TL與TRnew大小，若TR≥TLnew則保留最新的出入庫任務(wù)分配結(jié)果，記錄最優(yōu)解Tbest=TLnew；反之保留原出入庫任務(wù)分配結(jié)果，記錄最優(yōu)解Tbest=TR。

②當(dāng)TLnew

針對自動化立體倉庫的兩端式雙堆垛機(jī)模式，在采用改進(jìn)防碰撞原則的基礎(chǔ)上，校驗通過防碰撞原則得到的左、右工作區(qū)的劃分界線e是否為最優(yōu)分界線，從而保證了兩堆垛機(jī)最優(yōu)的貨位分配，極大地縮短了堆垛機(jī)的最大行程，提高了出入庫作業(yè)的效率。將上述的最優(yōu)防碰撞邊界檢驗機(jī)制嵌入到算法后續(xù)優(yōu)化的每一次迭代中，根據(jù)TL、TR以及TLnew、TRnew的大小情況對左、右兩堆垛機(jī)任務(wù)的分配結(jié)果進(jìn)行自適應(yīng)地調(diào)整，最終得到最優(yōu)的任務(wù)分配方案（具體步驟見3.3 節(jié)）

3 出/入庫調(diào)度路徑的優(yōu)化

為了解決自動化立體倉庫出入庫調(diào)度優(yōu)化的多目標(biāo)、多約束性等問題，通常采用啟發(fā)式算法進(jìn)行求解，常用的就是遺傳算法。而在遺傳算法中，交叉操作和變異操作對遺傳算法的優(yōu)化結(jié)果和收斂速度影響頗深，傳統(tǒng)遺傳算法中先進(jìn)行交叉操作后進(jìn)行變異操作，若種群的適應(yīng)度值比較集中，交叉操作可能導(dǎo)致遺傳算法（Genetic algorithm，GA）過早收斂，即使再進(jìn)行變異操作，算法也很難跳出局部最優(yōu)，在解決實際問題中，往往很難取到最優(yōu)值［17?18］。針對傳統(tǒng)遺傳算法“爬山能力差”，跳出局部最優(yōu)能力弱的問題，本文提出了一種基于種群適應(yīng)度疏密程度的不同而自適應(yīng)調(diào)節(jié)進(jìn)化過程的新型改進(jìn)遺傳算法NIGA。

NIGA 算法在優(yōu)化過程中先求出種群個體適應(yīng)度的最小值fmin、最大值fmax和平均值favg，再判斷不等式“（fmax-favg）/（fmax-fmin）≥1/2”是否成立，若成立則說明當(dāng)前種群的最大適應(yīng)度值、平均適應(yīng)度值的差值與最大適應(yīng)度值、最小適應(yīng)度的差值比較接近，且比值比1/2 大得越多，則說明此時種群的適應(yīng)度值越密集，多樣性不強(qiáng)，個體之間交叉產(chǎn)生優(yōu)秀后代的幾率不大，且算法容易陷入局部最優(yōu)解，因此先執(zhí)行變異操作，能增加算法跳出局部最優(yōu)的能力，然后再執(zhí)行交叉操作；若不成立則表明當(dāng)前種群的最大適應(yīng)度值、平均適應(yīng)度值的差值與最大適應(yīng)度值、最小適應(yīng)度的差值存在偏差，且比值比1/2 小的越多，說明此時的種群的適應(yīng)度值分布比較分散，種群的基因多樣性豐富，個體之間交叉產(chǎn)生優(yōu)秀后代幾率較大，極大地提高了算法收斂效率，因此先執(zhí)行交叉操作，再執(zhí)行變異操作。

3.1 編碼設(shè)計

由于算法優(yōu)化的目的是找到雙堆垛機(jī)調(diào)度的最優(yōu)任務(wù)執(zhí)行順序，高效地安排貨物的出入庫。若NIGA 算法采用二進(jìn)制編碼，則不能直觀地描繪出堆垛機(jī)揀取貨物的路徑軌跡，反而會使編碼過程變得更加復(fù)雜。因此本文NIGA 算法采用實數(shù)編碼，每個實數(shù)代表待執(zhí)行任務(wù)的編號。

每臺堆垛機(jī)接收到的出入庫任務(wù)指令按照前后順序（左堆垛機(jī)Chrom1、右堆垛機(jī)Chrom2）分別編寫成兩段編碼，每段編碼中的實數(shù)代表著相應(yīng)任務(wù)的序號。第1 段編碼X=［x1，x2，…，xi，…，xm］表示堆垛機(jī)接收到的入庫指令順序，第2 段編碼Y=［y1，y2，…，yj，…，yN］表示堆垛機(jī)接收到的出庫指令順序，Chrom=X∪Y=［x1，x2，…，xi，…，xM，y1，y2，…，yj，…，yN］，其中M為入庫任務(wù)的個數(shù)，N為出庫任務(wù)的個數(shù)，xi為第i個入庫貨物在貨架中的坐標(biāo)位置，yj為第j個出庫貨物在貨架中的坐標(biāo)位置。自左往右，從X、Y的第一位開始，對應(yīng)編號的出入庫任務(wù)優(yōu)先組成DC 作業(yè)，最后落單的出庫或入庫任務(wù)按SC 作業(yè)執(zhí)行。例如，在經(jīng)過防碰撞原則的任務(wù)分配后，左端堆垛機(jī)可能收到4 個入庫任務(wù)和6 個出庫任務(wù)的指令，隨機(jī)生成的任務(wù)序列為Chrom1=［2，4，1，3，5，2，3，4，6，1］，其中入庫任務(wù)為X1=［2，4，1，3］，出庫任務(wù)Y1=［5，2，3，4，6，1］，則左側(cè)堆垛機(jī)編碼Chrom1 對應(yīng)的任務(wù)執(zhí)行順序是：先執(zhí)行DC 作業(yè)：先執(zhí)行入庫任務(wù)2，出庫任務(wù)5；再執(zhí)行入庫任務(wù)4，出庫任務(wù)2；以此類推先執(zhí)行完DC 作業(yè)，最后執(zhí)行落單的出庫任務(wù)6 和出庫任務(wù)1 兩個SC 作業(yè)，右端堆垛機(jī)工作模式與其一致。

目標(biāo)函數(shù)為耗時較長一側(cè)堆垛機(jī)完成所有任務(wù)運(yùn)行時間的最小值，因此采用個體目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，定義為

3.2 算法設(shè)計

（1）選擇操作

對群體中個體使用輪盤賭選擇法進(jìn)行選擇操作，個體被選擇的概率與適應(yīng)度函數(shù)值有關(guān)，個體適應(yīng)度值越高，被選中的概率越大，并在選擇過程中加入精英保留策略，將上代中最優(yōu)染色體保留到下一代。每個染色體被選中的概率為

式中：f（i）為第i個染色體的適應(yīng)度值，m為種群個體的數(shù)目。

（2）交叉操作

分別對左、右兩堆垛機(jī)的出/入庫任務(wù)序列Chrom1、Chrom2 采用兩點(diǎn)交叉，將相鄰的兩染色體分為一組，當(dāng)每組染色體的隨機(jī)概率rand≤pc時，從區(qū)間［1，m］隨機(jī)選取兩交叉點(diǎn)，對入庫任務(wù)序列進(jìn)行交叉操作，子代1 繼承父代1 交叉點(diǎn)兩側(cè)的基因，中間缺失的基因按順序從父代2 的基因中獲得；子代2 同理獲得。從區(qū)間［1，n］隨機(jī)選取兩交叉點(diǎn)對出庫任務(wù)序列進(jìn)行相同操作。用交叉后的子代染色體代替父代染色體。

（3）變異操作

分別對左、右兩堆垛機(jī)的出/入庫任務(wù)序列Chrom1、Chrom2 采用位置變異，每組染色體的隨機(jī)概率rand≤pm時，從區(qū)間［1，m］隨機(jī)產(chǎn)生兩個變異點(diǎn)，對入庫任務(wù)序列進(jìn)行變異操作，交換兩個變異點(diǎn)位置的基因形成新的染色體，同時從區(qū)間［1，n］隨機(jī)產(chǎn)生兩個變異點(diǎn)，對出庫任務(wù)序列進(jìn)行相同操作。用變異后的子代染色體代替父代染色體。

3.3 算法步驟

立體倉庫出入庫調(diào)度同軌雙車的工作模式下，采用改進(jìn)的防碰撞原則雖然能有效防止兩車干預(yù)碰撞，但并不能使第1 次得到的貨架的左右分界線e為最優(yōu)分界線，所以在新型改進(jìn)的自適應(yīng)遺傳算法的每一次優(yōu)化迭代中插入滿足改進(jìn)防碰撞原則的最優(yōu)防碰撞邊界檢測機(jī)制，對分界線e進(jìn)行最優(yōu)處理，結(jié)合算法，最終得到同軌雙車調(diào)度模型的最優(yōu)解。

改進(jìn)的防碰撞原則劃分左右兩端貨區(qū)初始任務(wù)種群的詳細(xì)處理步驟如下：

步驟2 把出庫貨物、入庫貨物對應(yīng)的貨位坐標(biāo)的橫坐標(biāo)提取出來構(gòu)成集合U。且按照從小到大的順序進(jìn)行排列。設(shè)定左右兩側(cè)堆垛機(jī)工作區(qū)域的分界線為e=U（i），i∈［1，n］。工作區(qū)域分界線e代表的含義為從第1 列到第e列貨位的貨物為左端堆垛機(jī)的工作區(qū)域，第e+1 列到第I列為右側(cè)堆垛機(jī)的工作區(qū)域。

步驟4 判斷tL≤tR，若成立，則令i=i+1，e=U（i），i∈［1，n］，轉(zhuǎn)步驟3；否則，執(zhí)行步驟5。

步驟5 左右兩側(cè)堆垛機(jī)任務(wù)分配完成，獲得初始種群工作序列。從第1 列到第e列貨位為左側(cè)堆垛機(jī)的工作區(qū)域，此工作區(qū)的出/入庫貨物由左側(cè)堆垛機(jī)完成；從第e+1 列到I列貨位為右側(cè)堆垛機(jī)的工作區(qū)域，此工作區(qū)的出/入庫貨物由右側(cè)堆垛機(jī)完成。

步驟6 將左端堆垛機(jī)所分配的出/入庫貨物的任務(wù)序列隨機(jī)排序，生成若干任務(wù)序列；對右端堆垛機(jī)所分配的出入庫貨物的任務(wù)序列隨機(jī)排序，生成相應(yīng)的任務(wù)數(shù)列。

滿足改進(jìn)防碰撞原則的最優(yōu)防碰撞邊界檢測機(jī)制的具體操作如下：

步驟1 把左端堆垛機(jī)負(fù)責(zé)的左側(cè)工作區(qū)的出入庫任務(wù)種群根據(jù)式（13）分別計算出它們的個體適應(yīng)度值FL1，F(xiàn)L2，…，F(xiàn)Ln1，把右端堆垛機(jī)負(fù)責(zé)的右側(cè)工作區(qū)的出入庫任務(wù)種群根據(jù)式（14）分別計算出他 們的個體適應(yīng)度值FR1，F(xiàn)R2，…，F(xiàn)Rn2，其中n1、n2分別為左右兩端堆垛機(jī)負(fù)責(zé)出入庫任務(wù)序列的 個 體 個 數(shù)，然 后，定 義TL= min（FL1，F(xiàn)L2，…，F(xiàn)Ln1），TR= min（FR1，F(xiàn)R2，…，F(xiàn)Rn2）。

步驟2 判斷TL與TR的大小。

步驟3 如果TL≥TR，工作區(qū)分界線enew=e（i-1），即e取貨位坐標(biāo)的橫坐標(biāo)集合U左側(cè)上一元素，根據(jù)新工作區(qū)分界線重新調(diào)整兩堆垛機(jī)任務(wù)分配后，計算兩堆垛機(jī)的運(yùn)行時間TLnew，TRnew。判斷TLnew≤TRnew，如果成立，記錄下TRnew，比較TL與TRnew大小，若TL≤TRnew，記錄最優(yōu)解Tbest=TL，左右兩堆垛機(jī)的任務(wù)分配結(jié)果不變，若TL>TRnew，記錄最優(yōu)解Tbest=TRnew，將［enew，e］區(qū)間，原屬于左堆垛機(jī)任務(wù)序列的對應(yīng)任務(wù)刪除，添加到右堆垛機(jī)的任務(wù)序列中；如果不成立，同理循環(huán)。

步驟4 如果TL

在上述的最優(yōu)防碰撞邊界檢測機(jī)制操作步驟中，重新劃分的左右工作區(qū)分界線enew，仍然約束著如下關(guān)系：左側(cè)堆垛機(jī)分配任務(wù)所處貨架的最大橫坐標(biāo)小于右側(cè)堆垛機(jī)分配任務(wù)所處貨架的最小橫坐標(biāo)，所以經(jīng)過最優(yōu)防碰撞原則檢測機(jī)制優(yōu)化后的左右堆垛機(jī)分配的任務(wù)依然滿足改進(jìn)的防碰撞原則，能夠有效防止兩堆垛機(jī)在運(yùn)行時發(fā)生碰撞干預(yù)的現(xiàn)象。將最優(yōu)防碰撞原則檢測機(jī)制在NIGA 算法的步驟7 中調(diào)用，插入到在NIGA 的每一次優(yōu)化迭代中。

嵌入改進(jìn)防碰撞原則以及最優(yōu)防碰撞原則檢測機(jī)制的NIGA 算法對立體倉庫同軌雙車出入庫調(diào)度優(yōu)化的具體步驟如下：

步驟1 設(shè)定初始參數(shù)，包括兩端I/O 臺O1、O2的坐標(biāo)，設(shè)置初始種群的規(guī)模m、以及NIGA 算法的最大迭代次數(shù)MAXiter。

步驟2 調(diào)用經(jīng)過改進(jìn)的防碰撞原則產(chǎn)生的兩個初始分配的種群Chrom1、Chrom2。Chrom1代表左端堆垛機(jī)需要負(fù)責(zé)的工作序列，種群Chrom2 代表右端堆垛機(jī)需要負(fù)責(zé)的工作序列。

步驟3 設(shè)定初始代數(shù)iter=0，若iter

步驟4 判斷（fmax-favg）/（fmax-fmin）≥1/2 是否成立，如果成立，則分別對種群Chrom1、Chrom2 先進(jìn)行選擇操作，然后進(jìn)行變異操作，最后進(jìn)行交叉操作；反之，先對種群進(jìn)行選擇操作，然后進(jìn)行交叉操作，最后進(jìn)行變異操作。

步驟5 經(jīng)過上述步驟，分別記錄進(jìn)化后Chrom1、Chrom2 兩種群的最優(yōu)值TL、TR。

步驟6 調(diào)用最優(yōu)防碰撞邊界檢驗機(jī)制的具體步驟，檢驗左、右工作區(qū)分界線e是否最優(yōu)，調(diào)整左右兩堆垛機(jī)的任務(wù)分配，并記錄最優(yōu)解Tbest；轉(zhuǎn)步驟4。

步驟7 迭代結(jié)束，輸出最優(yōu)解Tbest以及最優(yōu)解對應(yīng)的兩堆垛機(jī)最佳調(diào)度序列Chrom1、Chrom2。

嵌入改進(jìn)防碰撞原則和最優(yōu)防碰撞邊界檢驗機(jī)制的NIGA 算法流程圖如圖2 所示。

圖2 嵌入改進(jìn)防碰撞原則的NIGA 算法流程圖Fig.2 Flow chart of NIGA algorithm embedded with improved anti-collision principle

改進(jìn)后的NIGA 算法，可以根據(jù)種群適應(yīng)度值的集中分散程度，來調(diào)整算法的進(jìn)化結(jié)構(gòu)，有效地提高了算法跳出局部最優(yōu)的能力，加快了算法的收斂速度。結(jié)合改進(jìn)防碰撞原則和最優(yōu)防碰撞邊界檢驗機(jī)制后，NIGA 算法有效地解決了兩堆垛機(jī)工作時發(fā)生碰撞的問題，并為它們分配了最優(yōu)的作業(yè)區(qū)域和任務(wù)序列，最終獲得了理想的堆垛機(jī)任務(wù)分配方案。

4 實驗仿真及分析

為證明本文所提出改進(jìn)遺傳算法的有效性，現(xiàn)通過一個具體的立體倉庫貨物出入庫實例來進(jìn)行驗證。某企業(yè)的自動化立體倉庫的一個貨架有12層80 列，共有960 個貨位。每個貨位的位置固定，且大小相同，每個貨位每次最多存儲一個貨物。貨架的兩端各分布著一個I/O 臺，倉庫的巷道左右兩端分別放置了型號規(guī)格完全相同的兩堆垛機(jī)，兩堆垛機(jī)在巷道上可以同時工作，且分別為各自負(fù)責(zé)的I/O 臺執(zhí)行貨物的出入庫作業(yè)，貨架及兩堆垛機(jī)的具體信息見表1。

表1 立體倉庫規(guī)格信息及堆垛機(jī)配置信息Table 1 Specification information of warehouse and con?figuration information of stacker

立體倉庫內(nèi)有一批要執(zhí)行的出入庫任務(wù)，包含17 個入庫任務(wù)和15 個出庫任務(wù)，任務(wù)坐標(biāo)位置信息如表2 所示。

表2 出入庫任務(wù)坐標(biāo)Table 2 Coordinates of storage and retrieval tasks

為了驗證本文算法的可行性以及優(yōu)越性，以NIGA 算法為基準(zhǔn)，分別利用GA，自適應(yīng)遺傳算法（Adaptive genetic algorithm，AGA）對上述的一批出入庫任務(wù)坐標(biāo)進(jìn)行優(yōu)化求解。對初始參數(shù)進(jìn)行設(shè)定，初始種群的規(guī)模m=100，最大迭代次數(shù)MAXiter=100，pc=0.6，pm=0.2。使用matlab2018b對上述立體倉庫參數(shù)以及出/入庫任務(wù)信息進(jìn)行編程實現(xiàn)，分別用NIGA、GA、AGA3 種算法對上述所給的出入庫貨物相關(guān)信息進(jìn)行優(yōu)化。

由圖3 可知，NIGA 算法和AGA 算法隨著迭代次數(shù)的增加均收斂到了最優(yōu)解307 s，而NIGA算法在第9 代就收斂到最優(yōu)值，其迭代速度更快，而GA 算法則陷入局部最優(yōu)，在第14 代才得到局部最優(yōu)解328 s，具體比較結(jié)果見表3。與GA、AGA 算法相比，NIGA 算法收斂速度更快，跳出局部最優(yōu)能力更強(qiáng)，迭代效果更優(yōu)。

圖3 針對表2 任務(wù)的目標(biāo)函數(shù)進(jìn)化曲線Fig.3 Evolution curves of the objective function for tasks in Table 2

表3 3 種算法結(jié)果對比Table 3 Comparison results of three algorithms

由NIGA 算法對表2 的出入庫貨物序列優(yōu)化后的最優(yōu)解輸出的左堆垛機(jī)調(diào)度序列為（3 8 5 4 7 6 2 1 1 7 4 3 5 6 2），右堆垛機(jī)調(diào)度序列為（4 9 2 3 6 7 5 8 1 3 7 8 1 2 6 4 5）。相應(yīng)的堆垛機(jī)工作路線如圖4 所示。

根據(jù)圖4 可知，通過NIGA 算法對表2 中的出入庫貨物信息進(jìn)行優(yōu)化，工作區(qū)的分界線為e=40，即從貨架的第1～40 列的出入庫貨物由左堆垛機(jī)負(fù)責(zé)調(diào)度，貨架第41～80 列貨物由右堆垛機(jī)負(fù)責(zé)調(diào)度，左右兩堆垛機(jī)分別在自己的工作區(qū)域內(nèi)工作，不會發(fā)生碰撞干預(yù)現(xiàn)象。

圖4 針對表2 任務(wù)得到優(yōu)化后兩堆垛機(jī)的行駛路線圖Fig.4 Driving routes of the two stackers after optimization for tasks in Table 2

為了證明嵌入改進(jìn)防碰撞原則以及最優(yōu)防碰撞邊界檢驗機(jī)制后的NIGA 算法能為堆垛機(jī)最大程度合理分配任務(wù)，使出入庫調(diào)度結(jié)果達(dá)到最佳，同文獻(xiàn)［15］的防碰撞原則以及任務(wù)分配機(jī)制作比較，用本文改進(jìn)遺傳算法對文獻(xiàn)［15］中的出入庫任務(wù)數(shù)據(jù)進(jìn)行優(yōu)化求解。兩算法參數(shù)調(diào)整一致，NI?GA 算法優(yōu)化后堆垛機(jī)運(yùn)行時間進(jìn)化曲線如圖5 所示，兩堆垛機(jī)行駛路線圖如圖6 所示。文獻(xiàn)［15］中利用改進(jìn)的化學(xué)反應(yīng)優(yōu)化（Improved chemical reac?tion optimization，ICRO）算法求解得到的優(yōu)化值為312.67 s，兩堆垛機(jī)的工作區(qū)間的分界線為e=39，而利用本文NIGA 算法求得的優(yōu)化值為251 s，減少了61.67 s，得到的兩堆垛機(jī)的工作區(qū)間的最佳分界線為e=37。

圖5 目標(biāo)函數(shù)最優(yōu)值進(jìn)化路線圖Fig.5 Evolution curve of the objective function

圖6 兩堆垛機(jī)優(yōu)化后行駛路徑圖Fig.6 Driving routes of the two stackers after optimization

5 結(jié) 論

針對目前大型企業(yè)的自動化立體倉庫規(guī)模較大，調(diào)度難的現(xiàn)象，分析了兩端式雙堆垛機(jī)出入庫調(diào)度問題，建立了相應(yīng)的數(shù)學(xué)模型。在該模型的基礎(chǔ)上提出了改進(jìn)防碰撞策略以及最優(yōu)防碰撞邊界檢測機(jī)制的解決方法，并提出一種新的改進(jìn)遺傳算法進(jìn)行優(yōu)化。對比實驗結(jié)果表明，該算法能夠根據(jù)種群適應(yīng)度值的集中分散情況，從而自適應(yīng)地調(diào)節(jié)進(jìn)化過程中交叉操作、變異操作的先后順序，加快了算法的收斂速度，提高了算法避免陷入局部最優(yōu)的能力，并在每次迭代中嵌入改進(jìn)防碰撞策略以及最優(yōu)防碰撞邊界檢測機(jī)制，有效地確定了兩堆垛機(jī)工作區(qū)的最佳分界線，避免了堆垛機(jī)運(yùn)行中的碰撞，平衡了兩堆垛機(jī)的工作時間，有效地解決了大型自動化立體倉庫雙堆垛機(jī)的出入庫調(diào)度問題。本文對立體倉庫的布局僅考慮了兩端式I/O 臺布置，在實際工作中，為了生產(chǎn)調(diào)度的方便，I/O 臺也可能放置在貨架中間。另外，本文假設(shè)堆垛機(jī)的水平和垂直速度是恒定的，堆垛機(jī)每次完成任務(wù)后都返回至I/O 臺。因此在今后的工作中，堆垛機(jī)的水平、垂直加減速和停靠點(diǎn)的位置選擇也是未來研究中有待解決的問題。