基于Android的校園導(dǎo)航系統(tǒng)路徑規(guī)劃的研究與應(yīng)用

1、基于Android的校園導(dǎo)航系統(tǒng)路徑規(guī)劃的研究與應(yīng)用摘要：以高校為研究對(duì)象，將數(shù)字校園與GPS手機(jī)導(dǎo)航系統(tǒng)相結(jié)合，利用移動(dòng)GIS的先進(jìn)性，在目前最流行的Android平臺(tái)下，結(jié)合ESRI推出的ArcGISAndroidAPI插件，設(shè)計(jì)了一款校園智能手機(jī)導(dǎo)航系統(tǒng)。以中北大學(xué)為例，完成了系統(tǒng)的架構(gòu)設(shè)計(jì)，介紹了數(shù)據(jù)組織及系統(tǒng)的功能，經(jīng)過(guò)對(duì)比三種經(jīng)典的最短路徑算法后選擇采用Dijkstra算法來(lái)實(shí)現(xiàn)校園智能手機(jī)導(dǎo)航系統(tǒng)中最短路徑的選擇。該校園智能手機(jī)導(dǎo)航系統(tǒng)的實(shí)施，為校園新生及校外來(lái)訪人員提供了方便、快捷的智能導(dǎo)航服務(wù)。關(guān)鍵詞：GPS手機(jī)導(dǎo)航；移動(dòng)GIS;ArcGISforAndroid;Dijkst

2、ra算法；最短路徑中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2014)06-1294-05ResearchandApplicationofCampusNavigationSystemPathPlanningBasedonAndroidWUQi1,LINJing1,YANGJiang-tao2,3(1.SchoolofComputerScienceandControlEngineering,NorthUniversityofChina,Taiyuan030051,China;2.ScienceandTechnologyonElectronicTestandMeasurem

3、entLaboratory,NorthUniversityofChina,Taiyuan030051,China;3.KeyLaboratoryofInstrumentationScience&DynamicMeasurementofMinistryofEducation,NorthUniversityofChina,Taiyuan030051,China)Abstract:RegardingcollegesanduniversitiesastheresearchobjectsandcombiningthedigitalcampuswithGPSmobilenavigationsystemas

4、martphonecampusnavigationsystemisdesignedbyusingthemobileGIS,AndroidplatformandESRIsArcGISAndroidAPIplug.TakingthecampusofTheNorthUniversityofChinaasanexample,thepaperrealizesthedesignofsystemarchitecturedescribesdataorganizationandthefunctionofsystem.Aftercomparingthreekindsofclassicalshortestpatha

5、lgorithms,theauthorsselectDijkstraalgorithmtoachievetheshortestpathselectioninthesmartphonecampusnavigationsystem.Theimplementationofthesystemprovidesaconvenient,fastandintelligentnavigationservicesforfreshmenandvisitors.Keywords：GPSmobilenavigation;mobileGIS;ArcGISforAndroid;Dijkstraalgorithm;short

6、estpath隨著高校校園的逐漸擴(kuò)建以及對(duì)外交流的日益增多，來(lái)高校參觀、訪問(wèn)的人也越來(lái)越多，但高校面積一般都很大，機(jī)構(gòu)和重要建筑分布錯(cuò)綜復(fù)雜，來(lái)訪者要經(jīng)過(guò)一番周折才能到達(dá)目的地。而且高校一般很少提供紙質(zhì)的地圖向來(lái)訪者提供導(dǎo)航服務(wù)，因此，建立具有校園信息查詢、智能導(dǎo)航服務(wù)等功能的系統(tǒng)，對(duì)高校提高人性化服務(wù)水平很有必要。目前，國(guó)內(nèi)高校對(duì)于基于PC的校園智能導(dǎo)航研究得比較多，如清華大學(xué)虛擬校園、華中科技大學(xué)校園導(dǎo)航系統(tǒng)。相比之下，大部分高校對(duì)Android系統(tǒng)上的校園導(dǎo)航都缺少研究，而今Android開(kāi)發(fā)技術(shù)日新月異，將傳統(tǒng)PC機(jī)的導(dǎo)航系統(tǒng)用Android技術(shù)實(shí)現(xiàn)已成為可能。隨著移動(dòng)通信的發(fā)展，手機(jī)

