1　引言

　　物流RFID數(shù)據(jù)的采集與積累為期不長，如何對它們進(jìn)行有效開發(fā)利用的研究還處于起步狀態(tài)。雖然大家都認(rèn)識到這項研究工作具有重大意義，但是目前還沒有尋找到適用的方法和技術(shù)。物流貨物的RFID數(shù)據(jù)與乘客利用公交IC卡刷卡乘車數(shù)據(jù)有相似之處，所以考察公交IC卡數(shù)據(jù)的研究工作有一定的借鑒作用。文獻(xiàn)中有對公交IC數(shù)據(jù)倉庫結(jié)構(gòu)和數(shù)據(jù)挖掘系統(tǒng)框架進(jìn)行探討的，利用傳統(tǒng)的統(tǒng)計方法，得到某些方面的匯總信息。但是文中沒有提出有效的數(shù)據(jù)挖掘技術(shù)，所以沒能獲取深層次的決策支持信息。與乘客乘車一樣，運載的貨物也處于一個時空不斷變化的動態(tài)過程中，要想得到貨物在路網(wǎng)上的運動規(guī)律，必須采用新的方法和技術(shù)。時空數(shù)據(jù)挖掘的研究給解決此類問題提供了一種新的思路。

　　時空數(shù)據(jù)挖掘即“從時空數(shù)據(jù)庫中發(fā)現(xiàn)知識”（Knowledge　Discovery　from　Spatio—Temporal　Data　bases），是指從時空數(shù)據(jù)庫中提取用戶感興趣的時空模式與特征、時空與非時空數(shù)據(jù)的普遍關(guān)系及其它一些隱含在數(shù)據(jù)庫中的普遍的數(shù)據(jù)特征，它是KDD技術(shù)在時空數(shù)據(jù)庫應(yīng)用的延伸，是數(shù)據(jù)挖掘近幾年發(fā)展起來的一個新研究領(lǐng)域。針對由RFID設(shè)備獲取物流信息的需求，選擇時空數(shù)據(jù)挖掘中的時空關(guān)聯(lián)規(guī)則的方法較為合適。文獻(xiàn)中研究移動物體時空數(shù)據(jù)預(yù)處理技術(shù)，為時空關(guān)聯(lián)規(guī)則數(shù)據(jù)統(tǒng)計提供基礎(chǔ)；文獻(xiàn)中對時空關(guān)聯(lián)規(guī)則算法進(jìn)行研究，得到了很多有趣的時空模式。上述算法適用于提取自由移動物體活動規(guī)律的情況。而在物流系統(tǒng)中，貨物的運送受配送車輛和線路的影響，需要對以自由移動物體為研究對象的時空關(guān)聯(lián)規(guī)則進(jìn)行改進(jìn)，以適用于具有路線約束的貨物運送時空模式的挖掘。

　　本文利用時空頻繁模式挖掘的基本思想，結(jié)合物流領(lǐng)域的專業(yè)知識，對物流貨物運送時空規(guī)律進(jìn)行提取，為物流公司線路優(yōu)化提供詳實科學(xué)的決策依據(jù)。借助于時空關(guān)聯(lián)規(guī)則挖掘中的時空頻繁模式來表示貨物在配送過程中的規(guī)律，如貨物于某時TIi從地點A裝載上車，于另一時間TIj從地點B卸載下車，這就是一個配送模式；當(dāng)貨物件數(shù)大于規(guī)定的閾值時，這就是一個頻繁的配送模式，反映了某一部分貨物的群體時空配送規(guī)律。結(jié)合有效的剪枝策略，可以獲取整個物流公貨物主要的時空流動規(guī)律。這是對物流RFID數(shù)據(jù)進(jìn)行時空模式挖掘的新探索，為獲取貨物主要的時空流動規(guī)律提供了新的方法與手段。

　　2　物流RFID數(shù)據(jù)庫時空模式挖掘的概念與符號定義

