蔣小燕，周先燁

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

0 引言

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

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

1 堆垛機的路徑優(yōu)化數(shù)學模型

1.1 倉庫整體布局設計

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

圖1 倉庫整體設計

1.2 堆垛機路徑優(yōu)化數(shù)學模型

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

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

2 堆垛機路徑優(yōu)化的混合遺傳算法

2.1 蟻群算法簡介

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

2.2 遺傳算法簡介

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

2.3 混合遺傳算法

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

（1）編碼的設計

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

（2）種群初始化

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

（3）適應度函數(shù)

（4）選擇操作

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

（5）交叉操作

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

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

（6）變異操作

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

（7）蟻群優(yōu)化操作

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

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

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

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

（8）結束操作

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

3 結果分析

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

表1 入庫信息表

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

表2 算法參數(shù)表

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

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

遺傳算法10 次搜索中的最優(yōu)解為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 結論

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