TW201420994A

TW201420994A - 電動交通載具之導航路徑規劃電腦程式產品

Info

Publication number: TW201420994A
Application number: TW101145209A
Authority: TW
Inventors: Ming-Jie Chen; zheng-yi Li
Original assignee: Hua Chuang Automobile Information Technical Ct Co Ltd
Priority date: 2012-11-30
Filing date: 2012-11-30
Publication date: 2014-06-01
Also published as: TWI465690B

Abstract

一種電動交通載具之導航路徑規劃電腦程式產品，係由一導航系統載入一導航路徑規劃程式，該導航系統包含一地圖資料庫、一輸入界面、一處理模組及一輸出界面；該導航路徑規劃電腦程式產品係利用地圖資料庫之地圖資訊將起始點定義為當前規劃點，以一路徑目標函數演算出各路徑之最小的總里程成本為最佳的導航路徑。其中，路徑目標函數可包含已耗費的里程成本、即將再耗費里程成本與路徑的距離成本乘以整體耗電權重之殘餘成本；而整體耗電權重更可分為與充電站特性相關之充電站現役權重、與道路特性相關的道路優先權重。藉此，可對電動交通載具提供最佳路徑之導航規劃。

Description

電動交通載具之導航路徑規劃電腦程式產品

本發明係關於一種電動交通載具之導航路徑規劃電腦程式產品，尤指一種藉由執行包含有充電站特性相關與道路特性相關之整體耗電權重之路徑目標函數，而規劃出電動交通載具之最佳化路徑的電腦程式產品。

隨著科技的進步與時代的發展，人們的生活觀念已漸漸地改變，因而逐漸地重視生活品質，進而帶動了開車旅行風氣的盛行，為方便人們能更迅速準確的前往目的地，因此衛星導航路徑規劃電腦程式產品已成為人們開車旅行的必備工具，其係利用電子地圖以及全球定位系統（Global Positioning System; GPS）來進行規劃路徑以及導航，也就是說，使用者只需要輸入欲前往之目的地後，衛星導航路徑規劃電腦程式產品即會依據使用者之所在位置，協助使用者找出到達目的地之最佳化路徑。
然而，近年來隨著環保意識的抬頭，電動車的發展因而受到重視，習知技術之衛星導航路徑規劃電腦程式產品中，雖然能夠規劃最佳化路徑，但一般未將充電站位置納入最佳化路徑規劃，而由於電動車具有電量續航力之限制，因此，雖然衛星導航路徑規劃電腦程式產品可規劃出最佳化路徑，但現有之電動車所具有之電量續航力有限，使得電動車到某個地點仍需要找尋充電站而偏離最佳化路徑，而無法依據所規劃之最佳化路徑到達目的地，進而使得導航效果不佳。
在習知上，各種導航路徑規劃方法如蟻群演算法（Ant Colony Optimization, ACO）、狄克斯特拉(Dijkstra)演算法、A*演算法或莫爾(Moore/Pape)演算法；蟻群演算法通常用於隨機路徑之規劃，Dijkstra演算法為從起點的周邊開始，一個一個的確定到各節點的最短路徑；Moore/Pape演算法則為最短路徑之計算方法，在對多對多的計算時最為快速，但比較不適合一對多的計算；而計算量較少且適合一對多的計算為A*演算法，其主要是定義一個目標函數，再對此目標函數進行微分以求得目標值的最大值(最小值)，目標函數通常以F=G+H計算成本後，找出最少成本作為結果來規劃路徑；其中F是從初始點到目標點的估計成本、G是從初始點到某一節點的實際成本、H是從某一節點到目標點最佳路徑的估計成本；且此演算法通常係取用電子地圖資料之道路屬性、長度以及所需時間作為計算依據。
在各種導航路徑規劃方法的先前技術，如台灣專利公開TW201122433號揭露的導航提示方法，係利用計算不同路徑的成本，在偏離路線與該最佳化路線之間產生成本差量，而以差量最小的路徑為導航提示的路徑；又如台灣專利公開TW201211508號揭露利用地圖資料及識別最小成本路徑，以確定自出發點至目的地之路線；這些揭露的技術，在目標函數上僅考量里程相關的成本，而對於電動車最悠關的耗電特性則尚無法直接使用，電動車除要考慮里程外，整體的耗電特性係與道路種類、是否有充電站或那一種類的充電站為直接相關。美國專利公開號US20120010767揭露混合動力車輛(Hybrid electric vehicle, HEV)使用電池電量狀態(Battery State-of-charge, SoC)為最佳化的目標函數，如第1圖，行駛路徑9中自起點Ps至終點Pt間經過數個節點(Pr1、Pr2、Pr3及Pr4)，計算每一節點的電池電量狀態並列出可能的電池電量狀態(SoC¹、SoC²、…、SoCⁿ)，經由最佳化的運算，運算出各節點的最佳SoC的組合，另在後續的導航上則再加入道路等級為路徑選擇的考量，但該揭露的技術中未將道路特性納入目標函數的計算；再者，美國專利US8204638則將行車速度納入混合動力車輛的目標函數中進行最佳動力路徑的計算；美國專利US5913917則以巷道的數量特性以分率(fraction)為權值。
但由於電動交通載具電量有限，現有之導航路徑規劃電腦程式產品或演算方法應用於電動車時，其所規劃最佳化路徑之考量因素中，僅以里程成本為計算或加入巷道的數量分率為權值，並不包含整體耗電的狀況；但實際上道路里程的成本不只是與距離長短有關，而應考量整體耗電的狀況、不同道路屬性的耗電(例如高速公路、快速道路、省道、縣道、鄉道、一般道路以及其他道路等的耗電特性不相同)及是否有充電站等等，僅以里程成本、時間成本或者加上巷道的數量特性為權值等計算方法，與實際電動交通載具行駛耗電狀況不同，尚無法具體應用於電動交通載具的導航系統中。

