基于歐氏距離聚合算法模型的倉庫配貨行走路徑研究

趙堅密 周旭 江駿風(fēng) 顏嘉梁

上海聚水潭網(wǎng)絡(luò)科技有限公司 上海 200040

引言

新零售時代，倉庫往往會面臨大量的SKU和訂單，在消費者對物流時效性和服務(wù)要求越來越高的趨勢下，配送任務(wù)隨之變得繁重而艱巨。配貨是客戶提交訂單后，配貨員盡可能在最短的時間內(nèi)完成對訂單上商品的分揀、配貨過程，或是倉庫按照商品配送計劃高效、準確地將貨品從對應(yīng)貨架庫位揀取出來，按照規(guī)定的方式對貨品配貨、分裝、等待送貨的作業(yè)，它是倉庫中最費時費力的環(huán)節(jié)，配貨效率的高低可以直接影響客戶滿意度，傳統(tǒng)依賴人海戰(zhàn)術(shù)、人腦記憶的作業(yè)形式已難以滿足倉庫高效配貨的需求。在倉庫所有作業(yè)流程中，訂單分揀配貨越來越受到企業(yè)的關(guān)注。

1 基于歐式距離的聚合算法模型

為解決配貨難題，越來越多的商家倉庫尋求突破，例如通過揀貨車配貨、聚合最早被揀貨的商品貨位、限定訂單揀貨通道等方式進行訂單配貨，此類方式在一定程度上緩解了配貨難題，但隨之也帶來揀貨工作量大、工作死板低效、揀貨通道擁堵等問題。由于倉庫所用貨架大都相對固定，因此在研究如何提高倉庫配貨工作效率的問題上，應(yīng)考慮對揀貨路徑進行優(yōu)化——縮短完成所有訂單所需的行走距離[1]。基于歐式距離聚合分析算法模型把批次路徑聚合尋優(yōu)的復(fù)雜問題轉(zhuǎn)化為一個對二維空間點進行聚類的簡單問題，將在揀貨路徑上相似度較高的訂單聚合到同一批次，讓完成批次所需行走的路徑貼近批次中任意訂單所需的路徑，從而縮短完成所有訂單所需的行走路長，提高倉庫配貨工作效率。

1.1 算法原理

歐氏距離是常用的一種距離計算方法，源自歐氏空間中兩點間的距離公式，即兩點之間直線距離，例如把A點和B點用一條直線連接，直線段的長度就是A點到B點的歐式距離，目前已廣泛用于工程學(xué)中的定位分析、數(shù)據(jù)挖掘領(lǐng)域的聚類分類、自然語言處理中的文本距離算法等各種應(yīng)用場景。

映射到倉庫訂單分揀配貨作業(yè)中，鑒于大多數(shù)倉庫所用的貨架相對固定，考慮當訂單路徑聚合程度足夠好的時候，完成某一訂單所需行走的路長與該訂單經(jīng)過的貨架數(shù)是成正比的。同時，由于訂單聚合足夠好，完成該訂單所在批次時，途徑通道都會有揀貨操作，而不能進行通道或區(qū)域的跳躍或抄捷徑[2]。因此，可以在以貨架行走index為標尺的一維坐標系中，如下定位一個訂單。

圖1 訂單A、B、C一維坐標系

圖2 訂單A、B、C二維坐標系

例如，設(shè)定A、B、C3個訂單最先揀貨的商品所在貨架分別為最后揀貨的商品所在貨架分別為從一維、二維坐標系中可以看出，距離相近的訂單B和訂單C就非常適合聚合在一個揀貨批次，揀貨人員可對訂單B、訂單C安排同批次揀貨。

1.2 算法模型

優(yōu)化揀貨路徑即讓配貨員完成批次所需行走的揀貨路徑貼近批次中任意訂單所需的路徑，縮短完成所有訂單所需的行走路長[3]。基于此，本文提出建立基于歐式距離的訂單聚合算法模型，通過算法演算從眾多待揀貨位中選擇n個點，一旦n個點確定之后，揀貨路徑便固定下來且唯一，以實現(xiàn)將揀貨路徑上相似度較高的訂單聚合到同一揀貨批次，使配貨員完成所有訂單揀貨、配貨行走的距離最短。

1.2.1 前提條件。基于歐式距離的訂單聚合算法模型來解決倉庫揀貨路徑優(yōu)化問題，需要設(shè)置一定的前提條件[4]：①每個訂單包括至少1種商品，至多N個商品（N為倉庫中的貨架庫位總數(shù)，每個庫位只能存放1種商品），商品坐標明確；②每位配貨員負責(zé)一批訂單貨品的揀貨、配貨；③配貨員在倉庫內(nèi)拉著揀貨車的行走距離可計算。

1.2.2 模型建立。定義O表示訂單集合，分別表示第1，2…n個訂單。

該距離越小的越適合聚合，該距離越大的越不適合聚合。

