基于聚類和動態規劃的組合路徑策略

所屬分類：電子論文閱讀次時間：2020-03-19 04:53

本文摘要：摘要：為提高電商倉庫的揀貨作業效率，本文提出了基于聚類和動態規劃的組合路徑策略，實現了生成路徑消耗時間和路徑長度之間的平衡，并將這一策略成功地應用到多區型倉庫。該策略分四步：首先，根據待揀儲位分布特征，運用聚類分析法對其進行分類;然后，以各

　　摘要：為提高電商倉庫的揀貨作業效率，本文提出了基于聚類和動態規劃的組合路徑策略，實現了生成路徑消耗時間和路徑長度之間的平衡，并將這一策略成功地應用到多區型倉庫。該策略分四步：首先，根據待揀儲位分布特征，運用聚類分析法對其進行分類;然后，以各類的首末儲位作為節點，運用動態規劃法對已得分類進行排序，得到相應的類序;其次，得到各類內部路徑;最后，依次揀取待揀商品，并返回出發點完成揀貨作業。在提出新的路徑策略后，通過仿真方法將新策略與三種傳統路徑策略(穿越策略、最大間隙策略和混合策略)和一種優質算法(蟻群算法)進行了對比分析，結果表明：該策略具備良好的適用性和實用性。

　　關鍵詞：揀貨路徑;聚類分析;動態規劃

電商倉庫

　　電商論文范文：電商售后貨物退換設計流程和步驟

　　這篇電子商務論文發表了電商售后貨物退換設計流程和步驟，隨著電子商務經濟模式不斷發展和完善，網絡購物逐漸成為人們日常消費的主要方式之一。論文分析了電商模式下貨物退換的流程和步驟，繪制了電商模式下貨物退換的流程設計圖。

　　0引言

　　2018年全國郵政管理工作會議公布的數據顯示，2017年，快遞業務量完成401億件，同比增長28%。中國電子商務研究中心物流行業分析師姚建芳指出，這意味著國內快遞包裹分發已經進入日均一億件時代。面對發展如此迅猛的電子商務，提高電商訂單處理效率勢在必行。相關研究表明[1～3]，作為訂單處理核心環節的揀貨作業在倉庫作業中耗時最長、耗力最多，成本比例高達65%。揀貨作業由行走、尋找、揀取、放置和其他五部分組成。其中行走用時比例高達50%，由此可見，行走距離會直接影響到揀貨員的揀貨效率，是提高揀貨效率首要改進目標。要想減小行走距離就要對揀貨路徑進行優化。揀貨路徑優化問題作為一種組合優化問題，當規模較小時，可通過精確算法求解，但隨著規模的增大，求解的復雜度將以指數級別增長，這時就需借助啟發式算法得到滿意解[4，5]。

　　關于倉庫揀貨路徑方法的研究主要有啟發式路徑策略、數學最優化方法和智能優化算法。傳統的啟發式路徑策略有穿越策略(Sshape)、最大間隙策略(LargestGap)和混合策略(Combined)[6～9]。穿越策略的引導策略為：揀貨員以S形路線穿越所有包含待揀商品的巷道(跳過不包含待揀商品的巷道)進行揀貨作業，這一策略僅適用揀貨密度較大的情況;最大間隙策略作為返回策略的一種改進策略，是指揀貨員以避開兩相鄰揀貨位之間、每個揀貨位與相應橫向通道之間的距離最大的間隙的方式進行揀貨作業;混合路徑策略是指通過將穿越策略與返回策略相結合，使兩相鄰巷道中最遠的待揀貨位置之間的距離最小化的方式進行揀貨作業。

