基于粒子群與遺傳算法的排序區(qū)揀選優(yōu)化研究

張巖

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

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.

關(guān)鍵詞：排序區(qū);燈光揀選;遺傳算法;粒子群算法;揀選路徑

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

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

0 ?引言

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

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

1 ?問題的提出

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

在對總裝車間排序區(qū)揀選作業(yè)進行研究后，發(fā)現(xiàn)以下幾種情況出現(xiàn)。

①現(xiàn)有揀選作業(yè)流程不合理，導(dǎo)致排序揀選作業(yè)時間較長，工人勞動效率較低，會出現(xiàn)滿足不了生產(chǎn)的情況。

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

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

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

③人工抄寫揀選信息，增加了錯揀的風(fēng)險。

揀選作業(yè)人員將領(lǐng)料單按照零件放置的位置進行排序，再將排序后的零件信息抄寫到手抄單上。在抄寫時，作業(yè)人員經(jīng)常出差錯，揀選信息抄寫錯誤，直接導(dǎo)致揀選作業(yè)人員揀選錯誤的零件，若沒有及時發(fā)現(xiàn)，有可能會造成停線等嚴重的后果。

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

④人工排序時，對現(xiàn)場熟悉成都要求高。

由于系統(tǒng)產(chǎn)生的訂單是由需求決定的，并無規(guī)律可言，故可將其看作是隨機產(chǎn)生的訂單。當(dāng)訂單產(chǎn)生并攢夠一定數(shù)量時，揀選人員將根據(jù)零件裝入拖車的順序?qū)㈩I(lǐng)料單進行排序，因此領(lǐng)料單上需要揀選的零件會分布在不同的貨架上。此時，揀選人員需要熟悉現(xiàn)場零件的擺放位置等，之后根據(jù)經(jīng)驗判斷所需要揀選的零件所在的位置再進行揀選作業(yè)。

若作業(yè)人員未接收良好的培訓(xùn)或?qū)ΜF(xiàn)場環(huán)境不夠了解，容易混淆零件，嚴重時甚至揀錯零件。

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

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

⑥揀選效率低，現(xiàn)場揀選作業(yè)人員多，人工成本增加。

2 ?建模與求解

針對M汽車企業(yè)生產(chǎn)過程中發(fā)現(xiàn)的上述問題，在符合物流中心布局以及工藝要求的條件下，應(yīng)用現(xiàn)存的技術(shù)，以最小的成本對揀選進行改進提升。

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

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

2.1 數(shù)學(xué)模型的構(gòu)建

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

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

2.2 算法的設(shè)計

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

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

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

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

具體的算法實現(xiàn)步驟如下：

①粒子編碼：對于揀選路徑的優(yōu)化求解問題，實現(xiàn)混合粒子群算法的關(guān)鍵環(huán)節(jié)就是對粒子進行編碼。將該問題的粒子編碼方式設(shè)置為整數(shù)編碼，每個粒子代表一個解，相當(dāng)于每個粒子是解空間的一個所有儲存位置信息的排列。

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

②適應(yīng)度函數(shù)：粒子的適應(yīng)度函數(shù) 代表行走完整個揀選路徑的長度。

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

粒子當(dāng)前值：[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]。

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

交叉后的個體：[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]。

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

④變異：本文在變異操作，是通過對粒子的內(nèi)部的隨機兩個基因進行互相交換位置的方式實現(xiàn)的。首先，在粒子中隨機選取兩個位置1和2，要對其采取變異操作，再將這兩個基因的位置互換，，針對上面的粒子，隨機選取兩個要產(chǎn)生變異的位置，第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]。

對所得到的個體保留了最優(yōu)個體，只有當(dāng)新得到的粒子的適應(yīng)度值比原來的粒子的適應(yīng)度值更優(yōu)的情況再更新粒子的當(dāng)前位置。

2.3 仿真驗證與結(jié)果分析

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

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

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

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

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

3 ?結(jié)論

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

參考文獻：

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

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

[3]王柏松.名華與寶馬的協(xié)同管理on site模式應(yīng)用研究[D].蘭州：蘭州理工大學(xué)，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].計算機應(yīng)用研究，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]陳曦，蔣加伏.免疫粒子群優(yōu)化算法求解旅行商問題[J].計算機與數(shù)字工程，2006，34（6）：10-13.

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