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

在審

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

本發明公開了一種城市興趣點敏感的個性化路徑規劃方法。本發明預先按照網格對城市區域進行劃分，然后基于實際路網構造網格連通關系，將各個區域連接，建模成圖。將路徑規劃問題建模成：規劃一條最短路徑，該路徑從給定的起點出發，以用戶指定的順序訪問多個不同興趣點(Point Of Interest,POI)類型的位置，最終抵達用戶給定的終點。路徑規劃求解分為三階段：一是節點間距計算階段，二是POI優先的貪心搜索階段，三是基于距離上界的動態規劃階段。通過預處理的最短距離，基于動態規劃算法思想，快速、準確地找到一條能夠滿足用戶按序訪問指定類型候選節點的需求的最短路徑。

技術領域

本發明涉及城市計算及其應用領域，尤其涉及城市興趣點敏感的個性化路徑規劃方法。

背景技術

隨著地理信息技術的發展和智能移動終端的普及，路徑規劃服務已經融入到人們的日常生活中。但是出行目的的復雜化使得最短路徑已經無法滿足人們日益增強的個性化需求。例如，當用戶下班回家，想要先運動后吃飯再回家時，他會按順序訪問健身房、餐飲區等不同類型的城市POI區域。在滿足上述需求的同時，用戶往往還希望出行成本盡可能小。

現有的導航系統能夠基于用戶提供的起點、終點和必經點，高效地規劃一條最短路徑，但是能夠滿足用戶經過某個必經點的需求的候選節點通常有很多，因此現有的路徑規劃方法不能泛化地解決此類基于城市POI的最優定序路徑問題。具體而言：以POI 的類型序列表示用戶的順序訪問需求，在當前城市環境下，用戶的出行需求是復雜的：用戶需要按序經過多種類型的POI，而并不關注具體POI。

此類最優定序路徑規劃問題具有搜索空間大，時間復雜度高的特征：在城市環境中，某一類型的POI或能夠提供某種服務的POI通常不唯一(如：存在多家美食店可提供餐飲服務，運動健康也包括很多體育館、健身房可供選擇)，因此需要在同類型的多個POI 中做出選擇，這是一個定序的多類型組合問題。而在滿足用戶對其途經POI類型需求的前提下，還需要找到一條較短的路徑，對路徑規劃算法提出了更高要求。現有的各類路徑規劃算法不能滿足按次序經過多種類型的POI的需求。因此，針對本路徑規劃問題的特征，如何實現高效地規劃基于城市POI的最優定序路徑，是當前學術界和工業界亟需解決的核心問題。

發明內容

發明目的：針對以上現有技術存在的問題，本發明提出了一種城市興趣點敏感的個性化路徑規劃方法，著重解決城市環境下路徑規劃功能單一、不能按POI類型選擇途經點的問題。預先按照統一大小將城市區域劃分為網格，基于實際路網構建網格間連通關系，將各個區域連接，建模成一張圖。這樣，路徑規劃問題就可以看成是：給定起點、終點、必經具備某些POI類型的地點的圖上路徑搜索問題。一是節點間距計算階段，二是POI優先的貪心搜索階段，三是基于距離上界的動態規劃階段。通過預處理的最短距離，基于動態規劃算法思想，快速、準確地找到一條能夠滿足用戶有序訪問指定類型POI 節點的需求的最短路徑。

技術方案：為實現本發明的目的，本發明所采用的技術方案是：城市興趣點敏感的個性化路徑規劃方法，該方法包括以下步驟：

步驟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；