基于粒子群與遺傳算法的排序區揀選優化研究

張巖

摘要：影響物流時效的核心環節是揀選作業，其對物流成本及競爭力都有著非常重要的影響作用。目前，我國多數的物流企業均是人工分揀。但是隨著分揀量的增加、分送點的增多，配貨響應時間的縮短和服務質量的提高，單憑人工分揀必將無法滿足大規模揀貨的要求。針對車間內既需要排序同時又需要揀選的操作來說，存在著人員行走距離較長，路線交叉，揀錯零件的風險高等問題。分析后對此問題提出了利用使用燈光揀選與多層貨架結合的方式替代現有的揀選方式，構建數學模型，并通過遺傳和粒子群的混合算法對其進行求解，進而對揀選的路徑進行優化，最終設計出成本最低的揀選方案。?

Abstract： As the core link that affects the effectiveness of logistics， picking operation， which has a very important impact on logistics cost and competitiveness. At present， most of the logistics enterprises in China are manual sorting. However， with the increase of sorting volume， distribution points， distribution response time and service quality， manual sorting alone will not meet the requirements of large-scale picking. For the operation of sorting and picking in the workshop， there are many problems， such as long walking distance， cross route and high risk of picking wrong parts. After analysis， this paper proposes to use the combination of light picking and multi-layer shelf to replace the existing way of picking， build a mathematical model， and solve it through the hybrid algorithm of genetic and particle swarm optimization， then optimize the path of picking， and finally design the lowest cost picking scheme.

關鍵詞：排序區;燈光揀選;遺傳算法;粒子群算法;揀選路徑

Key words： sorting area;PTL;GA;PSO;Picking Path

中圖分類號：TP18 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1006-4311（2020）19-0249-05

0 ?引言

作為影響物流時效的核心環節，揀選作業對物流成本和競爭力有著至關重要的影響作用[1]。在物流領域內，揀選是指揀選式配貨作業，是揀選人員或揀選工具在各個儲存點內行走并將待揀選的貨物取出，完成揀選任務的相對運動[2]。作倉儲運營系統中的重要環節，揀選技術的發展日新月異，從傳統的揀選人員手持揀貨單揀貨到使用PDA掃描揀貨，從射頻識別技術到電子標簽輔助揀選技術，從貨到人系統到機器人自動揀貨技術，琳瑯滿目。企業在設計倉儲運營系統時，面臨越來越多的選擇。

一般需要物流揀選操作的車間，進行的都是揀選作業。而某些汽車企業不同，物料零部件并不是直接從倉庫直接運送到生產線上進行裝配的。汽車零部件從原料區到生產線旁，都是需要經過配套排序區的一系列揀選排序的操作的在該區域內揀選作業人員不僅需要將零件揀放到指定的位置，還需要對這些零件按照訂單上的順序進行排序，保證生產。在這個過程中，除了揀選零件需要一定的時間外，還增加了零件的排序時間。其中，配套排序區，就是指根據生產訂單排序， 從不同的零件族揀選出一些零件，放到同一臺車的配套器具里（KC）， 或是從同一個零件族中揀選出差異的零件放到一個排序器具里（SQ）。配套（KC）：配套是把不同類別的多個零件根據系統的生產訂單順序放入一個配套器具中。排序（SQ）：排序是將同一類別的多個零件（通常種類不小于3種）根據系統生產訂單順序放入一個排序器具中。

1 ?問題的提出

M汽車企業的總裝車間擁有著柔性的生產線，該企業用四年的時間實現了每小時40臺車的產能，而這個產能效率還在不斷提升，到目前，產能為60臺車每小時，按照車型、高低配等的不同，可能在這條生產線下線的產品有近百種。為了生產這些產品，需要準備的原材料需要幾千種。物流部門每天需要將超過3000000零部件及時的分配到各條裝配生產線上，這就要求信息的傳遞必須是正確的，相關的流程必須是合理的，高效的，關鍵是成本必須是在一個可控范圍，這樣才能保證汽車的正常生產[3]。而龐大的數字只是物流工作面對的維度之一。實際上，物流是生產系統的核心，是極其重要的。要確保一切都在同步進行，在正確的時間，把正確的零件送到正確的地點，這樣才能汽車才能順利誕生。因此在這樣先進的企業中，高效物流系統是不可缺少的，而汽車制造流程復雜，科學的物流至關重要。在該工廠里，每天都有幾千立方米的原料需要被運送到相應的生產環節，若是原料大批堆積將很大程度的降低生產效率揀選。

在對總裝車間排序區揀選作業進行研究后，發現以下幾種情況出現。

①現有揀選作業流程不合理，導致排序揀選作業時間較長，工人勞動效率較低，會出現滿足不了生產的情況。

