基于遺傳粒子群動態聚類算法的物流柔性分揀系統品規分配

杜佳奇，楊旭東*，孫棟，張磊，王晉冰

基于遺傳粒子群動態聚類算法的物流柔性分揀系統品規分配

杜佳奇1，楊旭東1*，孫棟2，張磊3，王晉冰3

（1.貴州大學 機械工程學院，貴陽 550000；2.貴州理工學院，貴陽 550000； 3.貴州省煙草公司貴陽市公司，貴陽 550000）

針對目前煙草物流配送中心條煙分揀量大，不同條煙品規的分配對訂單的總處理時間影響較大的問題，研究平衡各個分揀區品規的分配，提高分揀效率。建立以各分區品規相似系數和最小為目標函數的數學模型，并采用改進的遺傳粒子群動態聚類（GAPSO-）算法進行求解。首先，結合各品規分揀量對品規相似系數進行改進，并將其作為適應度函數；然后在粒子群算法中對慣性權重因子進行改進，使其值可以進行自適應改變；最后，在粒子群動態聚類算法中引入遺傳算法中的交叉變異擴大解的搜索范圍，基于Matlab對文中的其他算法進行求解對比，求得結果在EM-plant中進行仿真驗證。結合某煙草物流配送中心數據仿真驗證，利用GAPSO-算法處理訂單的時間為234.5 s，較傳統時間大幅度較少，有效提升了柔性物流分揀效率。采用該算法可充分發揮2種算法的優良性，具有更好的收斂性及尋優性，為柔性物流品規分配提供了新思路。

品規分配；品規相似系數；慣性權重因子；遺傳粒子群動態聚類算法

由于自動化程度差異，物流分揀可被分為人工分揀（MSS）和自動化分揀系統（ASS）[1]。自動化分揀具有效率高、出錯率低、常被用于柔性分揀中。柔性分揀由于嵌入了信息化、模塊化、可視化、機械化、電子化等組件，故而其分揀過程中可以通過上位機及時進行信息反饋，并對分揀過程中出現的問題及時反饋。物流柔性分揀策略為多個分區對同一訂單中的煙并行分揀，并暫時存儲至緩存區，等待上一分區流過后緩存區擋板上下開合進行有序合流。并行分揀下，訂單總處理時間由各個分揀區中分揀時間最長的分揀時間決定，各個分揀區的分揀時間是由訂單在該分區分揀的各品規的分揀量決定，若將2個分揀量較大的品規放在一個分揀區進行分揀將延長該分區的分揀時間，從而影響訂單的總處理時間?；诖吮疚膶p少訂單總處理時間作為目標來對分區之間的品規分配問題進行研究。

張貽弓等[2]對自動分揀系統的品規分配優化提出了最大最小蟻群算法（MMAS）結合動態優化來求解模型。劉靖明等[3]針對-均值聚類算法易陷入局部收斂結合了粒子群算法，來對聚類問題進行更好效果的求解。李建明等[4]在品項似系數中加入了分揀量的影響因子，并采用了結合禁忌搜索算法的動態聚類對品項分配模型進行求解。王艷艷等[5]分析了品規的分揀量拆分對并行分揀系統延時時間的影響，并設計啟發式算法進行求解。Lee等[6]對基于品規之間的關聯性差異分配貨位問題，提出了一種啟發式聚類算法進行求解，再結合關聯性差異和空間填充曲線來對貨位區域進行分配。Peterson等[7]在人工分揀系統里，分析品規分配影響的因素，得到人在分揀區行走距離受品規分配的影響較大。Wu等[8]針對品規分配聚類問題，建立了0-1整數規劃模型，利用訂單的總數和各個品規訂購量確定品規相似系數，采用歸類方法進行求解。Garfinkel等[9]考慮到入庫時貨物品規間的相似性，采用循環交換算法進行求解分析。Liu等[10]根據訂單、品規數、分揀量3個限制條件分別對品規和客戶定義2個變量進行對比，建立了0-1整數規劃模型，提出原始-對偶算法求解模型。本文考慮到粒子群結合動態聚類算法在解的搜索過程中容易陷入局部最優，故在粒子群算法的基礎上結合遺傳算法中的交叉變異來擴大解的搜索范圍，提高收斂速度。