本發明主要目的在於提供一種電動交通載具之導航路徑規劃電腦程式產品，以里程成本與整體耗電權重定義出路徑目標函數，在運算各路徑之總里程成本後，而規劃出最佳化路徑，藉此提供更為符合電動交通載具的導航電腦程式產品。
根據本發明的目的，提供一種導航路徑規劃電腦程式產品，其主要係在規劃最佳化路徑之考量因素中，進一步考量整體耗電因素；該導航路徑規劃電腦程式產品適用於一導航系統，該導航系統配置在車載電腦、筆記電腦、地圖導航電腦、手持電腦、智慧手機等，不為所限；係由一導航系統(navigation system)載入一導航路徑規劃程式，該導航系統包含一地圖資料庫(map database)、一輸入界面、一處理模組(processing unit)及一輸出界面；執行下列步驟：

S1：由使用者利用輸入界面及該地圖資料庫定義一起始點(starting point)為一當前規劃點(current point)，該導航路徑規劃程式規劃出由該當前規劃點至該終點之複數個路徑n；
S2：該處理模組利用該地圖資料庫與該當前規劃點，載入包含複數個中繼節點之地圖資訊及載入複數個充電站位置之地圖資訊；找出鄰近於該當前規劃點之每一中繼節點為各路徑i(i=1,2,…,i,…N個路徑)，各路徑i包含一個中繼節點，若該路徑i上有充電站，則該路徑i也包含該充電站位置；
S3：該處理模組藉由該導航路徑規劃程式之一路徑目標函數(route objective function)F(n)，演算出各路徑i之一總里程成本F_i；其中路徑目標函數F(n)係如式(1)所定義：

其中，F(n)為路徑n之總里程成本函數，G(n)為耗費里程成本函數、H(n)為殘餘里程成本函數；其中，H(n)殘餘里程成本函數如式(2)所展開：

其中，h(n)為當前規劃點至該終點之直線距離成本函數，W(n)為整體耗電權重函數；式(2)代表殘餘里程成本函數H(n)為殘餘里程之直線距離成本函數h(n)與整體耗電權重函數W(n)之乘積，意即，殘餘里程成本不僅為距離的成本，仍應乘上整體耗電的權值；
S4：該導航路徑規劃程式將路徑目標函數F(n) 最小化，即找出該些路徑之最小的總里程成本F*，演算出該最小總里程成本所對應之該中繼節點，定義為一接續行進節點(approaching node)；其中，該最佳化路徑係為自該起始點沿至少一上述接續行進節點而行進至該終點之路徑集合；其中，各路徑i的總里程成本F_i及路徑目標函數最佳化如式(3)及式(4)：

S5：在該電動交通載具行進至該接續行進節點時，該導航路徑規劃程式判斷該接續行進節點是否為該終點；以及
S6：在步驟S5之判斷結果為否時，該導航路徑規劃程式將該接續行進節點重新定義為上述之起始點，並重複執行上述步驟S1至S5；該輸出界面輸出該導航路徑規劃程式執行過程或執行結果至少其一。
其中，在該步驟S3中，耗費里程成本函數G(n)為自該起始點已實際行經之每一中繼節點之實際已耗費里程成本函數G₁(n) 與該即將再耗費里程成本函數G₂(n) 之和、該整體耗電權重W為由充電站位置所定義之充電站權重與道路權重之積，如式(5)及式(6)；

