于蕾 吳強(qiáng)

摘 要： 隨著物流網(wǎng)絡(luò)的快速擴(kuò)張，如何在異構(gòu)系統(tǒng)中交換物品信息已經(jīng)成為影響物流效率的重要因素，而社交網(wǎng)絡(luò)與物流網(wǎng)絡(luò)都具有異構(gòu)的特征，因此將物流網(wǎng)的各個(gè)節(jié)點(diǎn)看作是社交網(wǎng)絡(luò)的社區(qū)，利用多關(guān)系社交網(wǎng)絡(luò)社區(qū)挖掘算法來尋找各個(gè)異構(gòu)的物流網(wǎng)絡(luò)中固有的社區(qū)結(jié)構(gòu)，從而發(fā)現(xiàn)物流網(wǎng)中隱藏的規(guī)律并進(jìn)行路徑優(yōu)化等網(wǎng)絡(luò)行為是可行的。通過對(duì)4 000例物流數(shù)據(jù)的對(duì)比試驗(yàn)，得出基于相似度的社區(qū)挖掘算法在準(zhǔn)確率、算法復(fù)雜度和效率上都優(yōu)于K均值算法和回歸算法。

關(guān)鍵詞： 社區(qū)挖掘； 物流網(wǎng)絡(luò)； 相似度分析； 優(yōu)化算法

中圖分類號(hào)： TN711?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）06?0045?04

A logistics network optimization algorithm based on community similarity analysis

YU Lei， WU Qiang

（Xian University of Technology， Xian 710048， China）

Abstract： With the rapid expansion of logistics network， how to exchange the information of goods in heterogeneous systems has become an important factor affecting the efficiency of logistics. However， both social network and logistics network have a same heteroid feature： heterogeneity. Therefore， it is entirely feasible to find out the hidden law of logistics network and optimizing route by using the intrinsic community structure of each heteroid logistics network， which is calculated by a community mining algorithm of multi?relation social network. The contrast test result of 4000 logistics data from three different algorithms shows that the community mining algorithm based on similarity is better than K?mean algorithm and regression?based algorithm in accuracy rate， complexity and efficiency.

Keywords： community mining； logistics network； similarity analysis； optimization algorithm

目前，對(duì)于物流網(wǎng)絡(luò)設(shè)計(jì)的研究分為三個(gè)層次：策略、戰(zhàn)術(shù)和運(yùn)作[1]。策略和戰(zhàn)術(shù)研究主要是為供應(yīng)商解決貨物儲(chǔ)備的決策問題，如倉庫大小和位置、貨物價(jià)格和數(shù)量以及組織一個(gè)高效、低成本的物流網(wǎng)絡(luò)。總之，物流網(wǎng)絡(luò)的建立和優(yōu)化，需要考慮四個(gè)層次的內(nèi)容：物流中的選址[2]、對(duì)客戶的聚類[3]、配送區(qū)域劃分[4]和車輛調(diào)度[5]。一些學(xué)者將復(fù)雜網(wǎng)絡(luò)理論應(yīng)用在物流網(wǎng)上，試圖解決區(qū)域選址問題[4]。一些學(xué)者利用遺傳算法建立染色體表達(dá)式解決車輛調(diào)度問題（Vehicle Scheduling Problem，VSP）[6?7]。

而物流網(wǎng)中普遍存在物流效率低、成本高、大量的異構(gòu)系統(tǒng)不能順暢交換數(shù)據(jù)等問題。在物流網(wǎng)中，如何準(zhǔn)確獲取物品信息、如何在異構(gòu)系統(tǒng)中交換物品信息，已經(jīng)成為近幾年物流網(wǎng)絡(luò)研究的熱點(diǎn)。本文提出一種基于相似度的社區(qū)挖掘算法，將物流網(wǎng)的各個(gè)節(jié)點(diǎn)看作是社交網(wǎng)絡(luò)（Social Networks）的社區(qū)，社區(qū)結(jié)構(gòu)可能各不相同，物品是隸屬于不同社區(qū)的成員（意味著，不同物流節(jié)點(diǎn)的信息組成是異構(gòu)的）。通過社區(qū)挖掘?qū)ふ腋鱾€(gè)異構(gòu)的物流網(wǎng)絡(luò)中固有的社區(qū)結(jié)構(gòu)，從而發(fā)現(xiàn)物流網(wǎng)中隱藏的規(guī)律并進(jìn)行路徑優(yōu)化等網(wǎng)絡(luò)行為。