1.2.3 執(zhí)行過程。

（1）選擇種子訂單。對訂單集合O首先按照的距離升序排序，距離相同的再按照升序排序，若距離依舊有相同的再按照付款時間先后排序，選擇排序后且?guī)齑娉渥愕牡谝粋€訂單作為種子訂單（距離越小表示這個訂單要走的貨架越接近，盡量把這樣的訂單作為種子訂單去聚合其他訂單）。

（2）計算相似度。計算其余所有訂單與種子訂單的歐式距離，由小到大排序，選擇固定框數(shù)且?guī)齑娉渥愕挠唵谓M成一個批次。

（3）完成所有訂單組批。重復(fù)步驟1、2直至所有訂單組批完成，實現(xiàn)對于同一批次的訂單，揀貨人員在途經(jīng)通道都會有揀貨操作，而不進行通道或區(qū)域的跳躍或抄捷徑。

1.3 算法實現(xiàn)流程[5]

①通過系統(tǒng)（例如借助聚水潭的天機智倉軟件）或手動錄入的模式，綁定每個庫位的行走index，該數(shù)據(jù)準備好之后，便可開始從系統(tǒng)獲取訂單進行處理；②對訂單進行初步的篩選和歸類。剔除庫存無法滿足商品需求的訂單（當前無法完成配貨，可等補貨到位后再配），然后根據(jù)訂單體積進行歸類，以便被分配到符合大小的揀貨車。一般訂單會被分為2-4類，不同類訂單被分配到不同訂單池，可裝載不同揀貨車。只有相同訂單池的底單才可聚合，不同訂單池的訂單不能聚合，否則會出現(xiàn)揀貨車裝載不下或裝載過少的情況。③根據(jù)訂單商品內(nèi)容確定訂單在二維坐標系中的坐標（X,Y）：每個訂單的起始貨架index值為X ，終止貨架index值為Y。④根據(jù)坐標距離和庫存，將訂單聚合到批次：距離接近的訂單應(yīng)被聚合到同一批次，庫存不足的訂單應(yīng)被剔除出訂單池。⑤為防止出現(xiàn)通道擁擠的情況，可在生成批次前對聚合完畢的批次按一定規(guī)則進行排序。⑥輸出訂單批次到系統(tǒng)，有序安排配貨。

2 預(yù)期效果分析

2.1 改善倉庫現(xiàn)場狀態(tài)

基于歐式距離的聚合算法模型優(yōu)化訂單揀貨路徑后，分揀人員能夠在指定揀貨通道或區(qū)域按照一定的操作標準（同一揀貨批次訂單統(tǒng)一揀貨）有序進行揀貨。同時通過體積歸類、庫存校驗、批次排序等措施，有效解決訂單體積大小不同、庫位庫存缺貨、通道擁堵等問題，從而確保倉庫分揀配貨作業(yè)有條不紊地進行。

2.2 提升配貨作業(yè)效率

最新的倉儲調(diào)查報告顯示訂單分揀是提高倉庫生產(chǎn)效率最優(yōu)先考慮的運營活動，對訂單分揀行走路徑優(yōu)化后，揀貨效率平均可提升25%以上，折算成時間能節(jié)省2個人的日工作時間，分揀配貨成本、配貨錯誤率、配貨員工作強度明顯降低。同時，倉庫配貨作業(yè)效率的提升對提升倉儲貨物出庫速度、縮短訂單配送時限、優(yōu)化客戶服務(wù)等方面具有重要意義。

2.3 推動數(shù)字倉儲建設(shè)

信息時代，該模型涉及的倉儲基礎(chǔ)數(shù)據(jù)資源的采集離不開信息技術(shù)的支撐，傳統(tǒng)人工方式數(shù)據(jù)采集的低效率、成本高、易出錯等弊端的顯現(xiàn)，一定程度上也倒逼各類智能化系統(tǒng)和設(shè)備在倉儲管理中的普及應(yīng)用，對數(shù)字倉儲建設(shè)乃至引領(lǐng)數(shù)字商務(wù)發(fā)展具有很大推動作用。

3 結(jié)束語

本文以一般倉庫為研究對象，提出基于歐氏距離訂單聚合算法的倉庫揀貨路徑優(yōu)化方法，根據(jù)訂單明細商品所對應(yīng)庫位的揀貨順序?qū)τ唵芜M行數(shù)據(jù)抽象和定義，并以此訂單定義為基礎(chǔ)將揀貨路徑長度問題轉(zhuǎn)化為一個二維空間中點與點距離問題的技術(shù)特征，把批次路徑聚合尋優(yōu)的復(fù)雜問題轉(zhuǎn)化為一個對二維空間點進行聚類的簡單問題，從而達到快速算得優(yōu)化結(jié)果的技術(shù)效果，以此求取倉庫配貨作業(yè)中揀貨員最優(yōu)行走路徑。