使用式(5)以路徑目標函數F(n)、耗費里程成本函數G(n)、實際已耗費里程成本函數G₁(n) 與該即將再耗費里程成本函數G₂(n)計算第i路徑之總里程成本F_i時，係於該開啟列表內找出上述鄰近於該當前規劃點之每一中繼節點之各路徑i之該耗費里程成本G_i以及各路徑i所對應之該殘餘里程成本H_i；其中，該耗費里程成本G_i為自該起始點已實際行經之每一中繼節點之實際已耗費里程成本G_1i與該即將再耗費里程成本G_2i之和；該殘餘里程成本H_i係由該中繼節點至該終點之直線距離成本h_i與各路徑i之該整體耗電權重W所計算。
較佳地，本發明一種導航路徑規劃電腦程式產品，該導航系統之導航路徑規劃程式，於步驟S1進一步執行下列步驟：
S11：該導航路徑規劃程式將每一鄰近於該當前規劃點之該些中繼節點列入一開啟列表(open list)。
於步驟S5進一步執行下列步驟：　　　
S51：該導航路徑規劃程式將該接續行進節點列入一關閉列表(close list)。

較佳地，本發明一種導航路徑規劃電腦程式產品，該處理模組藉由該導航路徑規劃程式之一路徑目標函數F(n)演算出各路徑i之一總里程成本F_i時，整體耗電權重W為由充電站位置所定義之充電站權重與道路權重之積如式(6)；

其中，充電站權重可分解為因充電站位置所產生的里程成本貢獻(充電站現役權重Ws)與因充電站種類所產生的里程成本貢獻(充電站種類權重Wst)，如式(7)；

該道路權重可分解為因道路等級所產生的里程成本貢獻(道路優先權重Wr)、因不同道路等級所產生的耗電貢獻(耗電速率權重Wc)及因不同的道路連結等級所產生的耗電貢獻(連結道路種類權重Wct)，如式(8)：

較佳地，本發明一種導航路徑規劃電腦程式產品，其中，該導航系統進一步包含一權重數據庫，該權重數據庫儲存各種的權重之數據，包含充電站現役權重Ws、充電站種類權重Wst、道路優先權重Wr、耗電速率權重Wc與連結道路種類權重Wct之數據；可由使用者利用輸入界面預先輸入與更新、或經由該導航系統預先下載與更新或內建於權重數據庫內，該權重數據庫亦可與該地圖資料庫相結合，不為所限。

在後續的實施方式中，提出的實施例對於充電站權重
、道路權重可自行定義其態樣：
(1)充電站現役權重Ws之數值，如：充電站服役中權重數值、充電站無服役權重數值，不為所限；
(2)充電站種類權重Wst之數值，如：快速充電站種類權重數值、充電電池更換站種類權重數值以及行動式充電站種類權重數值，不為所限；
(3)道路優先權重Wr之數值，如：高速公路優先權重數值、快速道路優先權重數值、省道優先權重數值、縣道優先權重數值、鄉道優先權重數值、市區主要道路優先權重數值、市區次要道路優先權重數值以及巷弄優先權重數值，不為所限；
(4)耗電速率權重Wc之數值，如：高速公路耗電權重數值、快速道路耗電權重數值、省道耗電權重數值、縣道耗電權重數值、鄉道耗電權重數值、市區主要道路耗電權重數值、市區次要道路耗電權重數值以及巷弄耗電權重數值，不為所限；
(5)連結道路種類權重Wct之數值，如：圓環種類權重數值、一般道路種類權重數值、主要道路種類權重數值、系統交流道種類權重數值、統合路口種類權重數值、交流道種類權重數值、側道種類權重數值以及休息站種類權重數值，不為所限。

