某航空標準件企業成品庫揀貨路徑優化研究

李健

摘要：以航空標準件企業的產品庫揀貨問題為研究對象，建立了以揀貨總時間最小化為目標的路徑優化模型，并采用遺傳算法對路徑優化模型進行求解，通過實際案例應用與傳統的穿越式揀貨策略相對比，驗證了模型的有效性。

Abstract： Taking the picking problem of product warehouse in aeronautical standard parts enterprises as the research object， a path optimization model aiming at minimizing the total picking time is established. Based on the characteristics of product warehouse in aeronautical standard parts enterprises， the practical case is compared with the traditional traversing picking strategy. The validity of the model is verified.

關鍵詞：航空標準件;揀貨路徑優化;成品庫

Key words： aerospace standard parts;order picking routing optimization;production warehouse

0? 引言

航空標準件企業屬于多品種、混批量的的制造型企業，近年來，隨著航空工業的快速發展，航空標準件產品的數量和種類日益激增，企業傳統的揀貨作業模式已無法滿足市場需求，導致企業成品庫存周轉效率低下，揀貨作業是倉儲管理中十分重要的一個環節，據統計，揀貨作業所耗費的時間約占整個倉儲作業所用時間的60%[1]，而揀貨作業大量的時間耗費在貨物的尋找過程中，因此，尋求最優的揀貨路徑，可以加快產品周轉效率，對于進一步提升公司的快速響應能力具有重要的意義。

1959年，學者Dantzig G B和Ramser J H首次提出路徑優化問題[2]。隨著物流活動的日益增多，該類問題日益受到學者們的重視，學者Felix T.S.Chan等從倉儲布局、存儲策略和訂單分配等三個角度出發，通過對于不同種組合下的策略進行仿真實驗，從而得出有效的組合策略[3]。J Renaud等將儲位分配與路徑優化相結合，結合產品的特點合理安排儲位和揀選路徑，有效的減少了揀選距離[4]。Kulak O等將訂單分批問題與路徑優化問題相結合，并采用改進的禁忌搜索算法來尋求最佳的揀貨路徑[5]。國內學者李軍將偏離度思想引入到路徑優化方面，并與傳統的穿越式策略和S型啟發式算法通過仿真進行對比，驗證模型的有效性[6]。劉建勝針對雙區型倉庫中揀貨的特點，采用蟻群算法優化揀貨路徑，并與傳統的穿越策略和S型啟發式算法進行了比較，驗證了算法的適用性[7]。

綜上可知，學者們在揀貨路徑優化領域的研究中大多以最短揀貨距離為優化目標，在計算最短距離時僅考慮兩個貨位點間的距離最短，并未將倉庫入口到第一個揀貨點的距離和最后一個揀貨點到倉庫出口的距離引入揀貨模型，并不能真實的反應揀貨實際距離;另一方面，以往的揀貨模型僅考慮揀貨的路徑最短，并未將揀貨過程中的揀貨時間并未計算在內。因此，本文綜合考慮揀貨時間和揀貨路徑時間，以揀貨總時間最短建立優化模型，從而更真實的反映整個揀貨過程。

1? 模型建立

1.1 問題描述

航空標準件企業成品根據產品類型分區管理，揀貨單根據產品類型分派到各揀貨員手中，在揀貨過程中不存在跨區揀貨的現象，因此，本文所研究的倉庫類型為單區型倉庫，揀貨路徑優化模型可以用圖論描述為：成品倉庫可視作一組網絡，一個周期內某揀選單中有多個產品待揀選，即多個頂點構成的頂點集N，A為各頂點間的連接所構成的邊集合，C=[dij]為距離矩陣，出入口為同一點，要求一名揀選人員或揀選設備進行揀選，從倉庫出入口出發，完成該次揀選任務并返回到出入口構成閉合回路，在遍歷每個待揀貨點（每個點只經過一次）的同時保證總揀貨時間最短。

1.2 模型假設

①揀貨方式：航空標準件企業目前主要采用的是人到貨的揀貨模式（Picker to Part）、根據訂單揀選系統生成的揀貨單進行揀貨，空閑等待的時間可以忽略不計。

②行走規則：每個揀貨員的分管區域可視為單區型倉庫，揀貨員可以橫向和縱向巷道行走。

③存儲狀態：每個貨架的規格相同，即每個庫位的大小、承載力均相同。本文研究的產品每個圖號代表一類產品，且產品體積較小，因此每個庫位可以完全存儲一個圖號的產品，每個庫位僅有一個圖號的產品。

④人工式揀貨的倉庫條件下，貨架高度與揀貨人員身高相近，忽略配貨區貨架的垂直高度，揀貨人員在揀選作業中垂直方向上的位移可忽略不計。將貨架視為單層貨架。

⑤揀貨執行過程中不存在缺貨情況，即補貨時間可視為瞬時的。

⑥每份揀貨單的容量不能超過揀貨員的最大揀貨量。

1.3 變量描述與符號說明

1.3.1 倉庫相關量描述