目前，在該汽車總裝車間內，隨著系統自動生成訂單，配套排序區的打印機自動打印出揀選領料單，當這些領料單攢到一定數量時，揀選操作人員需要將領料單進行手動排序，再將信息匯總到手抄紙上，接著帶著領料單推著揀選小車到存放汽車零部件的架子處進行揀選作業，當領料單上的零件揀選完畢時，操作人員再將小車中的零件依次放入到待發走的拖車中，完成此次揀選任務。

整個流程中，出現了人員先將零部件按照順序放入揀選小車中，再將零件取出，依次放入到待發走的拖車中，整個過程中揀選小車僅是起著過渡的作用，并非必須使用的器具。由于揀選作業流程中存在這種無用不產生實際價值的操作，導致揀選作業時間過長。

②同一區域，多名作業人員并行接力式揀排序揀選（最多有10個人），不僅會出現信息交接偏差，重復作業等，還會出現交叉作業，相互影響等情況。

③人工抄寫揀選信息，增加了錯揀的風險。

揀選作業人員將領料單按照零件放置的位置進行排序，再將排序后的零件信息抄寫到手抄單上。在抄寫時，作業人員經常出差錯，揀選信息抄寫錯誤，直接導致揀選作業人員揀選錯誤的零件，若沒有及時發現，有可能會造成停線等嚴重的后果。

故將信息手動抄寫這種方式，會增加零件錯揀的風險，甚至造成更加嚴重不可挽回的結果。于此同時，作業人員作業時為了盡量降低錯揀漏揀的情況發生需要集中注意力，從人因角度來說這樣是非常不合理的。此外，在長時間揀選作業后，隨著作業人員疲勞程度的增加，錯揀的幾率會增加很多。

④人工排序時，對現場熟悉成都要求高。

由于系統產生的訂單是由需求決定的，并無規律可言，故可將其看作是隨機產生的訂單。當訂單產生并攢夠一定數量時，揀選人員將根據零件裝入拖車的順序將領料單進行排序，因此領料單上需要揀選的零件會分布在不同的貨架上。此時，揀選人員需要熟悉現場零件的擺放位置等，之后根據經驗判斷所需要揀選的零件所在的位置再進行揀選作業。

若作業人員未接收良好的培訓或對現場環境不夠了解，容易混淆零件，嚴重時甚至揀錯零件。

⑤每天打印的紙質單據，大量消耗紙張和墨盒，造成資源的浪費。

排序區揀選作業的時間要求是十幾分鐘就要排完揀選完一個器具，一般器具平均有十幾二十幾張的紙質單據，而每班最少生產8小時，最多10.65小時，兩班制生產，每周工作6天，計算下來每周物流排序區會產生四五千張排序單需要處理。生產操作工人除了要做排序揀選任務外，還要額外增加處理紙張的工作，增加了作業人員的工作量的同時還增加了成本。除此之外，也影響了車間現場5S管理。

⑥揀選效率低，現場揀選作業人員多，人工成本增加。

2 ?建模與求解

針對M汽車企業生產過程中發現的上述問題，在符合物流中心布局以及工藝要求的條件下，應用現存的技術，以最小的成本對揀選進行改進提升。

為此智能揀選系統可以解決大多數的問題，本文針對這些問題提出相應的智能揀選方案。首先，從排序揀選信息的處理入手，將物料的需求進行整合，盡可能的減少揀選操作的數量。整合同一類型的訂單，使得可以一次完成對一張訂單的揀選，并且縮短了時間。其次，對排序揀選方式的類型和零件的存儲方式進行優化，將地面件放置到多層料架上，減少物料的存儲空間，避免空間的浪費。同時，采取智能的排序揀選方式，燈光揀選的電子標簽式的輔助揀選方式，利用燈光指引的方式指導揀選作業人員先揀選何種零件，放置到何處，當該種零件揀選完畢后，再依次按照順序對訂單待排序揀選的零件進行操作。減少揀選人員的自主判斷，還能縮短查找與檢查的時間等。對現階段的揀選模式進行分析，明確揀選的目的，進而優化揀選配送過程。最后，對揀選的路徑進行優化研究。

在燈光揀選的智能揀選方式的基礎上，對其中亮燈待揀零件的揀選路徑進行優化，主要針對現階段重復路徑多，產品類型轉換帶來的額外決策時間等。使用科學，系統的揀選方法，減少重復路徑。使用智能技術對揀選路徑計算，優化揀選過程的路線，使揀選作業人員按照智能揀選系統提供的路徑進行揀選，可以進一步減少移動的重復距離，提高揀選的效率。

2.1 數學模型的構建