　　本文研究的對象是物流公司通過RFID設(shè)備獲取的貨物時空數(shù)據(jù)庫。從某一物流公司的貨物配送數(shù)據(jù)庫中，可得到表1的記錄形式：

 　　從表1中可以看出，物流公司通過RFID技術(shù)詳細(xì)記錄了貨物的動態(tài)信息，包括貨物從接貨到到達(dá)顧客手中所經(jīng)歷的地點與時間。有了這些信息，可以利用關(guān)聯(lián)規(guī)則挖掘哪些地點對或地點鏈?zhǔn)穷l繁出現(xiàn)的，據(jù)此可以進(jìn)行物流網(wǎng)優(yōu)化調(diào)整。

　　一個物流線路網(wǎng)G由一組不同的貨物配送線路Ii組成，且每條線路上分布有若干裝卸貨物的地點Sij。可以表示為：

　　式中，G一物流線路網(wǎng)；L一線路集合；Ii一第i條配送線路；S一裝卸站點集合；Sij一第i條配送線路上的第i個裝卸點。

　　每條配送線路都有一定的發(fā)送頻率。線路上任何相鄰兩個地點之間的一段稱為線段，不同的線路之間會有部分相交或不相交的線段。貨物從某一起點可能需要一次或多次轉(zhuǎn)運才到達(dá)收貨人的手中，形成一條裝卸點序列。當(dāng)某序列只包含兩個裝卸點，即起點與終點，說明此次配送沒有中途轉(zhuǎn)運；當(dāng)序列包含三個及以上裝卸點，即除起點與終點外，還包含中間的一個或幾個轉(zhuǎn)運點，說明此次配送中途進(jìn)行了轉(zhuǎn)運。本文借助于時空關(guān)聯(lián)規(guī)則挖掘中的時空模式來表示貨物在配送網(wǎng)中的運送情況，結(jié)合物流領(lǐng)域的專業(yè)知識，定義配送線路模式這一術(shù)語來表示貨物在配送網(wǎng)中的時空狀態(tài)，見定義1。

　　定義1   時空配送線路模式：帶時間屬性的配送路線，是由帶時間屬性轉(zhuǎn)運點所組成的序列，貨物在每個轉(zhuǎn)運點上都會停留一段時間，所以時間屬性采用時間TI表示。如式（2）所示：

 　　式中，R一帶時間屬性的轉(zhuǎn)運點集合和線路集合；
　　S一轉(zhuǎn)運點集合；
　　Si一第i個轉(zhuǎn)運站點；
　　T一所有轉(zhuǎn)運點對應(yīng)的時間集合；
　　ti一第i個轉(zhuǎn)運點對應(yīng)的時間；
　　L一轉(zhuǎn)運點涉及的配送線路集合。

　　根據(jù)式（2）中的s={s1，s2…，Sy}所含轉(zhuǎn)運點數(shù)量的不同，可分為直達(dá)的配送模式，即y=2，和轉(zhuǎn)運的配送模式，即y>2。

　　為了便于利用數(shù)據(jù)挖掘技術(shù)，在此用時空關(guān)聯(lián)規(guī)則對配送模式的表達(dá)方式進(jìn)行轉(zhuǎn)換。

　　定義2   直達(dá)路線的時空關(guān)聯(lián)規(guī)則：用時空關(guān)聯(lián)規(guī)則的表示方法描述的直達(dá)配送模式，即貨物于某一時間ti從裝載點si，裝載上車q1，于另一時間tj從卸載點sj卸載下車q2，就成一條配送的時空關(guān)聯(lián)規(guī)則ζi記為：

　　式中，ζi一帶時間屬性的直達(dá)路線的時空關(guān)聯(lián)規(guī)則:
　　si、sj一第i，j個裝卸點；
　　ti，tj一裝卸點所需時間段集合；
　　q1一裝載；
　　q2一卸載；
　　sup一支持?jǐn)?shù)；
　　m一滿足此條時空關(guān)聯(lián)規(guī)則的貨物件數(shù)。

{$page$}