在現有的品規分配問題中，有著較多啟發式算法來求解問題，如：遺傳算法、粒子群算法、灰狼算法等。但這類算法對解搜索過程中依賴于參數的設定，存在陷入局部最優的死角。故以上算法各自都有其適用的途徑，并不具備解決多種問題的普遍性，需要在已有的算法中進行組合優化?；诖?，本文對如何均衡分揀區之間的品規分配問題進行研究，建立以各分區品規相似系數之和為適應度函數的數學模型，并提出2種聚類算法求解模型；然后針對動態聚類算法中的均值取聚類中心容易陷入局部最優的缺點，利用粒子群算法中的種群尋優和遺傳算法中的交叉、變異等步驟對動態聚類算法進行改進；最后經過某煙草物流中心實例仿真驗證該改進算法的高效性。

1 問題描述

1.1 物流柔性分揀系統

物流柔性分揀系統主要由立式機、臥室機、開箱機、滑箱機、傳輸皮帶等部分組成，目前大部分物流柔性分揀線采取異型煙和標準煙混合分揀的方式，由于異型煙具有尺寸不同、分揀量較少、品規數量多等特點，故而異型煙進行自動化分揀難度較大，對自動分揀系統設計有著較高要求。本文對某煙草物流分揀中心進行現場場景建模，如圖1所示。整個分揀系統由4條分揀線組成，分別為3條復合一體化分揀線以及1條異型煙分揀線，提高了異型煙分揀及標煙分揀效率。

圖1 煙草物流分揀中心

物流柔性分揀系統有2種分揀方式：串行分揀、并行分揀[11]。串行分揀策略：前一個分揀區對訂單分揀完成后，后一個分揀區可進行分揀，該分揀策略適合分揀小批量小品規物品。并行分揀策略：多個分揀區對一個訂單同時分揀，依次進行合流，該分揀策略適合大批量多品規的物流柔性分揀系統[12]。由于分揀機中的臥式機品規種類較少，而立式機的品規種類較多，故本文主要研究內容為立式機的品規分配。對一定數量的立式機進行分區，基于每個分區來對煙的品規進行分配，本文采取并行分揀策略來進行分揀，如圖2所示。本文研究方向為將煙的品規進行合理分配，提高分揀效率，減少訂單總處理時間。

圖2 并行分區柔性分揀系統

1.2 確定分區間的品規相似系數并改進

各訂單在各分揀區的分揀時間越短，其分揀效率越高，訂單的總處理時間就越短。為了減少各訂單在各分揀區的分揀時間，條煙品規分配的均勻性較為重要。條煙的品規分配是將每個品種的煙指定到某個分揀機的分揀通道進行分揀，該問題可歸結為分類已知數，是一個聚類問題。

Jane等[13]在聚類問題中引入了品規相似系數，用來表示2種品規在一個分區的共存關系。如式（1）所示，品規相似系數越大，表示該2種品規應該分配到不同的分揀區。

式中：S為品規與品規之間的品規相似系數；為待分揀訂單的總數。式（2）為0-1變量，表示品規相似系數對應的2種品規必須同時出現在一個訂單中。

由于在條煙物流分揀中，立式機每個儲煙通道出煙時間相同，故分揀量也是制約分揀時間的關鍵因素。由于文獻[13]提出來的品規相似系數并未考慮到條煙的分揀量，所以本文在品規相似系數中加入條煙的分揀量影響因子?？紤]到品規分揀量可能會出現2種品規相同情況，為了避免無窮大產生，故而對分揀量影響因子添加條件數，如式（3）所示。

由式（3）可知，若兩品規分揀量都十分大并且2種分揀量相差很大，品規相似系數就會較大，則2種品規應分到不同的分揀區；若2種品規分揀量都很小并且2種分揀量相差很小，則2種品規應分到一個分揀區進行分揀。

1.3 模型假設

為了建立更好的數學模型，做出如下假設：

