[發明專利]一種多途經點導航路線規劃方法和系統

有效

• 申請號: 201610054144.4
• 申請日: 2016-01-27
• 公開（公告）號: CN105675002B
• 公開（公告）日: 2018-03-30
• 發明（設計）人: 閆凱;劉釗
• 申請（專利權）人: 閆凱;劉釗
• 主分類號: G01C21/34
• 分類號: G01C21/34;G01S19/39
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及道路導航規劃，優化調度領域，具體來說，涉及針對多途經點（多目的地）、多影響因子情境下的路線規劃及影響因子權重確定的方法和系統。

背景技術

近年來，隨著交通工具的普及以及人們出行尤其是遠距離出行的增多，運行在各類導航儀、移動終端上的路線導航系統（包含汽車、自行車、步行導航）得到快速發展。尤其是安裝在移動終端的利用GPS的電子地圖程序，憑借其低廉的價格、實時更新的地圖數據以及與其他應用軟件方便結合的能力，給人們出行的方案帶來了一場革命。用戶只需要在電子地圖上標出起點和終點，就可以方便的找到出行的路線。

在當前背景下，導航路線的自動、優化規劃算法成為熱門研究領域。國內外地圖、位置、導航等領域的服務廠商均投入大量精力進行導航算法的優化改進。國外較著名的包括谷歌地圖和蘋果地圖等，國內較著名的有百度地圖、高德地圖等，以及各類導航儀生產商家自己生產制作的地圖服務系統。從用戶體驗度來說，在最短的時間內提供出使用者所認為的最優化的道路行駛方案是該領域的終極目標。

對于這個目標可從兩個方面來看，首先是“最短時間”，這是指從用戶輸入起點和目的地到生成一條規劃路線的時間。這主要取決于軟件的操作界面人性化程度以及后臺優化算法的效率。目前而言，各廠商的操作界面大同小異，均提供手動輸入、地圖點取、常用地址等多種方法便于確定起點目的地。各廠商的差異主要集中在作為商業秘密的優化算法。對此各廠商存在較大差異。比如同時運行在相同硬件上的谷歌地圖路線規劃速度較大多廠商有明顯優勢。且在行駛過程中不間斷計算新的最優路線，供用戶選擇。當用戶出現路線偏移時，能迅速給出新的路線。如何優化算法，在“最短計算時間”內提供路線是當前各廠商研究的主要內容。

上述目標的第二個方面是“使用者所認為的最優化道路”。通常而言用戶出行的目的是快速到達目的地，因此這個最優化道路一般是指最短路徑或者最短行駛時間的路線。對此各廠商也提出了多種解決方案。比如谷歌地圖會憑借其巨大用戶數通過大數據分析，在決定路線的時考慮一系列因素，并依賴于某一特定地區的可用數據流。這些因素包括道路的官方最高限速、建議駕駛速度、某一道路類型的實際行駛速度、某段時間內的歷史平均速度(谷歌地圖有時會調取這一路段的行駛速度平均值，有時則會調取某一天內特定時間的行駛速度)、此前用戶的實際行駛時間以及實時路況等信息。在獲得這些信息后，谷歌地圖會將這些不同來源的數據進行整合，并給出自己最好的判斷。事實上，大部分提供路線導航服務的廠家都會將預測駕駛時間與實際結果進行對比，從而幫助自己不斷改進算法和數據源。而在這一方面做得較好的公司則往往是那些擁有巨大用戶使用量的企業，他們往往可以在長期內提供最好的路線推薦。除此之外，考慮到有時用戶的需求并不是最快的到達目的地，因此“最優路線”并不單指最快的路線。對此，部分廠家也進行了研究。比如雅虎實驗室的員工日前開發出了一套導航算法。在新算法下，地圖導航的依據不再是兩點間最短的距離，而是哪條路線沿途的風景更“亮麗”。在用戶輸入起點和終點信息后，算法會搜索所有可能的路線，把各路線沿途地點的景致得分相加，通過比較找到一條最美麗的行程。雅虎員工表示，“美麗”的路線平均下來會比那些最短的路線長12%。但該規劃策略一般適用于步行導航而非汽車導航。

其實在某些情境下“用戶所認為的最優路線”并非最短、最快路線的情況比比皆是。而對此當前廠商所提供的服務幾乎空白。絕大多數導航軟件只提供最短時間、最短路程、避開高速三種規劃策略。因此不能滿足用戶的個性化路線需求。比較突出的一種情景是用戶對于途經點的需求。這一需求在快遞服務、送餐服務、接送服務等涉及到多個目的地的領域顯得特別突出。雖然當前部分廠家提供在道路規劃開始前添加途經點（waypoint），以強制要求路線必須經過這些點，但是并不能考慮到這些途經點之間的優先級差異性。這個優先級一般又是由多種因素隱式決定的，因情況改變的，因此也并不能強制規定路線途經順序。對于這一需求，當前使用者采取的方法是先在電腦端利用一些多目的地路線規劃輔助軟件進行人工的路線規劃，然后按順序輸入移動端導航軟件，從而得到用戶所需求的路線。但是這不僅費時費力，在某些情況下更是不可實現的。比如送餐司機在執行多個目的地送達時，不可能預先規劃好每個客戶的送餐順序并手動輸入導航儀。