1 相關(guān)工作

對(duì)物流中所涉及到的數(shù)據(jù)，建立一個(gè)適用于物流的地理社會(huì)網(wǎng)絡(luò)，通過分析和處理，優(yōu)化物流流程，提高物流效率。物流的產(chǎn)生和發(fā)展的原因在于沒有將時(shí)間、空間以及人這三者關(guān)系結(jié)合起來，地理社會(huì)網(wǎng)絡(luò)可以實(shí)現(xiàn)時(shí)間、地點(diǎn)與人三者關(guān)系的疊加處理[8]。因此，將地理社會(huì)網(wǎng)絡(luò)與物流信息平臺(tái)相結(jié)合，關(guān)注用戶與系統(tǒng)、用戶與用戶間關(guān)系，讓用戶作為系統(tǒng)的一個(gè)節(jié)點(diǎn)，有效地參與并發(fā)布數(shù)據(jù)；結(jié)合地理社會(huì)網(wǎng)絡(luò)，消除信息之間的孤立等研究具有一定的研究價(jià)值和實(shí)際意義。

1.1 物流網(wǎng)關(guān)系模型

物流關(guān)系：一個(gè)物流網(wǎng)絡(luò)可以用一張圖來表示，如圖1所示。供應(yīng)商、客戶、物流企業(yè)對(duì)應(yīng)圖中的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)擁有自己的屬性，包括身份，公司，車隊(duì)等；邊代表節(jié)點(diǎn)之間的關(guān)系，包括買賣關(guān)系，合作關(guān)系等。用一個(gè)無向圖來表示這樣的網(wǎng)絡(luò)，Nsocial =（P，C，T），P是代表一組供應(yīng)商用戶的節(jié)點(diǎn)集合；C代表一組客戶用戶的節(jié)點(diǎn)集合；T代表物流企業(yè)，T包含于P×C的笛卡爾乘積中，是無向圖中的邊的集合。一條邊（p1，c2）屬于T，表示p1，c2這兩個(gè)的關(guān)系。

對(duì)物流網(wǎng)絡(luò)進(jìn)一步抽象，用連通的無向圖G=（V，E）來表示，節(jié)點(diǎn)集V表示物流網(wǎng)絡(luò)中個(gè)體（既可以是供應(yīng)商也可以是消費(fèi)者客戶）的集合，V={v_1，v_2，…，v_n}，邊集合E表示網(wǎng)絡(luò)中供應(yīng)商或者消費(fèi)者之間的關(guān)系，E={e_1，e_2，…，e_m}。

這樣，物流中的每類關(guān)系都可以對(duì)應(yīng)出一個(gè)子圖Gj=（Vj，Ej），j=l，2，…，k，k≥2，Vj表示該子圖中供應(yīng)商的集合；Ej表示子圖中供應(yīng)商之間關(guān)系的集合。在圖G中，邊E上是有標(biāo)有權(quán)重的，供應(yīng)商之間關(guān)系的緊密程度是通過權(quán)重來體現(xiàn)的，權(quán)值的計(jì)算是根據(jù)計(jì)算供應(yīng)商之間的標(biāo)記數(shù)目得到的。所以，在構(gòu)建子圖Gj=（Vj，Ej）所對(duì)應(yīng)的關(guān)系矩陣Rj時(shí)，需要計(jì)算邊上的權(quán)值，同樣，通過計(jì)算物流網(wǎng)絡(luò)中供應(yīng)商之間的標(biāo)記數(shù)，得到個(gè)體邊上的權(quán)重，用如下公式進(jìn)行計(jì)算：