1）前一個訂單分揀完成后才可進行下一個訂單的分揀。

2）各個分區的立式機完全相同，每臺立式機每分揀一條煙所需的時間都相等。

3）立式機內的煙一直都余量充足，即補貨效率高。

4）每種品規只能分配到一個立式機的一個分揀位。

2 品規分配優化建模

為了減少訂單總處理時間，解決品規分配的聚類問題尤為重要。各分區品規相似系數和累加值越大，品規的分配越不均勻，訂單的總處理時間越長。即訂單總處理時間和各分區品規相似系數和累加值成正比，故將求訂單總處理時間最小值轉換為求各分區品規相似系數和累加值的最小值。目標函數如式（5）所示。

約束條件：

3 品規分配模型求解

3.1 動態聚類算法的設計

通過動態聚類算法（-means）求解品規分配問題模型，得到聚類中心。將各個品規的卷煙進行合理歸類，歸類后篩選最優解。算法流程如圖3所示，求解品規分配問題步驟如下：

圖3 K-means算法流程

1）隨機選取個聚類中心。

2）用式（3）代替動態聚類算法中的歐氏距離判別，計算其余的每個品規和這個品規的品規相似系數，儲存至行列的矩陣中。

3）尋找矩陣中每一行的最小值對應的分揀區號，記錄每一個分揀區的個數為行1列的矩陣。設定每個分揀區最大容納品規數為，先將中小于的品規進行分配，后將中大于的品規進行分配，按照從小到大品規相似系數對分揀區進行品規分配，將分配完的品規從矩陣中刪除。

4）計算未全部完成分配品規的各個分揀區品規相似系數之和()，取其中最小值對應的分揀區，從矩陣中找出對應該分揀區品規相似系數的最小值。將最小值對應的品規分配至該分揀區。

5）判斷是否存在未完成分配的分揀區，若存在則轉步驟4，若不存在則轉步驟6。

6）求新的聚類中心，即求每個分區的所有品規數的均值然后取整。

7）判斷聚類中心是否已經不變，或者已經達到最大迭代次數；若沒有則轉步驟2。

由求解步驟可知，該算法可以快速地求得較好的聚類結果，但是以最小()為聚類標準限制了搜尋解的范圍。一旦有一兩個壞點的產生，進行后續迭代容易會讓算法陷入局部收斂。

3.2 GAPSO-K算法設計

3.2.1 適應度函數

3.2.2 粒子信息更新

粒子特征信息有速度和位置，按照式（12）和式（13）對種群中的每個粒子進行速度和位置的更新。

3.2.3 選擇

根據個體的適應度大小不同進行選擇。選擇方法常用的有輪盤賭、精英選擇等。精英選擇操作步驟是先選取適應度前/2個個體，然后進行后續的交叉變異等操作，但精英選擇容易讓搜尋解陷入到局部最優。輪盤賭則是按照適應度的不同來計算每一個粒子被選中的概率。其中遵循適應度越大個體越容易被選中，擴大了對下一代個體的搜索范圍，不易陷入局部最優[14]。輪盤賭示意圖如圖4所示，本文采取輪盤賭的選擇方式來對粒子進行選擇，粒子被選中的概率為：

式中：為粒子i的適應度。

3.2.4 交叉

采取基于交叉因子[15]的方式進行兩兩交叉。將輪盤賭選擇出來的2個父代粒子進行交叉得到子代粒子，對比子代父代適應度大小，選擇最優粒子進入下一代，其余沒有被選擇的粒子直接進入下一代。這樣通過交叉不但可以增加粒子的多樣性，不容易讓求解過程陷入局部最優解，而且可以加快求解速度，減少迭代次數。子代粒子的位置以及速度計算方法如式（15）～（16）所示。

3.2.5 變異

3.2.6 慣性權重因子改進

3.2.7 速度位置限制

因粒子群算法在搜索最優解過程中容易出現速度或者位置超過設定的范圍，故要加以限制讓解的范圍得到約束。

3.3 遺傳粒子群動態聚類（GAPSO-K）算法求解

