一種實時路徑規劃的方法和系統的製作方法

2023-10-19 06:28:12 1

一種實時路徑規劃的方法和系統的製作方法
【專利摘要】本發明提供了一種實時路徑規劃的方法和系統，涉及智能交通【技術領域】。所述方法包括：當前客戶端按初始路逕行駛時，實時採集其他客戶端的目的地、採樣位置和採樣時間；根據所述其他客戶端的目的地、採樣位置和採樣時間分別規劃其他客戶端的導航路徑，並從所述導航路徑中分別提取包括所述初始路徑的各路段、與所述各路段相關的關聯路段的目標路段；對所述目標路段、其他客戶端的採樣位置和採樣時間進行統計分析，預測未來時間段內所述初始路徑中各路段的路況信息。本發明，數據範圍廣，樣本均勻，提高了路徑規劃的結果的準確度，特別是對於規律性不強的路況變化，提高了路徑規劃的準確度。
【專利說明】一種實時路徑規劃的方法和系統

【技術領域】
[0001] 本發明涉及智能交通【技術領域】，特別是涉及一種實時路徑規劃的方法和系統。

【背景技術】
[0002] 道路的路徑規劃是GPS【技術領域】中的一種典型應用，目前已經開始被廣泛應用。 在現有技術中，路徑規劃往往基於路網拓撲關係，考慮路網的相關道路基本屬性，比如道路 的等級、車道數、十字路口數量、紅綠燈的數量等基本屬性，利用拓撲算法給出起點和終點 之間的總距離最短或總耗時最短等路徑方案。
[0003] 傳統的路徑規劃的方法是利用公路一些車輛中的GPS歷史記錄的車速，來判斷採 樣時間下這個路段的通暢情況，如果歷史上當前路段的車速普遍較高，則判斷為通暢，如 果歷史上當前路段的車速普遍較低，則視為擁堵。並以記錄GPS車速的方式持續記錄路 況信息，從而利用歷史上的GPS路況信息來推斷未來的路況信息。比如歷史上路段A在 11:00-14:00之間擁堵，那麼預測路段A在當天的11:00-14:00之間也擁堵。
[0004] 在實時導航時，往往依據路網的當前交通流量狀況進行導航，如果某路段中的各 車輛移動緩慢，則認為該路段的流量較高；反之該路段的流量較低。將各路段交通流量設定 不同的權值，根據當前車輛的移動速度和各路段的交通流量計算從車輛的採樣位置到目的 地的總代價，從而進行路徑規劃，並將代價最低，即時間花費最少的路徑返回給當前車輛。
[0005] 但是，上述方案中，第一：數據信息稀疏且範圍有限：只有很少量的出租、公交裝 載了速度記錄儀，所以得到的歷史數據只對主幹道有效，作用範圍有限，而且所有樣本並非 均勻分布在所有的汽車中，歷史數據中樣本不夠均勻，也可能會導致結果不夠準確。第二： 預測能力較差：僅僅通過道路的歷史通行狀況或當前採集的實時流量來預測未來路況，信 息不夠充分，特別是對於規律性不強的路況變化無法準確預測，由於當前車輛在進行路徑 規劃時所依據的各路段的路況將在當前車輛的行駛過程中不斷變化，在當前車輛行駛到之 前進行路徑規劃的某一路段時，該路段的路況很可能由好變差，則用戶很可能行駛在預測 時路況好、但實際已變得擁堵的道路上，反而增加了行駛時間。


【發明內容】

