ECO模式路徑規劃模型在導航器中應用

摘 要：論文提出ECO（Ecology，Conservation，Optimization）模式的導航求路模型。在雙向A-STAR算法的基礎上參考傳統以最快時間或最短路徑為權值的路徑算法，并將汽車油耗數據應用于ECO求路模型中。得到基于不同車型最經濟省油的行駛路線。最后再從用戶體驗角度出發對算法進行改進，使得用戶更能接收ECO模式的算路結果。論文中所有研究都在，公司專用導航模擬平臺上進行實現，分析，驗證并改進。

關鍵詞：導航；ECO；省油；路徑規劃

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1674-7712 （2014） 06-0000-04

一、引言

ECO這一名稱由Ecology（環保）、Conservation（節能）和Optimization（動力）合成而得。ECO這一名稱由Ecology（環保）、Conservation（節能）和Optimization（動力）合成而得。在環保觀念日益深入人心的今天，作為碳排放大戶的私人汽車一向是各方目光聚集的焦點。但是如今新能源汽車還在起步階段，怎樣使得試用傳統石油作為動力的汽車在不影響用戶正常使用的情況下，盡可能的減少廢氣排放就成為一個非常具有現實意義的話題。一般車輛廠商會根據汽車的自動變速檔位，發動機轉速，車速以及油溫等進行綜合判斷，最后由ECU控制單元得出一個最佳燃油量，這套系統稱為ECO駕駛模式。而隨著汽車的普及，車載導航也已經深入每個車主的日常行車生活。當去一個不熟悉的地方時，車主絕大多數會選擇車載導航提供的路徑。除了駕駛習慣，最后路線的選擇也會對實際產生的能源消耗產生決定性的影響。而針對每種車型，實際上省油的路線都是不同的。本文研究如何在根據汽車的油耗參數獲得一條適合本車行駛的路線已達到減少能源消耗的目的。無論在經濟上還是環境保護上都能起非常大的作用。

本文研究基于以時間距離為參數的算路模型，將用戶車型的能源消耗信息引入。本課題采用和企業項目同步推進，研究成果與項目同步應用驗證的模式。論文研究成功將會在公司導航軟件上實現并驗證。

二、傳統求路算法

汽車導航系統傳統路徑計算通常基于Djistra或者A-Star算法，并以時間或者路線長度為權中實現。由于本文研究的ECO求路算法是以傳統路徑計算為原型進行改進。本節首先需要介紹傳統A-star求路算法的實現原理。

（一）A-Star

A-Star算法是一種靜態路網中求解最短路最有效的方法。公式表示為：f（n）=g（n）+h（n），其中f（n）是節點n從初始點到目標點的估價函數，g（n）是在狀態空間中從初始節點到n節點的實際代價，h（n）是從n到目標節點最佳路徑的估計代價。

（二）bidirectional A-Star

雙向A-Star算法是從路徑規劃的起點終點同時采用A-Star算法進行路徑發散。并以非常快的速度在2點的中間地帶進行碰撞從而快速獲得最短路徑。

車載導航求路算法采用的是一道路作為最小單位進行發散，在上圖中紅色部分的就是根據道路類型計算出來的真實路徑權值g（n），而h（n）則是當前已經發散的線路的端點到終點的估計代價，又稱啟發權值。在論文使用的A-star算法中啟發權值的計算公式為：

啟發權值（Heuristic weight）= 當前發散端點到對面終點（起點）的直線距離/啟發速度（Heuristic speed）

由于啟發權值的作用，A-Star算法的發散形狀由Djistra圓形變為了橢圓形。并且能夠快速向對面方向的終點（起點進行發散）。雙向A-Star算法，由于2個方向都呈橢圓形發散，最終會在2個橢圓的公共部位發生碰撞，從而獲得最優路線。由于本文重點在對權重模型的分析，關于雙向A-Star算法只做介紹，并不進行深入分析。

（三）以時間為權值的代價模型

時間代價模型將發散的最小單位（道路）的權值計算分為link cost即通過這段道路所用的時間，和turn cost即在2段道路之間切換所花費時間（在路口的等待時間）。

Link cost= 道路（edge）的長度/道路的速度。

道路的速度與其屬性有關系。本文的導航引擎使用的道路數據提供以下幾種屬性：道路類型（高速路，國道，主干道等），道路子類型（匝道，環島等），道路平均速度和道路優先級.導航引擎通過對以上這些道路屬性。導航引擎通過對以上數據進行建表，對每一種可能的屬性組合的道路設置速度。并通過對大量的case結果的驗證分析。調整表內的速度的值從而獲得合理的路徑計算結果。

