基于改進防碰撞策略的兩端式雙堆垛機出入庫優化研究

耿 賽，王 雷，李東東

（安徽工程大學機械工程學院，蕪湖 241000）

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

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

1 問題描述

1.1 兩端式雙堆垛機問題描述

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

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

圖1 兩端式雙堆垛機立體倉庫模型結構圖Fig.1 Structure diagram of the warehouse model with two?end double stacker

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

式中TL和TR分別為同一巷道左端堆垛機和右端堆垛機完成各自任務所花費的時間。

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

若立體倉庫為兩端式布局，同一巷道上有兩臺堆垛機負責貨物的出入庫調度。現僅分析左堆垛機完成所有的單一作業任務，復合作業任務所用的時間為

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

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

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

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

1.2 相關參數的基本假設

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

2 出入庫調度模型

兩端式雙堆垛機出入庫調度模式下，首要問題就是避免兩堆垛機執行任務時發生碰撞以及合理分配左、右兩堆垛機執行任務。因此本節首先提出了改進的防碰撞原則，并以此為約束條件，建立相關的雙堆垛機調度模型，最后嵌入最優防碰撞邊界檢驗機制。

2.1 改進的防碰撞原則

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

改進的防碰撞原則數學表達式為

采用式（8，9）表示的改進的防碰撞原則，可將左、右兩堆垛機負責執行的出/入庫貨物，根據其所處貨位的列坐標從左往右按大小排列，劃分為沒有重疊部分的左、右兩工作區域。

2.2 雙堆垛機調度模型

雖然該調度模型下堆垛機型號完全一致，但是左、右堆垛機被分配的出庫任務、入庫任務的數目可能完全不同。假設左側堆垛機需要執行n1個入庫任務，m1個出庫任務，右側堆垛機需要執行n2個入庫任務，m2個出庫任務，取

由式（12）可知，兩端式雙堆垛機模式下，左側堆垛機要執行Q1個DC 作業和Q2-Q1個SC 作業，右側堆垛機要執行P1個DC 作業和P2-P1個SC 作業，結合式（2～6），參考文獻［10］的相關內容，可得左、右兩側堆垛機完成各自任務所運行的總時間為

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

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

2.3 最優防碰撞邊界檢驗機制

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

最優防碰撞邊界檢驗機制判斷依據如下：根據改進的防碰撞原則得到左、右工作區分界線e；左、右堆垛機執行完各自分配任務所運行的時間TL、TR。

（1）當TL≥TR時，左、右工作區分界線左移取e左邊較小元素，enew=U（i-1），將［enew，e］區間內橫坐標對應的任務從左堆垛機負責的任務集合L中刪去添加進右端堆垛機負責的集合R中，重新計算任務更新后，左、右堆垛機執行各自任務的運行時間TLnew，TRnew。比較兩者大小：

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

②當TLnew>TRnew時，令TL=TLnew，更新左、右堆垛機出入庫任務分配結果，邊界enew繼續左移取U中最近的較小元素……按上述規則繼續循環判斷，直 至TLnew≤TRnew時，比 較TL與TRnew大 小，若TL≥TRnew則保留最新的出入庫任務分配結果，記錄最優解Tbest=TRnew；反之保留原出入庫任務分配結果，記錄最優解Tbest=TL。

（2）當TL

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

②當TLnew

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

3 出/入庫調度路徑的優化

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

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

3.1 編碼設計

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

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

目標函數為耗時較長一側堆垛機完成所有任務運行時間的最小值，因此采用個體目標函數的倒數作為適應度函數，定義為

3.2 算法設計

（1）選擇操作

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

式中：f（i）為第i個染色體的適應度值，m為種群個體的數目。

（2）交叉操作

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

（3）變異操作

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

3.3 算法步驟

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

改進的防碰撞原則劃分左右兩端貨區初始任務種群的詳細處理步驟如下：

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

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

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

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

滿足改進防碰撞原則的最優防碰撞邊界檢測機制的具體操作如下：

步驟1 把左端堆垛機負責的左側工作區的出入庫任務種群根據式（13）分別計算出它們的個體適應度值FL1，FL2，…，FLn1，把右端堆垛機負責的右側工作區的出入庫任務種群根據式（14）分別計算出他 們的個體適應度值FR1，FR2，…，FRn2，其中n1、n2分別為左右兩端堆垛機負責出入庫任務序列的 個 體 個 數，然 后，定 義TL= min（FL1，FL2，…，FLn1），TR= min（FR1，FR2，…，FRn2）。

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

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

步驟4 如果TL

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

嵌入改進防碰撞原則以及最優防碰撞原則檢測機制的NIGA 算法對立體倉庫同軌雙車出入庫調度優化的具體步驟如下：

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

步驟2 調用經過改進的防碰撞原則產生的兩個初始分配的種群Chrom1、Chrom2。Chrom1代表左端堆垛機需要負責的工作序列，種群Chrom2 代表右端堆垛機需要負責的工作序列。

步驟3 設定初始代數iter=0，若iter

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

步驟5 經過上述步驟，分別記錄進化后Chrom1、Chrom2 兩種群的最優值TL、TR。

步驟6 調用最優防碰撞邊界檢驗機制的具體步驟，檢驗左、右工作區分界線e是否最優，調整左右兩堆垛機的任務分配，并記錄最優解Tbest；轉步驟4。

步驟7 迭代結束，輸出最優解Tbest以及最優解對應的兩堆垛機最佳調度序列Chrom1、Chrom2。

嵌入改進防碰撞原則和最優防碰撞邊界檢驗機制的NIGA 算法流程圖如圖2 所示。

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

改進后的NIGA 算法，可以根據種群適應度值的集中分散程度，來調整算法的進化結構，有效地提高了算法跳出局部最優的能力，加快了算法的收斂速度。結合改進防碰撞原則和最優防碰撞邊界檢驗機制后，NIGA 算法有效地解決了兩堆垛機工作時發生碰撞的問題，并為它們分配了最優的作業區域和任務序列，最終獲得了理想的堆垛機任務分配方案。

4 實驗仿真及分析

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

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

立體倉庫內有一批要執行的出入庫任務，包含17 個入庫任務和15 個出庫任務，任務坐標位置信息如表2 所示。

表2 出入庫任務坐標Table 2 Coordinates of storage and retrieval tasks

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

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

圖3 針對表2 任務的目標函數進化曲線Fig.3 Evolution curves of the objective function for tasks in Table 2

表3 3 種算法結果對比Table 3 Comparison results of three algorithms

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

根據圖4 可知，通過NIGA 算法對表2 中的出入庫貨物信息進行優化，工作區的分界線為e=40，即從貨架的第1～40 列的出入庫貨物由左堆垛機負責調度，貨架第41～80 列貨物由右堆垛機負責調度，左右兩堆垛機分別在自己的工作區域內工作，不會發生碰撞干預現象。

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

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

圖5 目標函數最優值進化路線圖Fig.5 Evolution curve of the objective function

圖6 兩堆垛機優化后行駛路徑圖Fig.6 Driving routes of the two stackers after optimization

5 結 論

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