[發明專利]查詢最小化最大距離位置的動態監控方法及系統

有效

• 申請號: 201310279898.6
• 申請日: 2013-07-04
• 公開（公告）號: CN103336823A
• 公開（公告）日: 2013-10-02
• 發明（設計）人: 姚斌;吳亦凡;李飛飛;肖小奎
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海思微知識產權代理事務所(普通合伙) 31237
• 代理人: 鄭瑋

1.一種查詢最小化最大距離位置的動態監控方法，其特征在于，包括：

給定一個客戶點的集合C和一個設施點的集合F，以及一個候選位置集合P,最小化最大距離位置為p=argminp∈P(maxc∈C{a^(c)|F=F∪{p}}),]]>其中為客戶點c的加權吸引距離，w(c)是客戶點c的權重，如果客戶點c和設施點f在道路網絡中的距離d(c,f)是c和F中的點的極小值，則定義f是c的吸引者，c被f吸引，a(c)=d(c,f)為c的吸引距離；

根據路網中初始的設施點集合F和客戶點集合C獲取p;

根據路網中設施點集合F或客戶點集合C發生的更新隨時動態監控p。

2.如權利要求1所述的查詢最小化最大距離位置的動態監控方法，其特征在于，根據路網中初始的設施點集合F和客戶點集合C獲取p的步驟包括：

通過向表示路網的無向連通圖G^o=(V^o,E^o)插入所有的設施點f和客戶點c來將E^o中的邊劃分成新的邊，對于每一個點ρ∈C∪F，先考慮ρ所在的邊e∈E^o，令e的兩個端點為v_l和v_r，然后將e分為兩部分即從v_l到ρ和從ρ到v_r，以使ρ成為無向連通圖的一個新頂點，加入所有的新頂點以生成了一個新的無向連通圖G=(V,E)，且V=V^o∪C∪F；

對于每一條邊e∈E_c初始化計算其局部最佳位置I以及對應的收益值m,其中，E_c為包含候選位置集合P中所有點的邊的集合，某個位置的收益值m為在該位置建立新設施后所有客戶點的最大加權吸引距離的減少量，局部最佳位置I為邊e上所有具有最大收益值的點集合；

根據所有邊上的局部最佳位置I選出對應的收益值m最大的作為最小化最大距離位置p。

3.如權利要求2所述的查詢最小化最大距離位置的動態監控方法，其特征在于，對于每一條邊e∈E_c初始化計算其局部最佳位置I以及對應的收益值m的步驟包括：

通過Erwig和Hagen的算法來計算G中每一個頂點v的最近設施點f以及距離d(v,f)；

分別計算e的兩個端點v_l和v_r的吸引集合A(v_l)和A(v_r)，其中，給定一個頂點v，A(v)是包含v能吸引到的所有客戶點c以及對應距離d(c,v)的集合；

根據已經計算出的A(v_l)和A(v_r)計算e的局部最佳位置I以及對應的收益值m。

4.如權利要求3所述的查詢最小化最大距離位置的動態監控方法，其特征在于，已知一個頂點v，A(v)通過如下步驟獲取：

初始化A(v)為空集；

用Dijkstra算法按照到v的距離升序遍歷G中所有頂點；

對于每一個遍歷到的頂點v′，令a(v′)為v′到其最近的設施點f的距離，如果d(v,v′)≤a(v′)，并且v′是一個客戶點，則將把<v′,d(v′,v)>加入頂點v吸引集合A(v)后；如果d(v,v′)>a(v′)，則忽略所有以v′為端點的邊。