[發明專利]一種用于路徑確定的系統和方法

有效

• 申請號: 202010847381.2
• 申請日: 2018-06-07
• 公開（公告）號: CN111998865B
• 公開（公告）日: 2022-06-21
• 發明（設計）人: 張逾
• 申請（專利權）人: 北京嘀嘀無限科技發展有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 成都七星天知識產權代理有限公司 51253
• 代理人: 袁春曉

1.一種用于路徑確定方法，該方法包括：

串聯多個節點以生成多個第一候選路徑，其中所述多個節點是基于一個或多個請求確定的，并且所述多個第一候選路徑滿足與該多個節點相關的第一條件；

基于多個節點中的任意兩個節點之間的地理距離確定多個第一候選路徑中的每一個的地理長度；

從多個第一候選路徑中確定參考路徑，其中，所述參考路徑的地理長度在多個第一候選路徑中最短；

基于所述參考路徑中相鄰節點之間的導航長度確定所述參考路徑的導航長度；

基于所述多個第一候選路徑中的每一個的地理長度，從所述多個第一候選路徑中確定出一個或多個第二候選路徑，其中所述第二候選路徑的地理長度短于所述參考路徑的導航長度；

確定一個或多個第二候選路徑中的每一個的導航長度；

基于所述一個或多個第二候選路徑中的每一個的導航長度、速度限制和/或實時因素，確定一個或多個第二候選路徑中每一個的行駛時間；

基于所述行駛時間從一個或多個第二候選路徑中確定目標路徑。

2.如權利要求1所述的方法，其中，所述目標路徑的行駛時間是所述一個或多個第二候選路徑中最短的。

3.如權利要求1所述的方法，其中，所述實時因素包括交通狀況、天氣狀況和道路工程安排中的一種或多種的組合。

4.如權利要求1所述的方法，其中，每個請求包括起始節點和目的地節點，并且第一條件是第一候選路徑中的起始節點的優先級高于第一候選路徑中的目的地節點的優先級。

5.如權利要求1中任一項所述的方法，其中，為了生成多個第一候選路徑，所述方法還包括：

基于多個節點確定初始回路，其中初始回路是具有第一節點序列的歐拉回路；

基于第一節點序列和與多個節點相關的第一條件來確定多個第二節點序列；

基于所述多個第二節點序列確定多個第一候選路徑。

6.如權利要求5所述的方法，其中，歐拉回路是基于Christofides算法確定的。

7.如權利要求5或6所述的方法，其中，所述多個第二節點序列是基于2-opt算法確定的。

8.如權利要求1所述的方法，其中，為了從所述多個第一候選路徑中確定出一個或多個第二候選路徑，所述方法還包括：

確定參考路徑的地理長度與多個第一候選路徑中的每一個的地理長度之間的多個第一差值；

基于參考路徑的導航長度與參考路徑的地理長度之間的差值來確定第一參數；

如果第一候選路徑對應的第一差值小于第一參數，則將該第一候選路徑分配為第二候選路徑。

9.如權利要求1或8所述的方法，其中：

每個第二候選路徑包括一個或多個區段，每個區段連接第二候選路徑中的兩個相鄰節點，

為了確定參考路徑的導航長度，該方法還包括：

獲得包括參考路徑多個區段的參考區段集，和

確定參考區段集中每個區間的導航長度以確定參考路徑的導航長度。

10.如權利要求9所述的方法，其中：

為了確定一個或多個第二候選路徑中的每一個的導航長度，該方法還包括：

確定參考路徑和第二候選路徑之間的一個或多個不同區段；

將該一個或多個不同的區段添加到參考區段集中；和

基于參考區段集確定第二候選路徑的導航長度。

11.如權利要求10所述的方法，其中，如果出現以下情況，則第二候選路徑的該區段不是不同的區段：

第二候選路徑的該區段的節點序列與參考路徑的某區段的節點序列相反，并且

該區段的導航長度與地理長度之間的差值不超過閾值。