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

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

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

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

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

　　0引言

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

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

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

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

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

　　1.1問題的描述

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

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

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

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

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

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

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

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

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

　　2.3CA�睤P策略的子路徑策略

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

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

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

　　4結(jié)語

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

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

轉(zhuǎn)載請(qǐng)注明來自發(fā)表學(xué)術(shù)論文網(wǎng)：http:///dzlw/22145.html