7、已經(jīng)不僅僅是解決通話的問(wèn)題了，它漸漸成了集通信手持電腦于一體的移動(dòng)計(jì)算工具，人們對(duì)手機(jī)所賦予的功能也已經(jīng)擴(kuò)展到分布式計(jì)算、移動(dòng)位置服務(wù)等更高端的領(lǐng)域。導(dǎo)航軟件在智能手機(jī)中的應(yīng)用現(xiàn)已成為研究熱點(diǎn)之一，越來(lái)越多的互聯(lián)網(wǎng)應(yīng)用被移植到智能手機(jī)中來(lái)，不但充分發(fā)揮數(shù)據(jù)業(yè)務(wù)運(yùn)營(yíng)商的潛力，而且極大的提高了用戶對(duì)手機(jī)多功能需求的滿意度，給人們的生活帶來(lái)了方便。本課題基于這種考慮，設(shè)計(jì)了一種基于Android的校園智能手機(jī)導(dǎo)航系統(tǒng)。采用Dijkstra算法并利用GIS系統(tǒng)的空間數(shù)據(jù)特性，根據(jù)實(shí)際情況對(duì)任意兩點(diǎn)間最短路徑進(jìn)行規(guī)劃，在智能手機(jī)平臺(tái)上實(shí)現(xiàn)了優(yōu)化路徑選易于開(kāi)發(fā)、管理和升既方便了新生和校外來(lái)?yè)瘢瑸樾律托Ｍ?/p>

8、來(lái)訪人員提供了非常便捷的服務(wù)。本系統(tǒng)實(shí)用性強(qiáng),級(jí)，很好地解決了初次來(lái)學(xué)校的新生和校外來(lái)訪人員所遇到的問(wèn)題，訪人員，又提高了學(xué)校的美譽(yù)度，具有很好的應(yīng)用價(jià)值1。1系統(tǒng)開(kāi)發(fā)理論基礎(chǔ)1.1系統(tǒng)背景介紹校園是大學(xué)生日常活動(dòng)的主要空間。大學(xué)校園通常具有面積大、開(kāi)放性強(qiáng)、建筑布局分散、各類設(shè)施雜亂等特點(diǎn)，校園地理信息相對(duì)來(lái)說(shuō)比較復(fù)雜。這給校園內(nèi)的每一個(gè)人尤其是對(duì)大一新生和校外來(lái)訪人員帶來(lái)諸多不便。因此，開(kāi)發(fā)出一個(gè)為新生和校外來(lái)訪人員提供校園信息服務(wù)的智能手機(jī)導(dǎo)航系統(tǒng)十分必要2,3。1.2移動(dòng)GIS技術(shù)地理信息系統(tǒng)（簡(jiǎn)稱GIS）4是一種特定的十分重要的空間信息系統(tǒng)，是在計(jì)算機(jī)軟、硬件系統(tǒng)支持下，對(duì)整個(gè)或部分

9、地球表層（包括大氣層）的有關(guān)地理分布數(shù)據(jù)進(jìn)行采集、存儲(chǔ)、管理、運(yùn)算、分析、顯示和描述的技術(shù)系統(tǒng)。移動(dòng)GIS5是GIS（地理信息系統(tǒng)）從靜態(tài)走向動(dòng)態(tài)環(huán)境的重大發(fā)展，通過(guò)綜合運(yùn)用GPS的精確定位技術(shù)、便攜移動(dòng)設(shè)備（如掌上電腦、智能手機(jī)）、移動(dòng)通信技術(shù)和GIS的空間信息處理能力，使野外工作者能夠利用該系統(tǒng)實(shí)時(shí)地獲取、存儲(chǔ)、更新、處理、分析和顯示地理信息。1.3ArcGISforAndroid介紹ArcGISforAndroid將GIS的適用范圍從辦公室擴(kuò)展到移動(dòng)Web。發(fā)布時(shí)，ArcGISforAndroid將包括一個(gè)應(yīng)用程序，您將能夠從AndroidMarket應(yīng)用商店下載這款稱為ArcGIS的應(yīng)

