基于“路網(wǎng)數(shù)據(jù)庫”的最佳位置及路徑選擇研究

劉　佳，劉　琳，陳　偉

(1.中國環(huán)境管理干部學院，河北 秦皇島　066004；2.秦皇島職業(yè)技術(shù)學院，河北 秦皇島　066004)

?

基于“路網(wǎng)數(shù)據(jù)庫”的最佳位置及路徑選擇研究

劉佳1，劉琳2，陳偉1

(1.中國環(huán)境管理干部學院，河北 秦皇島066004；2.秦皇島職業(yè)技術(shù)學院，河北 秦皇島066004)

摘要：本文綜合“位置查詢”及“路徑查詢”為一體，同步解決最佳位置及路徑的查詢問題，并在此基礎上考慮其合理性，以滿足實際路網(wǎng)查詢與分析應用的要求。同時針對實際問題，進行實際案例分析，找出了影響效率的指標屬性，進而構(gòu)建了合理性路網(wǎng)最佳位置及路徑分析框架，有效地實現(xiàn)最佳位置及路徑的選擇問題。

關(guān)鍵詞：路網(wǎng)；數(shù)據(jù)庫；最佳位置；最優(yōu)路徑

河北省教育廳青年基金項目(基于空間網(wǎng)絡的“興趣集群”的最優(yōu)選擇查詢研究，QN2015133)。

1.問題提出

目前，關(guān)于空間信息查詢的研究越來越多，包括：最近鄰查詢和它的變體。他們可以應用在餐飲、娛樂、醫(yī)療救護、事故救援、區(qū)域分析、數(shù)量統(tǒng)計等各方面，幾乎囊括了生活中的各行各業(yè)。尤其在路網(wǎng)上的位置查詢服務，應用極廣。(最佳路徑選擇是空間信息查詢中的關(guān)鍵技術(shù)，是智能交通及路網(wǎng)應用的重要指標。在實時性和有效性上完善路徑選擇算法，優(yōu)化查詢效率及準確度，提高實際應用價值，建立高效的路網(wǎng)分析策略。)例如：查找最近位置(查找最近的加油站)、查找最合適位置(某個商店開設分店)、查找最優(yōu)路徑(旅游景點的游玩順序)等。根據(jù)實際路網(wǎng)應用問題，最佳位置及路徑選擇問題毫無疑問地成了目前路網(wǎng)的研究重點。目前常見的路網(wǎng)應用問題有如下兩類：

(1)查找最近目標，如：加油站、旅游景點、醫(yī)院等，現(xiàn)有的系統(tǒng)直接通過距離測算，查找最近的一個。

(2)查找最佳位置，如：在幾塊候選土地上開發(fā)項目，哪個最合適？現(xiàn)有的系統(tǒng)也是直接通過距離量算，對附近周圍同類型項目的距離進行分析，然后來選擇合適的地方。

然而，多數(shù)的路網(wǎng)上的研究大多基于距離量算，如：歐氏距離和路網(wǎng)距離，從它們的分析方式就能夠看出其存在選擇的盲目性：有的應用不能只靠距離測算，比如上邊提到的“查找最近醫(yī)院”，距離最小了，但是沒有相關(guān)科室或不是優(yōu)勢專業(yè)，這給急病的選擇者都帶來了不便。而“查找最合適位置”的分析中，同類設施的距離考慮了，但是其服務門類，服務范圍等屬性數(shù)據(jù)都對新建設施產(chǎn)生影響，這些屬性數(shù)據(jù)有的時候比距離重要的多，這顯然是不合理的。

綜上所述，本文基于上述問題，提出選擇合理性要求，利用目標的屬性數(shù)據(jù)信息作為評價指標，將“最佳位置和最佳路徑”選擇綜合考慮，在一個模式架構(gòu)下，解決多個問題。這種方式不僅能夠解決目前路網(wǎng)查詢的盲目性，還具有以下兩個意義：

(1)將最優(yōu)位置及路徑查詢由理論過渡到實際的路網(wǎng)應用，為現(xiàn)實的交通應用、選址分析、綜合價值計算等提供理論依據(jù)。

(2)考慮到實際應用價值，對查詢本身進行合理性評估，根據(jù)各個查詢屬性值進行不同的權(quán)值設定，使得最終查詢結(jié)果應用性更強，應用價值更高。

2.國內(nèi)外研究現(xiàn)狀