藉由本發明之電動交通載具之導航路徑規劃電腦程式產品，可具有下列一個或多個優點：
(1)本發明的導航路徑規劃電腦程式產品藉由地圖資料庫之地圖資訊，經由一處理模組可對電動交通載具的導航路徑進行規劃，運算出該電動交通載具自一起始點經由一中繼節點而抵達一終點的最佳化路徑；可使電動交通載具採用最小的總里程成本由起始點抵達終點。
(2)本發明的導航路徑規劃電腦程式產品在最佳化的路徑規劃上，採用里程成本與耗電權重為路徑目標函數，藉此可將電動交通載具最重要的耗電因素對里程成本進行加權，使路徑目標函數與電動交通載具最基本的需求一致外，運算獲得的最佳路徑不但考慮了里程成本，更加權了耗電因素；相較於習知技術，由於現有之衛星導航路徑規劃電腦程式產品應用於電動交通載具時，其所規劃最佳化路徑之考量因素中，並不包含耗電因素，使電動車之行駛因不同道路狀況或因充電而造成總里程成本的增加，即行駛路徑並非電動交通載具的真正最佳化路徑之缺點；進一說明，由於電動交通載具電量有限，常在中途因電量不足而需要充電，習知技術中電動交通載具導航路徑規劃，未考慮因充電所造成的里程成本，使得電動交通載具到某個地點仍需要找尋充電站而偏離最佳化路徑，進而使得導航效果不佳。
(3)本發明的導航路徑規劃電腦程式產品在最佳化的路徑規劃上，為能與電動交通載具實務上更接近，所加權的耗電因素，更可綜合加入各種不同的耗電因素，如充電站現役權重、充電站種類權重、道路優先權重、耗電速率權重、連結道路種類權重等，提高了電動交通載具導航的精確性與實用性。
(4)本發明共提出一種電動交通載具之導航電腦程式產品，可利用一導航系統載入一導航路徑規劃程式，由使用者使用輸入界面及地圖資料庫定義起始點及一終點，導航路徑規劃程式由地圖資料庫之地圖資訊及數據資料，可運算出已考量了耗電因素的最小里程成本最佳的路徑，在顯示界面上顯示出來，提供給電動交通載具駕駛人參考使用。

為使本發明更加明確詳實，茲列舉較佳實施例並配合下列圖示，將本發明之結構及其技術特徵詳述如後。
請參閱第2圖，其係為本發明之導航路徑規劃電腦程式產品架構圖，在圖中，導航路徑規劃電腦程式產品10包含一導航系統11及一導航路徑規劃程式12，由導航系統11將導航路徑規劃程式12載入以執行導航路徑規劃，該導航系統11由一地圖資料庫111、一輸入界面112、一處理模組113及一輸出界面114所構成；地圖資料庫111內儲存有行車範圍內的地點位置、道路種類、連結道路種類、距離(或各地點的座標)，甚至該地圖資料庫111內存有充電站的位置、充電站是否服務可進行充電、充電站的種類等資料；處理模組113通常為由硬體、軟體及韌體所構成，可接受輸入界面112進入的資料、自地圖資料庫111或其他資料庫(如權重數據庫13)獲取資料、執行軟體程式、進行數學或邏輯運算等、及將運算後的資訊在輸出界面114上顯示。請參閱第3圖，其係為本發明之導航路徑規劃電腦程式產品應用的示意圖，導航系統11係以地圖導航電腦為繪示、權重數據庫13則可為儲存卡(如SD卡)之方式讀取，但不以此為限；運算後的最佳路徑則可顯示在地圖導航電腦之螢幕(輸出界面114)上。

請參閱第5圖，係顯示本發明實施例之導航路徑規劃方法之規劃示意圖，在圖中，導航路徑規劃方法係規劃運算出電動交通載具自起始點Ps經由中繼節點Pr1與中繼節點Pr2(路徑1：)或經由中繼節點Pr1經由充電站Cs及中繼節點Pr3(路徑2：)而抵達終點Pt之最佳化路徑(optimal route)。請參閱第4圖，係顯示本發明實施例之導航路徑規劃方法之方法流程示意圖，在圖中，該導航路徑規劃方法包含以下步驟：
S1：利用地圖資料庫111，定義一個當前規劃點Pc，規劃出由當前規劃點Pc至終點Pt之複數個路徑n；將每一鄰近於該當前規劃點Pc之中繼節點(Pr)列入一開啟列表；其中，若電動交通載具由起始點Ps開始，則首次規劃路徑時，起始點Ps即定義一個當前規劃點Pc；若電動交通載具行至中繼節點Pr1於規劃下一個路徑時，中繼節點Pr1即為定義的當前規劃點Pc；
S2：利用該地圖資料庫111，載入相鄰當前規劃點Pc之每一個中繼節點(Pr)之地圖資訊及載入相鄰當前規劃點Pc之每一個充電站位置(Cs)之地圖資訊；找出鄰近於當前規劃點Pc之每一中繼節點為各路徑i(i=1,2,…,i,…N個路徑)，各路徑i至少包含一個中繼節點，若該路徑i上有充電站，則路徑i也包含該充電站位置；
在步驟S1及S2，以較佳實施例應用於本發明之導航路徑規劃電腦程式產品10為例，由導航系統11或由使用者利用輸入界面112將起始點Ps定義為一當前規劃點Pc，導航系統11利用地圖資料庫111之地圖資訊，將每一鄰近於當前規劃點Pc之該些中繼節點列入開啟列表。更進一步來說，使用者在電動交通載具內，藉由導航路徑規劃電腦程式產品10設定完起始點Ps以及終點Pt，並確定開始規劃路徑後，導航系統11會啟動導航路徑規劃程式12自地圖資料庫111中（地圖資料庫111係位於導航路徑規劃電腦程式產品10之資料庫中或雲端系統資料庫中），載入包含複數個充電站位置Cs與複數個中繼節點Pr之地圖資訊，並且列出由起始點Ps至終點Pt之最佳化路徑中所需經過之複數個中繼節點，接著將起始點Ps定義為一當前規劃點Pc，然後將每一鄰近於起始點Ps之該些中繼節點Pr列入開啟列表，舉例來說，假若使用者係以台中為起始點Ps，而台北為終點Pt，那麼鄰近於台中之中繼節點(Pr)包含了大甲、后里以及豐原，因此系統會將大甲、后里以及豐原之三個中繼節點列入開啟列表；對於不同的顯示畫面設計，導航系統11可將開啟列表或其他資訊在輸出界面114上顯示出來。
S3：藉由一路徑目標函數F(n)，演算出各路徑i之一總里程成本F_i；其中總里程成本F_i依路徑目標函數F(n)所定義，如式(9)：