遺傳算法（GA）是模擬自然界物競天擇、適者生存的定律而產生的一種自適應全局優化算法，其基本步驟為編碼、選擇、交叉、變異等。通過逐代篩選，直到算法達到最大迭代次數結束。粒子群算法（PSO）是模仿自然界中鳥類的群體捕食行為，將每個個體稱為粒子，用位置、速度、適應度來表征。粒子利用自身歷史最佳位置和種群歷史最佳位置來更新速度和位置，信息更新完計算適應度來衡量優劣程度[16]。

圖5 GAPSO-K算法流程

7）若迭代次數超過最大迭代次數或者種群的最佳位置不發生變化則算法結束，否則轉到步驟3。

4 仿真分析

4.1 仿真數據

為了驗證該算法性能，本文利用MATLAB通過仿真方法對GAPSO-、粒子群動態聚類（PSO-）、-means等3種算法進行了對比分析。參數設置如下：各個立式機分揀通道分揀一件煙的時間=0.3 s，每個緩存區的合流時間=1 s，品規總數=50，訂單的總數=10。每個訂單中的每種品規分揀量如表1所示。

表1 各品規在各訂單中的分揀量

Tab.1 Picking volume for each specification in each order

4.2 仿真結果與分析

對3種優化算法（GAPSO-、PSO-和-means）在MATLAB上進行30次仿真驗證，其算法的初始參數設定如表2所示。仿真結果最優值結果見表3。

表2 GAPSO-參數

Tab.2 GAPSO-K parameters

表3 優化后的品規號分配

Tab.3 Optimized specification number allocation

利用EM-Plant軟件對分揀系統工藝流程圖進行1∶1建模，并按照實際運行時需要的各種參數賦予模型中的各個設備。按照分揀系統實際統運行時的控制方法，編寫該仿真系統的各種控制策略。將3種算法得出的品規分配優結果利用EM-Plant軟件進行仿真驗證，其復合一體化分揀系統二維模型如圖6所示。其系統是由補貨小車、臥式機、立式機、傳輸帶、緩存區、包裝機等部分構成。在EM-Plant中設置與實際物流系統相近的參數，達到與實際高度相關，故可在EM-Plant進行模擬得到較好的品規分配方案，從而減少訂單總處理時間。

現場布局由3條復合一體化分揀線以及一條異型煙分揀線組成。本文主要研究立式機的品規分配對訂單總處理時間的影響，故取其中的異型煙分揀線進行研究。其中每個分揀區代表異型煙分揀線的一個子線，異型煙分揀線如圖7所示?，F場采用了5條異型煙子線，故而本文討論的分區數目也為5，整個異型煙分揀線模型由立式機、傳輸帶、緩沖區、合單區、包裝機等部分組成。由于現場布局條件使得每個子線傳輸帶長度不同，在EM-Plant中模擬傳輸帶的長度來表示。

對前文經過3種算法得出的品規分配結果在異型煙分揀線中進行仿真模擬獲取訂單總處理時間，并且將各個分揀區的品規相似系數和累加值、訂單的總處理時間進行對比，如表4所示。

由表4可知，對比3種算法優化后得到的平均值，PSO-算法相較于-means算法提升了10.2%，GAPSO-算法相較于-means算法提升了15.2%。對比優化后的平均值，PSO-算法相較于-means算法提升了12.5%，GAPSO-算法相較于-means算法提升了16.4%。由于GAPSO-算法是在PSO-算法基礎上進行改進的，2種優化算法具有一定的相似性，相較于PSO-算法只提升了5.6%。因此按照GAPSO-算法得到的品規分配結果最好，能大幅度降低訂單總處理時間，提高分揀效率。

對比MATLAB仿真結果中3種算法最優值對品規相似系數和的進化過程如圖8所示。

圖6 復合一體化分揀系統二維模型

圖7 異型煙分揀線模型

表4 仿真結果對比

Tab.4 Comparison of simulation results

圖8 3種算法最優適應度進化過程對比