　　只有當揀貨密度較大時，穿越策略優于最大間隙策略;當揀貨密度較小時，最大間隙策略優于穿越策略;而總體上來說混合策略要優于其他兩種策略。應用于倉庫揀貨路徑研究的數學最優化方法主要是動態規劃法[10，11]，當揀貨規模較小時，該方法可以得到最佳的揀貨路徑，但隨著揀貨規模的增加，方法的復雜度將呈現指數級的增加，而且其適用的倉庫布局類型是有限的。受到人類智能、生物群體社會性或自然現象規律的啟發，人們發明了很多智能優化算法來解決復雜的優化問題。應用于倉庫揀貨路徑研究的智能優化算法[12～14]主要包括模擬退火算法(SimulatedAnnealing，SA)、遺傳算法(GeneticAlgorithm，GA)、蟻群算法(AntColonyOptimization，ACO)以及針對這些算法的改進算法。這些智能優化算法通過反復迭代，在滿足收斂條件時，得到較優的揀貨路徑，這些迭代必然要以消耗一定的資源為代價的，且隨著揀貨規模的增大，智能優化算法消耗的資源和時間是難以忍受的。

　　針對傳統策略適用范圍受限，且有時與最佳揀貨路徑差距較大，數學優化算法和智能優化算法適用的揀貨規模受限的問題，本文提出了一種新的揀貨路徑策略：基于聚類分析[15～18]和動態規劃[19，20]的組合路徑策略(CADP)，該策略首先根據待揀儲位分布特征，對其進行分類;然后運用動態規劃的方法對各類進行排序，得到相應的類序;接著確定各類內部路徑;最后通過類序連接各子路徑找到一個較優的啟發式路徑，將規模較大的揀貨路徑問題，簡化成幾個較小的子路徑問題，達到了化繁為簡的效果。

　　1問題的描述與模型的建立

　　1.1問題的描述

　　本文以人至物平面倉庫作為研究背景，重點討論雙區型倉庫和三區型倉庫的揀貨路徑問題。倉庫由若干條平行的巷道構成，巷道兩側為平行排列貨架，集貨區位于整個分揀區的左下角。包含三條橫向通道的為雙區型倉庫，包含四條橫向通道的為三區型倉庫。其中，每個區塊都有相應的前端橫向通道和末端橫向通道，以距離depot較近的橫向通道作為前端橫向通道，距離depot遠的橫向通道為末端橫向通道。

　　depot是倉庫的進出口，為簡化計算默認其位于第一條橫向通道和第一條巷道中心線的交匯處。以離depot最近的區塊為第1區，由近及遠，區塊編號依次遞增。其中巷道寬度為D1=1m，橫向通道寬度為D2=2m。D3=3m為兩條相鄰巷道之間的寬度。每一方格代表一個儲位(儲位長度和寬度均為1m)，且有對應的編號(B，A，S，R)，其中B(正整數，且Bmin=2，Bmax=3)表示該儲位所在的區塊編號，A表示所在的巷道編號(Amin=1為第一條巷道編號，Amax為最大巷道編號)，S表示位于該巷道的哪一側(S=0表示左側，S=1表示右側)，R表示當前區塊的行數編號(Rmin=1為第一行編號，Rmax為最大行數編號)。

　　揀貨員從depot出發依次揀取待揀儲位上的商品，返回至depot完成當前的揀貨任務。可以看出揀貨路徑問題是特殊的旅行商問題，其特殊之處在于當兩待揀儲位位于不同巷道時，揀貨員在揀完當前儲位后，需離開當前巷道，并通過相應的橫向通道進入下一個待揀儲位所在的巷道。以下就倉庫中任意兩個儲位之間的距離計算進行說明：文中計算的儲位之間、儲位與巷道和儲位與橫向通道的距離均為中心線之間的距離。

　　2基于聚類和動態規劃的組合路徑策略

　　本文提出了基于聚類和動態規劃的組合路徑策略：首先，根據待揀儲位的分布特征，對其進行聚類分析;其次，運用動態規劃法得到相應的類序;接著，確定各類的子路徑;最后，按照類序連接對應的子路徑得到最終的啟發式路徑。

　　2.1聚類分析法在路徑優化中的應用