　　定義3   轉(zhuǎn)運路徑的時空關(guān)聯(lián)規(guī)則：具有轉(zhuǎn)運關(guān)系的兩個或兩個以上的直達(dá)路徑時空關(guān)聯(lián)規(guī)則的組合。在時間ti從線路li的裝卸點si裝載的貨物，于另一時間tj從裝卸點sj卸載，又于時間tk在裝卸點sj裝上線路lj的車上，再于另一時間tg從sn卸下。可用式（4）表示:

 　　為了簡化，用ζ*來表示轉(zhuǎn)運路徑關(guān)聯(lián)規(guī)則，則有:

    把除裝卸點si之外同一條線路l1上的其它所有裝卸點稱為sielse，那么可以單獨地把某個裝卸點的裝卸載貨物情況看成一個特殊的時空關(guān)聯(lián)規(guī)則。

      定義4     裝載點的時空關(guān)聯(lián)規(guī)則：于某一時間ti從裝卸點si裝載的貨物，將于其后時間tielse在同配送線路的其它sielse卸載，用關(guān)聯(lián)規(guī)則形式表示：

      式中的0nζi表示裝載點的時空關(guān)聯(lián)規(guī)則。

　　定義5   卸載點的時空關(guān)聯(lián)規(guī)則：貨物于先于某一時間的時間從裝卸點Si裝載，于時間ti在裝卸點sielse卸載，用關(guān)聯(lián)規(guī)則的形式表示：

　　式（6）中的Offζi、表示卸載點的時空關(guān)聯(lián)規(guī)則。

　　這樣裝卸點、裝卸點對、裝卸點鏈在時空關(guān)聯(lián)規(guī)則上就有了統(tǒng)一的表述方式。

　　定義6  頻繁模式：當(dāng)某個關(guān)聯(lián)規(guī)則的支持?jǐn)?shù)大于一個設(shè)定的閾值時，這條關(guān)聯(lián)規(guī)則就是有趣的，是一個頻繁模式。這個設(shè)定的閾值稱為最小支持?jǐn)?shù)，用minsup表示。對應(yīng)上述各種規(guī)則就有了各自的頻繁模式。頻繁直達(dá)路徑的關(guān)聯(lián)規(guī)則是指在路線l；上，于某一時間t從裝卸點s裝載的貨物，將于某一時間tj從裝卸點sj卸載，用F=（f，I，q.）（，，q）pup=≥minsup]表示，所有的F‘組成的集合用Fζi表示。同理可得頻繁轉(zhuǎn)運路徑Fζ*，頻繁的裝載點F0nζ，頻繁的卸載點Foffζ等概念。

　　3　物流 

　　RFID數(shù)據(jù)庫時空模式挖掘的算法設(shè)計要想在上千萬條記錄中找出這些有趣的時空關(guān)聯(lián)規(guī)則是一件相當(dāng)不容易的事情，必須依靠有效的剪枝策略。根據(jù)物流專業(yè)領(lǐng)域的知識，可以得到以下的性質(zhì)：

　　性質(zhì)1：線路]i上頻繁的直達(dá)路徑必然頻繁的裝卸點集合中。可以直觀地想象，沒有很多貨物發(fā)運的裝載點，不可能成為頻繁直達(dá)路徑的前項；沒有很多貨物到達(dá)的卸載點，不可能成為頻繁直達(dá)路徑的后項。

     性質(zhì)2：線路]i和]j；頻繁轉(zhuǎn)運路徑必然發(fā)生在包含在具有轉(zhuǎn)運可能性的裝卸點的頻繁直達(dá)路徑的集合中。因為頻繁轉(zhuǎn)運路線時空關(guān)聯(lián)規(guī)則是用兩個或兩個以上的直達(dá)路徑時空關(guān)聯(lián)規(guī)則的組合進(jìn)行表示，所以頻繁轉(zhuǎn)運路徑必定出現(xiàn)在頻繁直達(dá)路徑的集合中。

      利用這些定義和性質(zhì)，就可以進(jìn)行物流配送數(shù)據(jù)庫時空頻繁模式挖掘。

