[發(fā)明專利]查詢最小距離和位置的動態(tài)監(jiān)控方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201310280203.6
• 申請日: 2013-07-04
• 公開（公告）號: CN103336824A
• 公開（公告）日: 2013-10-02
• 發(fā)明（設(shè)計）人: 姚斌;吳亦凡;李飛飛;肖小奎
• 申請（專利權(quán)）人: 上海交通大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海思微知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 31237
• 代理人: 鄭瑋

1.一種查詢最小距離和位置的動態(tài)監(jiān)控方法，其特征在于，包括：

給定一個客戶點的集合C和一個設(shè)施點的集合F，以及一個候選位置集合P,最小距離和位置為其中為客戶點c的加權(quán)吸引距離，w(c)是客戶點c的權(quán)重，如果客戶點c和設(shè)施點f在道路網(wǎng)絡(luò)中的距離d(c,f)是c和F中的點的極小值，則定義f是c的吸引者，c被f吸引，a(c)=d(c,f)為c的吸引距離；

根據(jù)路網(wǎng)中初始的設(shè)施點集合F和客戶點集合C獲取p;

根據(jù)路網(wǎng)中設(shè)施點集合F或客戶點集合C發(fā)生的更新隨時動態(tài)監(jiān)控p。

2.如權(quán)利要求1所述的查詢最小距離和位置的動態(tài)監(jiān)控方法，其特征在于，根據(jù)路網(wǎng)中初始的設(shè)施點集合F和客戶點集合C獲取p的步驟包括：

通過向表示路網(wǎng)的無向連通圖G^o=(V^o,E^o)插入所有的設(shè)施點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以及對應(yīng)的收益值m,其中，E_c為包含候選位置集合P中所有點的邊的集合，某個位置σ的收益值為局部最佳位置I為邊e上所有具有最大收益值的點集合；

根據(jù)所有邊上的局部最佳位置I選出對應(yīng)的收益值m最大的作為最大競爭力位置p。

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

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

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

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

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

初始化A(v)為空集；

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

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

5.如權(quán)利要求4所述的查詢最小距離和位置的動態(tài)監(jiān)控方法，其特征在于，根據(jù)已經(jīng)計算出的A(v_l)和A(v_r)計算e的局部最佳位置I以及對應(yīng)的收益值m的步驟包括：

計算e的兩個端點的收益值；

如果兩個端點的收益值不同，則返回收益值較大的那個端點作為e的局部最佳位置I，兩個收益值中較大的作為e的對應(yīng)收益值m；否則，將這兩個相等的收益值作為e的對應(yīng)收益值m，并考察e的中點的收益值，如果比端點收益值小，則將兩個端點作為e的局部最佳位置I，如果e的中點的收益值與兩個端點的收益值相等，則把整條邊e都作為局部最佳位置I。