基于混合遺傳算法的堆垛機路徑優化研究

蔣小燕，周先燁

（重慶交通大學 機電與車輛工程學院，重慶 400074）

0 引言

隨著物流行業的迅速發展，倉庫貨物的存儲逐漸變得智能化，在不斷優化的倉儲系統中，堆垛機作為連接貨物和貨架的紐帶[1]，一直是不可或缺的存在，堆垛機的行走路徑對貨物的存取效率有較大影響，提高運送效率能夠提高立體庫的整體運作效率，降低公司成本。

優秀的路徑規劃能夠提高堆垛機系統的工作效能。華祎明等[2]利用遺傳算法研究了堆垛機的作業形式對立體庫工作效率的影響，構建了多目標優化模型。蔡安江等[3]利用遺傳算法研究和解決了堆垛機的調度問題。閆青等[4]利用遺傳算法將集束搜索作為初始路徑，有效避免了算法陷入局部最優解。因此，對效率要求高的立體倉庫貨物存儲系統，普遍存在貨架的布局沒有達到最優化、堆垛機的路線雜亂、WCS 控制系統的算法落后等問題[5]。這些問題都會對堆垛機的運行效率帶來巨大的影響，針對上述問題，提出了新的混合遺傳算法，以此來優化堆垛機路徑，從而提高整個立體倉庫的工作效率。

1 堆垛機的路徑優化數學模型

1.1 倉庫整體布局設計

通過立體倉庫貨架的巷道數量以及堆垛機的數量來確定所需堆垛機的數量，立體倉庫的模型參數設置為：庫位層數12 層、巷道數目4 條、庫位列數50 列、每個庫位長度2 米、每個庫位高度為1.8 米，利用已知的倉庫參數條件進行立體倉庫的整體布局圖設計如圖1（a）所示，就單個的倉庫貨架俯視圖，將堆垛機的運行區域劃分成3 個，A 區表示傳送區、B 區表示存取區、C 區表示暫存區，如圖1（b）所示，由于堆垛機是在直線巷道中工作，因此為了方便對堆垛機的行走路徑進行簡化可視，將其視為豎直的二維格子地圖。

圖1 倉庫整體設計

1.2 堆垛機路徑優化數學模型

立體倉庫的運行從數學上可以描述為有n 個待取的貨物要在m 個貨架上進行逐個存取，設立體倉庫中有N 臺堆垛機，有S個輸入庫任務，堆垛機的載重量為Q，每單個任務的重量qn（n=1,2,3…,m），需要向M 個貨架庫位送貨，及貨架的庫位編號為m（m=1,2,…,M），將S/N=P（令P 為整數）個作業批次，且每個批次的任務總重量小于或等于堆垛機的載重量，一個作業批次，堆垛機進行逐個入庫處理，可建立如下的堆垛機行走路徑數學模型[6]：

其中：式（1）為總體運行的目標函數，Dmin為堆垛機完成一個任務批次所行走的最短距離，庫位i 到庫位j 的運距為dij，貨臺到各庫位的距離為d0i（i、j=1,2,…,m），設D01=0 表示第一個存貨庫位到取貨臺的距離，D0M表示最后一個存貨庫位到取貨臺的距離。式（2）為重量的約束條件，設常數Q=30kg。

2 堆垛機路徑優化的混合遺傳算法

2.1 蟻群算法簡介

利用蟻群算法解決路徑優化問題的過程可以概括為：螞蟻能夠走通的路線表示優化問題中的可行解，那么螞蟻在多個點上形成的所有不同路線，就代表了路徑優化中的所有解，最優解就會在這些解空間中產生[7]。螞蟻在路徑選擇點上會留下信息素，通過不同的路徑嘗試，螞蟻會在最短的路徑點上留下較強的信息素，隨著不斷的累積，最短路徑上的信息素沉淀總和最多[8]。在正反饋機制下，螞蟻群體會自然而然的集中到最優路徑上，此時的路線就是優化過程中的最優解[9]。

2.2 遺傳算法簡介

遺傳算法是一種進化算法，其主要思想是模仿生物界的“物競天擇”的進化法則[10]。通過編碼、選擇、交叉以及變異等操作，獲得優化后的最優染色體。遺傳算法在全局搜索上的能力較強，而在局部搜索上就相對薄弱，因此，在搜索最優解的過程中，遺傳算法所耗費的時間較多[11]。

2.3 混合遺傳算法