　　（1）數(shù)據(jù)準(zhǔn)備。根據(jù)物流配送數(shù)據(jù)庫中的數(shù)據(jù)，得到各線路各個時段的貨物裝卸點OD矩陣。

　　（2）設(shè)定minsup的值，尋找滿足式（8）所列條件的頻繁裝載點集合FOnζ.和頻繁卸載點集合FOffζ，如式（9），（10）所示。

　　（3）利用性質(zhì)1來尋找頻繁直達(dá)路徑集合。由于一條路線上會有不同的車次，所以要用一個矩陣來表示各條路線不同車次的頻繁直達(dá)路徑，如（11）所示。

 　　式中Fζi表示線路li上的頻繁直達(dá)路徑集合，F(xiàn)ζij表示路線li上第j個車次頻繁直達(dá)路徑集合。

　　（4）獲取頻繁轉(zhuǎn)運路徑集合。在頻繁直達(dá)路徑集合式（11）中，針對具有轉(zhuǎn)運可能的裝卸點，根據(jù)貨物號進(jìn)行跟蹤，利用性質(zhì)2來尋找頻繁轉(zhuǎn)運路徑集合，如（12）所示。

 　　式中Fζ表示線路l上的頻繁轉(zhuǎn)運路徑集合，F(xiàn)‘表示路線l；上第j個頻繁轉(zhuǎn)運路徑集合。

　　4  實驗及其結(jié)果分析

　　為了能簡單有效地說明上述算法，我們從物流配送線路網(wǎng)中截取兩條具有代表性的單向線路l1和l2，它們有一個共同的裝卸點C。如圖1所示。

{$page$}

　　第一步根據(jù)貨物配送數(shù)據(jù)，得到線路l和l各個裝卸點裝卸貨物的件數(shù)，時間精度取到小時，見表2和表3。

 　　根據(jù)車輛的出行信息，可以得到線路l1和l2各裝卸點的時間列表，見表4和表5。

　　第二步在各條路線每個車次裝卸點OD中，獲取大于最小支持?jǐn)?shù)的各頻繁裝卸點。在本例中，設(shè)定minsup=10，則表2和表3中頻繁的裝卸有（AB）、（EFC），頻繁的下客裝卸點（BCD）、（CG）.如圖2和圖3所示：

　　根據(jù)性質(zhì)1可以得到線路l1上頻繁的直達(dá)路徑有: 

　　簡記為A==>C，如圖4所示。

　　線路l2上頻繁的直達(dá)路徑有：

       簡記為C==>G，如圖5所示。

       第四步在具有轉(zhuǎn)運可能的裝卸點c，對貨物進(jìn)行跟蹤，搜尋出這些貨物中后來又上另一輛貨車的貨物件數(shù)超過設(shè)定轉(zhuǎn)運支持?jǐn)?shù)的裝卸點，如圖6所示。

　　通過上述的實驗，驗證本文提出的物流RFID數(shù)據(jù)庫時李模式挖掘方法能快速獲取頻繁裝卸點、頻繁直達(dá)路徑和頻繁轉(zhuǎn)運路徑等。這些信息就可以為庫存控制和線路優(yōu)化提供決策依據(jù)。

　　5 結(jié)論及展望

　　隨著各種檢測設(shè)備與RFID技術(shù)的投入使用，物流公司的信息部門每天都可采集并存儲大量貨物運送方面的數(shù)據(jù)，但是這些積累的海量物流時空數(shù)據(jù)并未得到有效的組織和利用，很多潛在的物流運送線路規(guī)律并未發(fā)現(xiàn)，造成了數(shù)據(jù)資源的浪費。本文提出了利用數(shù)據(jù)挖掘技術(shù)來抽取這些隱含在數(shù)據(jù)中的潛在有用的規(guī)律。但是時空數(shù)據(jù)挖掘方法在很多方面都需要進(jìn)一步完善才能應(yīng)用到物流領(lǐng)域中，本文只是在這方面做了一些探索，需要進(jìn)一步研究的內(nèi)容還有很多，比如時空模式的可視化，挖掘算法的智能化，挖掘結(jié)果的后處理與利用問題等。