　　以待揀儲位間的兩兩距離為依據，對待揀儲位進行聚類分析，將一個復雜的旅行商問題分解成幾個簡單路徑問題。前期通過大量探索試驗可知：當聚類數量p在[9，12]范圍內取值時，聚類效果最佳。文本借助MATLAB編程，運用層次聚類分析法，對待揀儲位進行聚類，具體的實現步驟如下：(1)首先計算兩兩坐標的最短距離cij，繼而生成相應的距離矩陣C。(2)運用linkage函數(內部為最短距離算法)生成具有層次結構的聚類樹Z。Z=Iinkage(C)(6)

　　2.2動態規劃法在路徑優化中的應用

　　由于參與動態規劃的節點個數受待揀儲位數和聚類分析影響，此處以q(pq2p)作為動態規劃節點數進行討論。通過引入動態規劃算法，可以將一個包含|N|個節點的旅行商問題轉化成一個包含q個節點的動態規劃問題和p個小型路徑問題。必須注意兩點：第一，當某類包含多個待揀儲位時，其首末待揀儲位都將作為動態規劃節點，此時，為保證聚類結果不被破壞，需將這兩節點的距離設為d(0

　　2.3CADP策略的子路徑策略

　　得到相應的類序后，需進一步確定各類相應的子路徑，下面就子路徑策略進行介紹說明：以當前類的首個待揀儲位所在巷道為當前巷道，最后一個待揀儲位所在巷道為終止巷道。從首個待揀儲位出發，依次揀取當前巷道的其余未揀儲位，當前巷道揀取完畢后，從下一巷道中最小行編號和最大行編號待揀儲位中選擇一個與當前儲位距離最短的一個作為下一個待揀儲位，在揀取該儲位后，依次揀取該巷道其余未揀儲位(當揀取的是最小行編號的儲位時，按從小到大的順序;當選取的是最大行編號的儲位時，按從大到小的順序)，按照以上規則揀取類內所有待揀儲位。

　　3應用實例分析

　　由于揀貨員使用的推車容量(或載重量)有限，本文以一單一車[21]的方式揀取處理后的揀貨單，即揀貨單中的全部商品可以由一輛推車往返一次從倉庫中全部取走，不會出現超過推車的最大容量(或載重量)的情況。本文就雙區型倉庫和三區型倉庫揀貨路徑問題進行研究，針對不同的倉庫隨機生成包括20、25、30、35和40個待揀儲位揀貨單5組(每組包含100個揀貨單)，每組訂單分別運用Sshape策略、LargestGap策略、Combined策略、CADP策略和ACO算法生成路徑，并對路徑長度和生成路徑所需時間進行比較分析。

　　4結語

　　揀貨作業是訂單處理作業的核心環節，也是倉庫作業中耗時耗力最多的作業，提高揀貨作業效率，優化揀貨路徑可以達到降低物流配送中心運營成本，提高物流作業效率和提高客戶滿意度的效果。一個良好的揀貨路徑策略不僅要考慮生成的路徑長度，而且還要考慮生成路徑消耗的時間。本文提出的基于聚類和動態規劃的組合路徑策略(CADP)，通過聚類分析法將一個復雜的旅行商問題轉化成幾個相對簡單的子路徑問題，通過動態規劃以最短的距離將這些子問題連接，實現了化繁為簡的效果。

　　通過大量實驗，可以得出結論：第一，在時間消耗很少的情況下，CADP策略生成的揀貨路徑長度明顯優于以往的傳統路徑長度;在路徑長度差距較小的情況下，CADP路徑的生成時間明顯短于ACO算法路徑的生成時間。CADP策略實現了生成揀貨路徑所需時間與優化路徑長度之間的平衡;第二，本文將CADP策略應用于三區型倉庫，試驗結果表明，該策略在在三區型倉庫具有良好的適用性，擴大了以往以二區型倉庫為主的適用環境。同時，本文對于揀貨路徑問題的研究還有許多值得繼續研究的地方，接下來的研究主要從以下兩個方向拓展：(1)如何將CADP策略與現代化的信息化技術相結合，實現在生成揀貨路徑后快速識別并揀取待揀商品，進一步提高揀貨速度的目標。(2)關于CADP策略中聚類數量的進一步探究和對子路徑策略的進一步優化。