[發明專利]多任務導航中最優路徑選擇方法

有效

• 申請號: 200810303901.2
• 申請日: 2008-08-15
• 公開（公告）號: CN101344399A
• 公開（公告）日: 2009-01-14
• 發明（設計）人: 陳亮
• 申請（專利權）人: 四川長虹電器股份有限公司
• 主分類號: G01C21/26
• 分類號: G01C21/26;G01C21/34;G09B29/00
• 代理公司: 成都虹橋專利事務所
• 代理人: 李順德

技術領域

本發明涉及電子地圖技術。

背景技術

目前交通運輸的發展在全球引起了廣泛的關注。同時國際石油、煤炭等不可再生資源的 價格攀升。因此除了增強運輸設備和運輸人力，開發出一套多任務旅行信息服務系統來提高 公司和個人的效率，減小成本就顯得日益重要。

現已有基于GPS(全球定位系統)和GPRS(通用無線分組業務)實現車輛導航的方法， 通過建立一個存儲有豐富地圖資源，可提供與GPRS進行連接的導航中心，在置有GPS模塊并 可顯示地圖的車載導航設備中加入GPRS模塊，通過GPRS網絡交互，導航設備就能通過GPRS 網絡請求導航中心對存儲的本地常用地圖進行更新和補充，或按照需要下發局部地圖，導航 中心根據車載導航設備提出的要求通過GPRS網絡向車載導航設備生成和發送各種導航要素 進行導航。

發明內容

本發明所要解決的技術問題是，提供一種多任務導航中使導航路徑更高效的最優路徑選 擇方法。

本發明為解決上述技術問題所采用的技術方案是，多任務導航中最優路徑選擇方法，包 括以下步驟：

a、確定多個任務點中的起點與終點；

b、計算多個任務點兩兩之間的最優路徑；

b1、初始化兩任務點間的可能經過的各中間點以及該兩個任務點本身，將其中一個 任務點作為已標記點，設另一個任務點與所有中間點為未標記點，進入步驟b2；

b2、計算已標記點到其它未標記點間的路徑參數，并標記路徑參數最小的未標記點， 記錄該路徑參數最小的未標記點對應的前一個已標記點，進入步驟b4；

b3、逐個計算出與已標記點間標記路徑參數最小的未標記點；標記從第一個已標記 點起累計路徑參數最小的未標記點，并記錄該累計路徑參數最小的未標記點對應的前一個已 標記點；

b4、檢驗另一個任務點是否已標記，如是，則多個任務點兩兩之間的最優路徑選擇 完成，進入步驟c；如否，返回步驟b2；

c、將多個任務點構成的路徑的組合分別進行路徑參數的累計，選擇路徑參數最小為多任 務導航的最優路徑。

所述路徑參數為路徑長度和/或途徑時間。所述起點為由GPS獲得的當前位置。所述路徑 參數由GPRS提供。

本發明的有益效果是，有助于減少物流、快遞等多多任務路途中花費的時間，同時也可 減小任務完成的成本。

附圖說明

圖1為計算兩任務點間最優路徑的實施例示意圖；

具體實施方式

基于GPRS獲得的任務點的路徑參數和基于GPS獲得當前位置的多任務導航導航終端包 括基于GPRS個人位置服務信息數據的GPRS收發模塊和導航路徑計算模塊、GPS模塊、GPRS 位置數據源模塊、空間數據集模塊。

其中，GPRS位置數據源模塊中存儲有由GPRS收發模塊獲取并保存的任務執行者所需求 的位置數據。GPS模塊提供的是任務執行者的當前位置信息。導航路徑計算模塊是根據各個 任務點的位置數據和GPS獲得的當前位置作為起始點，規劃出一條經過多個任務點的且花費 最小(路徑最短或時間最短)的最優路徑。

GPRS位置數據源模塊接收數據的工作流程如下：

(1)多任務導航終端是個人需求端，在其有需要時它將其需求和個人位置信息通過GPRS 網絡發送到多任務導航中心；

(2)多任務導航中心接收到多任務導航終端發送的需求信息后，首先保存需求信息和個人 位置信息，成功之后，將確認信息發送到多任務導航終端；

(3)多任務導航中心是根據需求信息，在服務數據庫中調取數據按照位置和時間分類存 儲，為任務執行者按照區域就近原則通過GPRS網絡向多任務導航終端發送數據，并保存在 GPRS位置數據源模塊中。