[發明專利]一種導航方法

在審

• 申請號: 201410371032.2
• 申請日: 2014-07-31
• 公開（公告）號: CN104142151A
• 公開（公告）日: 2014-11-12
• 發明（設計）人: 李保印
• 申請（專利權）人: 上海聞泰電子科技有限公司
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 上海新天專利代理有限公司 31213
• 代理人: 王敏杰

技術領域

本發明屬于移動通信及導航技術領域，涉及一種導航方法，尤其涉及一種可提供多條路徑可供選擇的導航方法。

背景技術

手機導航(Mobile?Navigation)即衛星手機導航,它可以告訴你在地圖中所在的位置,以及可以顯示出你要去的地方在地圖中的位置,通過系統中的最短路徑算法顯示最佳的路線,在導航的路途中用語音提示用戶行進的方向。

導航由GPS模塊,導航軟件,GSM通信模塊組成：由GPS模塊通過GPS衛星采集數據,導航軟件中的地圖模塊分析得到的數據,通過不斷的刷新使位置在地圖上不斷的變化,軟件中的路徑接收用戶的指令或者需求,計算出用戶計劃要去的地點,規劃出一條最優路線并引導用戶,最后GSM模塊對這些數據分析處理之后上傳服務器中。

手機導航系統就是在可以在手機上運行的導航軟件,它是以手機作為硬件平臺的。通過手機中的GPS模塊接收信號,再把獲得的數據信息傳遞給導航軟件,經過軟件確定用戶的位置,再通過GIS模塊實現導航功能。

最短路徑(Shortest?Path,SP)問題是圖論中的經典問題，在計算機網絡路由，機器人路徑規劃，交通線路導航等諸多領域有著廣泛應用。Dijkstra算法是求解SP的經典方法，可在多項式時間內找到有向圖中任意兩頂點間的最短路徑。而在許多實際應用中，不僅需要求出最短路徑，而且往往還需要找出次短等多條最優路徑，如，城市道路交通導航中，用戶通常希望獲知多條最優路徑并根據實際的出行需要進行選擇。因此，在一個網絡圖中如何快速求得高質量的k條最短路徑問題引起人們的極大關注。

近年，很多學者對基于進化和仿生計算的智能方法求解復雜優化問題進行了深入的研究，獲得了許多理論和應用成果。然而，對于k條最短路徑問題的研究文獻目前尚不多見。國內研究者提出了一種能夠求解k條最短路徑問題的遺傳算法，直接以自然路徑作為染色體，根據路徑節點的連接關系對染色體實施交叉操作，將節點路徑塊作為染色體的變異基因塊來實施變異，采用對種群排序的方法進行世代更新。國外研究者曾提出了一種求解最短路徑的粒子群算法。基于粒子自我學習和社會學習的進化機理，最終多數粒子會落入優化解區域，因而算法在求得最短路徑的同時也可以得到一些次優路徑，而且算法收斂速度較快。但由于該算法不是將求解k條最短路徑作為優化目標，因而，當k比較大時求解質量不高且穩定性不夠好。

混合蛙跳算法(Shuffled?Frog?Leaping?Algorithm，SFLA)結合了基于遺傳的模因演算法(Memetic?Algorithm)和基于社會行為的粒子群算法的優點，全局尋優能力強，參數少，計算速度快，在一些實際應用中取得了良好效果。

發明內容

本發明所要解決的技術問題是：提供一種導航方法，可提供多條路徑供用戶選擇，可提高導航質量及穩定性。

為解決上述技術問題，本發明采用如下技術方案：

一種導航方法，所述導航方法包括：

步驟S1、獲取目的地位置信息及實時位置信息；

步驟S2、根據目的地位置信息、實時位置信息實時獲取到達目的地的K條最短路徑，進行實時導航，在導航的過程中不斷的計算著用戶的路線軌跡,直到導航結束；通過GPS傳輸數據，再根據地址數據庫、地圖數據庫、第三方路況信息數據庫和用戶數據庫，隨時更新用戶和目的地直接的路徑；采用混合蛙跳算法求解K條最短路徑；具體包括：

步驟S21、初始化蛙群，隨機產生F只青蛙，計算青蛙個體的評價值并將蛙群按評價值升序排序；青蛙個體的評價值的獲取方法為：用路徑path所有邊的代價之和表示青蛙的評價函數，即f(frogj)=Σe∈pathcost(e);]]>