1.4 模型構建

1.4.1 揀貨路徑模型構建

2? 模型求解

本文所研究的問題屬于問題，采用遺傳算法對模型進行求解，遺傳算法的具體求解步驟如圖3所示。

①確定揀貨單中的待揀貨產品坐標構成問題參數集。

②設定編碼規則。揀選單中的待揀貨貨位總計n個，本文采用十進制編碼規則對問題參數集進行編碼，采用自然數序列{1，2，…，n}表示每個待揀貨位的編號（每個貨位編號唯一），由此構成一定序列的染色體。

③產生初始化種群。根據模型規則隨機求解出一組50個包含計n個待揀貨位的初始方案。

④適應度評估。適應度函數是倉儲揀貨人員遍歷所有的待揀庫位一次所行走的所用的時間。揀貨路徑的優化問題是以揀貨總時間最小化為目標，可建立適應度函數評價求解結果與最優情景的接近程度，即找出適應度最大的染色體。

⑤選擇操作。選擇操作主要是指通過個體的適應度的優劣程度來決定個體的淘汰或者遺傳，通過聯賽選擇法從種群中隨機選擇n個個體（種群中個體被選擇的概率相同），并計算每個個體的適應度值，比較其適應度大小，選擇適應度最大的個體進入下一代的種群。迭代多次，直到新的種群規模達到原來的種群規模。

⑥交叉操作。采用段交叉法以概率隨機地交換染色體群中的兩個個體的某些片段產生新的個體。

⑦變異操作。變異操作對遺傳算法的局部搜索能力進行優化，從而維持遺傳算法的群體的多樣性，同時防止早熟現象的發生。采用對換變異操作。以pm的變異概率從當前代的種群中選擇進行變異的個體，并隨機選擇兩個不同的點，對這兩個點的編號進行交換從而得到新的個體。

⑧是否滿足停止準則。對形成的可行解的適應度進行判斷，如果其適應度不再上升或者達到設定的相應的閥值，則結束迭代計算;否則繼續計算或者改進遺傳策略后再進行計算。

⑨輸出最優解P（t+n）。在使用遺傳算法進行n次迭代后，若滿足目標最小化需求，則停止運算，輸出最優揀貨路徑。

3? 實例分析

H公司是我國航空工業集團下屬的一家航空標準件制造三級供應商，隨機選取某段時間內到達的1組揀貨單，產品信息如表1所示，其中L1=0.5m，L2=0.5m，L3=0.5m，L4=1.75m，tm=3.4m，v=1.2m/s。

3.1 原有揀貨模式揀貨總時間

按訂單順序進行揀選時，每批揀選單按公司原有的穿越式策略進行揀貨，設總揀選時間為T′，可求得揀貨總時間為T′=2309.7s。

3.2 改進揀貨模式揀貨總時間

設置遺傳算法種群規模為50，交叉概率為pc=0.9，變異概率為pm=0.1，迭代次數為500次，在VS2015軟件中，通過C#編程求解可得，揀貨作業順序為P0-P1-P2-P7-P9-P8-P11-P10-P12-P13-P16-P15-P14-P20-P19-P18-P17-P4-P5-P6-P3-P0，設總揀選時間為，揀貨總時間為T=2275.5s。

如圖4所示，對比公司傳統的揀貨模式，可以節省揀貨總時間，提高揀貨效率。

4? 總結

針對航空標準件企業的單區型倉庫，以揀貨總時間最短為優化目標，設計了路徑優化模型，并采用GA算法通過企業實際案例進行求解，對比航空標準件企業傳統的穿越式揀貨模式，可以有效節省揀貨時間，提高揀貨效率，可為同類型制造企業規劃揀貨路徑提供相應的決策參考。

參考文獻：

[1]王轉，陳國全.配送中心系統規劃[M].北京：中國物資出版社，2003：148.

[2]Dantzig G B， Ramser J H. The Truck Dispatching Problem[J]. Management Science， 1959， 6（1）：80-91.

[3]Chan F T S， Chan H K . Improving the productivity of order picking of a manual-pick and multi-level rack distribution warehouse through the implementation of class-based storage[J]. Expert Systems with Applications， 2011， 38（3）：2686-2700.

[4] Renaud J ， Ruiz A . Improving product location and order picking activities in a distribution centre[J]. Journal of the Operational Research Society， 2008， 59（12）：1603-1613.

[5]Kulak O ， Sahin Y ， Taner M E . Joint order batching and picker routing in single and multiple-cross-aisle warehouses using cluster-based tabu search algorithms[J]. Flexible Services and Manufacturing Journal， 2012， 24（1）：52-80.

[6]李軍，魏玲艷，李翔宇.基于偏離度的倉儲中心揀貨路徑優化研究[J].遼東學院學報（社會科學版），2018，20（2）：29-37.

[7]劉建勝，熊峰，陳景坤，等.基于蟻群算法的雙分區倉庫揀貨路徑的優化[J].高技術通訊，2017，27（1）：72-80.