[0006] 本發明提供一種實時路徑規劃的方法，解決現有技術中數據信息稀疏且範圍有限 的問題，對規律性不強的路段預測能力差等問題。
[0007] 為了解決上述問題，本發明公開了一種實時路徑規劃的方法，其特徵在於，包括：
[0008] 當前客戶端按初始路逕行駛時，實時採集其他客戶端的目的地、採樣位置和採樣 時間；
[0009] 根據所述其他客戶端的目的地、採樣位置和採樣時間分別規劃其他客戶端的導航 路徑，並從所述導航路徑中分別提取包括所述初始路徑的各路段、與所述各路段相關的關 聯路段的目標路段；
[0010] 對所述目標路段、其他客戶端的採樣位置和採樣時間進行統計分析，預測未來時 間段內所述初始路徑中各路段的路況信息。
[0011] 優選的，所述對所述目標路段、其他客戶端的採樣位置和採樣時間進行統計分析， 預測未來時間段內所述初始路徑中各路段的路況信息，包括：
[0012] 對所述其他客戶端的採樣位置和採樣時間進行統計分析，預測未來時間段內每個 客戶端的對應的位置，統計目標路段中的車輛數得到所述初始路徑中各路段的路況信息。
[0013] 優選的，所述對所述其他客戶端的採樣位置和採樣時間進行統計分析，預測未來 時間段內每個客戶端的對應的位置，統計目標路段中的車輛數得到所述初始路徑中各路段 的路況信息，包括：
[0014] 針對每個客戶端的採樣位置和採樣時間，結合既定的車速模型計算每個客戶端對 應的車速；
[0015] 根據所述每個客戶端的車速和所述車速模型，預測各個客戶端未來時間段內在對 應的導航路徑上的位置；
[0016] 以目標路段為單位對預測得到的所述各個客戶端未來時間段內在對應導航路徑 上的位置進行統計，得到在未來時間段內所述初始路徑中各路段的路況信息。
[0017] 優選的，所述車速模型通過採集各客戶端在路網中的不同地點和不同時間的行駛 信息並進行結構化訓練獲得。
[0018] 優選的，所述初始路徑根據當前客戶端的採樣位置、採樣時間和目的地，採用路況 預測模型規劃獲得。
[0019] 優選的，所述根據所述其他客戶端的目的地、採樣位置和採樣時間分別規劃其他 客戶端的導航路徑，包括：
[0020] 根據其他的客戶端的目的地、採樣位置和採樣時間，採用路況預測模型規劃其他 客戶端對應的導航路徑。
[0021] 優選的，所述路況預測模型通過以下步驟構建：
[0022] 採集各客戶端記錄的各種類型的歷史出行信息；
[0023] 根據所述歷史出行信息進行規劃，得到各客戶端對應的規劃路徑；
[0024] 根據歷史出行信息的類型對應的權重，以路段為單位對所述規劃路徑進行統計， 統計每條路段在各時段對應的車輛流量；
[0025] 根據每條路段上各時段內的車輛流量進行數據訓練，構建路況預測模型。
[0026] 優選的，所述採集各客戶端記錄的各種類型的歷史出行信息包括：
[0027] 採集每個客戶端對應記錄的個性化信息，並將個性化信息轉化為語義信息；所述 個性化信息包括郵件、簡訊、日程中的文本數據；
[0028] 從所述語義信息中提取歷史出行信息。
[0029] 優選的，所述預測未來時間段內所述初始路徑中各路段將的路況信息包括：
[0030] 根據所述目標路段、其他客戶端的採樣位置和採樣時間，統計未來時間段內各目 標路段上的車輛總流量，並將所述車輛總流量與相應路段上的飽和閾值進行比較；
[0031] 根據比較結果判斷所述未來時段內各路段的路況信息。
[0032] 優選的，還包括：
[0033] 根據所述初始路徑中各路段的路況信息對所述初始路徑進行實時修正。
[0034] 優選的，所述根據所述初始路徑中各路段的路況信息對所述初始路徑進行實時修 正，包括：
[0035] 如當前客戶端在所述初始路徑中將要行駛的第一路段對應的交通壓力大於第一 閾值，則根據與第一路段相關的關聯路段的交通壓力情況，將第一路段變更為所述關聯路 段中對應的交通壓力小於第一閾值的第二路段。
[0036] 本發明還提供了一種實時路徑規劃的系統，包括：
[0037] 採集模塊，用於當前客戶端按初始路逕行駛時，實時採集其他客戶端的目的地、採 樣位置和採樣時間；
[0038] 關聯路段提取模塊，用於根據所述其他客戶端的目的地、採樣位置和採樣時間分 別規劃其他客戶端的導航路徑，並從所述導航路徑中分別提取包括所述初始路徑的各路 段、與所述各路段相關的關聯路段的目標路段；
[0039] 擁堵判斷模塊，用於對所述目標路段、其他客戶端的採樣位置和採樣時間進行統 計分析，預測未來時間段內所述初始路徑中各路段的路況信息。
[0040] 優選的，所述擁堵判斷模塊包括：
[0041] 路況分析模塊，用於對所述其他客戶端的採樣位置和採樣時間進行統計分析，預 測未來時間段內每個客戶端的對應的位置，統計目標路段中的車輛數得到所述初始路徑中 各路段的路況信息。
[0042] 與現有技術相比，本發明包括以下優點：
[0043] 本發明在當前客戶端行駛時實時獲取其他客戶端對應的實時行駛信息，以對當前 的客戶端進行實時的路徑規劃，數據範圍廣，樣本均勻，提高了路徑規劃的結果的準確度； [0044] 由於採集了各客戶端的實時行駛信息，預測其他用戶對當前客戶端對應的初始路 徑和初始路徑相關的關聯路段造成的影響，從而實時計算初始路徑中將要發生擁堵的路 段，進一步實時對當前客戶端的行駛路徑進行調整，從而使當前客戶端可以避免將要發生 擁堵的路段，特別是對於規律性不強的路況變化，提高了路徑規劃的準確度。

【專利附圖】

【附圖說明】
[0045] 圖1是本發明實施例一的一種實時路徑規劃的方法的流程示意圖；
[0046] 圖2和圖3是本發明的實時路徑規劃的方法的一種示例；
[0047] 圖4是本發明實施例二的一種實時路徑規劃的方法的流程示意圖；
[0048] 圖5是本發明實施例三的一種實時路徑規劃的系統的結構示意圖；
[0049] 圖6是本發明實施例四的一種實時路徑規劃的系統的結構示意圖。