目前，國內(nèi)外關(guān)于路網(wǎng)信息檢索內(nèi)容主要集中在：最近鄰查詢、選址分析、索引機制。

(1)最近鄰查詢：根據(jù)實際查詢需要，近鄰可以是1個，也可以是K個(k個最近的目標點)，以下簡稱KNN(k-NearestNeighbor)查詢。

KNN查詢方法以傳統(tǒng)的路徑選擇算法Dijktra算法為代表，在Dijktra算法基礎上做些優(yōu)化選擇，其在小數(shù)據(jù)網(wǎng)中應用較多，但卻不能支持大數(shù)據(jù)的路網(wǎng)，其查詢和存儲的代價都很高，尤其當數(shù)據(jù)量很大的時候，這種方法基本就是不可用。

(2)選址分析：也可稱為最佳位置查詢，以下簡稱OL(Optimal Locations)查詢。

OL查詢是對空間信息資源的合理規(guī)劃，部分文獻對最優(yōu)位置查詢也提出了多種方法，但前提是假設現(xiàn)有查詢目標存在Lp空間中，這種假設在實際中很受限制，因為空間位置之間的活動常常受其實際路網(wǎng)情況的約束，所以兩個位置點之間的距離不是簡單的Lp空間距離，故相應的實用價值也隨之降低。

(3)索引機制：有效的剪枝策略，能夠快速地引導查詢算法，避免重復查詢。

路網(wǎng)上信息量太大，實施查詢都需要創(chuàng)建索引，無論是樹結(jié)構(gòu)還是圖結(jié)構(gòu)，都可以通過索引有效地實施剪枝策略，過濾不必要的查詢，提高查詢速度和準確度。

由上述分析可知，近年來路網(wǎng)信息查詢一直處在不斷地研究過程中，但都是基于距離求得最短路徑或多個近鄰。隨著路網(wǎng)信息的增加，人們獲取的信息除了滿足距離最短以外，還要考慮信息應用價值和意義。

3.最佳位置及路徑查詢

3.1 最佳位置查詢

最佳位置查詢常常涉及設施的選址問題，可用于城市規(guī)劃、商業(yè)選址等。而這樣的問題僅僅將距離和關(guān)鍵屬性作為檢索條件是不足夠的，因為不同的用戶關(guān)注的屬性不同，不能一概而論。所以本文將討論如何給屬性數(shù)據(jù)設置動態(tài)權(quán)值，用戶在應用的時候可以自行選擇權(quán)值設置，來滿足各自的需求。

例如：某個人想開個童裝店，想選取一塊合適的地方，這個地方應具備以下條件的組合：

(1) 交通便利(方便逛街)

(2) 人口密集(保證基礎的銷售量)

(3) 周邊有童裝店(在童裝店一條街上最好，有對比往往更好銷貨)

(4) 小區(qū)為近5年內(nèi)新建小區(qū)(青年人多，有小孩)

(4)周邊有時尚女裝店(通常都是媽媽給孩子買衣服)

P=1×0.3+1×0.3+1×0.2+0×0.1+0×0.1=0.8

最終的值越接近于1，越符合要求。為方便理解，本方法將條件f做了0或1的設置，而現(xiàn)實中，它的取值范圍應該更寬，而不僅僅是兩個值，比如仍然是上述案例：

(1) 交通便利程度不同，取值也不同，可以查詢點為始點，對周邊最近交通站點做距離計算，計算值作為條件基礎值。

(2) 人口密度也可以劃分不同范圍，根據(jù)年齡、消費水平等屬性數(shù)據(jù)做基礎參考值，綜合形成條件基礎值。

(3) 現(xiàn)有的童裝店應該如何分布，對于商業(yè)區(qū)，應該聚集分布較好，即某個范圍內(nèi)存在的越多越好，越能吸引更多人；反之，如果是居民區(qū)，消費范圍固定，那就不宜過多，否則利益被分割。所以，根據(jù)實際需求情況決定該條件的基礎值。

(4) 選擇小區(qū)周邊，那么一定重點考慮父母年齡階段，才能保證童裝有基礎的需求。

(5) 周邊的輔助條件雖然不是重點，但是在某些條件下起到很好地促進作用。時尚女裝是年輕媽媽的最愛，如果它與童裝店鄰接，那么媽媽們逛完女裝店會不自覺地逛童裝，而不一定是需要了才去，這樣更能增加消費。