GAPSO-在迭代了18次后完成收斂，為1 150；PSO-在迭代78次后收斂于1 193，-means則于139次迭代后收斂于1 337。GAPSO-有最少的迭代次數和最優的收斂結果，效果明顯優于其他2種算法，并且經過EM-Plant軟件的驗證得出該算法處理后的品規對訂單的總處理時間明顯低于其他2種算法。

5 結語

本文針對柔性物流分揀系統，以品規相似系數作為適應度函數建立品規聚類模型，針對模型求解提出一種具有創新性的改進遺傳粒子群動態聚類算法?？紤]到品規分揀量對適應度函數的影響，對品規項系數引入了分揀量以及條件數進行改進。為提高算法子代選擇多樣性，在算法中添加了遺傳操作中的交叉變異來提高搜索范圍。利用MATLAB進行算法求解，通過算例對比，證明所提算法對品規分配問題具有較好的適應性。結合某煙草物流實例數據，利用EM-Plant軟件進行系統仿真，相比其他2種算法，采用GAPSO-算法得到的訂單總處理時間從302.4 s減少至252.7 s，訂單總處理時間較-means算法的減少了16.4%，相較PSO-算法減少了5.6%，分揀效率明顯提升。結果表明了本文提出的GAPSO-算法適用于物流柔性分揀系統的品規分配，為提高物流柔性分揀系統的效率提供了新思路。

本文僅考慮了立式機的品規分配對訂單總處理時間的影響，但是在柔性物流分揀中臥式機品規分配對分揀效率的影響也是不可忽略，因此臥式機品規分配問題有待進一步研究。

[1] DE KOSTER R B M, LE DUC T, ROODBERGEN K J. Design and Control of Warehouse Order Picking: A Literature Review[J]. European Journal of Operational Research, 2007(2): 481-501.

[2] 張貽弓, 吳耀華, 耿耀華. 并行揀選策略下的自動揀選系統品項分配優化[J]. 計算機工程與應用, 2011, 47(3): 240-243.

ZHANG Y G, WU Y H, GENG Y H. Item Assignment Optimization of Automated Picking System Based on Synchronized Zoning Strategy[J]. Computer Engineering and Applications, 2011, 47(3): 240-243.

[3] 劉靖明, 韓麗川, 侯立文. 基于粒子群的K均值聚類算法[J]. 系統工程理論與實踐, 2005, 25(6): 54-58.

LIU J M, HAN L C, HOU L W. Cluster Analysis Based on Particle Swarm Optimization Algorithm[J]. Systems Engineering-Theory & Practice, 2005, 25(6): 54-58.

[4] 李建明. 物流配送中心分區自動分揀系統品項分配方法研究[D]. 蘭州: 蘭州交通大學, 2017: 16-31.

LI J M. Research on Item Distribution Method of Automatic Sorting System in Logistics Distribution Center[D]. Lanzhou: Lanzhou Jiatong University, 2017: 16-31.

[5] 王艷艷, 吳耀華, 吳穎穎. 并行自動揀選系統品項揀選量拆分優化[J]. 機械工程學報, 2013, 49(16): 177-184.

WANG Y Y, WU Y H, WU Y Y. SKU Picking Quantity Splitting Optimization of Parallel Automatic Picking System[J]. Journal of Mechanical Engineering, 2013, 49(16): 177-184.

[6] LEE M K. A storage assignment policy in a man-on-board automated storage/retrieval system[J]. International Journal of Production Research, 1992, 30(10): 2281-2292.

[7] PETERSON C G, GERALD A. Considerations in Order Picking Zone Configuration[J]. International Journal of Operations & Production Management, 2002, 27: 793-805.

[8] WU C. An Association-Based Clustering Approach to Order Batching Considering Customer Demand Patterns[J]. Omega, 2005, 33(4): 333-343.

[9] GARFINKEL M. Minimizing Multi-Zone Orders in the Correlated Storage Assignment Problem[D]. Georgia: Georgia Institute of Technology, 2005.

[10] LIU C M. Clustering Techniques for Stock Location and Order-Picking in a Distribution Center[J]. Computers & Operations Research, 1999, 26(10/11): 989-1002.