[Rjxy=1， x和y具有相同標(biāo)記0， x和y不具有相同標(biāo)記]

其中[x，y∈Vj，]表示在物流子圖Gj中存在的兩個(gè)供應(yīng)商x，y，假設(shè)x和y具有3個(gè)相同的標(biāo)記，則[Rjxy]為3，是通過這種方式進(jìn)行計(jì)算物流網(wǎng)絡(luò)中所有邊上的權(quán)值的。對(duì)于關(guān)系矩陣Rj，j=1，2，…，k，k≥2，通過除以物流網(wǎng)絡(luò)中邊上的最大權(quán)值作歸一化處理，使得所有的邊上的權(quán)重值在范圍[0，1]內(nèi)。因?yàn)镽j是一個(gè)對(duì)稱矩陣，所以可以采用一個(gè)向量表示它。

1.2 物流網(wǎng)絡(luò)中的社區(qū)

一個(gè)社區(qū)可以簡單地定義成享有一些共同屬性的一群對(duì)象的集合，這個(gè)共同屬性就是對(duì)象之間的關(guān)系。例如，給出一個(gè)用戶的一組選擇[P={p1，p2，…，pk}]，構(gòu)建出相應(yīng)的關(guān)系矩陣RP，關(guān)系矩陣RP是一個(gè)對(duì)稱矩陣；然后，找出最能匹配選擇關(guān)系向量的已有關(guān)系的線性組合，根據(jù)得到的關(guān)系組合，來挖掘符合用戶需求的社區(qū)。

這些關(guān)系矩陣具有如下的屬性：

頻率：[f（xj）=xjn]，表示社會(huì)網(wǎng)絡(luò)中供應(yīng)商[xj]在關(guān)系[Rj]中所對(duì)應(yīng)的標(biāo)記占關(guān)系[Rj]中的有對(duì)象對(duì)應(yīng)的標(biāo)記的百分比，其中[xj]表示對(duì)象[xj]在關(guān)系[Rj]中所對(duì)應(yīng)的標(biāo)記數(shù)；n為關(guān)系[Rj]中所有對(duì)象對(duì)應(yīng)的標(biāo)記總和。若[xj]在關(guān)系[Rj]所對(duì)應(yīng)標(biāo)記中出現(xiàn)的次數(shù)越多，則[f（xj）]值越大，表示[xj]在關(guān)系[Rj]中與其他個(gè)體之間的聯(lián)系越緊密。

重要性：[I（xj）=Nxj]，表示供應(yīng)商[xj]在整個(gè)網(wǎng)絡(luò)中的一個(gè)重要參數(shù)，式中的N表示整個(gè)物流網(wǎng)絡(luò)中所有物流個(gè)體對(duì)應(yīng)的標(biāo)記總數(shù)目，[xj]表示對(duì)象[xj]在整個(gè)網(wǎng)絡(luò)中對(duì)應(yīng)的標(biāo)記總數(shù)。若[xj]對(duì)應(yīng)標(biāo)記在整個(gè)網(wǎng)絡(luò)中出現(xiàn)的次數(shù)越多，則[I（xj）] 的值就越小。

次序值：[RV（xj）=f（xj）I（xj）]，由頻率與重要性的定義可知，若對(duì)象[xj]所對(duì)應(yīng)標(biāo)記總數(shù)在社會(huì)網(wǎng)絡(luò)中出現(xiàn)的次數(shù)越多，并且在某一關(guān)系中出現(xiàn)次數(shù)越多，則對(duì)象[xj]的次序值就越大。若以這樣的[xj]作為一組選擇實(shí)例，則在網(wǎng)絡(luò)中，次序值越大的關(guān)系就更可能符合用戶的需求。

綜合次序值：整個(gè)網(wǎng)絡(luò)中某關(guān)系中的次序值。[j=1kRV（xj）]表示用戶選擇[P={p1，p2，…，pk}]，在整個(gè)網(wǎng)絡(luò)某關(guān)系中的次序值。

