基于GIS和Dijkstra算法的高校學(xué)生家訪路徑規(guī)劃研究

葛琳琳，張 威

（遼寧石油化工大學(xué) 遼寧 撫順　113001）

基于GIS和Dijkstra算法的高校學(xué)生家訪路徑規(guī)劃研究

葛琳琳，張 威

（遼寧石油化工大學(xué) 遼寧 撫順113001）

隨著高校招生規(guī)模的不斷擴大，高校學(xué)生的數(shù)量也急劇增加。針對在高校學(xué)生家訪過程中，如何高效快速尋找出一條滿足符合條件（時間、費用）的路徑的問題。文中采用了結(jié)合GIS數(shù)據(jù)和Dijkstra算法，通過Matlab隨機生成兩地之間收費和擁堵度，模擬多因素作用下的路徑的選擇，得出符合時間或費用最優(yōu)的路徑規(guī)劃方案。

Dijkstra算法；GIS；家訪路徑規(guī)劃；權(quán)重；Matlab仿真

隨著高校招生規(guī)模的不斷擴大，高校學(xué)生數(shù)量急劇增加，在有限的資金條件下，利用寒暑假的有限時間，對盡可能多的高校學(xué)生進行家訪，是高校學(xué)生工作者需要考慮的問題。傳統(tǒng)的做法是利用交通導(dǎo)航系統(tǒng)來對高校學(xué)生家訪路徑進行規(guī)劃。然而，在導(dǎo)航系統(tǒng)進行路徑規(guī)劃過程中，不一定要設(shè)計出一個最短的路徑，有時需要基于多方面因素（如費用，路況等）考慮的導(dǎo)航系統(tǒng)可能更加合適高校學(xué)生家訪的路徑規(guī)劃。

文中通過聯(lián)合分析路途中起始點到目的地的距離、兩地之間的費用情況以及兩地之間的擁堵程度進行考慮，同時在為了彌補Dijkstra算法本身只能求解出一條最短路徑的缺陷，通過標(biāo)識矩陣對合理路徑進行標(biāo)識，利用回溯的方法求出其他的一些合理路徑。這樣在求得多條路徑規(guī)劃的情況下，供家訪人員進行選擇，在進行家訪之前就可以對每次家訪的時間、花費和家訪學(xué)生的數(shù)量有效的控制。

1　GIS數(shù)據(jù)特點

使用軟件所提供的上海交通的矢量地圖，矢量地圖如圖1所示，GIS矢量圖去除了河流，只保留了重點的街道結(jié)合，交通圖主要由眾多的街道相交、相連而成，同時交通網(wǎng)絡(luò)圖又縱橫交織、錯綜復(fù)雜［1-3］。

圖1　交通網(wǎng)絡(luò)圖

在交通網(wǎng)絡(luò)中，街道間的地理位置關(guān)系相當(dāng)復(fù)雜，一條街道可能與若干條街道相連且相交、相連的模式復(fù)雜。為了避免考慮過多的考慮街道間的拓撲關(guān)系，抽取交通圖街道交叉口作為分析對象之一，并對分析的另一對象——街道以交叉路口為點進行分割成線段。這樣，整個GIS交通網(wǎng)絡(luò)圖將由交叉路口和線段組成，并定義交叉路口為網(wǎng)絡(luò)圖的節(jié)點，路段為網(wǎng)絡(luò)圖的邊。可網(wǎng)絡(luò)圖中，可以得到以下特點［4-6］：

1）網(wǎng)絡(luò)中節(jié)點和邊的數(shù)目遠在100個以上：

2）在城市1：100（或以上）的地圖上，路段（網(wǎng)絡(luò)邊）近似直線或弧度數(shù)不大的弧，尤其在經(jīng)過規(guī)劃的現(xiàn)代化大都市。

3）網(wǎng)絡(luò)的拓撲關(guān)系圖復(fù)雜。

根據(jù)上述城市網(wǎng)絡(luò)圖的特點，可以作以下分析［7-8］：

1）所有的城市路段都是直的，對于弧度稍大的路段，為了求解弧度間的夾角方便并使所求得夾角能夠正確反映弧段間的相對位置關(guān)系，如圖2可通過在路段的拐點處加一個節(jié)點的方法來減小弧的度數(shù)，使得原來的路段分解成兩個弧度較小的路段，即在網(wǎng)絡(luò)中增加一個節(jié)點，把一條邊分解為兩條邊，每條邊都可以看作直線進行角度的運算；