其中，F_i為路徑i之總里程成本，G_i為耗費里程成本、H_i為殘餘里程成本；其中，路徑i之H_i殘餘里程成本可如式(2)所定義計算，總里程成本F_i計算如式(10)：

其中，h_i為路徑i當前規劃點Pc至該終點Pt之直線距離成本，W_i為路徑i整體耗電權重數值；式(10)代表殘餘里程成本函數H_i等於殘餘里程之直線距離成本h_i與整體耗電權重數值W_i之乘積；其中，路徑i之耗費里程成本G_i為自起始點Ps已實際行經之每一中繼節點之實際已耗費里程成本G_1i與即將再耗費里程成本函數G_2i之和、整體耗電權重W_i為由充電站位置所定義之充電站權重與道路權重之乘積。
又充電站權重可為充電站現役權重Ws與充電站種類權重Wst之乘積；道路權重可為道路優先權重Wr、耗電速率權重Wc及連結道路種類權重Wct之乘積；因此，總里程成本F_i計算如式(11)；

在步驟S3，以較佳實施例應用於本發明之導航路徑規劃電腦程式產品10為例，處理模組113與導航路徑規劃程式12依路徑目標函數F(n)對各路徑i演算總里程成本F_i，如上述大甲、后里以及豐原三個中繼節點為例，處理模組113與導航路徑規劃程式12演算出經由大甲之總里程成本F₁、經由后里之總里程成本F₂以及經由豐原之總里程成本F₃；對於不同的顯示畫面設計，導航系統11可將各路徑的總里程成本及其大小次序或其他資訊在輸出界面114上顯示出來。
S4：將路徑目標函數F(n) 最小化，即在各路徑中找出該些路徑之最小的總里程成本(F_i,i=1,n)為F*，演算出該最小總里程成本所對應之該中繼節點，定義為一接續行進節點Pa(approaching node)；其中，最佳化路徑係為自該起始點Ps沿至少一上述接續行進節點Pa而行進至終點Pt之路徑集合。
在步驟S4，以較佳實施例應用於本發明之導航路徑規劃電腦程式產品10為例，處理模組113與導航路徑規劃程式12在該些總里程成本F_i中尋找出一最小總里程成本F*，並將所對應之中繼節點定義為一接續行進節點Pa。更進一步來說，繼續以上述大甲、后里以及豐原三個節點為例，假設往大甲之路徑中具有充電站而使總里程成本F最低，那麼導航路徑規劃電腦程式產品10立即選擇大甲之中繼節點Pr作為接續行進節點Pa，表示大甲是下一個行車的中繼節點；對於不同的顯示畫面設計，導航系統11可將各路徑及優選的接續行進節點Pa或其他資訊以圖示或文字在輸出界面114上顯示出來。
S5：在該電動交通載具行進至接續行進節點Pa時，判斷該接續行進節點Pa是否為該終點Pt；若接續行進節點Pa為終點Pt時，將接續行進節點Pa列入一關閉列表。
在步驟S5，以較佳實施例應用於本發明之導航路徑規劃電腦程式產品10為例，步驟S5係在電動交通載具行進至接續行進節點Pa時，將接續行進節點Pa列入關閉列表。繼續以上述大甲、后里以及豐原三個節點為例，由於在步驟S4時，已選擇大甲作為接續行進節點Pa，因此使用者即駕駛電動交通載具到了大甲，而此時導航路徑規劃電腦程式產品10會將大甲這個接續行進節點Pa列入關閉列表，藉以表示大甲已走過而在下次計算時，不列入計算範疇。另外，值得一提的是，在步驟S5中，其餘上述每一鄰近於當前規劃點Pc之該些中繼節點Pr，係列入開啟列表，也就是說，后里以及豐原二個中繼節點會列入開啟列表，以供下次演算用。對於不同的顯示畫面設計，導航系統11可將關閉列表、開啟列表或其他資訊以圖示或文字在輸出界面114上顯示出來。
S6：在步驟S5之判斷結果為否時，將該接續行進節點Pa重新定義為上述之起始點Ps，並重複執行上述步驟S1至S5。
在步驟S6，以較佳實施例應用於本發明之導航路徑規劃電腦程式產品10為例，導航路徑規劃電腦程式產品10係判斷大甲是否為終點Pt，而假若大甲不是使用者所設定的終點Pt的話，隨即將接續行進節點Pa重新定義為起始點Ps，並重複進行步驟S1至S5，亦即再將大甲視為起始點Ps，進而繼續規劃路徑直至接續行進節點Pa係為終點Ps為止，藉以規劃最佳化路徑；而假若大甲是使用者所設定的終點Ps的話，隨即進行步驟結束。對於不同的顯示畫面設計，導航系統11可將導航路徑規劃的即時狀況或其他資訊以圖示或文字在輸出界面114上顯示出來。
為了使本發明較佳實施例更為清楚，請參閱第5圖，第5圖係顯示本發明較佳實施例之導航路徑規劃方法之規劃示意圖。如第5圖所示， Ps係為起始點，Pr1、Pr2以及Pr3係為中繼節點，Pt為終點，其中當電動交通載具自起始點Ps行駛至中繼節點Pr1（此時中繼節點Pr1為開始進行下個路徑規劃的起始點，即為當前規劃點Pc）時，會有二中繼節點Pr2以及Pr3(路徑1及路徑2)需計算總里程成本F_i(i=1,2之二個路徑)。又G₁係為起始點Ps至中繼節點Pr1之實際已耗費里程成本，G_2i(i=1,2)係為中繼節點Pr1至中繼節點Pr2(路徑1)或中繼節點Pr1至中繼節點Pr3 (路徑2)之即將再耗費里程成本；進一步來說，G_2i為第i路徑中繼節點Pr1至中繼節點(Pr2或Pr3)之距離與道路優先權重Wri之乘積，而h_i(i=1,2)中，h₁係為中繼節點Pr1至終點Pt(路徑1)或中繼節點Pr2至終點Pt(路徑1)之直線距離成本、h₂係為中繼節點Pr3至終點Pt(路徑2)之直線距離成本。
其中，以中繼節點Pr2(路徑1)之總里程成本F₁來說，其G₁係為起始點Ps至中繼節點Pr1之實際已耗費里程成本，其G₂₁係為中繼節點Pr1至中繼節點Pr2 (路徑1)之即將再耗費里程成本，進一步來說，G₂₁為中繼節點Pr1至中繼節點Pr2之距離與道路優先權重Wr1之乘積，而h₁係為中繼節點Pr2至終點Pt(路徑1)之直線距離成本、h₂係為中繼節點Pr3至終點Pt(路徑2)之直線距離成本。
對於另一具體實施例，如第3圖，導航路徑規劃電腦程式產品10包含一導航系統11、一導航路徑規劃程式12、一權重數據庫13，其中權重數據庫13包含有充電站權重與道路權重之資料，對於不限定實施例，可由使用者輸入、內建於導航路徑規劃電腦程式產品10中，或可自雲端下載資料，如下例之態樣：
(1)充電站現役權重Ws之數值，如：