10、用程序。這個(gè)應(yīng)用程序類似于已經(jīng)發(fā)布的ArcGISforiOS和WindowsPhone應(yīng)用程序。使用該ArcGIS應(yīng)用程序，您能夠?yàn)g覽ArcGIS.com或ArcGISServer提供的地圖，并且利用程序中提供的工具進(jìn)行搜索，識(shí)別位置和要素，測(cè)量線和面，以及編輯6。2系統(tǒng)設(shè)計(jì)2.1 系統(tǒng)結(jié)構(gòu)設(shè)計(jì)本系統(tǒng)的結(jié)構(gòu)分為服務(wù)器端的搭建和客戶端軟件的開(kāi)發(fā)。使用ArcGISServer在服務(wù)器計(jì)算機(jī)上搭建一套完整的地圖服務(wù)，能夠發(fā)布自己的地圖和隨時(shí)對(duì)地圖信息進(jìn)行編輯?？蛻舳塑浖_(kāi)發(fā)的功能有地圖顯示、地圖定位、位置搜索、選擇圖層、路徑導(dǎo)航等。系統(tǒng)功能結(jié)構(gòu)圖如圖1所示。圖1系統(tǒng)功能結(jié)構(gòu)圖2.2 數(shù)據(jù)庫(kù)設(shè)計(jì)1

11、）在圖層中創(chuàng)建一個(gè)線要素Road,用于表示地圖中的道路，再給該要素添加屬性，為了方便與最短路徑的計(jì)算，添加了道路的長(zhǎng)度、限速值、行駛時(shí)間、端點(diǎn)信息等屬性，OBJECTID是自動(dòng)生成的用于唯一標(biāo)識(shí)一個(gè)要素，SHAPE是指要素的類型，這里是幾何類型，由于Road是線要素，所以系統(tǒng)也會(huì)自動(dòng)生成SHAPE_LENGTH屬性，默認(rèn)表示該線段的幾何長(zhǎng)度，SpeedLimit和DriveTime都是自己另外添加的屬性，為計(jì)算最短路徑功能所用。如表1所示。2）為了實(shí)現(xiàn)智能導(dǎo)航系統(tǒng)的選擇圖層功能，再向圖層中添加一些生活常用的信息點(diǎn)，如醫(yī)院、停車(chē)場(chǎng)、電影院、美食、銀行、加油站、超市等，所以又添加了11個(gè)點(diǎn)要素：F

12、ood、Hospital、Shop、Park、KTV、Movie、Bank、Gas、Medicine、KFC、Mcdonald。每個(gè)要素各對(duì)應(yīng)有自己的屬性表，由于他們都類似，下面只列出其中的一個(gè)表，如表2所示。表1道路信息表表2醫(yī)院信息表3核心問(wèn)題和難點(diǎn)問(wèn)題路徑導(dǎo)航功能是該系統(tǒng)最核心且最有難度的功能，路徑導(dǎo)航就是用戶設(shè)定一個(gè)起點(diǎn)（或以當(dāng)前定位點(diǎn)為起點(diǎn)）和一個(gè)終點(diǎn)，系統(tǒng)采用一種最短路徑算法來(lái)通過(guò)計(jì)算求出所設(shè)起點(diǎn)到終點(diǎn)的最優(yōu)路徑。在空間決策模型中，實(shí)現(xiàn)行駛最優(yōu)路徑的規(guī)劃算法是空間決策的核心內(nèi)容。只有構(gòu)建出最優(yōu)路徑模型，系統(tǒng)終端獲取的地理位置信息才能夠最迅速快捷地用到校園導(dǎo)航路線的選擇和優(yōu)化中。三種