從揀選作業的流程上看可以把揀選作業路徑簡化歸納成如下問題：在該區域內有P個揀選人員，每個人揀選人員都會在揀選單打印處領到1張揀選單，而這1張揀選你單上有n個揀選任務，即有n個待揀選的儲位，揀選作業人員從初始點出發，分別到達n個儲位點，且每個儲位點只去一次，最后回到起點，求揀選作業人員行走的最短路徑。系統打印出來的揀選單是與生產線上需要裝配的汽車的零件信息是一一對應的，這就存在著和排序區的架位置不一致，而每個人的揀選任務數量是一致的，故本文可以將問題簡化為1個揀選人員對應n個揀選任務，m個貨架。

相類似的可將本文的問題歸納為旅行商問題，并根據實際情況添加約束條件。規定揀選人員推著揀選器具需從空/滿車點出發，訂單中的揀選任務出現的儲位都要被走到，并且只走到1次，最后揀選器具要返回空/滿車點。需要在滿足以上幾點的約束條件之下，制定出合理的揀選路線。最優的路線代表著揀選時間最短，揀選效率最高，繼而代表著揀選的成本最低。

2.2 算法的設計

Grenfenstette提出的遺傳算法從代表問題可能潛在解集的一個種群（Population）開始，對種群反復進行選擇（Selection）、交叉（Crossover）以及變異（Mutation）操作，估計各個個體的適應值（Fitness），根據“適者生存、優勝劣汰”的進化規則，使得群體越來越向最優解的方向進化[4-6]。其在計算過程中的前期有較大波動、計算結果變化大，在經過了一定代數的迭代后計算結果的波動逐漸減小并最后趨于穩定。基本遺傳算法在迭代過程中易陷入局部最優。

粒子群算法是一種比較年輕的算法，在1999年由電氣工程專家Eberhart與社會學專家Kennedy所提出[7]。其算法簡單，收斂速度快，并且易于實現但后期容易出現早熟收斂的情況[8]。而遺傳算法在全局性的最優解的搜索上有其獨特的高效性，但是作為一種群體并行搜索的全局尋優算法，在局部搜索能力上有明顯的不足，本文主要通過在粒子群算法中引入一算算法的交叉算子，使得成對的粒子可以互相交換信息，以便粒子具有向新的搜索空間飛行的能力。在粒子群算法中引入遺傳算法的變異算子來增強粒子群算法跳出局部小的能力。

粒子群優化算法的計算過程是沒有波動，并且它們也是分階段的逐漸向最優解收斂的[9]。遺傳算法與粒子群算法在優化方面具有很強的互補性[10]。遺傳算法的探索精度與求變能力很強，其求解全局搜索能力很強，但局部搜索能力不足，而粒子群算法在全局尋優算法中具有隨機的特性，其優點在于對優化目標的函數不要求可解析性。本文主要通過在粒子群算法中引入遺傳算法的交叉算子，使得成對的粒子可以互相交換信息，以便粒子具有向新的搜索空間飛行的能力。為了實現增強粒子群算法能夠跳出局部求解的能力，可以將遺傳算法的變異操作引入到粒子群算法中，這種方式不僅增強了粒子的全局搜索能力，除此之外還保留了收斂速度快的優點。

組合算法示意圖如圖1所示。

具體的算法實現步驟如下：

①粒子編碼：對于揀選路徑的優化求解問題，實現混合粒子群算法的關鍵環節就是對粒子進行編碼。將該問題的粒子編碼方式設置為整數編碼，每個粒子代表一個解，相當于每個粒子是解空間的一個所有儲存位置信息的排列。

假設有1-20，共20個待揀選的零件，假設某個粒子的編碼為[16 13 1 2 5 7 4 20 3 18 12 14 15 6 8 10 9 11 17 19]，這個編碼代表了揀選作業人員需要行走的路徑是從16開始的，接下來一次順序為13，1，2，5，7，…，19。

②適應度函數：粒子的適應度函數 代表行走完整個揀選路徑的長度。

③交叉：粒子通過將當前所在的位置與個體極值或群體極值進行交叉操作，來 更新更新目前的位置。交叉的操作方法使用整數交叉法。首先，在所選擇的粒子中選擇兩個地方要進行交叉操作，接著將其與個體極值或群體極值進行交叉，隨機誕生兩個交叉點3與10，交叉的具體方法如下所示：

粒子當前值：[16 13 1 2 5 7 4 20 3 18 12 14 15 6 8 10 9 11 17 19]。

個體的極值：[12 3 20 14 11 17 18 8 9 10 15 6 1 4 2 5 7 13 16 19]。

交叉后個體：[16 13 20 14 11 17 18 8 9 10 12 5 15 6 7 3 1 2 4 19]。

粒子當前位置的從第3個基因至第10個基因的一段基因為[1 2 5 7 4 20 3 18]，而個體極值的從第3個基因至第10個基因為[20 14 11 17 18 8 9 10]，將這兩段基因進行交叉操作，即可得到新的個體。而使用該種交叉操作后，會出現位置重復的情況，此時需要對新個體進行適當的調整，消除重復位置。具體調整的方法為，將交叉后的個體內已經重復夫人儲存位置用還未包含的儲存位置進行替換，具體操作如下：

