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

葛琳琳，張 威

（遼寧石油化工大學 遼寧 撫順　113001）

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

葛琳琳，張 威

（遼寧石油化工大學 遼寧 撫順113001）

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

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

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

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

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

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

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

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

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

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

3）網(wǎng)絡的拓撲關系圖復雜。

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

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

2）道路是雙向可通的；

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

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

通過上述方法對圖1中標記為紅色的處求解出兩兩之間的權值。

2　算法設計

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

2.1只考慮主要因素

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

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

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

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

4）將當前位置與目標位置進行比較。如相等推出；否者轉入5）；

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

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

2.2基于GIS和Dijkstra算法

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

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

3　仿真研究

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

圖4　兩地之間的距離

圖5　兩地之間收費價格

圖6　兩地之間擁堵情況

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

圖7　路徑的選擇

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

4　結果分析

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

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

由圖可得鄰接矩陣為：

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

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

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

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

5　結束語

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

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

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

［3］黃震，薛文科，李鵬，等．Dijkstra算法在停車誘導系統(tǒ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］．計算機技術與發(fā)展，2006（9）：73-75．

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

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

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

［10］葛琳琳，張威．數(shù)字化檔案IP網(wǎng)網(wǎng)絡設計方法的研究與應用［J］．遼寧石油化工大學學報，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

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

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