1.3 基于相似度的社區(qū)挖掘算法

進(jìn)行用戶推薦，需要了解客戶的購買行為?？梢酝ㄟ^大量的訂單的信息來了解，因?yàn)橛唵涡畔⒁话惆蛻舻木幪?hào)、物品名稱、數(shù)量、時(shí)間等信息；然后根據(jù)不同用戶提取相關(guān)數(shù)據(jù)并調(diào)用推薦算法，最后找出1～3個(gè)供應(yīng)商作為結(jié)果展現(xiàn)給用戶。

對(duì)于兩位用戶，當(dāng)他們?cè)谖锪餍畔⑵脚_(tái)上購買物品，選取的物流公司相同，則認(rèn)為兩位用戶有一定的相似性；假如兩位用戶同時(shí)都在物流服務(wù)平臺(tái)上購買相同的物品并且選取的物流公司也相同，可以認(rèn)為這兩位用戶在選取物流公司的相似度較高；假如兩位用戶同時(shí)都在物流服務(wù)平臺(tái)上購買相同的物品并且選取的物流公司也相同，而且兩位用戶在同一個(gè)區(qū)域，認(rèn)為這兩位用戶在選取物流公司的相似度更高。

在物流社交網(wǎng)絡(luò)中，用戶每一次下單行為可以稱作一個(gè)購買興趣點(diǎn)（Purchase of interest，PI）。PI庫中都會(huì)記錄每一個(gè)PI的供應(yīng)商、物品名稱、發(fā)貨地、送貨地、送貨方式（物流公司名稱），即PI=（P，N，O，D，T）。在物流過程中，經(jīng)常會(huì)涉及到訂單，需要對(duì)訂單進(jìn)行定義。這樣，每一個(gè)訂單都會(huì)有供應(yīng)商、物品名稱、發(fā)貨地、送貨地、物流公司名稱，即Order=（ProviderName，GoodsName，Origin，Destination，LogisticsCompanyName）。n個(gè)訂單可以看成[n×5] 的矩陣：

[On×5=O11O12…O15???Oi1Oi2…Oi5????On1On2…On5]

首先，給出一個(gè)連通的無向圖G（V，E），|V|=M，代表物流網(wǎng)絡(luò)中的有M個(gè)物流個(gè)體，確切地說是M個(gè)供應(yīng)商；E代表個(gè)體之間的關(guān)系。并對(duì)其對(duì)應(yīng)的關(guān)系向量[R1，R2，…，Rn]作標(biāo)準(zhǔn)化處理。

其次，物流社會(huì)網(wǎng)絡(luò)中物流個(gè)體間存在著各種關(guān)系，每種關(guān)系都可以映射為一個(gè)關(guān)系圖，因此一個(gè)社會(huì)網(wǎng)絡(luò)映射出多個(gè)關(guān)系圖，[G1，G2，…，Gn]，并根據(jù)用戶的選擇信息，由次序值公式：[RV（xj）=f（xj）I（xj）]計(jì)算綜合次序值[j=1kRV（xj）]，然后重新排序關(guān)系，其中N表示關(guān)系的種類數(shù)目。

最后，選擇次序值高于一定閾值t的關(guān)系，在此關(guān)系基礎(chǔ)上，調(diào)用基于回歸的多關(guān)系抽取算法，求出組合系數(shù)：[R=a1R1′+a2R2′+…+anRn′]，其中[a1，a2，…，an]為對(duì)應(yīng)關(guān)系的組合系數(shù)，得到一組關(guān)系組合[R1′，R2′…，Rn′] ，調(diào)用K?means算法，得到K個(gè)聚類，即挖掘出k個(gè)社區(qū)。

該算法偽代碼如下所示：

2 實(shí)驗(yàn)及分析