2）道路是雙向可通的；

3）節(jié)點都為實節(jié)點。

圖2　加節(jié)點減小弧度法示意圖

通過上述方法對圖1中標(biāo)記為紅色的處求解出兩兩之間的權(quán)值。

2　算法設(shè)計

算法是在路徑規(guī)劃過程中根據(jù)不同的權(quán)重因素來進行設(shè)計。比如在行進路途行駛過程中所花費的費用、時間的長短等因素設(shè)置為不同的權(quán)重所等到的路徑規(guī)劃［9-10］。

2.1只考慮主要因素

假設(shè)在實際路徑規(guī)劃中，在路程花費的時間作為主要的影響因子，算法為：

1）導(dǎo)入GIS數(shù)據(jù)；

2）在GIS數(shù)據(jù)中添加需要家訪的學(xué)生家庭地址作為GIS數(shù)據(jù)中的節(jié)點；

3）將當(dāng)前位置做為起始位置，添加的節(jié)點做為目的位置；

4）將當(dāng)前位置與目標(biāo)位置進行比較。如相等推出；否者轉(zhuǎn)入5）；

5）將路程的花費時間做為主要因素進行Dijkstra算法規(guī)劃，路徑規(guī)劃過程中，需要實時獲取路況信息，將道路擁堵時間及行車時間同時考慮到整個路程的花費中；

6）如果沒有路況信息發(fā)生變化，則按照規(guī)劃的路徑行駛；否則轉(zhuǎn)入3）。

2.2基于GIS和Dijkstra算法

考慮用戶在規(guī)劃路徑時不僅要對主要因素進行考慮，同時也要對其他因素（如花費等）進行一個綜合的考慮，我們得到基于GIS和Dijkstra算法，其算法流程如圖3所示。

圖3　基于GIS和Dijkstra算法流程圖

3　仿真研究

采用圖1所示的GIS數(shù)據(jù)導(dǎo)入matlab中進行路徑規(guī)劃仿真，使用數(shù)據(jù)的節(jié)點為圖1的黑色字體標(biāo)記的久事大廈、上海電信科技發(fā)展公司、金外灘花園東門、復(fù)興商務(wù)大廈、海琪園、海琪園南門、象山建筑設(shè)計有限公司、東仁商貿(mào)中心、上海灘花園9個節(jié)點，同時隨機生成兩地之間的收費價格和擁堵度的值。三組數(shù)據(jù)如圖4，圖5，圖6所示。

圖4　兩地之間的距離

圖5　兩地之間收費價格

圖6　兩地之間擁堵情況

模擬家訪從節(jié)點1到節(jié)點8的路徑搜索過程。得出從起始點1到目標(biāo)點8，以路程為主要考慮因素的經(jīng)過節(jié)點的選擇；以費用為主要考慮因素的經(jīng)過節(jié)點的選擇；以擁堵為主要考慮因素的經(jīng)過節(jié)點的選擇；如圖7所示。

圖7　路徑的選擇

可以看出在出于對總共花費代價上面的考慮因素，建議家訪路徑使用方案一為路程優(yōu)先或者方案三為擁堵優(yōu)先。除此之外在某種特殊的情況下起始點和目標(biāo)點相同的情況下，雖然所有的路徑不同但所走的路程卻是相同的。

4　結(jié)果分析

在仿真研究中我們只考慮的以某一個主要因素，求出了主要因數(shù)最小值一個解，但是有可能都是最小值的方案有不止一種。這種情況下就可能會丟失一部分有參考價值路徑選擇。如圖8中，從到同時有3條都是最短的路徑。如果只求最小解，就可能丟失2個解。

圖8　節(jié)點拓撲網(wǎng)絡(luò)圖

由圖可得鄰接矩陣為：

1）通過Dijsktra算法求解得到以到其他頂點最短路徑長度為v4，即d到v2，v3，v4，v5，v6的長度分別為20，10，50，30，100。

2）我們通過根據(jù)數(shù)組d和矩陣A來構(gòu)造一個標(biāo)識矩陣F，用來存儲從v1到其他節(jié)點求解最短路徑時所有的前趨節(jié)點。假設(shè)節(jié)點是節(jié)點的前趨節(jié)點那么在矩陣F中，把矩陣F中的相應(yīng)位置標(biāo)記為1；否則標(biāo)記為0。標(biāo)記的方法為：若di+aij=dj，那么fji=1；否則fji=0。