13、最短路徑算法的比較與選擇本系統(tǒng)最核心的算法就是導(dǎo)航功能中的最短路徑選擇算法，為了選擇最適合于本系統(tǒng)的最短路徑算法，對(duì)常見(jiàn)的三種最短路徑算法進(jìn)行分析和比較，歸納出這三種最短路徑算法的對(duì)比如表3所示。表3三種最短路徑算法對(duì)比表根據(jù)對(duì)比可以看出，Dijkstra算法在時(shí)間和空間上都是優(yōu)于Floyd算法和Bellman-Ford算法的。不足之處就是Dijkstra算法不能處理含負(fù)權(quán)邊的圖。但根據(jù)本系統(tǒng)的實(shí)際情況，地圖中的道路長(zhǎng)度一定為正數(shù)，最短行駛時(shí)間也一定為正數(shù)，所以對(duì)于本系統(tǒng)來(lái)說(shuō)，Dijkstra算法的這個(gè)缺陷可以忽略不計(jì)。因此，本系統(tǒng)選用Dijkstra算法來(lái)計(jì)算導(dǎo)航功能中的最短路徑問(wèn)題。經(jīng)典D

14、ijkstra算法過(guò)程分析Dijkstra算法也是求單源最短路徑的算法，思想就是以源點(diǎn)s為中心，向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。算法思路如下7:1)初始化：設(shè)源點(diǎn)s的diss=0,除源點(diǎn)外的其他點(diǎn)disi=無(wú)窮大，同時(shí)把所有的結(jié)點(diǎn)的狀態(tài)都設(shè)為未擴(kuò)展?fàn)顟B(tài)；2)循環(huán)V次：在未擴(kuò)展的點(diǎn)中取一個(gè)dis值最小的點(diǎn)i,把結(jié)點(diǎn)i標(biāo)記為已擴(kuò)展的，并對(duì)和點(diǎn)i相鄰的每一個(gè)點(diǎn)j進(jìn)行松弛操作，即更新disj的值；3)算法結(jié)束后，對(duì)于任意的點(diǎn)i,disi就是源點(diǎn)s到結(jié)點(diǎn)i的最短距離。算法的偽代碼如下：ForeachvCV(G)dodisv=INF;diss=0;把結(jié)點(diǎn)都插入優(yōu)先隊(duì)列QwhileQ非空doi=Q.top

15、();把i標(biāo)記為已擴(kuò)展Foreachedge(i,j)doIfj未標(biāo)記anddisjdisi+wi,jthendisjdisi+wi,j如果用普通的鄰接矩陣來(lái)存儲(chǔ)圖的結(jié)構(gòu)，只能在每次循環(huán)里面再用一個(gè)循環(huán)來(lái)找出dis值最小的結(jié)點(diǎn)，那么時(shí)間復(fù)雜度將是O(V2)。所以為了優(yōu)化時(shí)間，可以使用優(yōu)先隊(duì)列來(lái)保存所有結(jié)點(diǎn)的dis值，優(yōu)先隊(duì)列的內(nèi)部實(shí)現(xiàn)一般都是使用二叉堆，所以建立和維護(hù)這個(gè)優(yōu)先隊(duì)列的時(shí)間復(fù)雜度是O(log|V|),所以Dijkstra算法的總時(shí)間復(fù)雜度是O(E+V*10gM),空間復(fù)雜度是O(V+E)。4系統(tǒng)功能及其實(shí)現(xiàn)系統(tǒng)主要功能我們要實(shí)現(xiàn)的是校園智能手機(jī)導(dǎo)航系統(tǒng)，服務(wù)的對(duì)象是入學(xué)不久的新生和

16、初到校園的校外來(lái)訪人員，所以此系統(tǒng)的設(shè)計(jì)應(yīng)遵從界面直觀，功能鮮明，使用簡(jiǎn)便”的原則，從而為新生和校外來(lái)訪人員了解校園環(huán)境提供便捷和幫助。系統(tǒng)具有的功能大致如下：1)數(shù)據(jù)的更改和刪除。由于高校校園逐漸擴(kuò)建，校園地理環(huán)境不斷變化，對(duì)于已經(jīng)建成的校園導(dǎo)航系統(tǒng)，進(jìn)行及時(shí)準(zhǔn)確的更新十分必要。系統(tǒng)可以在數(shù)據(jù)庫(kù)中對(duì)現(xiàn)有的數(shù)據(jù)進(jìn)行刪除、修改，從而實(shí)現(xiàn)對(duì)校園地圖和屬性的及時(shí)更新。2)數(shù)據(jù)的查詢和顯示。用戶可以通過(guò)輸入關(guān)鍵詞后在地圖上搜索地點(diǎn)。對(duì)于顯示在地圖窗口的地圖可以進(jìn)行放大、縮小、漫游等操作，用戶還可以根據(jù)自己的需要及興趣點(diǎn)控制各個(gè)圖層的顯示，使查詢的信息更加明顯。3）空間分析查詢。打開(kāi)客戶端軟件時(shí)，手機(jī)進(jìn)

