基于余弦相似度的貨品屬性關聯(lián)度研究

孫秋天 張 凱 王玄平 崔宏兵

北京起重運輸機械設計研究院有限公司 北京 100007

0 引言

倉庫管理是制造業(yè)達到供需平衡的必要一環(huán)，其中智能立體倉庫以其高度自動化、高效貨品流轉效率可幫助企業(yè)實現(xiàn)貨品的量化管理，從而受到醫(yī)藥、家具、紡織、電氣等行業(yè)的青睞與推崇。智能立體倉庫整合、優(yōu)化了物流所需的各種資源，提高了物流行業(yè)的自動化和智能化水平，為物流行業(yè)的模式和流程帶來新的變革和創(chuàng)新[1]。隨著市場規(guī)模的不斷擴大與發(fā)展，倉庫中貨品種類的不斷增多，貨品入出庫體量的逐步增長，故高效而有序實現(xiàn)倉庫貨品的系統(tǒng)化、規(guī)范化、自動化管理是一個亟待解決的問題。高效二字也成為智能倉庫研究方向的重點，合理有效地提高物流運作效率對節(jié)約企業(yè)運行成本以及提高倉庫運轉流暢性具有重要意義。

在倉庫物流運作中，貨物揀選是必不可少的一環(huán)。有研究表明，貨物揀選的作業(yè)成本大約占整個倉儲中心運行成本的 50%～75%，作業(yè)時間大約占整個倉儲中心所有作業(yè)時間的60%，是整個倉儲中心勞動最密集、運作成本最高的一環(huán)，成為牽制倉儲中心整體運營效率的瓶頸環(huán)節(jié)[2]。因此，提高揀選出庫效率將有助于提升倉庫物流運作效率、提高自動化立體倉庫的效能。

1 研究現(xiàn)狀

在倉庫管理中，貨物揀選在智能倉庫中扮演重要角色并起到重要作用，提高訂單的揀選效率，一方面可通過購買先進的設備提高運行速度與效率，但這樣也會大幅增加企業(yè)運行成本；另一方面可改進揀選策略，在單位時間內揀選更多的貨品，此優(yōu)化可在不增加企業(yè)運行成本的前提下提高揀選效率。因此，提高訂單分揀系統(tǒng)的效率成為學術界和產(chǎn)業(yè)界關注的焦點之一[2]。

由相關文獻可知，倉庫揀選可分為兩種模式：人到貨揀選模式和貨到人揀選模式，針對人到貨揀選模式優(yōu)化，張宇[3]提出基于時間窗約束多種群遺傳揀選路徑優(yōu)化算法，建立以揀選路徑長度最短為目標的多人作業(yè)揀選路徑優(yōu)化模型；王璐璐[4]采用訂單分批下的路徑優(yōu)化揀選策略建立揀選模型，找到一條可以揀選出所有貨物的最優(yōu)路徑；楊學春等[5]將揀貨路徑簡化成 TSP 問題，引入C-W 節(jié)約算法改進傳統(tǒng)揀貨路徑，提高了揀選效率；閆軍等[6]基于遺傳算法對訂單進行排序，使揀貨員獲得較優(yōu)的揀貨路徑；袁瑞萍等[7]建立了基于最小化貨架搬運次數(shù)以及最小化機器人總揀選路程的數(shù)學模型，并設計兩階段啟發(fā)式算法求解，仿真實驗表明該方法有效提高揀選效率。李悅[8]基于禁忌搜索算法提出一種在不同場景下，貨位分配與揀貨路徑協(xié)同優(yōu)化的方法，使倉庫更好地適應市場實時變化，提高分揀人員的工作效率。針對貨到人的揀選模式優(yōu)化，霍達等[9]介紹了一種食品行業(yè)中貨到人系統(tǒng)的應用，根據(jù)業(yè)務流程和客戶需求，提出了系統(tǒng)的難點和特點所在，設計詳細、系統(tǒng)地解決方案；李珍萍等[10]建立了以揀選訂單過程中搬運貨架總時間最短為目標的整數(shù)非線性規(guī)劃模型，設計了求解模型的貪婪算法和單親進化遺傳算法；Li等[11]以搬運貨架總時間極小化為目標建立了混合整數(shù)規(guī)劃模型，并設計了求解模型的啟發(fā)式算法；Yuan等[12]在一種物品只能存放到一個分區(qū)的假設下，設計了按照物品出庫速率確定物品儲位分區(qū)的入庫策略，提高了揀選效率。

