基于聚類和動態(tài)規(guī)劃的組合路徑策略

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

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

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

　　關(guān)鍵詞：揀貨路徑;聚類分析;動態(tài)規(guī)劃

電商倉庫

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

　　這篇電子商務(wù)論文發(fā)表了電商售后貨物退換設(shè)計流程和步驟，隨著電子商務(wù)經(jīng)濟模式不斷發(fā)展和完善，網(wǎng)絡(luò)購物逐漸成為人們?nèi)粘ＯM的主要方式之一。論文分析了電商模式下貨物退換的流程和步驟，繪制了電商模式下貨物退換的流程設(shè)計圖。

　　0引言

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

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

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

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

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

　　1.1問題的描述

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

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

　　揀貨員從depot出發(fā)依次揀取待揀儲位上的商品，返回至depot完成當前的揀貨任務(wù)�？梢钥闯鰭浡窂絾栴}是特殊的旅行商問題，其特殊之處在于當兩待揀儲位位于不同巷道時，揀貨員在揀完當前儲位后，需離開當前巷道，并通過相應(yīng)的橫向通道進入下一個待揀儲位所在的巷道。以下就倉庫中任意兩個儲位之間的距離計算進行說明：文中計算的儲位之間、儲位與巷道和儲位與橫向通道的距離均為中心線之間的距離。

　　2基于聚類和動態(tài)規(guī)劃的組合路徑策略

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

　　2.1聚類分析法在路徑優(yōu)化中的應(yīng)用

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

　　2.2動態(tài)規(guī)劃法在路徑優(yōu)化中的應(yīng)用

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

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

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

　　3應(yīng)用實例分析

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

　　4結(jié)語

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

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