17、行實(shí)時(shí)GPS定位，獲取當(dāng)前位置后在地圖上顯示位置坐標(biāo)，并顯示附近的地圖信息?；凇癉ijkstra算法”的最短路徑導(dǎo)航功能還可以對(duì)任意兩點(diǎn)可以進(jìn)行最短路徑的查詢和導(dǎo)航，這是系統(tǒng)最核心的功能，用戶通過(guò)輸入起點(diǎn)（或以當(dāng)前定位點(diǎn)為起點(diǎn)）和終點(diǎn)可以迅速查詢出兩點(diǎn)間最短路徑，為新生和校外來(lái)訪人員提供了非常便捷及人性化的服務(wù)。性能測(cè)試分析GPS定位功能實(shí)現(xiàn)。在移動(dòng)端采用坐標(biāo)定位的方法，如果手機(jī)的GPS定位功能已開(kāi)啟，地圖會(huì)自動(dòng)定位，獲取到當(dāng)前的坐標(biāo)時(shí)，地圖控件會(huì)自動(dòng)平移到當(dāng)前的位置。界面如圖2所示。2）搜索地點(diǎn)功能實(shí)現(xiàn)。在搜索框中輸入關(guān)鍵詞地名，例如金虎超市”，點(diǎn)擊搜索按鈕，就會(huì)向服務(wù)器發(fā)送請(qǐng)求，若能找到

18、，則返回它的坐標(biāo)，然后客戶端就在地圖中顯示一個(gè)藍(lán)色的點(diǎn)，表示搜索的位置。界面如圖3所示。3）選擇圖層功能實(shí)現(xiàn)?；谟脩襞d趣點(diǎn)選擇圖層，其中包含的圖層有：美食、醫(yī)院、超市、停車(chē)場(chǎng)、KTV、電影院、銀行、加油站、藥店等。用戶選擇感興趣的圖層后，可以在地圖上顯示對(duì)應(yīng)的圖標(biāo)。界面如圖4所示。4）路徑導(dǎo)航功能實(shí)現(xiàn)。采用Dijkstra算法實(shí)現(xiàn)最短路徑的選擇，當(dāng)用戶設(shè)置起點(diǎn)（或以當(dāng)前定位點(diǎn)為起點(diǎn)）和終點(diǎn)后地圖會(huì)在該兩點(diǎn)顯示標(biāo)記，點(diǎn)擊導(dǎo)航按鈕后，地圖上就會(huì)顯示出從起點(diǎn)到終點(diǎn)的一條最優(yōu)路徑。界面如圖5和圖6所示。圖2GPS實(shí)時(shí)定位界面圖3關(guān)鍵詞搜索地點(diǎn)界面圖4興趣點(diǎn)選擇圖層界面圖5最短路徑導(dǎo)航界面（用戶設(shè)置起點(diǎn)）圖6最短路徑導(dǎo)航界面（以當(dāng)前定位點(diǎn)為起點(diǎn)）5結(jié)束語(yǔ)校園智能手機(jī)導(dǎo)航系統(tǒng)的建立是校園數(shù)字化的一種體現(xiàn)，為學(xué)校日后建立綜合校園管理體系奠定了基礎(chǔ)。利用Dijkstra算法實(shí)現(xiàn)了最短路徑的選擇，獲得的最短路徑的屬性數(shù)據(jù)得以顯示，提供了及時(shí)且更直觀的校園導(dǎo)航系統(tǒng)的信息。通過(guò)測(cè)試，本系統(tǒng)起到了為新生報(bào)到和校外來(lái)訪人員提供指南導(dǎo)航的作用，提供了方便、快捷的智能導(dǎo)航服務(wù)信