[11] 楊姣. 煙草異標合一多模式分揀系統仿真研究[D]. 貴陽: 貴州大學, 2022: 37-49.

YANG J. Simulation Study of Tobacco Heterogeneous Multi-Mode Sorting System[D]. Guiyang: Guizhou University, 2022: 37-49.

[12] 李露莎. 多子線復雜煙草分揀系統研究[D]. 貴陽: 貴州大學, 2022: 22-42.

LI L S. Research on Multi-Subline Complex Tobacco Sorting System[D]. Guiyang: Guizhou University, 2022: 22-42.

[13] JANE C C, LAIH Y W. A Clustering Algorithm for Item Assignment in a Synchronized Zone Order Picking System[J]. European Journal of Operational Research, 2005, 166(2): 489-496.

[14] 張長勇, 劉佳瑜. 基于改進遺傳算法的航空集裝箱裝載優化[J]. 包裝工程, 2022, 43(11): 253-260.

ZHANG C Y, LIU J Y. Optimization of Aviation Container Loading Based on Improved Genetic Algorithm[J]. Packaging Engineering, 2022, 43(11): 253-260.

[15] 許晨, 康雪, 楊玲. 基于粒子群K均值聚類算法的多時相去云處理[J]. 成都信息工程大學學報, 2020, 35(4): 424-429.

XU C, KANG X, YANG L. Multi-Temporal Cloud Removal Based on Particle Swarm K-Means Clustering Algorithm[J]. Journal of Chengdu University of Information Technology, 2020, 35(4): 424-429.

[16] 吳延凱, 張偉, 王亞剛. 基于GA-PSO的印版滾筒溫度二自由度PID參數整定[J]. 包裝工程, 2020, 41(5): 185-191.

WU Y K, ZHANG W, WANG Y G. Parameter Tuning of Two-Degree-of-Freedom PID Controller for Plate Cylinder Temperature Based on GA-PSO[J]. Packaging Engineering, 2020, 41(5): 185-191.

Genetic Particle Swarm-based Dynamic Clustering Algorithm for Logistics Flexibility Sorting System of Specification Allocation

DU Jiaqi1, YANG Xudong1*, SUN Dong2, ZHANG Lei3, WANG Jinbing3

(1. School of Mechanical Engineering, Guizhou University, Guiyang 550000, China; 2. Guizhou University of Technology, Guiyang 550000, China; 3. Guiyang Branch of Guizhou Province Tobacco Company, Guiyang 550000, China)

In order to solve the problems of the large sorting quantity of cigarette in tobacco logistics distribution center and the great impact of assignment of cigarette specification on the total processing time of orders, the work aims to study the allocation of each sorting zone and improve the sorting efficiency. A mathematical model with the objective function of minimizing the similarity coefficients of specification in each zone was developed and solved by an improved genetic particle swarm dynamic clustering (GAPSO-) algorithm. Firstly, the similarity coefficient of each specification was improved by combining the sorting quantity of each specification as the fitness function. Then, the inertia weight factor was improved in the particle swarm algorithm so that its value could be changed adaptively. Finally, the cross-variance in the genetic algorithm was introduced in the particle swarm dynamic clustering algorithm to expand the search range of the solution, and the results were compared with the other algorithms based on Matlab. The results were simulated and verified in EM-plant. Combined with the data simulation verification in a tobacco logistics distribution center, the time for processing order with GAPSO-algorithm was 234.5 s, which was significantly reduced compared with the traditional time, effectively improving the efficiency of flexible logistics sorting. The use of this algorithm can give full play to the goodness of both algorithms, with better convergence and merit-seeking, and provides a new idea for flexible logistics product rule allocation.

product specification distribution; similarity coefficient of specifications; inertia weight factor; genetic particle swarm dynamic clustering algorithm

TB485.3；TP278

A

1001-3563(2024)05-0126-09

10.19554/j.cnki.1001-3563.2024.05.015

2023-09-20

貴州省煙草公司貴陽市公司科技項目（黔煙筑科（2022）1號）；貴州省普通高等學校青年科技人才成長項目（黔教合KY字[2021]268）