　係對路徑上的充電站是否有服役(營業中)或沒有服役(歇業中)，給予不同的權重。
(2)充電站種類權重Wst之數值，如：

　係對路徑上的充電站不同的種類給予不同的權重，如快速充電站需要花費里程成本較高，而可更換電池的充電電池更換站(將整組電池拆下換裝上另一組電池)與行動式充電站(如在車後拖著一個電池的拖式電池進行快速更換)則花費里程成本接近，在本實施例給予相同的權重。
(3)道路優先權重Wr之數值，如：

係對路徑上的各種道路的選擇，依其不同的里程成本給予不同的權重。
(4)耗電速率權重Wc之數值，且其主要係依據道路型態之參考速率而設定，如：

係對路徑上的各種道路有不同的耗電基準，依其不同的里程成本給予不同的權重；通常耗電基準可由各種道路的行駛的速率為參考。
(5)連結道路種類權重Wct之數值，如：

係對路徑上因道路連結的各種連結道路有不同的里程成本，依其不同的里程成本給予不同的權重。
整體耗電權重W_i係為路徑i中之充電站現役權重Ws、充電站種類權重Wst、道路優先權重Wr、耗電速率權重Wc以及連結道路種類權重Wct之乘積；因此對於路徑1(中繼節點Pr2至終點Pt)，整體耗電權重W₁= Ws₁* Wst₁* Wr₁* Wc₁* Wct₁。假若中繼節點Pr1至中繼節點Pr2之路徑不具有充電站，而其行走路徑之道路型態係為高速公路，連結道路型態係為系統交流道，因此充電站現役權重Ws₁係為1；道路優先權重Wr₁係為0.8；耗電速率權重Wc₁係為0.033；連結道路種類權重Wct₁係為1；而充電站種類權重Wst₁則可為1，據此，整體耗電權重W₁之乘積結果為1*0.8*0.033*1*1。
同理，以中繼節點Pr3(路徑2)之總里程成本F₂來說，其G₁係為起始點Ps至中繼節點Pr1之實際已耗費里程成本，其G₂₂係為中繼節點Pr1至中繼節點Pr3之即將再耗費里程成本，進一步來說，G₂₂為中繼節點Pr1至中繼節點Pr3之距離與道路優先權重Wr之乘積，而h₂係為中繼節點Pr3至終點Pt之直線距離成本。