turn cost 基于轉彎的角度，將0°（直行）到360°分成若干區間。以u turn（掉頭）>左轉>右轉>直行的基準對每個區間的角度賦予轉彎等待時間的估計值。除此之外，turn cost中還會加入一些對路形控制的參數，比如對于進出高速路會加入額外的cost，防止計算出短時間內進出高速路的結果。

（四）以距離為權值的代價模型

距離代價模型比較簡單，道路的長度是唯一影響影響cost的大小的因素。

三、ECO求路模型

ECO 求路模型是一種以傳統雙向A-star算法作為基礎，并以油耗為作為權值的cost模型。

（一）ECO 模型參數

ECO 模型參數是在ECO路線計算中會影響權值的因素，即ECO求路算法的輸入，也就是我們能得到關于汽車油耗的一些參數。

1.勻速油耗

勻速油耗是汽車在某一特性速度下行駛一定距離所產生的能量消耗。

Delta Fuel 表示從上行的速度A加速到本行的速度B需要的油耗（單位：升）.例：0.00182761620681083 表示從15km/h 加速到 25km/h 所需要的油耗是0.0018L。第一行的油耗表示從停止加速到15km/h的油耗于是我們利用速度的平方作為x，delta fuel作為y。同樣可以建立一張分段函數圖，這樣我們可以獲得任意2種道路速度之間的加速能耗。

3.車重

車子的重量會影響汽車在加減速，上下坡中能量消耗。

對于某些車型沒有提供加速油耗信息（表2）。我們可以根據動能公式：E=?MV2

得到2個速度之間的能量消耗。

Cost = ?MV12-?MV22

除此之外，因為現在地圖數據信息日益豐富，道路的高度信息也已經被采集在導航地圖數據之中。有了高度信息之后，我們可以計算車輛在爬升過程中所消耗的能量，從而使得汽車能夠回避一些上升趨勢的路段。

根據勢能公式我們得到爬坡能量Cost=mgΔh

由于ECO模型中cost的單位為油耗，我們還需要將動能勢能公式中的能量單位轉換成油耗才能使用在cost模型中。

4.能量轉化率

由于傳統內燃機在轉換能量時無法將全部燃燒得到的能量轉化成動能，大部分能量將變成熱能散發掉。所以我們在將能量消耗轉化成油耗的時候必須要使用到能量轉化率。例如某種汽油一升能量為5680KJ，經過一臺能量轉化率為30%的汽油機，最終獲得的能量應該為1704KJ.

5.車輛怠速油耗

車輛怠速油耗用于計算在汽車等紅綠燈過路口時，發動機在怠速運轉時所需的能量消耗。

（二）ECO 求路算法

從3.1中列出的各個參數我們可以獲得一輛汽車的基本油耗信息。現在我們需要將這些信息應用于傳統的雙向A-Star算法中從而獲得一條最省油的路線。

1.傳統雙向A-Star算法的實現

雙向A-Star 算法需要起點終點同步進行求路發散，具體流程如下：

（1）計算起點終點所在道路的cost，分別放入2個隊列中；

（2）根據算法選擇一個隊列。（可以采用輪詢方式）；

（3）在隊列中POP出一個cost（ECO權重+啟發權重）最低的節點；

（4）將這個節點在另一個隊列中查找如果有相同的節點存在則找到最優路線，判斷算法結束。否則進入5；

（5）取得POP出來cost最低節點的相鄰節點。并分別計算從原節點到相鄰節點cost，最后將這些相鄰節點存入隊列中。回到步驟2。

其他雙向A-Star算法中使用的技術，如啟發速度，剪枝，判斷算法結束，保證結果最優在本文不做詳細說明。

2. ECO Cost 計算模型

ECO Cost由2部分組成

Link cost：即汽車通過彈出節點與相鄰節點之間道路的油耗

Turn cost：即汽車從彈出節點之前道路到下一個相鄰節點道路之間切換的油耗

（1）ECO Link cost。ECO 模型中link cost可以從地圖數據中的道路長度和，道路行駛速度和勻速油耗的迅速行駛油耗表中計算得到。首先通過查表的方式或者當前道路速度值所對應的單位油耗并轉換成單位：m/ml（即每米耗油毫升量）。最后Link cost = 道路長度 / 單位油耗。

（2）ECO Turn Cost。ECO 模型中的turn cost表示汽車在2段道路之間切換所需的能耗。相對于link cost更復雜。Turn cost需要考慮以下因素。

