劉　佳，劉　琳，陳　偉

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

?

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

劉佳1，劉琳2，陳偉1

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

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

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

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

1.問題提出

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

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

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

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

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

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

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

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

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

(1)最近鄰查詢：根據(jù)實(shí)際查詢需要，近鄰可以是1個(gè)，也可以是K個(gè)(k個(gè)最近的目標(biāo)點(diǎn))，以下簡(jiǎn)稱KNN(k-NearestNeighbor)查詢。

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

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

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

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

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

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

3.最佳位置及路徑查詢

3.1 最佳位置查詢

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 最佳路徑選擇

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

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

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

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

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

(3) 不會(huì)特別疲憊。

根據(jù)上述條件，在選擇路徑中提取指標(biāo)為<景點(diǎn)游玩時(shí)間、餐飲、酒店>，并將游玩條件根據(jù)指標(biāo)項(xiàng)，分解如下：

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

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

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

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

4. 結(jié)論

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

參考文獻(xiàn)：

[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ù)范圍查詢算法研究,計(jì)算機(jī)科學(xué)，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

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

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

收稿日期：2015-10-08

中圖分類號(hào)：U12

文獻(xiàn)標(biāo)識(shí)碼：A

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