另外，假若中繼節點Pr1至中繼節點Pr3之路徑具有充電站Cs，且充電站Cs之種類係為充電電池更換站，而其行走路徑之道路型態係為高速公路，連結道路型態係為系統交流道，因此充電站現役權重Ws係為0.5；道路優先權重Wr係為0.8；耗電速率權重Wc係為0.033；連結道路種類權重Wct係為1而充電站種類權重Wst則可為0.4，據此，整體耗電權重W之乘積結果為0.5*0.8*0.033*1*0.4。因此，在比較中繼節點Pr2以及Pr3之總里程成本F後可發現中繼節點Pr3之總里程成本F₂較小，使得規劃路徑會以中繼節點Pr3為最佳路徑。
為了使本發明較佳實施例更為清楚，請一併參閱第2圖以及第6A圖至第6D圖，第6A圖至第6D圖係顯示本發明較佳實施例應用於導航路徑規劃電腦程式產品之規劃路徑示意圖。如圖所示，上述步驟開始後，係進行步驟S1利用地圖資訊，將起始點定義為一當前規劃點Pc，並將每一鄰近於當前規劃點Pc之該些中繼節點Pr列入開啟列表。更進一步來說，使用者係設定A為起始點，E為終點，而在開始規劃路徑時，系統會將起始點A定義為當前規劃點Ps，並將三個中繼節點B1、B2以及B3列入開啟列表。
於步驟S2中，導航系統11使處理模組113開始依據前述之路徑目標函數F(n)演算經由B1、B2以及B3各路徑i的總里程成本F_i。更具體來說，由於殘餘里程成本H之整體耗電權重W中包含一充電站現役權重Ws，而僅只有出發點A出發至中繼節點B1之路徑中具有充電站Cs1，因此中繼節點B1之總里程成本F較小，而出發點A出發至中繼節點B2以及B3之路徑都不會行經充電站，因此相較於中繼節點B1之總里程成本F會較大。
於步驟S3中，處理模組113及導航路徑規劃程式12運算出開啟列表內之鄰近於當前規劃點Pc之每一個分別對應於上述每一個中繼節點(各路徑i)之總里程成本F_i。更進一步來說，經由上述演算後，處理模組113及導航路徑規劃程式12會在步驟S3中依據式(11)運算出各中繼節點B1、B2以及B3之總里程成本F_i，假設中繼節點B1之F₁係30、中繼節點B2之F₂係60，而中繼節點B3之F₃係70。
在步驟S4中，處理模組113及導航路徑規劃程式12在該些總里程成本F_i中尋找出一最小總里程成本F*，並將所對應之中繼節點定義為一接續行進節點Pa。更進一步來說，由於在步驟S3中，找出中繼節點B1之F₁係30、中繼節點B2之F₂係60，而中繼節點B3之F₃係70，因此，處理模組113及導航路徑規劃程式12在步驟S4中進一步找出中繼節點B1，因為其F₁係為最小，進而將中繼節點B1定義為接續行進節點Pa，此時導航路徑規劃電腦程式產品100之輸出界面114顯示如第6A圖之畫面。
在步驟S5中判斷該接續行進節點Pa是否為終點Pt。更進一步來說，使用者駕駛電動車至中繼節點B1時，導航路徑規劃電腦程式產品10會將中繼節點B1列入關閉列表，藉以表示中繼節點B1已走過而在下次計算時，不列入計算範疇，此外，導航路徑規劃電腦程式產品10會將中繼節點B2以及B3列入開啟列表。另外，由於接續行進節點Pa是中繼節點B1，而終點是E，因此判斷結果係為否，因此會直接進行步驟S6將接續行進節點Pa重新定義為起始點Ps，也就是說，中繼節點B1重新定義為起始點Ps，接著重複執行步驟S1至S5。值得一提的是，在重複執行的過程中，以中繼節點B1為起始點Ps之開啟列表內，導航路徑規劃電腦程式產品10會將中繼節點B2、B3、C1、C2以及C3列入開啟列表，而在較佳實施例中，由於中繼節點B2以及B3係經由一驗證機制而認為係走回頭路，因此中繼節點B2以及B3會隨即被排除在開啟列表外。
而在下一次重複執行的過程中，中繼節點B1為起始點Ps，路徑上有中繼節點C1、C2以及C3，及充電站Cs2，經由導航路徑規劃電腦程式產品10依據式(11)從中選出較佳的路徑，例如，往中繼節點C2之路徑上有充電站Cs2，其經運算後其總里程成本F較小而使得接續行進節點係為C2，此時導航路徑規劃電腦程式產品10之輸出界面114顯示如第6B圖之畫面，而由於中繼節點C2並不是終點E，因此會再重複執行步驟S1至S5。
在第二次重複執行的過程中，導航路徑規劃電腦程式產品10會從中繼節點D1、D2以及D3中選出較佳的路徑，例如，雖往中繼節點D1之路徑上有充電站Cs4，但其路徑係經由巷弄，道路優先權重Wr及耗電速率權重Wc均較高，因此其總里程成本F較大，而以中繼節點D2之總里程成本F較小，而使得接續行進節點Pa係為D2，此時導航路徑規劃電腦程式產品10之顯示界面114顯示如第6C圖之畫面，而由於中繼節點D2並不是終點E，因此會再重複執行步驟S1至S5。
後續在第三次重複執行的過程中，係規劃出往終點E之路徑，進而規劃出如第6D圖所示之最佳化路徑P*。
藉由以上較佳具體實施例之詳述，係希望能更加清楚描述本發明之特徵與精神，而並非以上述所揭露的較佳具體實施例來對本發明之範疇加以限制。相反地，其目的是希望能涵蓋各種改變及具相等性的安排於本發明所欲申請之專利範圍的範疇內。

