芒果app成年版下载污
    歡迎進入上海陽合供應鏈管理有限公司!
  •  13472705338 

  • 基於PLC的倉庫恒溫控製係統設計與探究
  • 船廠倉庫建築設計初探
  • 多區型倉庫多複核台場景的揀貨路徑優化研究
  • 基於元數據的物資倉庫管理軟件設計方法
  • 《倉庫管理實操從入門到精通》
  • 淺談水利工程倉庫管理精細化智慧化
  • 最新動態

    當前位置:首頁 >> 走進陽合 >> 新聞資訊 >>   資訊詳細新聞資訊

    多區型倉庫多複核台場景的揀貨路徑優化研究

      信息來源:   發布時間:2021-08-07  點擊數:

    隨著電子商務的蓬勃發展,海量、個性化已成為當今網絡購物訂單的主要特點。而倉庫作為各類商品重要的中轉站之一,承擔著貨物入庫、存儲、管理、揀貨、派出等一係列作業過程。其中,揀貨作業過程是倉庫作業的核心環節。數據顯示,就配送中心等勞動密集型倉庫來說,與揀貨直接相關的人力占50%以上,貨物揀選時間大概占整個倉庫作業的30%∼40%,而配送中心總物流成本大約60%用於揀貨[1]。因此,優化揀貨路徑、縮短揀貨時間不僅能夠更快地完成訂單商品出庫,而且對於降低倉儲成本、提高配送中心的運行效率具有極其重要的意義。

    在倉庫貨物的擺放布局方麵,已有研究表明,雙區型倉庫比單區型倉庫在揀貨效率上具有明顯提升[2,3]。隨著倉儲係統的創新發展,出現了V型布局和魚骨型布局等新型倉儲布局方式,且在單命令模式下,魚骨型倉儲布局的揀貨效率相對於普通倉庫提升約20%[4]。現實應用中的倉庫大多為雙區型或多區型[5],特別是對於規模較大的配送中心,多區型倉庫布局已成為主要模式。基於此,結合京東物流實際布局模式,本文選擇多區型倉庫作為研究對象,並設計了相應的路徑優化算法。

    在路徑優化方麵,基於遺傳算法、蟻群算法、模擬退火等智能算法的改進和混合算法已被廣泛應用於大型倉儲揀選係統的路徑優化策略[6,7,8]。文獻[9]結合傳統啟發式優化算法和動態規劃思想,提出了適用於雙區型倉庫的揀選路徑優化算法;文獻[10]基於禁忌搜索算法提出了一種在不同場景下,適用於倉庫同時優化貨位分配及揀貨路徑的方法,表明算法能較好地優化貨位分配與揀貨路徑;文獻[11]提出了基於混合遺傳模擬退火算法,且認為該算法在靜態揀貨路徑優化基礎上,可以進一步提升倉庫揀貨效率,且揀貨單越多,算法優化效果越明顯。

    此外,部分學者嚐試從訂單分配和路徑規劃兩個層次對揀貨作業進行優化。文獻[12]采用動態的揀貨策略,在揀貨周期中進行揀貨單分配和路徑優化;文獻[13]針對不同揀貨單分配方式下的揀貨路徑規劃問題,采用S型啟發算法和遺傳算法進行優化,結果顯示將揀貨單分批策略和遺傳算法的路徑規劃相結合能夠得到更為合理的揀貨作業規劃;文獻[14]針對上述揀貨單分配和揀貨路徑分布優化難以獲得最優解的缺陷,提出了一種基於嵌套遺傳算法的揀貨單分批和路徑優化的聯合揀貨策略,采用外層優化揀貨單分批結果、內層優化揀貨路徑相結合的方式,為配送中心揀選係統優化提供依據。

    然而,目前對於路徑優化的研究主要集中在單出入口或單複核台,即揀貨員從該位置出發,揀貨完成後需返回起始點。但對於大型配送中心來說,往往設置有多個複核台、出入口進行貨物的複核與打包工作,以盡可能地提升訂單貨物出庫的效率。於是,結合京東物流倉儲係統實際情況,本文提出替換複核台以解決多複核台起始點與終點不確定的複雜場景,並在此基礎上給出多揀貨員、多複核台情況下的倉儲揀貨路徑優化策略,以解決大規模複雜場景下的揀貨作業。

    本文引用了圖論相關知識,提出了替換複核台的概念,並解決多複核台場景下因始終點不確定而導致的遍曆搜索困難,根據實際情況給出在多複核台多揀貨員情況下多揀貨單的路徑優化與合理分配的動態調整策略。研究表明,本文給出的算法在同等條件下相比其他算法計算效率更高、揀貨路徑更短、路徑規劃更準確,滿足了大規模揀貨要求,也為多複核台的後續研究奠定了基礎。

    1 問題描述

    1.1 多區型倉庫簡介

    結合京東物流倉庫實際情況,本文所考慮的大規模多區型倉庫由5條平行的橫向通道和26條縱向巷道構成;每條通道的寬度相等,每條巷道的寬度也相等。倉庫共有4排貨架,每排25組貨架,每組兩個貨架,所有貨架均采用背靠背模式;每個貨架包含15個貨格,共3 000個儲位。倉庫共有13個複核台,其中8個複核台(FH01-FH08)設置在倉庫通道1南側、另外5個複核台(FH09-FH13)設置在巷道1西側,倉儲係統會根據實際情況選擇開啟部分或全部複核台以滿足揀貨單揀貨效率的最大化,具體倉庫布局如圖1所示。

    圖1 多區型倉庫平麵示意圖

    圖1 多區型倉庫平麵示意圖   下載原圖

    Figure 1 Multi-zone warehouse plan diagram

    1.2 參數設置

    關於貨架與貨格的符號說明如下:

    1)xi,yi分別為第i個貨格左下角的坐標信息,i=1,2,···,3 000。

    2)Xj,Yj分別為第j個複核台左下角的坐標信息,j=1,2,···,13。

    3)Di1i2,Dij,Dj1j2分別為貨格i1與貨格i2之間、貨格i與複核台j之間、複核台j1與複核台j2之間的距離。

    4)ri,ci分別為第i個貨格所在貨架緊鄰巷道的行數與列數;因多區型倉庫包含4行貨架、26列巷道,故ri=1,2,3,4;ci=1,2,···,26。

    5)ai,bi分別為第i個貨格所處的貨櫃號與貨格號,ai=1,2,···,200;bi=1,2,···,15。

    6)l1,w1分別為貨格的長度與寬度,l2,w2分別為複核台的長度與寬度,lroad,wroad分別為縱向巷道與橫向通道的寬度。

    關於揀貨單的符號說明如下:

    1)T表示所有揀貨單的數量,編號t=1,2,···,T;

    2)Nt為第t個揀貨單待揀選商品總數,nt為第t個揀貨單中的第n個商品,nt=1,2,···,Nt;

    3)Hnt為第t個揀貨單中第n個貨物所在的貨格編號,其中包含貨櫃號a和貨格號b。

    關於揀貨員的符號說明如下:

    1)V為揀貨人員的平均行走速度;

    2)T為揀貨人員揀取每個貨物商品所消耗的平均時間;

    3)d為揀貨員繞障礙物折線行走時橫向及豎向偏移量。

    1.3 模型假設

    1)揀貨員均按照揀貨單揀取貨物,到達複核台後揀貨員無需等待,繼續開始下一個揀貨單的揀貨流程;

    2)貨架和複核台為障礙物,不可通行,其餘位置均可通行;

    3)商品擺放在貨格中,且每個貨格最多擺放一種商品,一件商品隻能存放在一個貨格;

    4)當開啟的複核台數量為多個時,揀貨員開始和結束複核台可以不一致;

    5)揀貨員隻有在完成一個揀貨單的揀選作業後,才能進行下一揀貨單貨物的揀選,即不存在跨單取貨的情況出現。

    2 模型準備——元素間距離求解

    基於上述假設,下麵詳細說明如何求解貨格之間、貨格與複核台之間、複核台之間各元素的距離。

    2.1 構建坐標偏移矩陣C

    考慮到貨格坐標表示為該貨格左下角點的坐標信息,與揀貨員在該貨格進行貨物揀取時所處坐標存在差異,且同一組中左右兩貨架的計算方式不同。因此,為了避免對該情況進行複雜的分類討論,本文在計算貨格距離之前,構建了各貨格坐標的偏移矩陣C(3013,2),將坐標值換算到該貨格緊鄰的巷道中心點位置,即揀貨員在取貨時所處位置的外偏移量,得到的左右兩貨架坐標偏移的計算公式為

     


    圖2 貨格坐標偏移示意圖

    圖2 貨格坐標偏移示意圖   下載原圖

    Figure 2 Schematic diagram of coordinates offsets of goods grid

    此外,複核台坐標偏移的計算公式為

     


    2.2 各貨格之間距離計算

    考慮到倉庫貨格分布的實際情況,結合貨格緊鄰巷道的行列號,可以將貨格距離的計算分成同一排同一巷道、同一排不同巷道、不同排同一巷道、不同排不同巷道4種情況。下列分別對上述4種情況進行分類討論:

    情況1兩貨格位於同一排同一巷道,即ri1=ri2且ci1=ci2

     


    情況2兩貨格位於同一排不同巷道,即時,揀貨員最短路徑的選取按照其所處貨格的位置決定;即當兩件貨物均處在貨架偏上方時,選擇從上方巷道行走距離較近;反之,揀貨員應選擇下方。

     


    圖3 同一排不同巷道討論示意圖

    圖3 同一排不同巷道討論示意圖   下載原圖

    Figure 3 Schematic diagram of the same row but different columns

    在圖3同一排不同巷道的討論示意圖中,對偏移量d也有了直觀的解釋:揀貨員在貨格之間行走移動時默認貨格為障礙物,揀貨員需要與其保持一定的距離,本文將該距離定義為偏移量d,為揀貨員繞障礙物折線行走時橫向及豎向偏移量,且將橫向偏移量與豎向偏移量默認為相等的值。

    情況3兩貨格位於不同排同一巷道,即

     


    情況4兩貨格位於不同排不同巷道,即

     


    2.3 貨格到複核台之間距離

    基於對倉庫貨架布局情況分析,定義貨格與複核台距離為貨格中點到複核台最近一條邊中點的距離;即當複核台處於通道1南側時(FH01∼FH08),從複核台上方進入距離最短。同理,對於巷道1西側的複核台(FH09∼FH13),最短距離與揀貨員所處的位置有關。

     


    此外,還需要考慮巷道在第1列,即處在複核台旁的特殊情況

     


    2.4 複核台之間距離計算

    兩個複核台之間距離的計算應該分為在同一排(均在左側/均在下方)以及不在同一側兩種情況。

    情況1複核台處於貨架同一側時

     


    情況2複核台處於貨架不同側時

     


    3 多複核台下揀貨路徑優化策略

    3.1 揀貨路徑優化策略

    傳統的單出口、單複核台揀貨路徑優化往往是起始點與終點均固定,針對此情況,文獻[15,16]基於TSP對倉庫的揀貨路徑進行建模,並利用模擬退火、蟻群算法和禁忌搜索等諸多算法對模型進行求解,得到了較為理想的揀貨路徑。

    與上述不同,多複核台的路徑優化往往是始終點均未固定的情況。假設倉庫開設n個複核台,倘若對所有複核台進行最短路徑遍曆,則單就複核台選擇的複雜度就達到O(n2),再加上智能優化算法本身,其計算效率會隨著複核台數量增多而急劇降低。基於此,本文將引入替換複核台的概念,將始終點未固定的多複核台路徑規劃問題轉化為已知起點與終點的揀貨路徑優化問題;並在此基礎上,給出針對多揀貨單的合理分配策略,以使揀貨員工作時間最短。

    3.1.1 模型準備——替換複核台的引入

    下列先以一個簡單的圖論問題為例引入替換終點的概念。

    在左圖中以A為起點,途徑B1、B2兩點,以C1或C2為終點的路徑有兩種,分別為A-B1-B2-C2、A-B2-B1-C1。注意到當最後一個途徑點為B1時會選擇更近的C1為終點,當最後一個途徑點為B2時會選擇更近的C2為終點,故可引入一個替換終點C,使得d(B1,C)=d(B1,C1),d(B2,C)=d(B2,C2),即可確定一個終點C,如上右圖所示。從而問題即被轉化為以A為起點,途徑B1、B2兩點,以C為終點的最短路徑規劃問題。

    圖4 替換終點的引入示意圖

    圖4 替換終點的引入示意圖   下載原圖

    Figure 4 Schematic diagram of introduction of replacement endpoints

    上文的例子是替換終點,而替換起點的方法也是一樣。下文將替換終點複核台和替換起始複核台統稱為替換複核台。

    本文通過引入替換複核台來解決終點待固定的路徑優化問題。假設該揀貨單中含有的貨格數為Nt,以Hi(i=1,···,Nt)表示這些貨格點,起始點與終點均可在所有複核台(FH01∼FH13)中任意選擇。

    為了得到最短的路線,引入替換複核台FH*,使得對於任意i=1,···,N滿足

     


    圖5中距離下標im,in表示N個貨格中任意兩個貨格。

    於是得到含FH*、Hi(i=1,···,N)、FH*共N+2個點在內的無向帶權圖,權值即為兩點之間的距離,從而將問題轉化為求解以已知始終點、途徑Hi的最小距離問題。

    圖5 替換複核台下最短路徑轉化示意圖

    圖5 替換複核台下最短路徑轉化示意圖   下載原圖

    Figure 5 Schematic diagram of the shortest path transformation under replacement review station

    3.1.2 倉內揀貨最短路徑模型

    優化目標函數如下所述。

    假設一個揀貨單中含有的貨格數為N,規定用0表示揀貨員開始揀貨的起點,該點通常是某一個複核台;用N+1表示完成揀貨後所到達進行複核/出庫的終點。

    揀貨路徑優化問題的目標是使揀貨完成的總距離D最小[17]

     


    式中,D(i,j)為任意兩個元素之間的距離;xij表示揀貨所經過的路徑,且

     


    考慮到倉庫的實際情況,該問題中約束條件主要包含路徑約束、貨格約束。構建模型時,應保證在揀貨過程中揀貨單上的每個點訪問數有且僅有1次,即貨格約束條件可以表示如下:

    (1)對於i=0,1,2,···,N+1來說,,即對於替換複核台FH*與中間所經過的每個貨格均會有下一個元素與之相連,其出度為1;

    (2)對於j=0,1,2,···,N+1來說,,即對於中間經過的貨格與替換複核台FH*均會有上一個元素與之相連,其入度為1。

    3.1.3 求解算法

    通過揀貨路徑優化策略,可以將多複核台路徑求解轉化為已知起點與終點的揀貨路徑優化問題。該問題為NP-hard問題,目前解決這類問題采用最多的是啟發式算法、遺傳算法、蟻群算法等一係列智能算法[15,16]。遺傳算法基於“優勝劣汰”思想的群體遺傳操作來實現優化;在求解較為複雜的組合優化問題時,相對常規的優化算法通常能夠更好地優化結果。因此,本文基於遺傳算法進行路徑規劃策略求解。

    3.2 多揀貨單合理分配策略

    基於上述揀貨單路徑優化策略,可以得到各揀貨單最優揀貨路徑;為了盡可能減少各揀貨員行走路程,應優先將具有相同起止點的揀貨單進行拚接。考慮到所構建的圖結構為無向帶權圖,即可通過調整各揀貨單最短路徑的方向或者端點的選擇盡可能使得揀貨單之間首尾相連,即在完成一單揀貨到達複核台後,可以立即將此複核台作為下一個揀貨單的起點。於是,本文合理分配揀貨單順序,以減少在複核台之間不必要的路徑損耗。

    得到首個揀貨單最優揀貨路徑的基礎上,結合式(11)可知Hi已經確定後,遍曆所有複核台計算該複核台與Hi的距離,即可以選擇距離最短的複核台作為首次揀貨的起始複核台。終點複核台的確定過程同理。

    此外,在完成揀貨單庫中所有揀貨單遍曆後,對於仍不能合理分配的揀貨單,可通過對比下列兩種行走路徑方案,優先選擇行走距離較短的方案,以使得該揀貨員在當前狀態下路徑最優。

    1)直接行走至下一揀貨單所在複核台,進行下一揀貨單的揀貨操作。

    2)改變下一揀貨單起始點,使之與當前揀貨單終點相同;並在此基礎上,通過揀貨路徑優化策略尋找較優的揀貨路徑。

    顯然,多揀貨單的合理分配方案會隨著單數的增加而呈現指數型增長,屬於NP-Hard問題。因此,本文嚐試通過將貪婪算法和動態調整相結合,給出在多揀貨單情況下,各揀貨員的揀貨單分配策略,具體算法如下。

    Algorithm 1基於動態調整的揀貨單拚接策略


    4 實例分析

    4.1 倉庫參數設定

    實驗數據來自京東物流的實際揀貨單數據1,包括各元素(貨櫃、貨格、複核台)的名稱、長寬及坐標信息,其中貨格名稱前3位為所在貨櫃編號a、後2位為在該貨櫃下貨格編號b;各揀貨單編號及其所包含貨物的貨格名稱等信息。

    實驗假設水平方向每組貨架之間的距離為1.5 m,豎直方向相鄰兩排貨架縱向距離為2 m,貨格長寬都是0.8 m,複核台長寬都是1 m,橫向通道與縱向通道寬度均為1.5 m;揀貨員繞障礙物折線行走時均沿道路中心線橫向和豎向偏移,都取d=0.75 m。對於揀貨操作,假定揀貨員平均行走速度為1.5 m/s,對每一待揀取貨物進行下架操作(包括揀取、掃描、檢查、確認等步驟)所需時間為5 s。

    考慮到實驗揀貨單共49個,本文基於合理假設,設置揀貨員5人、複核台開啟4台,以盡可能降低倉庫運營成本。不失一般性,假設通道1南側與巷道1西側各開啟2個複核台,分別為FH01、FH03與FH10、FH12。

    4.2 多複核台下揀貨路徑優化

    4.2.1 各揀貨單揀貨路徑優化

    基於3.1.2構建的模型,引入替換複核台將問題轉化為已知起點與終點的最短路徑問題;本文采用遺傳算法進行求解。算法具體步驟可參考文獻[14]的闡述,此處不再贅述。

    對於實際給出的49個揀貨單采用揀貨路徑優化策略,得到各揀貨單最優揀貨路徑。限於篇幅,此處僅給出對T0001揀貨單計算得到的最優路徑順序為:FH03→S07305→S10508→S10501→S12103→S13004→S13809→S14510→S13812→S14908→S14401→S15911→S13509→S12608→S11205→S11106→S10115→S06213→S07212→S08502→S07515→S01308→S01713→S00107→FH01,總揀貨距離為388.5 m,總揀貨時間為454.0 s,揀貨路徑見圖6,其中黑色標記為待揀取貨物所在位置。

    圖6 揀貨單T0001揀貨的實際路徑圖

    圖6 揀貨單T0001揀貨的實際路徑圖   下載原圖

    Figure 6 Order T0001 picking actual path diagram

    4.2.2 多揀貨單合理分配策略

    基於算法1得到的各揀貨員揀貨單分配集合如表1所示,其中揀貨單編號順序即代表揀貨員揀貨順序。

    為了驗證本文提出算法的效果,引入對比實驗1和2。

    實驗1基於下一揀貨單起點驅使的隨機遊走:依靠揀貨路徑優化策略,得出各揀貨單最優路徑下的起始點。當揀貨員完成此單揀貨工作時,需行走至下一揀貨單的起始複核台處,進行下一揀貨單的揀貨操作。

    實驗2基於當前揀貨單終點驅使的逐步優化:按照揀貨所需時間對各揀貨單進行排序,優先完成所需時間較長的揀貨單的揀貨工作依次完成,對於下一揀貨單起止點與當前揀貨單終點不同的情況,即不能完成揀貨單的拚接;選擇將當前揀貨單終點作為下一揀貨單起始複核台,重新進行下一揀貨單的路徑規劃。

    將上述方法與本文動態調整的仿真結果進行對比,表2為各揀貨員行走距離對比表,表3為揀貨員揀貨耗時結果。

    表1 各揀貨單分配結果 
    Table 1 Results of each order allocations     下載原表

    表1 各揀貨單分配結果

    表2 揀貨員行走距離計算結果對比 
    Table 2 Comparison of picker walking distance calculation results     下載原表

    m

    表2 揀貨員行走距離計算結果對比

    表3 揀貨員揀貨耗時計算結果對比 
    Table 3 Comparison of picker picking time calculation results     下載原表

    s

    表3 揀貨員揀貨耗時計算結果對比

    需要特別說明的是,由於隨機遊走是按照揀貨單順序進行分配、逐步優化是按照揀貨單揀選時間長度排序後分配,而動態調整則是基於貪婪算法和動態規劃相結合得到的分配方案;換言之,分配同一揀貨員的揀貨單編號會因為不同算法而產生差異。因此,單個揀貨員的揀貨距離與所耗時間不具有可比性。

    通過比較揀貨員行走總距離可以發現,本文所提出的動態調整的解決策略中所有揀貨員行走總距離為19 443.2 m,相對於隨機遊走和逐步優化算法分別縮短239.6 m和657.7 m。此外,就揀貨總耗時來說,動態調整相較於逐步優化節約的揀貨時間為55.4 s,相較於隨機遊走節約109.8 s;可以看出,本文所提出的動態調整的解決方案能夠縮短揀貨員行走距離,提升揀貨效率。

    從算法運行的效率來看,逐步優化算法的計算耗時為3.5 s,大約是動態調整方案耗時0.4 s的8倍。換言之,本文所提出的動態調整策略在解決49個大規模揀貨單情況下,仍然能夠完成亞秒級的規劃響應。

    5 結語

    與中小型配送中心不同,大型倉儲係統往往配設有多複核台、多出口以滿足眾多揀貨單的揀貨、打包與出庫。傳統起止點固定的單個揀貨單揀貨作業往往考慮成TSP問題,而對於多複核台來說,倘若直接遍曆所有路徑以尋找最優,其計算成本是極其巨大的。

    基於此,本文提出了“替換複核台”以解決多複核台場景下起止點不確定導致的遍曆搜索困難,這一概念能夠為多出口的後續研究奠定理論基礎。此外,本文結合了京東物流倉儲實際情況,給出在多複核台、多揀貨員情況下,進行多揀貨單的路徑優化與合理分配的動態調整策略,以滿足大規模、複雜場景下的揀貨作業。

    結合揀貨單揀貨實例的結果發現,本文所提出的基於替換複核台的動態調整算法相較於其他算法的計算效率更高、同等條件下的揀貨路徑更短、揀貨效率更高,能夠為大規模、複雜場景的倉庫揀貨提供更加準確的揀貨路徑規劃。

    標簽:

    版權所有©:上海陽合供應鏈管理有限公司 聯係電話:134-7270-5338
    地址:上海市嘉定區南翔鎮瀏翔公路885號(靠近豐翔路) 
    友情鏈接 :電鍋爐  國際貨代  教育加盟   撕碎機   杭州裝修  明泰鋁業  集成吊頂  成都活動策劃公司 貨代管理軟件 打印機租賃 進出口代理清關公司 模具鋼  煙霧淨化器 工作服價格 工業設計公司 雙軸螺旋輸送機 激光打標機   電子簽章   小吃培訓  植發多少錢
    定製禮品 數顯推拉力計  香港服務器租用 精品資源網 
    武漢拓展公司 連接器 磁性過濾器  招標網 上海物流公司
    夜光粉 膏藥OEM 爬架網 遠程工作 汙水提升器
    防爆配電箱 臭氧機價格  係統之家  MRO工業品
    滬公網安備31010702002684號 滬ICP備14036201號-29