3）依據(jù)d=［0，20，10，50，30，100］和標(biāo)識矩陣F聯(lián)合求解。假設(shè)以v1為起始點以v4為目標(biāo)點。求解從v1到v4為的過程可以化解為v4節(jié)點為棧底，v1節(jié)點為棧頂，采用回溯求解。如果表示標(biāo)識矩陣fji=0，把節(jié)點壓入棧。否則跳過。直達找到起始節(jié)點，算法結(jié)束。

4）把棧中的節(jié)點順序出棧就可以得到了多因素的路徑規(guī)劃。

5　結(jié)束語

考慮多因素選擇最短路徑更加的符合路徑規(guī)劃的實際用途，同時它也是交通網(wǎng)絡(luò)的重要組成部分。本文結(jié)合實際情況，通過引入權(quán)值的概念，用matlab對GIS中多因素聯(lián)合的數(shù)據(jù)進行路徑規(guī)劃仿真測試，取得了理想的結(jié)果。在高校學(xué)生家訪的實際應(yīng)用中，可以針對相同區(qū)域的多個學(xué)生家庭住址進行標(biāo)注，跨學(xué)院，跨專業(yè)的分多組家訪人員同時進行交叉家訪，可以更好的提高時間和資金的利用率。

［1］王防修，周康．基于回溯法的Dijkstra算法改進及仿真［J］．計算機仿真，2013（11）：352-355．

［2］蘇寶莉，李寧．Dijkstra算法優(yōu)化及在GIS系統(tǒng)中求最佳路徑的應(yīng)用［J］．遙感技術(shù)與應(yīng)用，2013（5）：866-870．

［3］黃震，薛文科，李鵬，等．Dijkstra算法在停車誘導(dǎo)系統(tǒng)中的應(yīng)用［J］．計算機時代，2013（12）：38-41．

［4］王笑京，沈鴻飛，汪林．中國智能交通系統(tǒng)發(fā)展戰(zhàn)略研究［J］．交通運輸系統(tǒng)工程與信息，2006（4）：9-12．

［5］Yong Deng，Yuxin Chen，Yajuan Zhang，et al．Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment［J］.Applied Soft Computing Journal，2011：123-135．

［6］陳益富，盧瀟，丁豪杰．對Dijkstra算法的優(yōu)化策略研究［J］．計算機技術(shù)與發(fā)展，2006（9）：73-75．

［7］謝輝，董德存，歐冬秀．基于物聯(lián)網(wǎng)的新一代智能交通［J］．交通科技與經(jīng)濟，2011（1）：33-36．

［8］張德全，吳果林．最短路問題的Floyd算法優(yōu)化［J］．許昌學(xué)院學(xué)報，2009（2）：10-13．

［9］葛琳琳．模糊控制在布料小車定位系統(tǒng)中的應(yīng)用［J］．遼寧石油化工大學(xué)學(xué)報，2014，34（5）：52-56．

［10］葛琳琳，張威．?dāng)?shù)字化檔案IP網(wǎng)網(wǎng)絡(luò)設(shè)計方法的研究與應(yīng)用［J］．遼寧石油化工大學(xué)學(xué)報，2015，35（1）：62-66．

Based on GIS and Dijkstra algorithm the path planning research for university students visiting

GE Lin-lin，ZHANG Wei
（Liaoning Shihua University，F(xiàn)ushun 113001，China）

With the university student scale uninterrupted growth，the number of university students also increased dramatically.In the process of university student visits，how to quickly and efficiently find out a optimal（time，cost）path.In this paper，we used the combination of GIS data and Dijkstra algorithm，through the Matlab random generated between the two charges and congestion，to simulate the multiple condition of the path selection，the path planning scheme with time or cost optimization.

dijkstra algorithm；GIS；visit path planning；weight；matlab simulation

TN01

A

1674－6236（2016）09-0056-04

2015-10-19稿件編號：201510118

撫順市科學(xué)技術(shù)發(fā)展資金計劃項目（FSKJHT201548）；大學(xué)生創(chuàng)新創(chuàng)業(yè)資助項目（201410148060；201510148068）

葛琳琳（1977—），女，遼寧沈陽人，碩士。研究方向：嵌入式系統(tǒng)設(shè)計。