在2條路進行切換時等待時間，如紅綠燈，左轉彎時對面車道車輛等情況。等待時間與車輛怠速油耗可以計算出turn cost中的 wait cost部分。我們根據已時間為權重的最快路徑模型可以獲得轉彎角度與所需時間的對照表。

在2條道路切換時發生速度變換所導致的油耗。速度變化有以下幾種可能：1）由低速路駛入高速路時，因為加速產生的油耗；2）在發生轉彎減速后，重新恢復原速所產生的油耗；3）在路口低優先級路上的車輛需要停止等待高優先級道路上的車輛，之后恢復元素所產生的油耗。道路優先級屬性也可以從地圖數據中獲得。

四、ECO 模型驗證

通過對3中提出算法的代碼實現，在win32模擬導航界面上完成ECO求路的設計。

我們選取短距離Test Case起點位于：舊金山的Lowell St。

目的地為：舊金山的聯合廣場。

分別計算一條ECO路線，最快路線，最短路線（圖6）進行分析。

圖4中紅色路線為最短路徑，綠色為最快路徑，黃色路線為ECO路徑結果。可以看出ECO路線有部分結果與最快路線重疊。

根據Route Summary （圖7）顯示：ECO路線（No02）的長度和ETT（預計旅行時間）介于最快路線（No00）和最短路線（No01）之間，比較“中庸”。現在我們將對差異部分路線進行分析，看下是否能達到省油的目的。

如圖8所示ECO路線和最快路線在Alemany Blvd和Geneva Ave路口分開，最快路線選擇先向西迂回以便能夠盡快上高速I-280前往目的地。而ECO路線選擇沿著時速在60km的 Alemany Blvd前進至US-101才上了高速。

根據之前勻速油耗表（表1）可以看出，該車型在60km速度的油耗（4.1）明顯低于高速120km的油耗（6.8）。

路線沿著Alemany Blvd這段基本沒有轉彎，而且Alemany Blvd的優先級高于其周圍的小路，這樣使其停車等待的幾率降低。最終ECO路線還是上了高速原因是雖然Alemany Blvd的時速更適合該車型，但是隨著離市中心越近，被其他道路打斷的可能性也就越高導致turn cost會不斷升高。最后選擇了高速。由此可見高速路對于中長途仍然是省油的不二之選。

最短路線直接選擇一路穿過舊金山市區到達目的地，無論從哪個角度看這條路線都與省油無關。

通過以上Test Case分析，ECO模型所獲得的路線確實比最快和最短路線更適合該車型的經濟行駛。

五、ECO求路算法總結及后續研究

ECO求路是基于傳統雙向A-Star算法，并以汽車油耗作為權值的路徑計算方法。ECO模型以特定車型油耗信息為基礎，并綜合地圖數據。從道路的速度，優先級，類型等數據綜合考慮。使得用戶能夠得到一條盡量保持勻速，經濟速度的路線。

本文實現的ECO求路還有以下不足：

油耗信息必須提前輸入，統一車型一個標準。不能設計符合用戶駕駛習慣的路線。

時間權重在整個cost 模型中沒有考慮，對于某些極端case，會出現ECO路線比最快路線ETT（預計旅行時間）大好多的情況。

地圖數據中的高度信息沒有使用。

以上問題會在本文的后續研究中逐一分析解決，除此之外本文的算法僅適用于傳統汽油車輛。現在新能源發展大背景下，將會有更多混合動力車，純電動車出現。如何改進本文的算法，使之適應于最新汽車發展方向，也是后續研究的重點內容。

參考文獻：

[1]Sanders，P.，Schultes， D.： Highway hierarchies hasten exact shortest path queries.In：13th European Symposium on Algorithms （ESA）.Volume 3669 of LNCS.，Springer，2005：568–579.

[2]Peter Sanders and Dominik Schultes ： Engineering Highway Hierarchies.In：ESA 2006：804-816

[3]陳圣群，董林飛.Dijkstra和A_star算法在智能導航中的應用分析[J].重慶科技學院學報，2010（06）.

Abstract：ECO （Ecology，Conservation，Optimization） route calculation cost module was proposed in this paper. The algorithm was based on bidirectional A* search and refer to traditional fastest and shortest route cost module algorithm. And also the fuel consumption data was applied in Ecology cost module. The algorithm can got a route which is the most fuel-efficient for a special vehicle type. Then algorithm was improved from the user experience to get a route which can be accepted by more users. All the search results were implemented， analyzed， verified and improved on the special navigation system

Keywords： Navigation； ECO； Fuel Saving； Path Planning