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

孫秋天 張 凱 王玄平 崔宏兵

北京起重運(yùn)輸機(jī)械設(shè)計(jì)研究院有限公司 北京 100007

0 引言

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

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

1 研究現(xiàn)狀

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

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

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

2 貨品關(guān)聯(lián)度計(jì)算

2.1 余弦相似度計(jì)算

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

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

圖1 二維向量余弦計(jì)算

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

圖2 n維向量余弦計(jì)算圖例

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

2.2 貨品屬性關(guān)聯(lián)度計(jì)算

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

首先，對貨品的屬性文本進(jìn)行分詞，分詞結(jié)果記做集合C，去除標(biāo)點(diǎn)符號及停用詞后得到詞典Dic1＝｛w1，w2，…，wn｝，計(jì)算詞典Dic1中的每個(gè)單詞的TF-IDF值，作為單詞的權(quán)重，TF-IDF值計(jì)算過程可表示為

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

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

3 實(shí)驗(yàn)與結(jié)果

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

4 結(jié)語

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