【具體實施方式】
[0050] 為使本發明的上述目的、特徵和優點能夠更加明顯易懂，下面結合附圖和具體實 施方式對本發明作進一步詳細的說明。
[0051] 本發明的核心思想之一是：當前用戶按初始的既定的初始路線行駛時，採集其他 用戶在終端中輸入的目的地、實時上傳的位置和採樣時間進行分析，統計其他車輛的規劃 路徑中涉及到的初始路線及其關聯路段，結合這些車的採樣位置和對應的規劃路徑，統計 未來時段這些車輛將對初始路線中各路段的路況信息，從而預測初始路線中將形成的擁堵 位置，進一步可對初始路線中的擁堵路段進行調整，將擁堵路段調整至交通壓力小的相關 路段。
[0052] 實施例一
[0053] 參照圖1，示出了本發明實施例一的一種實時路徑規劃的方法的流程示意圖，具體 可以包括：
[0054] 步驟110,當前客戶端按初始路逕行駛時，實時採集其他客戶端的目的地、採樣位 置和米樣時間；
[0055] 參照圖2,比如當前客戶端從A出發至X時，給客戶端規劃初始路徑為A-B-F-G，那 麼在得到初始路徑後，採集在線的其他的客戶端的目的地、採樣位置和採樣時間，在本發明 中，可規定每隔一定時間間隔進行採集。當前客戶端規劃初始路徑時，可以採用通用的、按 照時間最短等拓撲方法進行規劃，當然也可以採用其他方法進行規劃。在本發明中，對於車 輛行駛過程來說，由於網絡存在時延，所述實時的意思可以為每隔指定的短時間段（比如 半分鐘、1分鐘等）。
[0056] 步驟120,根據所述其他客戶端的目的地、採樣位置和採樣時間分別規劃其他客戶 端的導航路徑，並從所述導航路徑中分別提取包括所述初始路徑的各路段、與所述各路段 相關的關聯路段的目標路段；
[0057] 在本發明中，根據採集到的其他客戶端的目的地、採樣位置和採樣時間分別規劃 對應客戶端的導航路徑。處於行駛過程中的各客戶端，其規劃的導航路徑可為實時規劃的， 即在客戶端行駛過程中可能在不斷修正其行駛路線。所述路徑規劃可以採用通用的、按照 時間最短等規劃方法進行規劃，當然也可以採用其他方法進行規劃。
[0058] 根據當前客戶端的初始路徑，從所述其他客戶端的導航路徑中分別提取目標路 段。其中，目標路段包括所述初始路徑的各路段、與所述各路段相關的關聯路段；與初始路 徑各路段相關的關聯路段可以理解為與初始路徑的各路段具有連接的相似目標節點的路 段，比如，路網中路段A連接節點L1和L2,而路段Μ也連接節點L1和L2,那麼路段Μ為與路 段Α相關的關聯路段；又比如路段Α1連接節點L1和L3,路段Α2連接節點L3和L2,那麼路 段A1+A2為與路段A相關的關聯路段，其他情況以此類推。其中，初始路徑的各路段的關聯 路段可以根據初始路徑的各路段、各節點間、及相隔距離確定，比如對於初始路徑A-B-C-D， 路段A的兩端節點可記為節點LI、L2,路段B的兩端節點可記為節點L2、L3,路段C的兩端 節點可記為節點L3、L4,路段D的兩端節點可記為節點L4、L5,而節點L2到L3之間可通過 路段F或者路段E1-E2或路段G1-G2-G3到達，而路段F和路段E1-E2的路程與路段B路程 的比值在指定範圍內，比如小於3.0,那麼可將路段F和路段E1-E2作為路段B的關聯路段。
[0059] 如此，可獲取與初始路徑相關所有路段中正在行駛車輛的導航路徑，從而可通過 後續步驟推測未來時段內對初始路徑路況的影響。
[0060] 步驟130,對所述目標路段、其他客戶端的採樣位置和採樣時間進行統計分析，預 測未來時間段內所述初始路徑中各路段的路況信息。
[0061] 針對每個客戶端的導航路徑，以採樣位置為起點，採樣時間為基準，計算該客戶端 在未來時間段內（比如10分鐘）在其導航路徑中的位置，該位置可能在所述初始路徑的某 一個路段中。如此，可根據各個客戶端在未來時間段內在其導航路徑中的位置，以路段為單 位，統計所述未來時間段內，初始路徑的各路段的交通量，從而預測未來時間段內初始路徑 中各路段的路況信息。
[0062] 其中，所述未來時間段還可根據當前客戶端的從當前位置行駛進入下一路段的時 間為標準，比如客戶端當前在路段B的位置bl時，行駛至路段B的終點b2(也為下一路段的 起點）花費的時間tl，若當前時刻為t，那麼可計算t+tl時刻附近的時間段內（比如t+tl 時刻的前1分鐘的時間段內）或者t+tl時刻的初始路徑中的交通壓力。
[0063] 優選的，所述對所述目標路段、其他客戶端的採樣位置和採樣時間進行統計分析， 預測未來時間段內所述初始路徑中各路段的路況信息包括：
[0064] 對所述其他客戶端的採樣位置和採樣時間進行統計分析，預測未來時間段內每個 客戶端的對應的位置，統計目標路段中的車輛數得到所述初始路徑中各路段的路況信息。 具體包括：
[0065] S11，針對每個客戶端的採樣位置和採樣時間，結合既定的車速模型計算每個客戶 端對應的車速；
[0066] 其中，通過採集各客戶端在路網中的不同地點和不同時間的行駛信息並進行結構 化訓練，獲得車速模型；所述車速模型用於分析路網中各路段的坐標點在不同時刻的車速。 [0067] 採集各客戶端在路網中的不同地點和不同時間的行駛信息，包括行車速度、採集 時間、採集地點等，並將採集到的各客戶端的行駛信息進行結構化，比如結構化為〈採集 時間、採集地點、行車速度〉的向量，然後根據採集地點所屬的路段對該結構化信息進行歸 並。再將歸併後的各路段的結構化信息按時間段進行統計，統計各客戶端的行駛速度，最後 對該時間段內該路段的各客戶端的行駛速度進行加權計算，得到的結果即為該路段在該時 間段內的車速。然後即可知道路網中不同路段在不同時刻的車速。當然分析得到路網中不 同路段在不同時刻的車速還可採用其他方法。
[0068] S12,根據所述每個客戶端的車速和所述車速模型，預測各個客戶端未來時間段內 在對應的導航路徑上的位置；
[0069] 比如，根據當前位置在路網中找到對應的路段，再找到當前時間的速度後，計算以 當前速度行駛完對應路段的時間，然後進入導航路徑中該路段對應的下一路段的時間，然 後在車速模型中根據該進入下一路段的時間找到該下一路段的速度，繼續根據上述過程進 行計算，即可計算導航路徑上未來時間段內該客戶端所在的位置。如此即可預測得到各個 客戶端在未來時間段內在其導航路徑中所處的位置。
[0070] S13,以目標路段為單位對預測得到的所述各個客戶端未來時間段內在對應導航 路徑上的位置進行統計，得到在未來時間段內所述初始路徑中各路段的路況信息。
[0071] 在統計目標路段中各客戶端在未來時間段內出現的位置後，即可以目標路段為單 位，對預測得到的所述各個客戶端未來時間段內在對應導航路徑上的位置進行統計，得到 在未來時間段內所述初始路徑中各路段的路況信息。比如參照圖2和圖3,在圖2中，在給 當前客戶端規劃初始路線A-B-F-G後，通過上述步驟統計到在當前客戶端路段B行駛完畢 時，在路段F中客戶端的數量很多，則路段F在當前客戶端路段B行駛完畢時交通壓力大。
[0072] 優選的，所述預測未來時間段內所述初始路徑中各路段的路況信息包括：
[0073] 步驟B11，根據所述目標路段、其他客戶端的採樣位置和採樣時間，統計未來時間 段內各目標路段上的車輛總流量，並將所述車輛總流量與相應路段上的飽和閾值進行比 較；
[0074] 其中，飽和閾值通過以下步驟獲得：
[0075] 1)獲取路網中各道路的道路信息，其中，所述道路信息包括以下至少一項：車道 數量、路線形狀、限速信息和車流信息；
[0076] 2)依據所述道路信息確定各道路上行駛車輛的飽和閾值。
[0077] 本發明實施例中，可以首先獲取各道路的道路信息，所述道路信息是道路的基本 數據，則所述道路信息包括以下至少一項：車道數量、路線形狀、限速信息，當然還可以包括 道路名稱，地理位置（坐標位置）等其他數據。從而，可以通過道路信息推斷出各道路上行 駛車輛的飽和閾值。
[0078] 其中，所述依據所述道路信息確定各道路上行駛車輛的飽和閾值包括：
[0079] 21)獲取全網中記錄的各車輛的歷史軌跡，拆分所述歷史軌跡中對應的路段，得到 路網中各路段的道路信息；
[0080] 22)將所述道路信息按時序進行統計，分析路網中各路段在對應時刻的流量數據， 從而確定各道路在擁堵狀態時的車輛的飽和閾值。
[0081] 由於實際情況中修路，車輛行駛等原因會導致各道路上可行駛的車輛數目變化， 因此，本發明實施例還採集了全網中記錄的各車輛的歷史軌跡，用於對各道路實際的車輛 通行量進行判定，如將所述道路信息按時序進行統計得，某路段中各車輛的平均速度小於 一定擁堵閾值，如l〇km/h時，該路段中對應的車輛的平均數量為該路段在擁堵狀態下可容 納的最多的車輛，即為車輛的飽和閾值。其中，全網指的是道路狀況的可預測範圍，如以城 市為範圍進行預測，則全網可以包括該城市的各條道路。則所述全網通行狀況指的是全網 內各道路的通行情況，如道路上行駛的車輛數目，是否擁堵等。
[0082] 因此，可以對所述歷史軌跡中對應的路段進行拆分，例如以500米為間隔進行拆 分，從而得到路網中各路段的道路信息，其中道路信息的車流信息中包括道路在各時段內 的通行狀況、車輛數據等數據。因此可以將該道路信息按時序進行統計，分析路網中各路段 在對應時刻的流量數據，即確定在各時段的對應時刻路網中各路段行駛的車輛數目，以及 道路的擁堵狀況，從而確定各道路在擁堵狀態時的車輛的飽和閾值。
[0083] 步驟B12,根據比較結果判斷所述未來時段內各路段的路況信息。
[0084] 在本發明實施例中，所述路況信息可標識未來時段內各路段的擁堵程度。
[0085] 本發明實施例中，若路段上行駛的車輛數目超過此飽和閾值即為擁堵，若路段上 行駛的車輛數目等於或低于于此車飽和閾值即為通暢，而車輛數目超出（或不足）的程度 即為該路段擁堵（或通暢）的程度。
[0086] 對於預測得到的未來時段內各路段的路況信息，可直接顯示給當前的客戶端，以 供客戶端參考。
[0087] 優選的，本發明還包括：
[0088] 步驟140,根據所述初始路徑中各路段的路況信息對所述初始路徑進行實時修正。
[0089] 在本實施例中，前述步驟可以分析初始路徑中的擁堵位置，即在未來時間段內當 前客戶端可能在初始路徑的哪個路段擁堵，那麼針對該擁堵的路段，可以採用該路段的關 聯路段中擁堵程度低的路段替換該擁堵的路段，直至當前用戶端到達目的地。
[0090] 其中，所述根據初始路線中各路段的交通壓力對當前客戶端的初始路徑進行實時 修正包括：
[0091] 步驟S140,如當前客戶端在所述初始路徑中將要行駛的第一路段對應的交通壓力 大於第一閾值，則根據與第一路段相關的關聯路段的交通壓力情況，將第一路段變更為所 述關聯路段中對應的交通壓力小於第一閾值的第二路段。
[0092] 如前所述，當路段中的車輛數量超出飽和閾值則為擁堵，車輛數量不超出飽和閾 值則為通暢，那麼以車輛數量設置為交通壓力程度（即第一閾值），該值也可為飽和閾值， 該值越小，說明越通暢。
[0093] 比如參照圖2和圖3中，當前客戶端的初始路徑為A-B-F-G，根據其當前位置和所 處的路段B，分析其十分鐘內會行駛完路徑B，進入下一路段，那麼此時依據前述步驟，預測 得未來十分鐘內有35%的用戶的位置在路段F上，但同樣與路段B、G鄰接的路段Η在未來 十分鐘內有10%的用戶，儘管當前時間路段F中的用戶數量比路段Η中的用戶數量少，則由 於預測得到當前車輛在行駛完路段Β時，下一路段的交通流量將要發生變化，即路段F中的 用戶數量將少變多，路段Η中的用戶數量將由多變少，則實時將路段F變更為路段Η，調整當 前用戶的路線為A-B-H-G，從而避免了用戶行駛至未來將擁堵的路段，減少了行駛時間。
[0094] 另外，若在通暢的情況下，調整到小於第一閾值的第二路段時，還可綜合考慮第一 路段和第二路段對應的路程，根據其通暢程度對應的各路段中的車速，綜合計算行駛完該 路段的時間，選擇時間花費較少的路段返回當前客戶端。
[0095] 本發明實施例中，路徑規劃可以不斷以其他客戶端的導航路徑進行規劃，規劃準 確度高，數據範圍廣泛。
[0096] 本發明實施例可以實時獲取不同路徑上的客戶端的實時行駛信息，以對當前的客 戶端進行實時的路徑規劃，數據範圍廣，樣本均勻，提高了路徑規劃的結果的準確度；並且， 由於採集了各客戶端的實時行駛信息，預測其他用戶對當前客戶端對應的初始路徑和初 始路徑相關的關聯路段造成的影響，從而實時計算初始路徑中將要發生擁堵的路段，進一 步實時對當前客戶端的行駛路徑進行調整，從而使當前客戶端可以避免將要發生擁堵的路 段，特別是對於規律性不強的路況變化，提高了路徑規劃的準確度。.
[0097] 實施例二
[0098] 參照圖4,其示出了本發明實施例二的一種實時路徑規劃的方法的流程示意圖。 [0099] 在本實施例中，可基於全網用戶的歷史出行信息構建路況預測模型，然後在對客 戶端進行路徑規劃的時候進行參考，進一步增加數據源，提高數據的廣度和深度，從而可進 一步提1?路徑規劃的準確度。
[0100] 本實施例具體可以包括：
[0101] 步驟200,根據當前客戶端的採樣位置、採樣時間和目的地，採用路況預測模型規 劃最優的初始路徑；
[0102] 在本發明實施例中，所述路況預測模型通過分析用戶的出行信息獲得；所述路況 預測模型通過分析用戶的歷史出行信息獲得包括：
[0103] 步驟D11，採集各客戶端的各種類型的歷史出行信息；
[0104] 在本發明實施例中，可以採集全網用戶的各種歷史出行信息，比如郵件中的出行 信息、簡訊中的出行信息、日程中的出行信息等等。
[0105] 可選的，所述採集各客戶端記錄的各種類型的歷史出行信息包括：
[0106] 步驟D21，採集每個客戶端對應記錄的個性化信息，並將個性化信息轉化為語義信 息；所述個性化信息包括郵件、簡訊、日程中的文本數據；
[0107] 在本發明實施例中，所述個性化信息包括用戶的簡訊、郵件、日程等文本信息，包 括但不限於用戶的簡訊，郵件，日程等。
[0108] 步驟D22，從所述語義信息中提取歷史出行信息。
[0109] 對於得到的對應各客戶端的個性化信息，比如簡訊、郵件、日程等文本信息，本步 驟可對上述文本信息進行語義分析，轉化為語義信息，然後再從語義信息中提取出用戶出 發時刻對應的地點信息（比如出發點、目的地等），在其他實施例中，也可根據客戶端中的 GPS模塊上傳的歷史位置信息，分析用戶的歷史移動軌跡，預測用戶在某特定時刻的目的 地，從而獲得地點信息。基於所述地點信息通過路徑推理模板分析用戶未來的移動預判信 肩、。
[0110] 在本發明實施例中，路徑推理模板可以通過統計各地點關鍵詞的共線頻率獲得。 比如得知出發點為A、目的地為F，可統計路網中全體車輛的行駛記錄得到，大批量的經過 A、F的路徑對應的關鍵地點，判斷與A、F在同一條規劃路線上的出現的概率，即為共線頻 率。比如A-B-C-F的概率為80 %，A-B-D-F的概率為20 %，那麼用戶aaa行駛於路徑A-B-C-F 的概率為80 %，行駛於路徑A-B-D-F的概率為20%。然後結合出發時間，即可獲得包括路 徑、行駛於路徑的概率和出發時間三個屬性。比如用戶aaa :"時間：2013-3-19上午10:00， 路徑4-8-(：4，概率：80%"、"時間：2013-3-19上午10:00，路徑4-8-04，概率 ：20%"。其 中，根據地點的關鍵詞統計共線頻率時，可能存在共線頻率非常低的地點的關鍵詞，取共線 概率大於閾值的關鍵地點，整合得到待定路徑，即在統計時可以對共線頻率非常小的相關 路徑進行忽略，選擇共線頻率大於閾值的關鍵地點對應的各路徑信息。
[0111] 步驟D12,根據所述歷史出行信息進行規劃，得到各客戶端對應的規劃路徑；
[0112] 在本發明中可根據每個客戶端的行駛信息以及歷史出行信息進行規劃，獲得每個 客戶端的路徑分布。即對於獲得的各客戶端的歷史出行信息，可根據行駛信息對出行信息 進行糾偏，然後進行規劃獲得客戶端的路徑。比如出行信息包括預計出發點、目的地、出發 時間等信息，而行駛信息則為實際出發時間、出發地，則可對出行信息進行糾偏，比如分析 得到的客戶端歷史出行信息為在2013-4-20上午10:00從行駛A-B-C-D，而提取到的客戶端 的實際的行駛信息為客戶端2013-4-20上午9:30已經從A出發，並且延著與預測的路徑相 同的方向行駛，那麼即可將歷史出行信息的出發時間修改為2013-4-20上午9:30。然後可 以糾偏後的出發地、出發時間、目的地等信息進行路徑規劃。可以採用通常衛星路況的路徑 規劃，也可以採用不斷更新的路況預測模型進行規劃，得到各客戶端對應的規劃路徑。然後 即可將各客戶端的路徑分布到路網中。
[0113] 步驟D13,根據歷史出行信息的類型對應的權重，以路段為單位對所述規劃路徑進 行統計，統計每條路段在各時段對應的車輛流量；
[0114] 在本步驟中，出行信息即可化為在本步驟中可把出行信息化為〈起點，終點，路 線，起始時間，結束時間，權重〉的信息分布到相應路徑上。
[0115] 在本發明實施例中，來自不同數據源的出行信息可設置不同的權重。不同來源的 出行信息可信度也有一定的差異，比如郵件的廣告多一些，就比簡訊的可靠新略低，又比如 從提醒類應用程式中獲得的出行信息一般又高於簡訊，因此，可對不同數據源的歷史出行 信息設置不同的權重，以提高信息的真實性。
[0116] 在本發明實施例中，可以針對每一類型數據源的出行信息，以該類的歷史出行信 息計算某一時間斷內的路況，然後與該時間段內的衛星路況比較相似度（比如比較擁堵位 置的相似度），根據相似度為該類型數據源的出行信息賦予相應的權重，相似度高的則權重 高，相似度低的則權重低。並且可以根據相似度優化選擇採集哪些類型的數據源。
[0117] 如，本實施例中日程類的出行信息權重為0. 6,簡訊類出行信息權重為0. 3,郵 件類出行信息權重為〇. 1，那麼對於日程類出行信息的各規劃路徑，將該客戶端的按〇. 6倍 車輛數分布到各路段上。對於前述簡訊出行信息根據一條出行信息給客戶端A規劃了 2條 路徑N1和N2,其中，客戶端行駛於路徑N1的概率為0. 6,行駛於路徑N2的概率為0. 4,那麼 對於路徑N1，客戶端A對應的車輛流量為：1*0. 3*0. 6,那麼對於路徑N2,客戶端A對應的車 輛流量為：1*0. 3*0. 4。
[0118] 步驟D14,根據每條路段上各時段內的車輛流量進行數據訓練，構建路況預測模 型。
[0119] 在得到每條路段在各時段對應的車輛流量後，經數據訓練即可構建路況預測模 型。
[0120] 在本路況預測模型中，可依據歷史上各時間段內各路段上產生的車輛流量預測未 來時間段內各道路的車輛總流量。在該模型中，可根據該車輛的當前時間找到其所在路段 對應的速度，再調用為該車輛規劃得到的路徑，計算該車輛走完當前路段後進入路徑中下 一路段的時間，然後根據相應時間段獲取相應路段的車速，再計算走完該路段進入下一路 段的時間，如此循環，直至規劃的路徑結束。
[0121] 在給用戶提供導航服務的時候，會根據所有導航請求，動態規劃所有客戶端的導 航信息。當收到當前用戶的導航請求的時候，會根據上文計算得到的路況預測模型，為當前 用戶給出幾條候選路線，然後查看正在導航中的其他客戶端對應的行駛路線，是否會造成 這些候選路線的擁堵，並從候選路線中給出最佳的導航路線作為初始路線。然後再通過後 續步驟實時對初始路線進行修正。
[0122] 步驟210,當前客戶端按規劃的初始路逕行駛時，實時採集在線的其他客戶端的目 的地、採樣位置和採樣時間；
[0123] 該步驟原理與步驟110類似，在此不再詳述。
[0124] 步驟220,根據所述其他客戶端的目的地、採樣位置和採樣時間規劃其他客戶端的 導航路徑，並從所述導航路徑中提取包括所述初始路徑的各路段、與所述各路段相關的關 聯路段的目標路段；
[0125] 其中，所述根據所述其他客戶端的目的地、採樣位置和採樣時間規劃其他客戶端 的導航路徑包括：
[0126] 根據其他的客戶端的目的地、採樣位置和採樣時間，採用路況預測模型規劃其他 客戶端對應的最優路徑。
[0127] 所述路況預測模型通過前述的分析用戶的出行信息獲得。
[0128] 本步驟中，針對其他客戶端進行路徑規劃時，優選的可以採用採用路況預測模型 規劃其他客戶端最優的導航路徑，還可以採用其他方式進行路徑規劃。其中路況預測模型 與前述的類似，其規劃方法也類似。
[0129] 步驟230,對所述目標路段、其他客戶端的採樣位置和採樣時間進行統計分析，預 測未來時間段內所述初始路徑中各路段的路況信息；
[0130] 預測未來時間段內所述初始路徑中各路段的路況信息，從而得到其他客戶端對初 始路徑中各路段對應產生的交通壓力。
[0131] 步驟230原理與步驟130類似，在此不再詳述。
[0132] 優選的，本發明還包括：
[0133] 步驟240,根據初始路線中各路段的路況信息對當前客戶端的初始路徑進行實時 修正。
[0134] 步驟240原理與步驟140類似，在此不再詳述。
[0135] 對於當前客戶端的實時規劃路徑，也可實時的作為其他需要進行路徑規劃客戶端 的參考數據。
[0136] 本發明實施例可以實時採集全網各路段上其他客戶端對應的實時行駛信息，以對 當前的客戶端進行實時的路徑規劃，數據範圍廣，樣本均勻，提高了路徑規劃的結果的準確 度。
[0137] 並且，由於採集了各客戶端的實時行駛信息，預測其他用戶對當前客戶端對應的 初始路徑和初始路徑相關的關聯路段造成的影響，從而實時計算初始路徑中將要發生擁堵 的路段，進一步實時對當前客戶端的行駛路徑進行調整，從而使當前客戶端可以避免將要 發生擁堵的路段，特別是對於規律性不強的路況變化，提高了路徑規劃的準確度。
[0138] .進一步的，本發明在對客戶端規劃路徑時，結合到路徑規劃的模型，選擇最優路 徑，而所述路徑規劃的模型通過採集和分析客戶端的出行信息（包括日程、郵件、簡訊等信 息中的出行信息）並分布到路網中獲得，從而進一步增加了數據源的範圍，提高本發明對 當前客戶端的路徑預測和修正的準確度。
[0139] 需要說明的是，對於上述方法實施例而言，為了簡單描述，故將其都表述為一系列 的動作組合，但是本領域技術人員應該知悉，本發明並不受所描述的動作順序的限制，因為 依據本發明，某些步驟可以採用其他順序或者同時進行。其次，本領域技術人員也應該知 悉，說明書中所描述的實施例均屬於優選實施例，所涉及的動作和模塊並不一定是本發明 所必須的。
[0140] 實施例三
[0141] 參照圖5,其示出了本發明實施例三的一種實時路徑規劃的系統實的結構示意圖， 具體可以包括：
[0142] 採集模塊310,用於當前客戶端按初始路逕行駛時，實時採集其他客戶端的目的 地、採樣位置和採樣時間；
[0143] 關聯路段提取模塊320,用於根據所述其他客戶端的目的地、採樣位置和採樣時間 分別規劃其他客戶端的導航路徑，並從所述導航路徑中分別提取包括所述初始路徑的各路 段、與所述各路段相關的關聯路段的目標路段；
[0144] 擁堵判斷模塊330,用於對所述目標路段、其他客戶端的採樣位置和採樣時間進行 統計分析，預測未來時間段內所述初始路徑中各路段的路況信息。
[0145] 優選的，所述擁堵判斷模塊包括：
[0146] 路況分析模塊，用於對所述其他客戶端的採樣位置和採樣時間進行統計分析，預 測未來時間段內每個客戶端的對應的位置，統計目標路段中的車輛數得到所述初始路徑中 各路段的路況信息。
[0147] 優選的，所述路況分析模塊包括：
[0148] 車速計算模塊，用於針對每個客戶端的採樣位置和採樣時間，結合既定的車速模 型計算每個客戶端對應的車速；
[0149] 客戶端位置預測模塊，用於根據所述每個客戶端的車速和所述車速模型，預測各 個客戶端未來時間段內在對應的導航路徑上的位置；
[0150] 交通壓力判斷模塊，用於以目標路段為單位對預測得到的所述各個客戶端未來時 間段內在對應導航路徑上的位置進行統計，得到在未來時間段內所述初始路徑中各路段的 路況信息。
[0151] 優選的，還包括：車速模型獲取模塊，用於通過採集各客戶端在路網中的不同地點 和不同時間的行駛信息並進行結構化訓練，獲得車速模型。
[0152] 優選的，所述擁堵判斷模塊包括：
[0153] 交通壓力判斷模塊，用於根據所述目標路段、其他客戶端的採樣位置和採樣時間， 統計未來時間段內各目標路段上的車輛總流量，並將所述車輛總流量與相應路段上的飽和 閾值進行比較；根據比較結果判斷所述未來時段內各路段的路況信息。
[0154] 優選的，還包括：路徑修正模塊，用於根據所述初始路徑中各路段的路況信息對所 述初始路徑進行實時修正。
[0155] 優選的，所述路徑修正模塊包括：
[0156] 第一修正模塊，用於如當前客戶端在所述初始路徑中將要行駛的第一路段對應的 交通壓力大於第一閾值，則根據與第一路段相關的關聯路段的交通壓力情況，將第一路段 變更為所述關聯路段中對應的交通壓力小於第一閾值的第二路段。
[0157] 實施例四
[0158] 參照圖6,其示出了本發明實施例四的一種實時路徑規劃的系統實的結構示意圖， 具體可以包括：
[0159] 初始路徑規劃模塊410,用於根據當前客戶端的採樣位置、採樣時間和目的地，採 用路況預測模型規劃初始路徑；
[0160] 優選的，還包括路況預測模型構建模塊，所述路徑規劃的模型構建模塊包括：
[0161] 信息採集模塊，用於採集各客戶端記錄的各種類型的歷史出行信息；
[0162] 第一規劃模塊，用於根據所述歷史出行信息進行規劃，得到各客戶端對應的規劃 路徑；
[0163] 統計模塊，用於根據歷史出行信息的類型對應的權重，以路段為單位對所述規劃 路徑進行統計，統計每條路段在各時段對應的車輛流量；
[0164] 模型構建模塊，用於根據每條路段上各時段內的車輛流量進行數據訓練，構建路 況預測模型。
[0165] 優選的，所述信息採集模塊包括：
[0166] 採集轉換模塊，用於採集每個客戶端對應記錄的個性化信息，並將個性化信息轉 化為語義信息；所述個性化信息包括郵件、簡訊、日程中的文本數據；
[0167] 提取模塊，用於從所述語義信息中提取出行信息。
[0168] 採集模塊420,用於當前客戶端按規劃的初始路逕行駛時，實時採集在線的其他客 戶端的目的地、採樣位置和採樣時間；
[0169] 關聯路段提取模塊430,用於根據所述其他客戶端的目的地、採樣位置和採樣時間 規劃其他客戶端的導航路徑，並從所述導航路徑中提取包括所述初始路徑的各路段、與所 述各路段相關的關聯路段的目標路段；
[0170] 其中，所述針對所述其他的客戶端的目的地、採樣位置和採樣時間進行實時規劃 時包括：根據其他的客戶端的目的地、採樣位置和採樣時間，採用路況預測模型規劃其他客 戶端對應的導航路徑。
[0171] 擁堵判斷模塊440,用於對所述目標路段、其他客戶端的採樣位置和採樣時間進行 統計分析，預測未來時間段內所述初始路徑中各路段的路況信息。
[0172] 優選的，所述擁堵判斷模塊包括：
[0173] 路況分析模塊，用於對所述其他客戶端的採樣位置和採樣時間進行統計分析，預 測未來時間段內每個客戶端的對應的位置，統計目標路段中的車輛數得到所述初始路徑中 各路段的路況信息。
[0174] 優選的，所述路況分析模塊包括：
[0175] 車速計算模塊，用於針對每個客戶端的採樣位置和採樣時間，結合既定的車速模 型計算每個客戶端對應的車速；
[0176] 客戶端位置預測模塊，用於根據所述每個客戶端的車速和所述車速模型，預測各 個客戶端未來時間段內在對應的導航路徑上的位置；
[0177] 交通壓力判斷模塊，用於以目標路段為單位對預測得到的所述各個客戶端未來時 間段內在對應導航路徑上的位置進行統計，得到在未來時間段內所述初始路徑中各路段的 路況信息。
[0178] 優選的，還包括：車速模型獲取模塊，用於通過採集各客戶端在路網中的不同地點 和不同時間的行駛信息並進行結構化訓練獲得，獲得車速模型。
[0179] 優選的，所述擁堵判斷模塊包括：
[0180] 交通壓力判斷模塊，用於根據所述目標路段、其他客戶端的採樣位置和採樣時間， 統計未來時間段內各目標路段上的車輛總流量，並將所述車輛總流量與相應路段上的飽和 閾值進行比較；根據比較結果判斷所述未來時段內各路段的路況信息。
[0181] 優選的，還包括：路徑修正模塊450,用於根據初始路線中各路段的交通壓力對當 前客戶端的初始路徑進行實時修正。
[0182] 優選的，所述路徑修正模塊包括：
[0183] 第一修正模塊，用於如當前客戶端在所述初始路徑中將要行駛的第一路段對應的 交通壓力大於第一閾值，則根據與第一路段相關的關聯路段的交通壓力情況，將第一路段 變更為所述關聯路段中對應的交通壓力小於第一閾值的第二路段。
[0184] 本實施例與實施例三類似的模塊，在此不再加以詳述。
[0185] 對於系統實施例而言，由於其與方法實施例基本相似，所以描述的比較簡單，相關 之處參見方法實施例的部分說明即可。
[0186] 本說明書中的各個實施例均採用遞進的方式描述，每個實施例重點說明的都是與 其他實施例的不同之處，各個實施例之間相同相似的部分互相參見即可。
[0187] 本發明可用於眾多通用或專用的計算系統環境或配置中。例如：個人計算機、服務 器計算機、手持設備或可攜式設備、平板型設備、多處理器系統、基於微處理器的系統、網絡 PC、小型計算機、大型計算機、包括以上任何系統或設備的分布式計算環境等等。本發明優 選應用於嵌入式系統中。
[0188] 本發明可以在由計算機執行的計算機可執行指令的一般上下文中描述，例如程序 模塊。一般地，程序模塊包括執行特定任務或實現特定抽象數據類型的例程、程序、對象、組 件、數據結構等等。也可以在分布式計算環境中實踐本發明，在這些分布式計算環境中，由 通過通信網絡而被連接的遠程處理設備來執行任務。在分布式計算環境中，程序模塊可以 位於包括存儲設備在內的本地和遠程計算機存儲介質中。
[0189] 最後，還需要說明的是，在本文中，諸如第一和第二等之類的關係術語僅僅用來將 一個實體或者操作與另一個實體或操作區分開來，而不一定要求或者暗示這些實體或操作 之間存在任何這種實際的關係或者順序。
[0190] 以上對本發明所提供的一種實時路徑規劃的方法和系統，進行了詳細介紹，本文 中應用了具體個例對本發明的原理及實施方式進行了闡述，以上實施例的說明只是用於幫 助理解本發明的方法及其核心思想；同時，對於本領域的一般技術人員，依據本發明的思 想，在【具體實施方式】及應用範圍上均會有改變之處，綜上所述，本說明書內容不應理解為對 本發明的限制。
【權利要求】
1. 一種實時路徑規劃的方法，其特徵在於，包括： 當前客戶端按初始路逕行駛時，實時採集其他客戶端的目的地、採樣位置和採樣時 間； 根據所述其他客戶端的目的地、採樣位置和採樣時間分別規劃其他客戶端的導航路 徑，並從所述導航路徑中分別提取包括所述初始路徑的各路段、與所述各路段相關的關聯 路段的目標路段； 對所述目標路段、其他客戶端的採樣位置和採樣時間進行統計分析，預測未來時間段 內所述初始路徑中各路段的路況信息。
2. 根據權利要求1所述的方法，其特徵在於，所述對所述目標路段、其他客戶端的採樣 位置和採樣時間進行統計分析，預測未來時間段內所述初始路徑中各路段的路況信息，包 括： 對所述其他客戶端的採樣位置和採樣時間進行統計分析，預測未來時間段內每個客戶 端的對應的位置，統計目標路段中的車輛數得到所述初始路徑中各路段的路況信息。
3. 根據權利要求2所述的方法，其特徵在於，所述對所述其他客戶端的採樣位置和採 樣時間進行統計分析，預測未來時間段內每個客戶端的對應的位置，統計目標路段中的車 輛數得到所述初始路徑中各路段的路況信息，包括： 針對每個客戶端的採樣位置和採樣時間，結合既定的車速模型計算每個客戶端對應的 車速； 根據所述每個客戶端的車速和所述車速模型，預測各個客戶端未來時間段內在對應的 導航路徑上的位置； 以目標路段為單位對預測得到的所述各個客戶端未來時間段內在對應導航路徑上的 位置進行統計，得到在未來時間段內所述初始路徑中各路段的路況信息。
4. 根據權利要求3所述的方法，其特徵在於，所述車速模型通過採集各客戶端在路網 中的不同地點和不同時間的行駛信息並進行結構化訓練獲得。
5. 根據權利要求1所述的方法，其特徵在於，所述初始路徑根據當前客戶端的採樣位 置、採樣時間和目的地，採用路況預測模型規劃獲得。
6. 根據權利要求1所述的方法，其特徵在於，所述根據所述其他客戶端的目的地、採樣 位置和採樣時間分別規劃其他客戶端的導航路徑，包括： 根據其他的客戶端的目的地、採樣位置和採樣時間，採用路況預測模型規劃其他客戶 端對應的導航路徑。
7. 根據權利要求5或6所述的方法，其特徵在於，所述路況預測模型通過以下步驟構 建： 採集各客戶端記錄的各種類型的歷史出行信息； 根據所述歷史出行信息進行規劃，得到各客戶端對應的規劃路徑； 根據歷史出行信息的類型對應的權重，以路段為單位對所述規劃路徑進行統計，統計 每條路段在各時段對應的車輛流量； 根據每條路段上各時段內的車輛流量進行數據訓練，構建路況預測模型。
8. 根據權利要求7所述的方法，其特徵在於，所述採集各客戶端記錄的各種類型的歷 史出行信息包括： 採集每個客戶端對應記錄的個性化信息，並將個性化信息轉化為語義信息；所述個性 化信息包括郵件、簡訊、日程中的文本數據； 從所述語義信息中提取歷史出行信息。
9. 根據權利要求1所述的方法，其特徵在於，所述預測未來時間段內所述初始路徑中 各路段將的路況信息包括： 根據所述目標路段、其他客戶端的採樣位置和採樣時間，統計未來時間段內各目標路 段上的車輛總流量，並將所述車輛總流量與相應路段上的飽和閾值進行比較； 根據比較結果判斷所述未來時段內各路段的路況信息。
10. 根據權利要求1所述的方法，其特徵在於，還包括： 根據所述初始路徑中各路段的路況信息對所述初始路徑進行實時修正。
11. 根據權利要求10所述的方法，其特徵在於，所述根據所述初始路徑中各路段的路 況信息對所述初始路徑進行實時修正，包括： 如當前客戶端在所述初始路徑中將要行駛的第一路段對應的交通壓力大於第一閾值， 則根據與第一路段相關的關聯路段的交通壓力情況，將第一路段變更為所述關聯路段中對 應的交通壓力小於第一閾值的第二路段。
12. -種實時路徑規劃的系統，其特徵在於，包括： 採集模塊，用於當前客戶端按初始路逕行駛時，實時採集其他客戶端的目的地、採樣位 置和米樣時間； 關聯路段提取模塊，用於根據所述其他客戶端的目的地、採樣位置和採樣時間分別規 劃其他客戶端的導航路徑，並從所述導航路徑中分別提取包括所述初始路徑的各路段、與 所述各路段相關的關聯路段的目標路段； 擁堵判斷模塊，用於對所述目標路段、其他客戶端的採樣位置和採樣時間進行統計分 析，預測未來時間段內所述初始路徑中各路段的路況信息。
13. 根據權利要求12所述的裝置，其特徵在於，所述擁堵判斷模塊包括： 路況分析模塊，用於對所述其他客戶端的採樣位置和採樣時間進行統計分析，預測未 來時間段內每個客戶端的對應的位置，統計目標路段中的車輛數得到所述初始路徑中各路 段的路況信息。
【文檔編號】G01C21/34GK104121918SQ201310148846
【公開日】2014年10月29日 申請日期:2013年4月25日 優先權日:2013年4月25日
【發明者】張帆, 柴思遠, 張闊 申請人:北京搜狗信息服務有限公司, 北京搜狗科技發展有限公司