[發明專利]面向大規模不確定物流網絡的需求概率查詢方法

有效

• 申請號: 201210248045.1
• 申請日: 2012-07-17
• 公開（公告）號: CN102799674A
• 公開（公告）日: 2012-11-28
• 發明（設計）人: 王國仁;袁野;孫永佼;趙相國;韓東紅;王斌
• 申請（專利權）人: 東北大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 沈陽東大專利代理有限公司 21109
• 代理人: 李運萍

技術領域

本發明屬于數據庫領域，特別涉及一種面向大規模不確定物流網絡的需求概率查詢方法。

背景技術

物流系統是一個網絡系統，既包括由物流線路與物流結點組成的實體網絡又包括由計算機和通信系統組成的虛擬網絡。無論是物流線路還是通信線路，它們僅僅具備傳輸貨物或信息的功能，而承擔發出與接受、轉換與控制等功能的則是物流結點，包括物資配送中心、倉庫、零售店等。物流結點不僅自身承擔多種物流功能，如對商品的加工、集中、中轉、分發，而且越來越多地執行指揮調度、信息處理等職能。物流結點能夠集物流集散、信息處理和控制等功能于一身，實現一體化運作，因而是物流系統的基礎和核心。

而在整個物流網絡系統中，物流線路規劃作為物流網絡體系中重要組成部份，也有著不可或缺的重要作用。對大多數企業來講，運輸成本通常代表物流成本中最大的單項成本。據統計，1997年，美國的物流超額運費高達450億美元；俄羅斯、法國和丹麥的各種運輸成本分別占了全國總支出的15%、9%和15%；而在食品行業中，配送成本占總物流成本近一半，附加值商品的配送成本占有比例更是高達70%。中國物流與采購聯合會課題組在其2005年的報告中指出，1991年以來，我國社會物流總額一直占到了GDP總額的五分之一；2005年上半年，我國社會物流總費用為1.4萬億元，相當于GDP總額的21.5%，其中運輸費用為7992億元，在物流總費用的比重達到了55.6%。這種高成本主要是由于物流網絡的不確定性造成的，主要體現在物流網絡結構、網絡運輸任務以及網絡環境都已呈現出明顯的動態性和隨機性。為此只有采用科學的方法來處理物流網絡的不確定性，才能提高運輸效率、減少成本。

不確定數據管理技術是當前數據庫技術的研究熱點，有著廣泛的理論和技術基礎。在物流配送領域，常需要將貨物在給定的時間內從一個地方運輸到另一個地方。如圖1所示，需要將貨物從s運輸到t，每條邊都有一個運輸時間上限（容量），需求查詢會提出能否在d時間內將貨物從s運輸到t。但由于交通流量、天氣等因素會使時間上限不再確定。已有大量的研究在分析道路交通網絡的不確定性，研究表明交通網絡的運輸時間上限符合離散高斯分布，即每邊的容量是一個隨機變量，有若干取值，每值對應一個存在概率。在此模型下，需求查詢會提出“在d時間內成功將貨物從s運輸到t的概率是多少?”。此問題的回答即是不確定圖（路網）的從s到t的需求查詢。

發明內容

本發明提供一種面向大規模不確定物流網絡的需求概率查詢方法。

定義1（不確定物流網絡）：將一個不確定物流網絡抽象成不確定圖。不確定圖是集合G=(V,E,Pr)，其中(V,E)是確定圖，Pr是邊集容量R的概率分布。每邊容量r(r∈R)是一離散隨機變量，其每一取值c_i:e→[0,∞)是定義在每條邊上的容量函數，該取值稱為一個概率狀態。

從定義1易知，確定圖是一個特殊的R概率為1的不確定圖，可表示為G=(V,E,R)，此時R是一確定值。在可能世界模型下，一個不確定圖可派生出一組確定圖G’=(V’，E’，R')，此確定圖稱為可能世界圖，簡稱可能圖，它滿足V'=V,

因為不確定圖不同邊容量的概率分布是相互獨立的，因此可能圖的概率為，

定義2（需求查詢）：給一個不確定圖G、其源節點、匯聚節點s和t、需求d，概率需求查詢返回s到t的需求概率：

qpr=ΣG′∈SR(G)Pr(G′)---(2)]]>

其中SR(G)是s到t滿足d的可能圖集合。可能圖G’滿足d被定義為G’的最大需求（最大網絡流）F(R')≥d。

本發明所用到的符號和意義見表1。