結合蟻群算法和遺傳算法的優點，形成新的混合遺傳算法，該算法可改進遺傳算法在局部搜索能力上的不足，算法通過遺傳算法的一系列操作后，通過蟻群尋優操作進行交叉處理得到的個體會取代原個體，以增強算法的局部搜索能力[12]。新的混合遺傳算法以遺傳算法為主體，在局部程序上加入蟻群算法。混合遺傳算法的優化如下[13]：

（1）編碼的設計

對貨架進行整數編碼排序，將存取貨架視為染色體，將染色體等分成貨架數量一致的切割段，其中不同段位對應不同的貨架編號[14]。

（2）種群初始化

對染色體的編碼設計完成之后，初始種群會產生初始解，通過貨架的容量及大小來決定初始種群的數量[15]，實驗中取得種群數量為80。

（3）適應度函數

（4）選擇操作

適應度值可以決定選擇操作中，在舊群體中被選擇的個體會被放入到新的種群里去，適應度值高的個體被選擇的概率也大[7]。

（5）交叉操作

利用順序局部交叉的方法，先確定兩條父代染色體交叉部分的左右兩個位置，假設為第5 段和第8 段，將5 和8 段之間的兩組節段進行交叉組位，如：灰色部分進行交叉為：

交叉后，同一條染色體中有重復的貨架編號，保留出現不重復的數字，重復的部分會利用映射關系進行數字填充，填充后的結果為：

（6）變異操作

變異操作在同一條染色體重新完成，采用兩兩對換的方式，例如將第5 段與第8 段的編號進行交換，得到新的子代染色體如下：

（7）蟻群優化操作

遺傳算法在局部搜索能力上存在很大的不足，在編碼、選擇、交叉、變異之后，引入蟻群算法進行尋優操作，即只保留信息素所增加的操作，否則忽略。螞蟻在不同點位之間移動就會構造出一個解，那么形成這個解的概率可用以下公式（4）表示[17]：

式中：τij表示螞蟻走過每條路線所留下的信息素；ηij表示驗證ij 路線的可取性，一般為ij 兩個庫位之間距離的倒數；α 表示控制τij的參數，需滿足大于或等于0 的條件；β 表示控制ηij的參數，需滿足大于或等于1 的條件；τiz和ηiz表示所有可能的解。

全局信息素的更新規則如式（5）、式（6）所示：

式中：τij表示螞蟻走過每條路線所留下的信息素總量；表示第k 只螞蟻所產生的信息素總量；ρ 表示螞蟻的信息素的揮發系數；S 表示螞蟻的數量；Q 表示信息素總量；Lk表示第k 只螞蟻行走的路程。

（8）結束操作

通過信息素濃度的高低來對每個個體進行交叉變異，利用適應度值的大小對其進行好壞評估，信息素濃度較好的會進入下一次的交叉、變異和逆轉操作，判斷操作是否循環的依據是：遺傳代數以及信息素濃度的大小是否達到最優[18]。不滿足條件就會轉入適應度值的計算，否則，結束遺傳循環操作。

3 結果分析

利用案例來完成算法優化的驗證試驗，通過已知條件將信息繪制成表格，如表1 所示：

表1 入庫信息表

在利用兩個算法進行對比實驗時，保證各個參數不變且相同，因此設置的算法參數如表2 所示。

表2 算法參數表

混合遺傳算法在10 次搜索中的最優解為96.3km，如表3 所示，相對于單純的遺傳算法，其余解與最優解也較為接近，其最優解對應的路線軌跡為：20→11→6→13→15→19→8→1→7→10→9→12→2→14→5→4→3→17→18。

表3 混合遺傳算法的搜索結果

遺傳算法10 次搜索中的最優解為99.5km，如表4 所示，對應的路線軌跡為：18→1→17→11→20→7→10→13→6→8→19→16→15→12→9→2→5→14→4→3。

表4 遺傳算法的搜索結果

實驗分析：混合遺傳算法和遺傳算法進行比較分析，分別對兩種算法進行10 次搜索，對其每項平均值進行對比，如表5 所示。

表5 兩種算法對比分析

4 結論

通過建立自動化立體倉庫的基礎模型，對堆垛機在傳統路徑選擇中使用到的遺傳算法進行了優化，形成新的混合遺傳算法，有效地解決了遺傳算法在局部搜索能力上的不足，使得堆垛機在揀選貨物的過程中行走的路徑最優，該算法對提高堆垛機運行效率提升上有顯著成效。不足之處，當訂單出現較多出庫和入庫要求時，堆垛機會出現呆滯問題。