本實(shí)驗(yàn)使用4 000個(gè)訂單數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，把這個(gè)數(shù)據(jù)集看作一個(gè)物流網(wǎng)絡(luò)，供應(yīng)商視為網(wǎng)絡(luò)中的對(duì)象，供應(yīng)商使用不同的物流公司配送物品視作一種關(guān)系，因?yàn)?0個(gè)物流公司，則至多有10種不同關(guān)系，那么這個(gè)數(shù)據(jù)集就是一個(gè)多關(guān)系社會(huì)網(wǎng)絡(luò)。本實(shí)驗(yàn)就是在其上研究供應(yīng)商的內(nèi)在的關(guān)系，對(duì)供應(yīng)商社區(qū)進(jìn)行挖掘。

首先構(gòu)建關(guān)系圖，把供應(yīng)商視為節(jié)點(diǎn)，標(biāo)記數(shù)初始值為0，如果有兩個(gè)供應(yīng)商使用同一個(gè)物流公司配送物品，則他們的標(biāo)記數(shù)加l，否則不變；然后生成關(guān)系圖，每一個(gè)物流公司生成一個(gè)關(guān)系圖，對(duì)每個(gè)物流公司，將數(shù)據(jù)相加獲得該物流公司的供應(yīng)商關(guān)系圖。這種關(guān)系圖反映了供應(yīng)商在配送某一類物品時(shí)的相似度，相似度越高，說明他們之間的具有共同喜好的可能性越大。一般來說，如果兩個(gè)供應(yīng)商在某一圖中邊的權(quán)值較大，就說明他們有著相似或者相同的物品或物流公司，也說明他們的相似度更高。最后，對(duì)于每一個(gè)關(guān)系圖，需要進(jìn)行歸一化權(quán)值，可以采用他們的權(quán)值除以整個(gè)網(wǎng)絡(luò)關(guān)系圖中的最大權(quán)值的方式來處理，權(quán)值結(jié)果都在區(qū)間[0，l]內(nèi)。本實(shí)驗(yàn)選取了配送物品較多的物流公司構(gòu)建了關(guān)系圖。所有供應(yīng)商的綜合次序值的計(jì)算結(jié)果如表1所示。

當(dāng)選擇淘寶、京東、天貓，閾值t為10時(shí)，綜合次序值對(duì)應(yīng)的是表1中的第4，9，10次序；抽取的關(guān)系組合系數(shù)分別為：

[R=0.736R1′+0.265R2′+0.182R3′+0.139R4′+0.092R5′+ 0.061R6′+0.043R7′+0.021R8′+0.019R9′+0.006R10′]

由上式可以看出，當(dāng)選擇淘寶、京東和天貓這幾個(gè)供應(yīng)商和物流公司[R1′]（順豐）的關(guān)系最密切，換言之，淘寶、京東和天貓與順豐的業(yè)務(wù)合作比較多。最終，通過聚類，得到一個(gè)社區(qū)，該社區(qū)如圖2所示。

從圖2中可以看出，這個(gè)社區(qū)中的供應(yīng)商有一個(gè)共同的特點(diǎn)，那就是他們的客戶主要是個(gè)人，而不是企業(yè)。他們使用的物流公司大都是一些快遞公司。因?yàn)檫@些快遞公司的費(fèi)用較低，速度快等特點(diǎn)，淘寶是最典型的例子。進(jìn)而得到一個(gè)供應(yīng)商和客戶的關(guān)系，該社區(qū)的供應(yīng)商大多數(shù)業(yè)務(wù)是面向個(gè)人用戶的。

同樣的，當(dāng)用戶選擇當(dāng)當(dāng)、TCL、索尼，閾值t為10時(shí)，綜合次序值對(duì)應(yīng)的是表1中的第1，2，3次序；抽取的關(guān)系組合系數(shù)分別為：

[R=0.636R1′+0.565R2′+0.532R3′+0.458R4′+0.394R5′+ 0.138R6′+0.119R7′+0.095R8′+0.062R9′+0.027R10′]