綜上所述，大多數(shù)針對揀選策略的優(yōu)化會選擇對揀選路徑進行優(yōu)化，部分會考慮貨品的入庫儲位、搬運載體的搬運次數(shù)以及搬運總時間，但這些研究都忽略了貨品本身屬性對揀選效率的影響。另外，相較于人到貨模式，目前主流系統(tǒng)更傾向于貨到人模式，以降低勞動強度與人工數(shù)量。一方面人員移動的速度會低于機器的移動速度，另一方面貨到人模式的運輸速度有更高的提升空間，所以目前的主流研究以貨到人模式為基礎，提出相應優(yōu)化措施提高揀選效率。考慮到以往智能倉庫一個單位貨架上只存放一種貨物，而隨著貨品種類的增多，貨品混放在一個托盤載體的情形不斷增多，貨品的混放也成為智能倉庫的關注點之一。因此，本文擬在貨到人揀選模式下對同一揀選訂單下不同貨品的屬性關聯(lián)強度進行深入研究，根據(jù)貨品的屬性關聯(lián)強度對入庫混放提出建議，優(yōu)化同一訂單揀選頻率與路徑，以達到減少同一揀選訂單下不同貨品揀選時間的目的，從而提高揀選效率與準確率。

2 貨品關聯(lián)度計算

2.1 余弦相似度計算

眾多周知，兩個向量的夾角越小其相似度越高。余弦相似度正是基于這個思想，用向量空間中兩個向量夾角的余弦值作為衡量兩個個體間差異的大小。余弦值越接近1，就表明夾角越接近0°，也就是兩個向量越相似，這就叫余弦相似性。

以二維空間為例，a和b是兩個向量，如圖1所示，用余弦定理計算夾角，則有

圖1 二維向量余弦計算

余弦定理也可以應用于n維向量上，假設A和B是兩個n維向量，如圖2所示，A為[A1，A2，…，An]，B為[B1，B2，…，Bn]，則A與B夾角θ的余弦可表示為

圖2 n維向量余弦計算圖例

余弦相似度計算源于向量余弦計算的思想，通過測量兩個向量內積空間夾角的余弦值來度量它們之間的相似性，常用于機器學習中對文本的處理過程。計算兩段文本的相似度首先需要將文本分詞，清除標點符號以及停用詞，對文本中涉及的詞進行統(tǒng)一數(shù)字編碼，根據(jù)編碼將文本中的詞頻向量化，再用余弦定理計算兩個向量的余弦值，即可得到兩段文本的相似度。因此，可將余弦相似度計算的思想用于貨品屬性關聯(lián)度的計算上。

2.2 貨品屬性關聯(lián)度計算

貨品屬性包括物料規(guī)格、物料單位、物料邏輯儲位、物料描述、物料類別等，這些屬性皆以文本形式存在數(shù)據(jù)庫中，故可借鑒余弦相似度的計算方法對貨品的關聯(lián)度進行計算。本文設計了一種基于余弦相似度的貨品屬性關聯(lián)度計算方法。

首先，對貨品的屬性文本進行分詞，分詞結果記做集合C，去除標點符號及停用詞后得到詞典Dic1＝｛w1，w2，…，wn｝，計算詞典Dic1中的每個單詞的TF-IDF值，作為單詞的權重，TF-IDF值計算過程可表示為

然后，將貨品A的屬性文本AttributeAtext與貨品B的屬性文本AttributeBtext作為向量空間模型（VSM），這兩段語料的向量空間可表示為

將貨品A屬性文本AttributeAtext與貨品B屬性文本AttributeBtext的向量空間模型余弦值作為貨品關聯(lián)度的度量值Similarity，Similarity值越大，貨品關聯(lián)度越大。由向量余弦值計算可得到2個貨品的屬性關聯(lián)強度為

3 實驗與結果

3.1 數(shù)據(jù)集與預處理

選取某企業(yè)的數(shù)據(jù)庫作為實驗數(shù)據(jù)集，數(shù)據(jù)集中出庫單據(jù)log_Erp_Out表中包含15 459條出庫單據(jù)，其中2 507條單據(jù)數(shù)據(jù)包含多個行號。為驗證同一單據(jù)下不同貨品的關聯(lián)度，選取這2 507條數(shù)據(jù)作為實驗數(shù)據(jù)集。在這些數(shù)據(jù)中，同一單據(jù)下最多有26行的出庫數(shù)據(jù)，最少有2行出庫數(shù)據(jù)。與此同時，需要結合貨品信息log_Material表中貨品的各種屬性信息，計算貨品的屬性關聯(lián)強度。