10．．．導航路徑規劃電腦程式產品

11．．．導航系統

111．．．地圖資料庫

112．．．輸入界面

113．．．處理模組

114．．．輸出界面

12．．．導航路徑規劃程式

13．．．權重數據庫

A．．．出發點

B1、B2、B3．．．中繼節點

C1、C2、C3．．．中繼節點

Cs、Cs1、Cs2、Cs3、Cs4、Cs5、Cs6．．．充電站

D1、D2、D3．．．中繼節點

E、Pt．．．終點(terminal point)

Pa．．．接續行進節點(approaching node)

Pc．．．當前規劃點(current point)

Pr、Pr1、Pr2、Pr3．．．中繼節點(relay node)

Ps．．．起始點(starting point)

R*．．．最佳化路徑

S1~S6．．．執行步驟

第1圖係習知技術路徑規劃方法示意圖；
第2圖係本發明之導航路徑規劃電腦程式產品架構圖；
第3圖係本發明之導航路徑規劃電腦程式產品應用示意圖；
第4圖係顯示本發明較佳實施例之導航路徑規劃電腦程式產品之導航路徑規劃程式執行步驟示意圖；
第5圖係顯示本發明較佳實施例之導航路徑規劃電腦程式產品之路徑規劃示意圖；以及
第6A圖至第6D圖係顯示本發明較佳實施例應用於導航路徑規劃電腦程式產品之路徑規劃示意圖。