由上式可以看出，當(dāng)選擇當(dāng)當(dāng)、TCL和索尼這幾個(gè)供應(yīng)商和物流公司[R1′]（順豐）[R2′]（中國外運(yùn)（集團(tuán)）總公司）[R3′] （EMS）[R4′] （中遠(yuǎn)國際貨運(yùn)有限公司）[R5′]（德邦物流）的關(guān)系比較密切；最終，通過聚類，得到2個(gè)社區(qū)，如圖3所示。從圖3中可以看出，社區(qū)1中的供應(yīng)商的共同特點(diǎn)是他們的客戶主要是個(gè)人。他們使用的物流公司大都是一些快遞公司，使用最多的是順豐快遞和EMS。此社區(qū)中的供應(yīng)商大多數(shù)業(yè)務(wù)是面向個(gè)人用戶的。社區(qū)2中的供應(yīng)商的共同特點(diǎn)是他們的客戶主要是企業(yè)。他們使用的物流公司大都是一些貨運(yùn)代理公司，如中國外運(yùn)（集團(tuán)）總公司、中遠(yuǎn)國際貨運(yùn)有限公司、德邦物流等。此社區(qū)中的供應(yīng)商大多數(shù)業(yè)務(wù)是面向企業(yè)用戶的。

3 結(jié) 語

傳統(tǒng)K均值數(shù)據(jù)挖掘算法的好處是不需要進(jìn)行關(guān)系選擇和抽取，但是其結(jié)果會(huì)隨著選取實(shí)例比率的不同在一個(gè)而上下浮動(dòng)。針對(duì)實(shí)驗(yàn)中的4 000個(gè)訂單數(shù)據(jù)，分別使用K均值算法[9]、回歸算法[10]和相似度挖掘算法在選擇實(shí)例的比例為5%，10%，15%和20%下得出的挖掘正確率如表2所示。

表2 算法正確率比較

經(jīng)過實(shí)驗(yàn)驗(yàn)證，在關(guān)系數(shù)恒定的情況下，相似度算法的正確率會(huì)隨著用戶選定實(shí)例比率的提高而提高，且明顯要好于傳統(tǒng)K均值挖掘算法，略微高于基于線性回歸的多關(guān)系抽取算法。

參考文獻(xiàn)

[1] SHANKAR L B， BASAVARAJAPPA S， CHEN J C H， et al. Location and allocation decisions for multi?echelon supply chain network： a multi?objective evolutionary approach [J]. Expert systems with applications， 2013， 40： 551?562.

[2] WANG Y， MA X L， WANG Y H， et al. Location optimization of multiple distribution centers under fuzzy environment [J]. Journal of Zhejiang University （Science A）， 2012， 13（10）： 782?798.

[3] MIRANDA P A， GARRIDO R A， CERONI J A. E?work based collaborative optimization approach for strategic network design problem [J]. Computer & industrial engineering， 2009， 57（1）： 3?13.

[4] IYOOB I M， KUTANOGLU E. Inventory sharing in integrated network design and inventory optimization with low?demand parts [J]. European journal of operational research， 2013， 224： 497?506.

[5] CHOPRA S， MEINDL P. Supply Chain management： strategy， planning and operation [M]. 3rd ed. [S.l.]： Pearson Prentice Hall， 2007.

[6] KO H J， EVANS G W. A genetic algorithm?based heuristic for the dynamic integrated forward/reverse logistics network for 3PLs [J]. Computers & operations research， 2007， 34： 346?366.

[7] KANNAN G， SASIKUMAR P， DEVIKA K. A genetic algorithm approach for solving a closed loop supply chain model： A case of battery recycling [J]. Applied mathematical modelling， 2010， 34： 655?670.

[8] 肖智清.基于SOA的物流信息系統(tǒng)集成平臺(tái)LESB的研究與實(shí)現(xiàn)[D].吉林：吉林大學(xué)，2012.

[9] GAZI V P， KAYIS E. Comparing clustering techniques for real microarray data [C]// 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. [S.l.]： IEEE， 2012： 788?791.

[10] YAN Chunlei， SHI Shumin， HUANG Heyan， et al. A method for network topic attention forecast based on feature words [C]// 2013 International Conference on Asian Language Processing. [S.l.]： IALP， 2013： 211?214.