[發明專利]城市興趣點敏感的個性化路徑規劃方法

在審

• 申請號: 202211218557.3
• 申請日: 2022-10-06
• 公開（公告）號: CN115638803A
• 公開（公告）日: 2023-01-24
• 發明（設計）人: 金嘉暉;徐志鵬;張競慧;羅軍舟
• 申請（專利權）人: 東南大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 張天哲

1.城市興趣點敏感的個性化路徑規劃方法，其特征在于，該方法包括以下步驟：

步驟1.將城市建模成網格圖G(V,E,P)，其中P表示POI類型集合，p_i表示一種POI類型；V表示將路徑規劃區域按統一大小劃分得到的網格集合，也就是G中的節點集合，為每個節點設置屬性pois，以集合的形式存儲該節點所包含的POI類型；E表示網格間的邊集合：若節點v_x和v_y在空間上相鄰，且實際路網中存在一條路段穿過網格區域v_x和v_y，那么就在G中構建一條連接兩個區域的邊，表示為e_x,y∈E，為每條邊設置權重系數e_x,y.w∈R⁺，視為從節點v_x到節點v_y的出行成本，用路徑距離或者出行時間來衡量，為了便于描述，設置為1；

步驟2.基于多源最短路徑算法離線計算出區域內各個節點間的最短路徑，用Path存儲節點間的最短路徑，path＝{v_x,v₁,v₂,…,v_y}∈Path,v_x∈V,v_y∈V；用Dist存儲對應距離，dist(v_x,v_y)∈Dist,v_x∈V,v_y∈V；

步驟3.輸入用戶的查詢，包括起點s、終點t和用戶需要按順序途經的POI類型列表R＝{p₁,p₂,…,p_|R|},表示用戶出行過程中需要經過的POI類型；

步驟4.執行貪心搜索，貪心地從當前節點尋找距離最近的能夠滿足用戶下一需求的節點，將當前節點更新為該節點，重復上述搜索操作直至滿足用戶所有需求，再尋找從最后一個節點出發抵達用戶指定終點的最短路徑，將局部的路徑一一拼接構成一條貪心路徑，以該路徑的距離作為最終解的上界，輔助后續節點篩選；

步驟5.執行基于距離上界的動態規劃，首先利用貪心路徑的距離上界對所有能夠滿足用戶POI類型需求的候選節點進行篩選，基于用戶需求的次序構造多段圖，每個階段對應用戶的一種POI類型需求，將問題轉化為多段圖的最短路徑問題，最后基于動態規劃思想進行推導求解；

步驟6.根據動態規劃返回的POI最短路徑基于Path，從起點s出發不斷構造最短路徑直至抵達終點t，即能返回滿足用戶POI需求的實際最短路徑