交叉后的個體：[16 13 20 14 11 17 18 8 9 10 12 14 15 6 8 10 9 11 17 19]。

對其進行更改：[16 13 20 14 11 17 18 8 9 10 12 5 15 6 7 3 1 2 4 19]。

重復的位置分別為第12位，第15位，第16位，第17位，第18位及第19位。將這些位置分別用5，7，3，1，2，4進行替代，對所得到的個體保留了最優個體，只有當新得到的粒子的適應度值比原來的粒子的適應度值更優的情況再更新粒子的當前位置。

④變異：本文在變異操作，是通過對粒子的內部的隨機兩個基因進行互相交換位置的方式實現的。首先，在粒子中隨機選取兩個位置1和2，要對其采取變異操作，再將這兩個基因的位置互換，，針對上面的粒子，隨機選取兩個要產生變異的位置，第2位和第5位，變異的操作方法如下所示：

變異操作前的粒子：[16 13 20 14 11 17 18 8 9 10 12 5 15 6 7 3 1 2 4 19]。

變異操作后的粒子：[16 11 20 14 13 17 18 8 9 10 12 5 15 6 7 3 1 2 4 19]。

對所得到的個體保留了最優個體，只有當新得到的粒子的適應度值比原來的粒子的適應度值更優的情況再更新粒子的當前位置。

2.3 仿真驗證與結果分析

假設改建后的排序區料架有15排15列（15×15）。將左下角的貨位設立為坐標原點，建立直角坐標系，（X，Y）代表貨架的第X列第Y排，初始插取點坐標為M（0，1）。則距離遠點最遠的點為（15，15）。在該區域內有十個不同的貨物需要揀選，并且這是個貨位的位置已經明確，分別為A（8，2），B（12，8），C（1，9），D（5，5），E（5，13），F（2，6），G（10，5），H（15，10），I（9，12）與J（2，7）。

按照前述公式，任意兩個貨位間的揀選作業時間成本可以求得如表1所示。

若不經過改善，直接按照車間目前的現狀及標準流程，當有這10個揀選任務時，揀選人員需要一次對其進行揀選以完成此次揀選任務。則其揀選路徑即為M→A→B→C→D→E→F→G→H→I→J→M，總時間成本為109.6。該揀選作業的路線如圖2所示。

而經過改善，通過計算機編程求解最終，得出最優路線為M→D→F→B→H→E→I→C→J→G→A→M，總時間成本為44。該揀選作業的最優方案如圖3所示。

經過改善，揀選成本由原來的109.6降低到44，降低了60%。

3 ?結論

本文在對在智慧物流的大環境下，利用先進的物流設備，燈光揀選和多層料架結合的方式，降低揀選人員的尋找，檢查等動作，從而達到降低成本的目的。在上述改善思想的前提下，建立了以最低揀選成本為目標的數學模型，采用遺傳算法與粒子群算法相結合的方式對其進行求解。驗證提出的方案是有效的合理的，大大降低了揀選成本。

參考文獻：

[1]聶劍平，凌四根，彭發恒，等.一種新型的揀選技術——Flowpicking[J].物流技術，2017，36（2）：51-55.

[2]李悅來.智能型自動分揀機的設計[J].機械設計，2011，28（7）：76-83.

[3]王柏松.名華與寶馬的協同管理on site模式應用研究[D].蘭州：蘭州理工大學，2013.

[4]Goldberg D E. Genetic Algorithm in search[J]. Optimization and Machine Learning， 1989， （11）： 3-26.

[5]Holand ?J.H. ?Adaptation ?in ?Natural ?and ?Artificial ?Systems ?[M].Massachusetts： MIT Press， 1975.

[6]馬永杰，云文霞.遺傳算法研究進展[J].計算機應用研究，2012，29（4）：1201-1206.

[7]J Kennedy， R C Eberhart. Particle Swarm Optimization[J]. Proc. IEEE International Conference on Neural NetworksUSA， IEEE Press. 1995，4： 1942-1948.

[8]DAS P K， BEHERA H ?S， PANIGRAHI B K. A ?hybridization of an improved partivle ?swarm optimization and gravitational search algorithm for multi-robot path planning[J]. Swarm and Evolutionary Computation. 2016，28： 11-28.

[9]陳曦，蔣加伏.免疫粒子群優化算法求解旅行商問題[J].計算機與數字工程，2006，34（6）：10-13.

[10]張鑫源，胡曉敏，林盈.遺傳算法和粒子群優化算法的性能對比分析[J].計算機科學與探索，2014，8（1）：91.