所以，對于公式P=∑f×q，其f與q的條件基礎值由用戶自行設定，那樣更符合實際需要。

3.2 最佳路徑選擇

目前多數(shù)的空間路徑選擇都是基于“最短路徑” 的思想，而最短路徑多基于歐式空間量算的較多。在路網(wǎng)的應用上，實際的最短路徑與歐式量算的可能剛好相反。同理，最短路徑也僅僅考慮距離因素，忽視了其目標的有效性。最簡單的例子：跑高速的車需要加油了，按照最短路徑找到的地方?jīng)]有該車對應的油號，甚至是什么油號的也沒有了，這種情況很糟糕，卻是實際存在的。所以， 我們提出了最佳路徑的選擇。

最佳路徑即無論從距離、時間、有效性等方面均能滿足查詢用戶的要求。

例如：去某個城市旅游，想查詢一條“理想” 的游玩路徑，其“理想”表現(xiàn)在：

(1) 最大合理化利用時間，保證每個景點在指定的時間內(nèi)玩好。

(2) 路徑上有餐飲、休息場所。

(3) 不會特別疲憊。

根據(jù)上述條件，在選擇路徑中提取指標為<景點游玩時間、餐飲、酒店>，并將游玩條件根據(jù)指標項，分解如下：

(1) 按照人一天正常的游玩時間計算：游玩4-5個小時，加上路程時間1-2個小時，不會太疲憊。

(2) 如果景點小，則可分成兩部分，但應該在休息處附近，方便中午休息。如果景點大，則設置全天，午餐選擇景點自助更劃算。

(3) 如果在一個城市游玩，那么住宿點可以根據(jù)景點位置固定1-2個，然后設置路線。

根據(jù)上述指標，將住宿點作為查詢點，找到目標的最佳位置(按照3.1中方法)，再將最佳位置組成路線，形成最佳路徑。不同用戶的指標項不同，所以同樣的旅游城市，同樣的景點，針對用戶的最佳路徑也會不同。用戶可以將歷史數(shù)據(jù)作為參考，調(diào)整重組條件，形成自己的最佳路徑。

4. 結(jié)論

最佳位置及路徑查詢與我們的生活息息相關(guān)，甚至無處不在，它符合實際應用，使得查詢變得“合理化”、“智能化”、“個性化”，從幾個角度降低了各自的應用成本。同時，它也使實際應用達到合理調(diào)配資源的作用。

參考文獻：

[1]Sankaranarayanan, J., Samet, H., Alborzi, H.: Path oracles for spatial networks. PVLDB 2(1), 1210-1221 (2009)

[2]Bin Yao, Xiaokui Xiao, Feifei Li, YifanWu, Dynamic Monitoring of Optimal Locations in Road Network Databases.(VLDB),pp:1-23(2013)

[3]Ruicheng Zhong, Guoliang Li, Kian-Lee Tan,Lizhu ZhouG-tree:An Efficient Index for KNN Search on Road Networks(CIKM),pp:39-48(2013)

[4]李艷紅,黃群,蔣宏,李國徽.路網(wǎng)中空間關(guān)鍵字連續(xù)范圍查詢算法研究,計算機科學，2014，41(7)

The Optimum Location and Path Selection Research Based on "Road Network Database"

LIU Jia1，LIU Lin2，CHEN Wei1

(1.Environmental Management College of China, Qinhuangdao 066004, China;

2. Qinhuangdao Institute of Technology, Qinhuangdao 066004, China)

Abstract:This paper integrates the "location query" and "path query, synchronously solves the problem of optimum location and the path query, and on this basis, considers the rationality, to meet the requirements of the actual road network query and analytical application, rather than just the distance analysis. Based on the practical problems, this paper, through practical case analysis, finds out the index attributes of query efficiency, then builds the reasonable optimum location and path analysis framework of road network, effectively achieving the optimum location and path selection questions.

Key words:road network; database; optimum location; optimal path

作者簡介：劉佳(1980- )，女，在讀博士，中國環(huán)境管理干部學院教務科研處副教授，研究方向：數(shù)據(jù)庫查詢技術(shù)。

基金項目：河北省教育廳青年基金項目(基于“路網(wǎng)數(shù)據(jù)庫”的最佳位置及路徑選擇研究，QN20141059)。

收稿日期：2015-10-08

中圖分類號：U12

文獻標識碼：A

文章編號：1671-3974(2015)04-0062-03