3.2 實驗結果

通過設計相應算法，計算每個單據(jù)下所有貨品的屬性關聯(lián)強度。對同一單據(jù)計算兩兩貨品間的關聯(lián)強度后求和取均值，作為某一單據(jù)下所有貨品的屬性關聯(lián)強度。假如單據(jù)A下有n行出庫記錄，則需計算n(n-1)/2對關聯(lián)強度，然后對n(n-1)/2對關聯(lián)強度求和取均值，作為單據(jù)A下貨品的關聯(lián)強度。表1為部分實驗結果。

表1 不同單據(jù)的關聯(lián)強度

在此，利用散點圖顯示值集之間的關系，2 507條單據(jù)數(shù)據(jù)中貨品的屬性關聯(lián)強度分布如圖3所示。

圖3 不同單據(jù)的關聯(lián)度散點圖

由圖3可知，大多數(shù)同一出庫單據(jù)的貨品屬性關聯(lián)度處于0.5～0.7之間，表明大部分同一出庫單據(jù)下的貨品具有較大關聯(lián)強度。由于某些單據(jù)下不同行的貨品為同一貨品，雖出現(xiàn)的概率較少，少部分單據(jù)在倉庫正常運轉過程中出現(xiàn)關聯(lián)強度為1的情況。另外，有少部分單據(jù)出現(xiàn)關聯(lián)強度較低的情形，在實驗數(shù)據(jù)集中有19.585%的出庫單據(jù)中貨品關聯(lián)度低于0.5，在實驗數(shù)據(jù)集中有7.020%的出庫單據(jù)中貨品關聯(lián)度低于0.4，在實驗數(shù)據(jù)集中有2.074%的出庫單據(jù)中貨品關聯(lián)度低于0.3，在實驗數(shù)據(jù)集中有0.479%的出庫單據(jù)中貨品關聯(lián)度低于0.2，在實驗數(shù)據(jù)集中有0.479%的出庫單據(jù)中貨品關聯(lián)度低于0.2，在實驗數(shù)據(jù)集中有0.359%的出庫單據(jù)中貨品關聯(lián)度低于0.1，故只有少部分單據(jù)存在同一出庫單據(jù)下貨品關聯(lián)度較低的情形。

由此可見，同一出庫單據(jù)下貨品關聯(lián)強度通常較大。據(jù)此，如果入庫時存在貨品混放的情形，即同一托盤載體可以存放不同貨品，操作人員可盡量將貨品屬性關聯(lián)度較大的貨品混放在同一托盤載體上，這樣出庫揀選時即可在同一托盤載體上找到所需貨品種類，達到減少堆垛機的工作時間及頻率、減少工作人員等待時間、提高倉庫的揀貨效率的目的。

如果允許存在混放的情形，考慮到同一托盤載體的容量有限，只能存放有限的貨品，入庫操作員在進行多種貨品的混放時可查詢貨品間的屬性關聯(lián)強度。通過手持PDA入庫操作員輸入兩個貨品的編號，點擊關聯(lián)度查詢，即可查詢到兩個貨品的屬性關聯(lián)強度，操作簡單容易上手。入庫操作員根據(jù)查詢結果，盡可能將關聯(lián)強度較大的貨品混放在同一托盤載體，這樣出庫操作員在揀選時可在一個托盤載體中取得更多貨品，提高了揀選出庫的效率以及倉庫運行的整體效率。手持終端程序界面如圖4所示。

圖4 RF手持關聯(lián)度查詢操作界面

4 結語

為了提高出庫揀選的效率，本文驗證了同一出庫單據(jù)下不同貨品的屬性關聯(lián)度，設計了一種基于余弦相似度的貨品屬性關聯(lián)度計算方法，實驗數(shù)據(jù)表明，同一出庫單據(jù)下貨品的關聯(lián)強度通常較大。根據(jù)這個結論，操作人員可以在允許混放入庫的情形下可盡可能將貨品關聯(lián)度較大的貨品放置在同一托盤載體，以在出庫揀選時有效提高工作人員的揀選效率。